# Next greater number

Given an array of integers, for each a[i] element print a[j] such that a[j] > a[i] and j>i. Also j should be as close to i as possible. For the rightmost element, value will be -1. If for any i if there is no such j, then result for that too will be -1. In simple terms, we need to print nearest greater number for each element in given array.

Simple brute force method would be to scan array in two loops. For each element in array, scan remaining right side elements and find out the greater number. Complexity of such code will be O(n2). How can we do better?
If we keep track of all the numbers for which we have yet not encountered a greater number, we keep improve. Idea is that whenever we examine a number, we check if there are elements which are already visited in array and yet there is no greater number assigned to them. If there are such elements, we check if current element is greater than them. If yes, then for all those numbers which are less than current element, next greater element will be current number.

## Find next greater element in array

To keep track of the numbers which have yet not assigned greater number, we can use stack. Steps are simple.

1. If stack is empty, push the element on to stack.
2. If stack is not empty, pop all elements from the stack which less than current element.
3. Print these numbers paired with current number.
4. If top of the stack is not less than current element or stack is empty, push the current element.(All the elements present in stack will be greater than current element why?)
5. After scanning all elements in array, print all elements in stack paired with -1 as there is no greater element on right side of these elements.

Let’s workout an example:
A  = {5,6,3,35,23,6,8}
Output should be {(5,6), (6,35), (3,35), (6,8), (8, -1), (23, -1), (35, -1)}

## Next greater number using stacks

```#define STACK_SIZE 10

typedef struct stack{
int top;
int items[STACK_SIZE];
}stack;

void push(stack *ms, int element){
if(ms->top < STACK_SIZE-1){
ms->items[++(ms->top)] = element;
}
else {
printf("Stack is full\n");
}
}

int pop (stack *ms){
if(ms->top > 0){
return ms->items[(ms->top)--];
}
else{
printf("Stack is empty\n");
}
}

int peek(stack ms){
if(ms.top < 0){
printf("Stack empty\n");
return 0;
}
return ms.items[ms.top];
}

int isEmpty(stack ms){
if(ms.top < 0) return 1;
else return 0;
}

void print_next_greater(int a[], int size){
stack ms;
int i;

ms.top = -1;
for(i=0; i<size; i++){
if(is_empty(ms)){
push(&ms, a[i]);
}
else{
while(!is_empty(ms) && a[i] > peek(ms)){
printf("(%d, %d)\n ", peek(ms), a[i]);
pop(&ms);
}
push(&ms, a[i]);
}
}
while(!is_empty(ms)){
printf("(%d, %d)\n ", pop(&ms), -1);
}
}

int main(){
int a[] = {5,6,3,35,23,6,8};
int size = sizeof(a)/sizeof(a[0]);

print_next_greater(a, size);
return 0;
}
```

Please refer Stack data structure to under stand more how to implement operation on stack.

Complexity of algorithm to find next greater element in array is O(N) with extra space complexity of O(N) for stack.

# Merge overlapping intervals

Given N events S = (e1,e2,…..en) with start time and end time ( (s1,e1), (s2,e2),(s3,e3), …. (sn,en)). Problem is to merge overlapping intervals. What are overlapping events or intervals? Events i and j overlap if start time of jth event is less than end time of ith event or vice-a-versa.

For example, [(1,3),(2,4),(5,8)] should be transformed into[(1,4),(5,8 )] as event 1 from (1,3 ) and event 2 from (2,4) are overlapping and will be merged into one as (1,4).
This problem is quite simple, however, we will understand concept of stacks and arrays by solving this.

## Merge overlapping intervals : Methods

Let’s see brute force solution first. Take ith event and compare start time of every jth event with end time of ith, if start time of jth event is less than end time of ith event and end time of jth event is greater than ith event then update the end time of ith event.

This solution has complexity of O(N^2). Can we do better than that?

How about sorting all events based on start time? If start time of ith event is greater than (i-1)th event’s end time, than start time of (i+1)th event will be greater than (i-1)th event. Hence, compare current event’s start time with previous event’s end time and update end time of previous event in case of overlap.
It’s required to keep track of last seen or updated event each time a new event is considered for overlap, stack is best data structure to be used when we are concerned about last thing first.

## Merge overlapping intervals: Algorithm

```1. Take event e from pool of events.
2. If stack is empty, push e to stack.
3. If stack is not empty, then pop event at top of stack call it e1.
3.1 Compare start time of e with end time of event e1.
3.2 If e.start < e1.end
3.2.1 if e.end > e1.end, update e1.end and push e1 on to stack.
3.2.1 if e.end < e1.end, push e1 onto stack.
3.3 Else push e to stack.```

## Merge overlapping intervals implementation

