Design a stack that supports getMin() in O(1) time and

O(1) extra space

#include<bits/stdc++.h>
using namespace std;
class SpecialStack {
stack<int> st;
int mini=INT_MAX;
public:
void push(int data) {
if([Link]()){
[Link](data);
mini=data;
}
else{
if(data<mini){
[Link](2*data-mini);
mini=data;
}
else{
[Link](data);
}
}
}

void pop() {
if([Link]()){
return;
}
int cur=[Link]();
[Link]();
if (cur <= mini) {
mini=2*mini-cur;
}
 }

int top() {
if([Link]()){
return -1;
}
int cur=[Link]();
if(cur<mini){
return mini;
}
else{
return cur;
}
}

int getMin() {
if([Link]()){
return -1;
}
return mini;
}
};

Nstack in an array :

class NStack
{
int *arr;
int *top;
int *next;
int free;
int n,s;
Public:
NStack(int N, int S)
{
n=N;
s=S;
arr = new int[s];
top = new int[n];
next = new int[s];
free = 0;
for(int i=0;i<n;i++){
top[i]=-1;
}
for(int i=0;i<s-1;i++){
next[i]=i+1;
}
next[s-1]=-1;
}
bool push(int x, int m){
if(free==-1){
return 0;
}
int index=free;
free=next[index];
arr[index]=x;
next[index]=top[m-1];
top[m-1]=index;
return 1;
}
int pop(int m){
if(top[m-1]==-1){
return -1;
}
int index=top[m-1];
top[m-1]=next[index];
next[index]=free;
free=index;
return arr[index];
}};
A celebrity is a person who is known to all but does not know anyone at
a party. If you go to a party of N people, find if there is a celebrity in the
party or not.
A square NxN matrix M[][] is used to represent people at the party such
that if an element of row i and column j is set to 1 it means ith person
knows jth person. Here M[i][i] will always be 0.
class Solution
{
public:
int celebrity(vector<vector<int> >& M, int n)
{
stack<int> st;
for(int i=0;i<n;i++){
[Link](i);
}
while([Link]()!=1){
int A=[Link]();
[Link]();
int B=[Link]();
if(M[A][B]==1){
continue;
}
else{
[Link]();
[Link](A);
}
}
int A=[Link]();
for(int i=0;i<n;i++){
if(A!=i && M[A][i]==1){
return -1;
}
}
 for(int i=0;i<n;i++){
if(A!=i && M[i][A]==0){
return -1;
}
}
return A;
}
};
Next smaller element in stack :

#include<bits/stdc++.h>
using namespace std;
vector<int> nextSmallerElement(vector<int> &arr, int n)
{
stack<int> buffer;
[Link](-1);
for(int i=n-1;i>=0;i--){
while([Link]()>=arr[i]){
[Link]();
}
int ans=[Link]();
[Link](arr[i]);
arr[i]=ans;
}
return arr;
}

Delete middle element from stack

#include <bits/stdc++.h>
void solve(stack<int> &i, int *N, int c) {
if (c == *N>>1) {
[Link]();
return;
}
int t=[Link]();
 [Link]();
solve(i,N,c+1);
[Link](t);

}
void deleteMiddle(stack<int>&inputStack, int N){
int c=0;
solve(inputStack,&N,c);
}

Valid parentheses

#include<bits/stdc++.h>
bool isValidParenthesis(string s)
{
stack<char> bufferstack;
map<char, char> mp = {
{'{', '}'},
{'(', ')'},
{'[', ']'}
};
for (int i = 0; i < [Link](); i++) {
if (s[i] == '{' || s[i] == '(' || s[i] == '[') {
[Link](s[i]);
}
else {
if ([Link]()) {
return false;
}
if(mp[[Link]()]==s[i]){
[Link]();
}
else{
return false;
}
}
}
if ([Link]()) {
return true;
}
 return false;
}

Insert at bottom of a given stack

void solve(stack<int> &myStack, int x) {

if ([Link]()) {
[Link](x);
return;
}
int y = [Link]();
[Link]();
solve(myStack, x);
[Link](y);
return;
}
stack<int> pushAtBottom(stack<int>& myStack, int x)
{
solve(myStack,x);
return myStack;
}

Reverse stack using recursion :

void atbottom(stack<int> &stack,int d){
if([Link]()){
[Link](d);
return;
}
int k= [Link]();
[Link]();
atbottom(stack,d);
[Link](k);
return;
}
void reverseStack(stack<int> &stack) {
if([Link]()){
 return;
}
int y=[Link]();
[Link]();
reverseStack(stack);
atbottom(stack,y);
return;}
Sort a stack:
#include <bits/stdc++.h>
void place(stack<int> &stack,int y){
if([Link]() || [Link]()<=y){
[Link](y);
return;
}
int x=[Link]();
[Link]();
place(stack,y);
[Link](x);
}
void sortStack(stack<int> &stack)
{
if ([Link]()) {
return;
}
int y=[Link]();
[Link]();
sortStack(stack);
place(stack,y);
}

Redundant Brackets
#include <bits/stdc++.h>
bool findRedundantBrackets(string &s)
{
stack<char> st;
 int count=0;
for(int i=0;i<[Link]();i++){
if(s[i]==')'){
count=0;
while([Link]()!='('){
if([Link]()=='+' || [Link]()=='-' || [Link]()=='*' || [Link]()=='/'){
count++;
}
[Link]();
}
[Link]();
if(count==0){
return 1;
}
}
else{
[Link](s[i]);
}
}
return 0;
}

Minimum reversal :
#include <bits/stdc++.h>
int findMinimumCost(string str) {
stack<char> st;
for (int i = 0; i < [Link](); i++) {
if (str[i] == '}') {
if ([Link]() || (![Link]() && [Link]()=='}')) {
[Link]('}');
}
else {
[Link]();
}
}
else{
[Link]('{');
}
}
int left=0,right=0;
 while(![Link]()){
if([Link]()=='{'){
right++;
}
else{
left++;
}
[Link]();
}
if((left+right)%2){
return -1;
}
return (left+right)/2+(right%2);
}

Max rectangle:
class Solution{
vector<int> previous(int arr[],int n){
vector<int> ans(n);
stack<int> buffer;
[Link](-1);
for(int i=0;i<n;i++){
while([Link]()!=-1 && arr[[Link]()]>=arr[i]){
[Link]();
}
ans[i]=[Link]();
[Link](i);
}
return ans;
}
vector<int> next(int arr[],int n){
vector<int> ans(n);
stack<int> buffer;
[Link](-1);
for(int i=n-1;i>=0;i--){
while([Link]()!=-1 && arr[[Link]()]>=arr[i]){
 [Link]();
}
ans[i]=[Link]();
[Link](i);
}
return ans;
}
int histo(int arr[],int m){
vector<int> pre(m);
vector<int> nxt(m);
int area=INT_MIN;
pre=previous(arr,m);
nxt=next(arr,m);
for(int i=0;i<m;i++){
int l=arr[i];
if(nxt[i]==-1){
nxt[i]=m;
}
int b=nxt[i]-pre[i]-1;
area = max(area,l*b);
}
return area;
}
public:
int maxArea(int M[MAX][MAX], int n, int m) {
int area = histo(M[0],m);
for(int i=1;i<n;i++){
for(int j=0;j<m;j++){
if(M[i][j]!=0){
M[i][j]=M[i][j]+M[i-1][j];
}
}
area = max(area,histo(M[i],m));
}
return area;
}};