Leetcode Solution 155: Min Stack

Problem Statement 

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

• push(x) -- Push element x onto stack.
• pop() -- Removes the element on top of the stack.
• top() -- Get the top element.
• getMin() -- Retrieve the minimum element in the stack. 

Example:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> Returns -3.
minStack.pop();
minStack.top();      --> Returns 0.
minStack.getMin();   --> Returns -2.

 
Problem link

Video Tutorial

You can find the detailed video tutorial here

Thought Process

Since the Min Stack preserves most of the stack operations, it is natural to composite with a normal stack, the question is how do we keep the minimum value. Simply keeping the smallest value won't work since once that value is popped out from the stack, there is no way to track the next smallest value.

One solution is to define an extra struct where it carries the minimum value before itself is popped out of the stack, basically the current minimum value so far seen in this stack. When newer element comes in, if value is smaller than the previous one, we update. Else ignore the larger values and carry over the smaller value.

Another solution is to keep two stacks. Similarly, the other stack only keeps the smallest value. We can only keep the smallest value or we can always push a value with the current smallest value seen far (essentially similar to solution one).

Solutions

Define own structure to carry over the minimum value so far

Time Complexity:O(1) Push, Pop, Top, GetMin
Space Complexity: O(N) , N is the total number of nodes, used extra class storage, negligible in practice.

 

Use two stacks.

As described above, we simply keep a minimum stack. Below implementation only pushes the smallest value, and when pop, need to peek the stack.
Time Complexity: O(1),Push, Pop, Top, GetMin
Space Complexity: O(N) , N is the total number of nodes

References

• Leetcode solution
  
  

   

Leetcode Solution 538: Convert BST to Greater Tree

Problem Statement 

Given a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus sum of all keys greater than the original key in BST.

Example:

Input: The root of a Binary Search Tree like this:
              5
            /   \
           2     13

Output: The root of a Greater Tree like this:
             18
            /   \
          20     13

Problem link

Video Tutorial

You can find the detailed video tutorial here

Thought Process

When a tree problem is presented, normally we will think if any kind of traversal could be applied, e.g, preorder/inorder/postorder or level order traversal. In this problem, we want to update the tree node value with the sum of itself and all the node values larger itself. Yep, directly modifying the input param values (In real world, it is bad practice to directly manipulate the input value since it might surprise your downstream callers unless it is clearly documented), so tree structure is not modified.

You might first think of a brute force method, perform a normal left to right inorder traversal, then it is sorted ascendingly, then do a rolling sum from largest to smallest element. This is normal when we don't really know how to deal with tree structure so we serialize the tree into an array and later we can deserialize it back. In this problem, we don't need to deserialize since tree structure is not changed. This however requires extra O(N) space.

Now let's look at a better solution. In BST, all the nodes that have greater value than the node itself lives in the right subtree, so if we traverse the right subtree first, update the tree value, then traverse the left subtree (all the right subtree nodes have greater value than left subtree), then the problem becomes doing an inorder traversal, except this time we go to right first, update value, then go to left. To keep the running sum, it is most easy to keep a global variable to track it.

Solutions

Naive inorder traversal with serialize tree into array 

Time Complexity: O(N), N is the total number of tree nodes
Space Complexity: O(N) , N is the total number of tree nodes, since we are using extra list.

 

 Reverse inorder traversal

As described above, we simply do a reverse inorder traversal, right to left and keep a running sum.


Time Complexity: O(N), N is the total number of tree nodes
Space Complexity: O(lgN) , N is the total number of tree nodes, since we are doing recursion.

References

• Leetcode solution