```#include <stdio.h>
#include<stdio.h>
#include<stdlib.h>
#include <string.h>

#define STACK_SIZE 10

typedef struct Event{
int startTime;
int endTime;
int jobNum;
}Event;

typedef struct stack{
int top;
Event items[STACK_SIZE];
}stack;

void push(stack *ms, Event element){
if(ms->top < STACK_SIZE-1){
ms->items[++(ms->top)] = element;
}
else {
printf("Stack is full\n");
}
}

Event pop (stack *ms){

if(ms->top >= 0){
return ms->items[(ms->top)--];
}
else{
printf("Stack is empty\n");
}
}

int isEmpty(stack ms){

if(ms.top < 0) return 1;

else return 0;
}

void swap(Event events[], int i, int j){

int tempStart = events[i].startTime;
int tempEnd   = events[i].endTime;
int jobNum 	  = events[i].jobNum;

events[i].startTime  = events[j].startTime ;
events[i].endTime    = events[j].endTime ;
events[i].jobNum     = events[j].jobNum;

events[j].startTime  = tempStart;
events[j].endTime    = tempEnd ;
events[j].jobNum     = jobNum;
}

int partition(Event events[], int start, int nEvents){
int i,j;
i = start+1;
j = nEvents;
int pivot =  events[start].startTime;

while(i<=j){
while(i<=nEvents && events[i].startTime < pivot)
i++;
while(j>start && events[j].startTime >= pivot)
j--;
if(i<j){
swap(events, i, j);
}
}
if(j>start)
swap(events,start, j);

return j;
}

void quicksort(Event events[], int start, int nEvents){

if(start < nEvents) {

int pivot = partition(events, start, nEvents);
quicksort(events, start, pivot-1);
quicksort(events, pivot+1, nEvents);
}
}

void mergeIntervals(Event events[], int nEvents){

int currentEventNum = 0;

stack s;
s.top = -1;

quicksort(events, 0, nEvents-1);
Event lastEvent;

while(currentEventNum < nEvents){
Event currentEvent = events[currentEventNum];

if(!isEmpty(s)){
lastEvent =  pop(&s);
if(currentEvent.startTime < lastEvent.endTime){
if( currentEvent.endTime > lastEvent.endTime){
lastEvent.endTime = currentEvent.endTime;
}
push(&s,lastEvent);
}
else{
push(&s, lastEvent);
push(&s, currentEvent);
}
}
else{
push(&s, currentEvent);
}
currentEventNum++;
}
while(!isEmpty(s)){
lastEvent = pop(&s);
printf("(%d,%d)", lastEvent.startTime,lastEvent.endTime);
printf("\n");
}
}

int main(){

Event events[5];

events[0].startTime = 0;
events[0].endTime 	= 2;
events[0].jobNum 	= 1;

events[1].startTime = 2;
events[1].endTime 	= 3;
events[1].jobNum 	= 2;

events[2].startTime = 1;
events[2].endTime 	= 5;
events[2].jobNum 	= 3;

events[3].startTime = 3;
events[3].endTime 	= 7;
events[3].jobNum 	= 4;

events[4].startTime = 8;
events[4].endTime 	= 9;
events[4].jobNum 	= 5;

mergeIntervals(events, 5);
printf("\n");

return 0;
}

```

Complexity of algorithm to merge overlapping intervals will be O(N log N) due to sorting with O(N) extra space.

# zigzag traversal of binary search tree

In this post, let’s discuss a problem which is very similar to level order traversal of binary search tree. However, there is a small difference between level order and zigzag traversal of binary search tree or spiral traversal. In zigzag traversal, at every level, direction of traversal of that level changes from left to right or right to left.

That is to say, printing levels, one level is printed left to right, second from right to left and then third, again from left to right.
Given a binary search tree, print all nodes of the tree in zigzag order. For example, for following tree, output should be : 30,40,20,15,25,37,45

We have already have solved for the level order printing of a tree, let’s use that knowledge and solve this problem. All that is different is the direction of traversal of levels. What if we can pass on hint for direction level to be traversed in? Well that solves our problem 🙂

## Zigzag traversal of tree : Recursive implementation

```#include<stdio.h>
#include<stdlib.h>
#include<math.h>

#define MAX(a,b)  a>b ?a:b

struct node{
int value;
struct node *left;
struct node *right;
};
typedef struct node Node;

int height(Node *root){
if(root == NULL)
return 0;

if(!root->left && !root->right)
return 1;

int lheight = height(root->left);
int rheight = height(root->right);

return 1+ (MAX(lheight, rheight));
}

void zigzagTraversalRecursive(Node * node, int desired, int ltr){
if(node == NULL) return;

if (desired == 1)
printf("%d  ", node->value);
/* Based on the flag call the recursive function accordingly */
if(ltr){
zigzagTraversalRecursive(node->left, desired-1, ltr);
zigzagTraversalRecursive(node->right, desired-1, ltr);
}
else{
zigzagTraversalRecursive(node->right, desired-1, ltr);
zigzagTraversalRecursive(node->left, desired-1, ltr);
}
}

void spiralLevelOrderTraversal(Node *root){
int h = height(root);
int i;
int ltr = 1;
for(i=1; i<=h; i++){
printf("\n Level %d :", i);
/* initially passing it to left to right */
zigzagTraversalRecursive(root, i, ltr);
/* For next iteration (level), it will be reversed */
ltr = !ltr;
printf("\n");
}
}

Node * createNode(int value){
Node * newNode =  (Node *)malloc(sizeof(Node));
newNode->value = value;
newNode->right= NULL;
newNode->left = NULL;
return newNode;
}

Node * addNode(Node *node, int value){
if(!node){
return createNode(value);
}
else{
if (node->value > value)
else
}

return node;
}

/* Driver program for the function written above */
int main(){
Node *root = NULL;
Node * last = NULL;
//Creating a binary tree

spiralLevelOrderTraversal(root);
return 0;
}
```

