## (Largest Rectangle in Histogram)

Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram. Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3]. The largest rectangle is shown in the shaded area, which has area = 10 unit.
For example,
Given height = [2,1,5,6,2,3],
return 10.

Thoughts:
The point of this algorithm is to maintain a stack where higher element is always greater or equal to the lower element. Why do we need to maintain that kind of stack? Because if we have a non-decreasing list, we can easily calculate the maximum area in one scan. We just need to compare: height[i] * (n – i) for every i. So how do we maintain this stack? If we keep seeing larger element, we just need to push them onto the stack. If we see a smaller (compared to the top element on the stack) element, we need to do two things:

1. Pop the stack until we can maintain the non-decreasing order. Pushing the smaller element for m times, where m = number of poped elements.
2. Keep track of the maximum area that cause by those pop.

For example, we have height = {1,3,5,7,4}.
We push onto the stack for {1,3,5,7} then we see 4. 4 is less than 7, so we need to pop. We stop popping until we see 3. However many times we pop, we push 4 onto the stack. Therefore the resulted stack would be {1,3,4,4,4}. Because of popping 7, we need to remember that the maximum area that contains 7 is 7. The largest area that contains 5, the other element which get popped, is 10. So we take that down. We then finish processing all the elements in the original array and end up with a non-decreasing stack {1,3,4,4,4}. We can compute the largest area of this stack, which is 4*3 = 12. Since 12 is larger than the previous largest, 10, we output 12.

Code (Java):

```public class Solution {
public int largestRectangleArea(int[] height) {
Stack<Integer> stack =
new Stack<Integer>();
int max = 0;
int i = 0;
while(i < height.length) {
if(stack.isEmpty() ||
height[i] >= stack.peek()) {
stack.push(height[i]);
i++;
}
else {
int count = 0;
while(!stack.isEmpty() &&
stack.peek() > height[i]) {
count++;
int top = stack.pop();
max = Math.max(max, top * count);
}
for(int j = 0; j < count + 1; ++j) {
stack.push(height[i]);
}
i++;
}
}

int count = 0;
while(!stack.isEmpty()) {
count++;
max = Math.max(max, stack.pop() * count);
}
return max;
}
}

Code (C++):
class Solution {
public:
int largestRectangleArea(vector<int> &height) {
stack<int> stack_;
int maxArea = 0;
int i = 0;
while(i < height.size()) {
if(stack_.empty() ||
height[i] >= stack_.top()) {
stack_.push(height[i]);
i++;
}
else {
int count = 0;
while(!stack_.empty() &&
stack_.top() > height[i]) {
count++;
int top = stack_.top();
stack_.pop();
maxArea = max(maxArea, top * count);
}
for(int j = 0; j < count + 1; ++j) {
stack_.push(height[i]);
}
i++;
}
}

int count = 0;
while(!stack_.empty()) {
count++;
maxArea = max(maxArea, stack_.top() * count);
stack_.pop();
}
return maxArea;
}
};

__ATA.cmd.push(function() {
__ATA.initDynamicSlot({
id: 'atatags-26942-5f0644952132d',
location: 120,
formFactor: '001',
label: {
},
creative: {
},
privacySettings: {
text: 'Privacy settings',
}
}
});
});
```

## Sort a stack without assumptions of implementation

Write a program to sort a stack in ascending order. You should not make any assumptions about how the stack is implemented. The following are the only functions that should be used to write this program: push | pop | peek | isEmpty.

Solution
The idea is simple enough: we use another stack as an auxiliary one. Then we pop items from the original stack and push into the auxiliary stack into the correct position. The time complexity is $O(N^{2})$. It’s similar as Insertion Sort.

```	public static Stack<Integer> sort(Stack<Integer> stack) {
Stack<Integer> auxiliary = new Stack<Integer>();
while (!stack.isEmpty()) {
Integer value = stack.pop();
while (!auxiliary.isEmpty() && value < auxiliary.peek())
stack.push(auxiliary.pop());
auxiliary.push(value);
}
return auxiliary;
}

```

## Implement queue using two stacks

Implement a MyQueue class which implements a queue using two stacks.

My initial thoughts:
The first stack keep pushing in new items as the enqueue function. When dequeue, stack1 pops element and stack2 push that element in. That will rearrange the order of FILO to FIFO. After the transfering, the first element will be on the top of stack2 so we just pop that out. Then we moving the elements in stack2 back to stack1.

My initial codes:

```import java.util.Stack;
public class Q3_5 {

private Stack<Object> stack1 = new Stack<Object>();
private Stack<Object> stack2 = new Stack<Object>();

public void enqueue(Object item) {
stack1.push(item);
}

public Object dequeue() {
if(stack1.empty())
return null;
else {
while(!stack1.empty())
stack2.push(stack1.pop());
Object item = stack2.pop();
while(!stack2.empty())
stack1.push(stack2.pop());
return item;
}
}
}

Not quite efficient for dequeue.
Solution:
public class MyQueue<T> {
Stack<T> s1, s2;

public MyQueue() {
s1 = new Stack<T>();
s2 = new Stack<T>();
}

public int size() {
return s1.size() + s2.size();
}

s1.push(value);
}

public T peek() {
if (!s2.empty()) return s2.peek();
while (!s1.empty()) s2.push(s1.pop());
return s2.peek();
}

public T remove() {
if (!s2.empty()) return s2.pop();
while (!s1.empty()) s2.push(s1.pop());
return s2.pop();
}
}

Comments: lazy implementation for peek() and pop(). Only move elements from stack1 to stack2 when needed.
```

## Solve Towers of Hanoi using stack

In the classic problem of the Towers of Hanoi, you have 3 rods and N disks of different sizes which can slide onto any tower. The puzzle starts with disks sorted in ascending order of size from top to bottom (e.g., each disk sits on top of an even larger one). You have the following constraints:
(A) Only one disk can be moved at a time.
(B) A disk is slid off the top of one rod onto the next rod.
(C) A disk can only be placed on top of a larger disk.
Write a program to move the disks from the first rod to the last using Stacks.

My initial thoughts:
Let us denote the three rods, from left to right, as src, transfer and des.

• 1 disk only: move from src to des. done.
• 2 disks(top to bottom: 1->2): move 1 from src to transfer, move 2 from src to des, move 1 from transfer to des.
• 3 disks: ‘magically(recursively)’ move {1,2} from src to transfer, move 3 from src to des, ‘magically(recursively)’ move {1,2} from transfer to des.
• n disks: recursively move the top n-1 disks from src to transfer, move n from src to des, recursively move the n-1 disks from transfer to des.

For $n$ disks, we need $2^{n}-1$ steps at minimum to finish the game.

My codes:(solution)

```import java.util.Stack;
public class Q3_4 {

private Stack<Object>[] stacks = new Stack;
private Object[] disks;

public Q3_4(Object[] disks) {
stacks = new Stack<Object>();
stacks = new Stack<Object>();
stacks = new Stack<Object>();
this.disks = disks;
for (Object o : disks)
stacks.push(o);
}

public void solve() {
solveRecursively(0, 2, 1, disks);
}

public void solveRecursively(int sourceIndex, int desIndex,
int transferIndex, Object[] disks) {
Stack<Object> source = stacks[sourceIndex];
Stack<Object> des = stacks[desIndex];

Object[] sub_disks = null;
if (disks.length > 1) {
sub_disks = new Object[disks.length - 1];
System.arraycopy(disks, 0, sub_disks, 0,
disks.length - 1);
solveRecursively(sourceIndex, transferIndex,
desIndex, sub_disks);
}
Object t = source.pop();
des.push(t);
System.out.println("Move " + t + " from " +
sourceIndex + " to " + desIndex);

if (disks.length > 1)
solveRecursively(transferIndex, desIndex,
sourceIndex, sub_disks);
}
}

```

## Set of stacks with capacity

Imagine a (literal) stack of plates. If the stack gets too high, it might topple. Therefore, in real life, we would likely start a new stack when the previous stack exceeds some threshold. Implement a data structure SetOfStacks that mimics this. SetOfStacks should be composed of several stacks, and should create a new stack once the previous one exceeds capacity. SetOfStacks.push() and SetOfStacks.pop() should behave identically to a single stack (that is, pop() should return the same values as it would if there were just a single stack).
Implement a function popAt(int index) which performs a pop operation on a specific sub-stack.

My initial thoughts:
Use stack of stacks. Push to the top sub-stack. Pop from the top sub-stack. If the top sub-stack becomes empty, remove it. Keep a array list of all the sub-stacks.

My initial codes:

```	public class MyStackOfStack<T> {

private MyStack<MyStack<T>> buffer = new MyStack<MyStack<T>>();
private static final int THRESHOLD = 10;
private int size = 0;
private List<MyStack<T>> indices = new ArrayList<MyStack<T>>();

public void push(T data) {
if (size < THRESHOLD && size > 1) {
buffer.peek().push(data);
size++;
} else { // size == 0 || size == THRESHOLD
MyStack<T> newStack = new MyStack<T>();
newStack.push(data);
size = 1;
buffer.push(newStack);
}
}

public T pop() {
MyStack<T> topStack = buffer.peek();
if (size > 1) {
} else { // size == 1
T data = topStack.pop();
buffer.pop();
indices.remove(indices.size() - 1);
size = THRESHOLD;
return data;
}
}

public T popAt(int index) {
return indices.get(index).pop();
}
}

popAt(int index) removes the bottom element of the sub-stack.
If one of the middle sub-stack is poped, its above sub=stack is supposed to pad down one element. This behavior is not supported.

Solution:
public class StackNode2<T> {
private T data = null;
private StackNode2<T> below = null;
private StackNode2<T> above = null;
// getters and setters are omitted.
}

public class MyStack2<T> {

private StackNode2<T> top = null;
private final int CAPACITY;
private StackNode2<T> bottom = null;
private int size = 0;

public MyStack2(int capacity) {
this.CAPACITY = capacity;
}

public void push(T data) {
StackNode2<T> item = new StackNode2<T>(data);
if (size == 0) {
top = item;
bottom = top;
size++;
} else if (size < CAPACITY) {
top.setAbove(item);
item.setBelow(top);
top = item;
size++;
}
}

public T pop() {
if (size > 0) {
size--;
StackNode2<T> item = top;
top = item.getBelow();
// top.setAbove(null);
return item.getData();
}
return null;
}

public T peek() {
if (size > 0) {
}
return null;
}

public int size() {
return size;
}

public boolean isEmpty() {
return size == 0;
}

public boolean isFull() {
return size == CAPACITY;
}

public T getBottom() {
if (size > 0)
return bottom.getData();
else
return null;
}

public T removeFromBottom() {
if (size > 0) {
size--;
StackNode2<T> item = bottom;
bottom = item.getAbove();
bottom.setBelow(null);
return item.getData();
} else {
return null;
}
}
}

public class SetOfStack<T> {

private ArrayList<MyStack2<T>> buffer =
new ArrayList<MyStack2<T>>();
private final int CAPACITY;

public SetOfStack(int capacity) {
this.CAPACITY = capacity;
}

public void push(T data) {
if (buffer.isEmpty()) {
MyStack2<T> stack = new MyStack2<T>(CAPACITY);
stack.push(data);
} else {
MyStack2<T> stack = buffer.get(buffer.size() - 1);
if (stack.isFull()) {
MyStack2<T> newStack = new MyStack2<T>(CAPACITY);
newStack.push(data);
} else {
stack.push(data);
}
}
}

public T pop() {
if (buffer.isEmpty()) {
return null;
} else {
MyStack2<T> stack = buffer.get(buffer.size() - 1);
T data = stack.pop();
if (stack.isEmpty())
buffer.remove(buffer.size() - 1);
return data;
}
}

public T popAt(int index) {
return leftShift(index, true);
}

public T leftShift(int index, boolean removeTop) {
MyStack2<T> stack = buffer.get(index);
T removedItem = null;
if (removeTop)
removedItem = stack.pop();
else
removedItem = stack.removeFromBottom();
if (stack.isEmpty())
buffer.remove(index);
else if (buffer.size() > index + 1) {
stack.push(leftShift(index + 1, false));
}
return removedItem;
}
}

```

## Stack with function min in O(1) time

How would you design a stack which, in addition to push and pop, also has a function min which returns the minimum element? Push, pop and min should all operate in O(1) time.

My initial thoughts:
We can keep an record of the current minimum element and dynamically update it when doing the push. However, the update cannot be kept when poping. Therefore I can only implement a O(1) push(), min() but O(n) pop() data structure.

My initial codes:

```public class Q3_2 {

private StackNode<Integer> top = null;
private Integer min = Integer.MAX_VALUE;

public void push(Integer item) {
StackNode<Integer> t = new StackNode<Integer>(item);
t.setUnderneath(top);
top = t;

if (item < min)
min = item;
}

public Integer pop() {
if (top == null)
return null;
Integer data = top.getData();
top = top.getUnderneath();

if (data == min) {
min = Integer.MAX_VALUE;
StackNode<Integer> curr = top;
while (curr != null) {
if (curr.getData() < min)
min = curr.getData();
curr = curr.getUnderneath();
}
}

return data;
}

public Integer min() {
return min;
}
}

Solution:
public class StackWithMinNode<T> extends StackNode<T> {

private Integer min = null;
private StackWithMinNode<T> underneath = null;

public StackWithMinNode(T item) {
super(item);
}

public Integer min() {
return min;
}

public void setMin(Integer min) {
this.min = min;
}

@Override
public StackWithMinNode<T> getUnderneath() {
return underneath;
}

public void setUnderneath(StackWithMinNode<T> underneath) {
this.underneath = underneath;
}

}

public class StackWithMin extends MyStack<Integer> {

StackWithMinNode<Integer> top = null;

@Override
public void push(Integer data) {
StackWithMinNode<Integer> item =
new StackWithMinNode<Integer>(data);
if (top != null)
item.setMin(Math.min(data, top.min()));
else
item.setMin(data);
item.setUnderneath(top);
top = item;
}

@Override
public Integer pop() {
if (top == null)
return null;
Integer data = top.getData();
top = top.getUnderneath();
return data;
}

public Integer min() {
if (top == null)
return null;
}
}

The idea is similar as my initial thought, only that we keep a local minimum for each node.
Another solution is implemented using an auxiliary stack to keep track of the local minimum, therefore potentially saving spaces taken by keep track local min for each single node.
public class StackWithMinStack extends MyStack<Integer> {

MyStack<Integer> minStack = new MyStack<Integer>();

@Override
public void push(Integer data) {
StackNode<Integer> item = new StackNode<Integer>(data);
if (minStack.isEmpty())
minStack.push(data);
else {
if (data.compareTo(minStack.peek()) <= 0)
minStack.push(data);
}
item.setUnderneath(top);
top = item;
}

@Override
public Integer pop() {
if (top == null)
return null;
Integer data = top.getData();
if (data.compareTo(minStack.peek()) == 0)
minStack.pop();
top = top.getUnderneath();
return data;
}

public Integer min() {
if (minStack.isEmpty())
return null;
return minStack.peek();
}
}

Comment: Be careful about line 11. We push into the auxiliary stack if we have found element less OR equal to the local min. We have to keep duplicates in order to further deal with the case where one duplicate is poped. Think about this stack from top to bottom (on the right is its auxiliary stack, storing the local min):
5
2
4 2
2 2
7 7
If we only store one 2 in the auxiliary stack, then when 5 and 2 are poped from the original stack, the auxiliary stack will only be left with 7, resulting in a wrong global min.
```

## Implement 3 stacks using a single array

Describe how you could use a single array to implement three stacks.

My initial thoughts:
If size of the array is n, we can allocate [0,n/3) to the first stack, [n/3,2n/3) to the second stack and [2n/3,n) to the third stack. We also need to maintain an array of pointers to the positions of the top for each stack.

My initial codes:

```public class Q3_1 {

private final int SIZE = 10;
private Integer[] data = new Integer[SIZE * 3];
private int[] tops = { 0, 0, 0 };

public void push(int stackNum, Integer item) {
data[tops[stackNum] + SIZE * stackNum] = item;
tops[stackNum]++;
}

public Integer pop(int stackNum) {
if (tops[stackNum] == SIZE * stackNum)
return null;
tops[stackNum]--;
Integer element = data[tops[stackNum] + SIZE * stackNum];
data[tops[stackNum] + SIZE * stackNum] = null;
return element;
}

public boolean isEmpty(int stackNum) {
}

@Override
public String toString() {
String result = new String();
for (int i = 0; i < data.length; ++i)
result += data[i] + " ";
return result;
}
}

It works well but if we can also dynamically increase the size, that would be more practically realistic.

Solution:
int stackSize = 300;
int indexUsed = 0;
int[] stackPointer = { -1, -1, -1 };
StackNode[] buffer = new StackNode[stackSize * 3];

void push(int stackNum, int value) {
int lastIndex = stackPointer[stackNum];
stackPointer[stackNum] = indexUsed;
indexUsed++;
buffer[stackPointer[stackNum]] = new StackNode(lastIndex, value);
}

int pop(int stackNum) {
int value = buffer[stackPointer[stackNum]].value;
int lastIndex = stackPointer[stackNum];
stackPointer[stackNum] = buffer[stackPointer[stackNum]].previous;
buffer[lastIndex] = null;
indexUsed--;
return value;
}

int peek(int stack) {
return buffer[stackPointer[stack]].value;
}

boolean isEmpty(int stackNum) {
return stackPointer[stackNum] == -1;
}

class StackNode {
public int previous;
public int value;
public StackNode(int p, int v) {
value = v;
previous = p;
}
}