In this implementation, we pass direction to each iteration of traversal. When level changes, flip the direction from left to right or right to left.

What is the complexity of algorithm? Well if height of BST is h, we traverse nodes as h*1 + (h-1)*2 + (h-2)*3…..1*n, which is quadratic in nature and hence, complexity of this method will be O(h *n2). (Thanks Gopi for pointing out).

Another problem of solution is that it uses recursion and we know if depth of recursion is too deep, we may end up in trouble. It consumes system space and hence adds to space complexity of solution.

What is the best way to replace recursion? Yes, use stacks.

## Zigzag traversal of BST : Iterative implementation

In order to traverse BST using stack, we will have to use two stacks. In first stack, push right child first and then left child, so that while popping left child is popped first and then right child. Hence, order of nodes in this first stack is left to right.
In second stack, push left child first and then right child. Order of popped nodes is right to left.

Algorithm to zig zag traverse a BST using stacks.<

```1. Create two stacks S1 and S2. Push root into stack S1
2. While any one of stacks is not empty, repeat below steps
2.1 While S1 is not empty, pop top node, currentNode.
2.2 Print currentNode->value
2.3 Push right child and left child of currentNode on stack S2.
2.4.If S2 is not empty, pop top node, currentNode.
2.5 Print currentNode->value
2.6 Push left child and right child of currentNode on S1.
```

Implementation is very simple. To understand how stack implementation in c, please go through below post  Stack Basics and implementation

### Iterative implementation of zigzag traversal

```#include <stdio.h>
#include<stdlib.h>
#include<math.h>

struct node{
int value;
struct node *left;
struct node *right;
};
typedef struct node Node;

#define STACK_SIZE 10

typedef struct stack{
int top;
Node *items[STACK_SIZE];
}stack;

void push(stack *ms, Node *item){
if(ms->top < STACK_SIZE-1){
ms->items[++(ms->top)] = item;
}
else {
printf("Stack is full\n");
}
}

Node * pop (stack *ms){
if(ms->top > -1 ){
return ms->items[(ms->top)--];
}
else{
printf("Stack is empty\n");
}
}
Node * peek(stack ms){
if(ms.top < 0){
printf("Stack empty\n");
return 0;
}
return ms.items[ms.top];
}
int isEmpty(stack ms){
if(ms.top < 0) return 1;
else return 0;
}

void zigzagTraversal(Node * root){
stack s1, s2;
s1.top = -1;
s2.top = -1;

if(root == NULL ) return;

push(&s1, root);

while(!isEmpty(s1) || !isEmpty(s2)){
printf("\n");
while(!isEmpty(s1)){
Node *currentNode = pop(&s1);
printf("%d " , currentNode->value);
if(currentNode->right)
push(&s2, currentNode->right);
if(currentNode->left)
push(&s2, currentNode->left);
}
printf("\n");
while(!isEmpty(s2)){
Node *currentNode = pop(&s2);
printf("%d " , currentNode->value);
if(currentNode->left)
push(&s1, currentNode->left);
if(currentNode->right)
push(&s1, currentNode->right);
}
}
}

Node * createNode(int value){
Node * temp =  (Node *)malloc(sizeof(Node));
temp->value = value;
temp->right= NULL;
temp->left = NULL;
return temp;
}
Node * addNode(Node *node, int value){
if(node == NULL){
return createNode(value);
}
else{
if (node->value > value){
}
else{
}
}
return node;
}

/* Driver program for the function written above */
int main(){
Node *root = NULL;
//Creating a binary tree

zigzagTraversal(root);
return 0;
}
```

Complexity of iterative approach is O(N) why? Because we visit each node of tree only once. However, space complexity would be O( 2h-1).

# Stack with constant time max operation

Design a stack which has constant time push, pop and max operation.
We know that stack has constant time push and pop operation. Now we need to design an solution where we get the max value in stack in constant time. To understand more about stack data structure please refer : stack data structure.

## Constant time max operation in stack

Push and pop operation in a stack are already constant time operations. Let’s concentrate on max operation. First thing we need to do is to keep track of the current max. This would suffice if are never going to pop from the stack. If we pop from the stack, the new remaining stack might have different max. Max in remaining stack can be different if the poped element is max too.
So we get the first condition : If the popped element is equal to current max value, we need to change the max.
Again we get the hint : We need to keep track of previous max too. Keep all the elements which were max in stack at any given time. These max values to be stored in such a way that the most recently encountered max can be accessed in O(1) . That’s is our base requirement right?

Last in first out again? Yes, keep another stack to store max.

```Insertion order : 1,2,3,4,5 then
Main stack : 1,2,3,4,5
Max stack would be : 1,2,3,4,5
Insertion order : 5,4,3,2,1
Main stack  : 5,4,3,2,1
Max stack : 5,5,5,5,5
```

From the second example we observe that we are unnecessarily storing 5 repeatedly. We can optimize it by storing element in max stack only if max is changed.

## Stack with constant time find max operation

Complexity of all operations is O(1).

# Implement queue using stacks

Before implementing queue using stacks, let’s understand what is queue and stack as abstract data structures. We already know that stack is a LIFO data structure, i.e. what goes in last, comes out first. Contrary to that, queue is a FIFO data structure, where what goes in first comes out first. Read array based queue implementation and linked list based queue and stack implementation for detailed discussions.

## Implement queue using stacks

Ask of the problem is to implement a FIFO data structure using LIFO data structure. Insertion in LIFO or FIFO data structure should not be a problem. As insertion in stack (LIFO) or queue (FIFO) does not vary. Removal or dequeuing items from LIFO and FIFO is totally different. Let’s take an example, with following elements to be queued and dequeued from queue : 1,2,3,4,6,7,8. Start implement queue with one stack S. Insert 1, S = {1}. No problem, even queue would have behaved in same way.
Insert 2 will result in S = {1,2}. No problem again.
Insert 3 will result in S = {1,2,3}.

Here comes tricky part. Dequeue now from stack. As per the definition of queue, first item, 1 in this case, should come out. However, we have stack with us, we can pop 3 from top of stack. So what to do now?
Simple, pop all elements from stack and take last element in stack. Cool!
What happens to all elements just popped out of stack? They are lost now. How can we save them too while popping elements from stack. While popping out elements from S, put popped elements into another stack.

After this, top of stack S2 will gives element entered in first stack after the element just dequeue, in this case 1. Now stacks are S = {} and S2 = {3,2}.
What if we insert 4. Where should it go or which stack it should be pushed into?
As explained, stack 2 contains elements in FIFO order (because we pushed element in reverse order of the first stack). Do not change S2 till it is empty. Hence,candidate for holding 4 is first stack S. S = {4}, S2 = {3,2}
Dequeue 2. Easy return top of the stack. S ={4} S2 ={3}
Dequeue 3. Easy return top of the stack. S ={4} S2 {}
Now Insert 5, simple add it to S. S ={4,5} S2 = {}
Dequeue. Pop all elements from the S and put them into S2. Now pop from S2 and return the element. Continue till we have operations to perform.

## Queue using stack implementation

```#include <stdio.h>
#define STACK_SIZE 10

typedef struct stack{
int top;
int items[STACK_SIZE];
}stack;

void initializeStack(stack *s){
s->top = -1;
}
void push(stack *ms, int element){
if(ms->top < STACK_SIZE-1){
ms->items[++(ms->top)] = element;
}
else {
printf("Stack is full\n");
}
}

int pop (stack *ms){
if(ms->top >= 0){
return ms->items[(ms->top)--];
}
else{
printf("Stack is empty\n");
}
}

int peek(stack ms){
if(ms.top<0){
printf("Stack empty\n");
return 0;
}
return ms.items[ms.top];
}

int isEmpty(stack *ms){
if(ms->top <0) return 1;
else return 0;
}

void implementQueueUsingStacks(int choice, stack *s1,
stack *s2, int n){

switch(choice){
case 1: //enqueue
push(s1,n);
break;

case 2 : //dequeue
if(!isEmpty(s2)){
printf("\n Element dequeued is : %d", pop(s2));
}
else{
while(!isEmpty(s1)){
push(s2, pop(s1));
}
printf("\n Element dequeued is : %d", pop(s2));
}
break;
}
}

int main(void) {
stack s1, s2;
initializeStack(&s1);
initializeStack(&s2);
for(int i=0; i<10; i++){
implementQueueUsingStacks(i%3, &s1, &s2,i);
}
return 0;
}

```

Only an auxiliary space is required for extra stack. Insertion is O(1). Dequeue operation in worst case can be O(N).

# Stock span problem

We are given a list of prices of a stock for N number of days. We need to find stock span for each day. Span is defined as number of consecutive days before the given day where the price of stock was less than or equal to price at given day. For example, {100, 60,70,65, 80, 85} span for each day will be {1, 1, 2, 1, 4, 5}.

For first day span is always 1. In example, notice that on day 2, price of stock is 60 and there is no day prior to it where price was less than 60. Hence span for day 2 is 1 again. For day 3, price at day 2 (60) is less than 70, hence span for day 3 is 2. Similarly, for day 4 and day 5. Remember days should be consecutive, that why span for day 4 is 1 even though there was a day 2 where price was less than 65. Hope this example clarifies the problem. Stock span problem is slightly complicated to understand but solution is pretty easy.
One solution which immediately comes into mind  is:  For every day, scan all days prior to it and increment span till price greater than given day is seen. Simple implementation but with quadratic complexity.

From above implementation, notice that the day of real interested  to us is the day where price was last seen greater than current day price. So we need to check last price which was greater than price today. Getting some hints? Yes, maintain a stack which contains prices seen in decreasing order.

So while scanning prices on given days, check if there are prices which are less than current price. If yes, just pop them out. When you encounter a price which is greater than current price, stock span with maximum profit of current day is difference between day of that price and current day.  So looking carefully, it becomes apparent that, storing index of last greatest seen price would make things easier as compared to storing actual price. Hence day is store i on stack, price[i] will give us the price of stock on day i.

Refer stack data structure to understand basics of stack.

## Algorithm to detect stock span

```1. Initialize span of day 1 as 1.
2. Put day 1 on to stack.
3. For all days starting from day 2, repeat following steps.
3.1 If price of stock on day at top of stack is less than price of stock on current day, Pop the index from stack.
3.2 If price of stock on the day on top of stack is greater than price of stock on current day, calculate span as current day - day at top of stack.
3.3 Push current day index on to stack.
```

Figure below explains algorithm in action

## Stock span algorithm

```package Problems;

import common.Stack;

import java.util.ArrayList;
import java.util.List;

/**
* Created by Sangar on 24-08-2015.
*/
public class StockSpanDemo {
public static void main(String[] args){
List<Integer> stockPriceList = new ArrayList<Integer>();

List<Integer> stockSpanList = getStockSpan(stockPriceList);
System.out.println(stockSpanList);

}
static List<Integer> getStockSpan(List<Integer> stockPriceList){
List<Integer> stockSpanList = new ArrayList<Integer>();

Stack s = new Stack();
s.push(0);

for(int i=1; i<stockPriceList.size(); i++){

while(!s.isEmpty() &&
stockPriceList.get(s.top())< stockPriceList.get(i)){
s.pop();
}

s.push(i);
}
return stockSpanList;
}
}
```

Stack implementation

```/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Stack
{
private int top;
private ArrayList<Integer> elements;
public void Stack(){
top = -1;
elements = new ArrayList<Integer>();
}

void push(int element){
top++;
}

int pop(){
if(top > -1){
int element = elements.get(top--);
return element;
}
else{
System.out.println("Stack is empty");
}
return -1;
}

int peek(){
if(top > -1)
return elements.get(top);
else{
System.out.println("Stack is empty");
}
return -1;
}

boolean iEmpty(){
if(top > -1)
return false;
return true;
}

}
```

## Stock span problem implementation in C

```#include<stdio.h>
#include<stdlib.h>

#define STACK_SIZE 100

typedef struct stack{
int top;
int items[STACK_SIZE];
}stack;

void push(stack *ms, int item){
if(ms->top < STACK_SIZE-1){
ms->items[++(ms->top)] = item;
}
else {
printf("Stack is full\n");
}
}

int pop (stack *ms){
if(ms->top > -1 ){
return ms->items[(ms->top)--];
}
else{
printf("Stack is empty\n");
}
}
int peek(stack ms){
if(ms.top < 0){
printf("Stack empty\n");
return 0;
}
return ms.items[ms.top];
}
int isEmpty(stack ms){
if(ms.top < 0) return 1;
else return 0;
}

void stockSpan(int prices[], int days){

stack ms;
int i;

int span[days];

if(days ==0) return;

span[0] = 1;

ms.top = -1;
push(&ms, 0);

for(i=1; i<days; i++){
while(!isEmpty(ms) && prices[i] > prices[peek(ms)])
pop(&ms);

if(isEmpty(ms)){
span[i] = i+1;
}
else{
span[i] =  i - peek(ms);
}
push(&ms, i);
}

for(i=0; i<days; i++)
printf("%d  ", span[i]);

printf("\n");
}

/* Driver program */
int main(){

int prices[6] ={100,60,70, 65, 85, 80};
int n  = sizeof(prices)/sizeof(prices[0]);

stockSpan(prices, n);
return 0;
}
```

Complexity of stock span with maximum profit is O(N).

# Infix to postfix conversion using stack

Today, we will discuss another problem which uses stacks, problem is to convert Infix to postfix expression. Infix expression is where the operator comes in between two operand. For example  4+5/6*7 is an infix expression. Postfix expression is where operator comes after operands like 43+5* is a postfix expression. Let’s take an example and come with algorithm to convert infix to postfix

## Algorithm for infix to postfix conversion

Infix expression : 4+5*6/7
We need to move all operator at the end of operands to which it applies.

Start with first digit 4, it is an operand onto expression string. Next character is ‘+’, keep it aside on stack as it needs to come at end of all operands it applies to. Next is 5, not an operator, put it with 4 in expression string, so current state of stack and output postfix string:

Next we get ‘*’, this is an operator. Here is some work we need to do. Check if there is an operator already encountered, which has higher precedence than current operator. If not, then we are fine, we will add this operator in the set of operators onto stack but not yet added to postfix expression.

If there is operator which has higher precedence, then take out one by one all such operator (in the order they were encountered), till an operator with lower precedence is seen. Add all these operators to the postfix expressions string. Put the current operator in the set.

In this case + has lower precedence than *, hence stack has two operators (+, *).

Next character is 6. Add it to postfix expression, it becomes 456 . Visit ‘/’. Since it has higher priority than + and *, it gets added to list. Set becomes (+,*, /).

Check 7 and add it to post expression, expression becomes 4567.

Now we reached at the end of the expression. Now go to stack and pop operators one by one and add them to postfix expression string. Resultant postfix expression is :

Let’s see another example :(4+8)*(6-5)/((3-2)*(2+2))

This is execution trace of the function which converts this infix expression to postfix. It explains the algorithm very well.

```Character being considered : (  Stack is :  Postfix exp is :
Character being considered : 4  Stack is :  (  Postfix exp is : 4
Character being considered : +  Stack is : ( +  Postfix exp is : 4
Character being considered : 8  Stack is : ( +  Postfix exp is : 4 8
Character being considered : )  Stack is : (  Postfix exp is : 4 8 +
Character being considered : *  Stack is :  Postfix exp is : 4 8 +
Character being considered : (  Stack is : *  Postfix exp is : 4 8 +
Character being considered : 6  Stack is : * (  Postfix exp is : 4 8 + 6
Character being considered : -  Stack is : * ( -  Postfix exp is : 4 8 + 6
Character being considered : 5 Stack is : * ( -  Postfix exp is : 4 8 + 6 5
Character being considered : )  Stack is : *  Postfix exp is : 4 8 + 6 5 -
Character being considered : /  Stack is : /  Postfix exp is : 4 8 + 6 5 - *
Character being considered : (  Stack is : / (  Postfix exp is : 4 8 + 6 5 - *
Character being considered : (  Stack is : / ( (  Postfix exp is : 4 8 + 6 5 - *
Character being considered : 3  Stack is : / ( (  Postfix exp is : 4 8 + 6 5 - * 3
Character being considered : -  Stack is : / ( ( -  Postfix exp is : 4 8 + 6 5 - * 3
Character being considered : 2  Stack is : / ( ( -  Postfix exp is : 4 8 + 6 5 - * 3 2
Character being considered : )  Stack is : / (   Postfix exp is : 4 8 + 6 5 - * 3 2 -
Character being considered : *  Stack is : / ( *  Postfix exp is : 4 8 + 6 5 - * 3 2 -
Character being considered : (  Stack is : / ( * (   Postfix exp is : 4 8 + 6 5 - * 3 2 -
Character being considered : 2  Stack is : / ( * (  Postfix exp is : 4 8 + 6 5 - * 3 2 - 2
Character being considered : +  Stack is : / ( * ( +   Postfix exp is : 4 8 + 6 5 - * 3 2 - 2
Character being considered : 2  Stack is : / ( * ( +  Postfix exp is : 4 8 + 6 5 - * 3 2 - 2 2
Character being considered : )  Stack is : / ( *  Postfix exp is : 4 8 + 6 5 - * 3 2 - 2 2 +
Character being considered : ) Stack is : /  Postfix exp is : 4 8 + 6 5 - * 3 2 - 2 2 + *
```

## Infix to postfix implementation

```#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAX_LENGTH_EXPRESSION 100

typedef struct stack {
char items[MAX_LENGTH_EXPRESSION];
int top;
}stack;

void push(stack *s, char element){
if(s->top == MAX_LENGTH_EXPRESSION ){
printf("\n Stack is full");
return;
}
s->items[++s->top] = element;
return;
}

char pop(stack *s){
if(s->top == -1){
printf("\n Stack empty");
}
return s->items[s->top--];
}
char peek(stack *s){
if(s->top == -1){
printf("\n Stack empty");
}
return s->items[s->top];
}

void initialize(stack *s){
s->top = -1;
}

int empty(stack *s){
if(s->top == -1) return 1;
return 0;
}
/* This function return true or false based on whether
character is operator or not */
int is_operand(char op){
if(op == '+' || op == '-' || op == '*' || op == '/' || op =='%')
return 1;
return 0;
}

/* This function returns associated precedence to an operator */
int precedence(char op){
switch (op){
case '+' :
case '-' :
return 1;
case '/' :
case '*' :
return 2;
case '%' :
return 3;
default :
return 4;
}
}
/* This function tell if the op1 has lower precedence than op2 */
int lower_precedence(char op1, char op2){
if(precedence (op1) < precedence(op2))
return 1;
return 0;
}

void printStack(stack *s){
printf("\n Stack is:");
for(int i =0; i<= s->top; i++){
printf("%c", s->items[i]);
}
}

void infix_to_postfix(char *s){
stack ms;

initialize(&ms);

char *p = (char *) malloc(strlen(s));
char *post = p;
char temp;

/* Wrong input */
if(!s) return ;

if(*s == '\0') return ;

while(*s != '\0'){
/* Case 1. If '(', push on to stack */
if(*s == '('){
push(&ms, *s);
}
/* Case 2. If ')', pop all op from stack till
we see '(', Discard ')' */
else if(*s == ')'){
while(!empty(&ms) && peek(&ms) != '('){
*p  = pop(&ms);
p++;
}
if(!empty(&ms))
pop(&ms);
}
/* Case 3. If it is operator, pop all op on stack which are of higher
precedence than it. Push this onto stack */
else if(is_operand(*s)){
while(!empty(&ms) && (!lower_precedence(peek(&ms), *s))){
*p  = pop(&ms);
p++;
}
push(&ms, *s);
}
/* Case 4. If it neither of above, add it to postfix expression */

else{
*p = *s;
p++;
}
s++;
}
/*Flush all ops from stack once infix is completely visited */
while(!empty(&ms)){

*p  = pop(&ms);
p++;
}
printf("\nPostfix expression is : ");
printf("%s\n" , post);
}

int main(void) {
infix_to_postfix("4+5*6/7");
return 0;
}
```

Code runs in O(N) time with O(N) space complexity.

### Test cases

```1. (4+8)*(6-5)/((3-2)*(2+2))
4 8 + 6 5 - * 3 2 - 2 2 + */

2. 4+8/7*8
487/8*+

3. 4
4

4. +
+ (No validation on expression).
```

# Parentheses matching problem

Given a string of characters ‘(‘ and ‘)’, we need to find if they form a valid parentheses, that is to say, find out if there are matching pairs or not. This known as parentheses matching problem.
Below are some examples

```1. ()() : valid
2. (() : Invalid, not matching parenthesis
3. ((())) : Valid
```

This problem is also know as Onion peeling problem or balanced parentheses
Simple solution to this would be to maintain a counter. Initialize counter to zero. When ‘(‘ is encountered, increment counter and when ‘)’ is encountered, decrement counter. If at the end of processing entire string, if counter is zero, then string has balanced parenthesis.

Above algorithm will fail for ‘())(‘. In this case, counter will be zero but still string does not have balanced parenthesis. To tackle this case, after decrementing counter, check if counter is less than zero. If yes, then return false at that time, no need to traverse entire string.

Problem becomes interesting, when we have multiple kind of brackets in string i.e ‘[‘, ‘{‘ ,’}’, ‘]’ are also present in string. Then either we keep count of each type of bracket. This approach is not scalable.

Parenthesis matching with multiple kind of brackets is a typical problem where stacks are used. When character  ‘)’ or any closing bracket is encountered, all we are interested in is whether there is a matching ‘(‘ or opening bracket for it or not. If not, then parentheses string is not correct.

For asserting that the current closing parenthesis is in sync with what we have already seen, we just need to check if current parenthesis completes a pair with opening parenthesis we last seen.

Next closing parenthesis should complete pair with the one prior to last and so on.

## Algorithm to check parentheses matching

```1. Whenever we see a opening parenthesis, we put it on stack.
2. For closing parenthesis, check what is at the top of the stack, if it corresponding opening parenthesis, remove it from the top of the stack.
3. If parenthesis at the top of the stack is not corresponding opening parenthesis, return false, as there is no point check the string further.
4. After processing entire string, check if stack is empty or not.
4.a If the stack is empty, return true.
4.b If stack is not empty, parenthesis do not match.
```

## Parentheses matching implementation

```#include<stdio.h>
#include<stdlib.h>

#define STACK_SIZE 10

typedef struct stack{
int top;
int items[STACK_SIZE];
}stack;

void push(stack *ms, int element){
if(ms->top < STACK_SIZE-1){
ms->top =  ms->top + 1;
ms->items[ms->top] = element;
}
else {
printf("Stack is full\n");
}
}

void pop (stack *ms){
if(ms->top >= 0){
ms->top =  ms->top - 1;
}
else{
printf("Stack is empty\n");
}
}

int peek(stack ms){
if(ms.top<0){
printf("Stack empty\n");
return 0;
}
return ms.items[ms.top];
}
int isEmpty(stack ms){
if(ms.top <0) return 1;
else return 0;
}

int parenthesesMatching(char *s){

stack ms;
char temp;
ms.top = -1;

/* Wrong input */
if(!s) return 0;

/*Empty string */
if(*s == '\0') return 1;

while(*s != '\0'){
//If char is opening parentheses, push it
if (*s == '(')
push(&ms, *s);
else if(*s == ')'){
/* If char is closing parenthesis, check if the top most
parenthesis on the stack is opening one or not */
temp  = peek(ms);
if(temp == '(')
pop(&ms);
else
return 0;
}
s++;
}
/* If we have something is stack remaining */
if(isEmpty(ms))
return 1;
else
return 0;
}

/* Driver program */
int main(){
char *str = "((()))";
printf("%d\n", parenthesesMatching(str));

return 0;
}
```

Complexity of parenthesis matching algorithm is O(N) time to scan N length string and O(N) extra space for stack.

Test cases

```1. ((()))
True

2. ()))
False

3. )(((
False

4. (
False

5 Empty string
True

6. NULL pointer
False
```

# Tower of Hanoi

Tower of Hanoi is a classic problem to learn recursion. Most of us programmers believe that recursion never easy to understand and truly so. Tower of Hanoi problem is a good problem to learn how recursive solutions are arrived at, base conditions for recursion are generated and how parameters to the successive call to the same function are modified to give the desired output.

This problem is inspired by a Hindu legend where priests at a temple were given three poles and 64 golden disk each one smaller than other. All of these disk were first places in one pole in such a way that larger disk is always below the smaller. Priest were given task to move these 64 disks from original pole to destination with below conditions:
1. Only one disk can be moved from one pole to another at a time.
2. No larger disk can be placed on smaller any time while moving disks.
And the legend is that when all these disks move to destination, temple will fall down.

For our mortal word problem statement is much simpler:We have three pegs : A, B, C. Peg A contains N disks which are stack in such a way that any disk below is larger that then disk above as shown in figure. Move these N (usually not more than 8) disks to Peg B in same condition mentioned above using the peg C.

Initial state

Final State

## Tower of hanoi algorithm

Above problem can be solved easily using intuition, problem is to come with a solution in code.
Take a problem with five disks and three poles. Now what is the simplest case to work on in any case? Yes, the case when there is only one disk, we can straight forwardly move it from origin to destination.  Now, we know solution with one disk, if we can some how move 4 other disk from origin to destination using intermediate tower, we are good!

Now how to we move four disks? Again move three disks on intermediate tower and then move last from origin to destination. Then how to move three disks and then how two disks? This continues till we are left with only one disk and that is our base case !!!

Move N-1 disks from peg A to peg C and then move the Nth disk to destination peg B. Now we have a problem left with N-1 disks which need to move from peg C to peg B using peg A as spare.

Generalized version of this algorithm is :

1. Move a tower of height-1 to an intermediate pole, using the final pole.
2. Move the remaining disk to the final pole.
3. Move the tower of height-1 from the intermediate pole to the final pole using the original pole.

So we get the sight of recursion here?
First  : We need to do same process to N-1 disk which we did for N disks.
Second : Base case is when we are left with only one disk at source, we directly move that to destination.
Pseudo-code for Tower of Hanoi

```
Function Tower_Of_Hanoi:
If N==1 : Move disk from source to destination
else
Tower_Of_Hanoi (N-1, source, destination, helper)
Move disk from source to destination
Tower_Of_Hanoi (N-1, helper, destination, source)

```

Now we would see how stacks can be used to solve this problem. A rule of thumb is :  If a problem can be solved using recursion, it can also be solve using stack. We need to map the recursion calls to stack.

### Tower of hanoi implementation

```void tower_of_hanoi(int N, char source, char dest, char help){
if(N>0){
tower_of_hanoi(N-1, source, help, dest);
printf("Moving disk from %c to %c\n", source, dest);
tower_of_hanoi(N-1, help, dest, source);
}
}
```

Below is execution of Tower of Hanoi with three disks.

Complexity of tower of Hanoi can be found using this recursive relation
T(n) = T(n-1) + 1 + T(n-1)  = 2 T(n-1) + 1

This means to solve problem of n disks we need move n-1 disk to intermediate tower, then one disk from origin to destination and then again n-1 disk from intermediate to final tower. We can find out the actual complexity by putting in values in equation:

```T(1)  = 2 T(0) + 1 =1
T(2)  = 2T(1) + 1 = 3
T(3)  = 2T(2) +1 = 7
T(4)  = 2T(3) + 1 = 15
```

If one looks closely, it is nothing but T(n)  = 2n -1. Hence complexity of Tower of Hanoi solution is exponential. Coming back to legend we started with, world is not going to end anytime soon as 264 -1 is quite a large number and even if it takes one second to move disk from one tower to another it will take 584, 942,417,355 years to solved this problem!
If you have any creative solution specially iterative, I would appreciate if you can share. Also, if you find something wrong or missing, please leave a comment.

## Convert decimal number to binary number

Problem to convert decimal number to binary representation is a very trivial one and asked only in very start of interview process. However, this problem explains couple of concept very effectively.

There are three ways to get binary representation of a decimal number.

decimal number to binary : Using stacks
Idea is to divide number by 2 each time till number becomes 1 and store remainder of each division in a stack. Why in stack? Because the last 1 or 0 will be most significant bit of binary number.

Example: Let’s say we want to convert 27  to binary number.

```27/2 =13  Remainder 1
13/2 =6   Remainder 1
6/2 = 3   Remainder 0
3/2 = 1   Remainder 1.
1/2 = 0   Remainder 1.```

When remainder is printed in reverse order it’s 11011 which is binary representation of 27.

```#include <stdio.h>

#define N 32

typedef struct stack {
short top;
short items[N];
} stack;

void initializeStack( stack *s){
s->top = -1;
}

void push( stack *s, short element ){
s->items[++s->top] = element;
}

short isEmpty( stack *s ){
return s->top < 0;
}
short pop (stack *s ){
if(!isEmpty(s)){
return s->items[s->top--];
}
return -1;
}
void main(){

stack bitStack;
initializeStack(&bitStack);

int n;

printf("Enter the number :");
scanf("%d", &n);

while(n){
/* Pushing the remainder to top of stack */
push(&bitStack, n%2);
n = n/2;
}

printf("\nBinary representation is :");
while(!isEmpty(&bitStack)){
/* Popping all remainders in reverse order from stack */
printf("%d ", pop(&bitStack));
}
printf("\n");

return 0;
}
```

Complexity of algorithm to convert a decimal number to binary representation is log(n).

## decimal number to binary : Using recursion

Method 1 can be implemented using recursion also and since we know that depth of stack will never be more than size of largest number that can be represented in machine, we can safely discard risk of stack overflow.

```#include <stdio.h>

void convertToBinary(unsigned int N){

if( N == 1 || N == 0 ) {
printf("%d", N);
return;
}

convertToBinary(N/2);
printf("%d", N%2);
}
int main(){

int n;

printf("Enter the number :");
scanf("%d", &n);

convertToBinary(n);

return 0;
}

```

decimal number to binary: A tricky one

Divide by two operation on a number is nothing but right shift of a number. And also checking if divide by 2 will give us remainder 0 or 1 is to just check last bit of number. Using this information we can easily find binary representation of a number.

Idea is to right shift number till it becomes 0 and check each time if last if bit is 0 or 1 by and number with 1 and output bit.

```#include <stdio.h>

void convertToBinary(unsigned int N){
while(N){
if( N & 1) printf("%d", 1);
else printf("%d", 0);

N = N>>1;
}

}
int main(){

int n;

printf("Enter the number :");
scanf("%d", &n);

convertToBinary(n);

return 0;
}
```