(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;
    }
};
Advertisements

Convert an integer to a roman numeral (Integer to Roman)

Given an integer, convert it to a roman numeral. Input is guaranteed to be within the range from 1 to 3999.

Thoughts:
Not a hard problem. Only tricky point is that 4 is “IV” not “IIII”, 9 is “IX” not “VIIII” or “VIV”. First, we might think the bases are { 1000, 500, 100, 50, 10, 5, 1}, but if we use bases { 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1 }, this problem would become really easy.

Code (C++):

class Solution {
public:
    string intToRoman(int num) {
        setup();
        string s;
        for(map<int, string>::reverse_iterator it = romanMap.rbegin();
            it != romanMap.rend(); ++it) {
            while(num >= it -> first) {
                s += it -> second;
                num -= it -> first;
            }
        }
        return s;
    }
    
private:
    map<int, string> romanMap;
    
    void setup() {
        romanMap[1000] = "M";
        romanMap[900] = "CM";
        romanMap[500] = "D";
        romanMap[400] = "CD";
        romanMap[100] = "C";
        romanMap[90] = "XC";
        romanMap[50] = "L";
        romanMap[40] = "XL";
        romanMap[10] = "X";
        romanMap[9] = "IX";
        romanMap[5] = "V";
        romanMap[4] = "IV";
        romanMap[1] = "I";
    }
};

Code (Java):

public class Solution {
	private static int[] bases = { 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9,
			5, 4, 1 };
	private static HashMap<Integer, String> map = new HashMap<Integer, String>();

	private static void setup() {
		map.put(1, "I");
		map.put(4, "IV");
		map.put(5, "V");
		map.put(9, "IX");
		map.put(10, "X");
		map.put(40, "XL");
		map.put(50, "L");
		map.put(90, "XC");
		map.put(100, "C");
		map.put(400, "CD");
		map.put(500, "D");
		map.put(900, "CM");
		map.put(1000, "M");
	}

	public String intToRoman(int num) {
		setup();
		String result = new String();
		for (int i : bases) {
			while (num >= i) {
				result += map.get(i);
				num -= i;
			}
		}
		return result;
	}
}

Division without using *, / or % (Divide Two Integers)

Divide two integers without using multiplication, division and mod operator.

Thoughts:
The common way to do this is to count how many times that divisor adding up to dividend. Of course, we should take care of signs. That’s not hard though. However, LeetCode won’t let you pass for the reason of time exceed exception. I have to use nother trick: since \log(\frac{a}{b}) = \log{a} - \log{b}, we have \frac{a}{b} = \exp (\log{a} - \log{b}). The tricky part of this question does not lie on the algorithm though. It has something to do with overflows. For particular, if we use Math.abs to compute the absolute value of Integer.MIN(-2147483648), we get -2147483648 again. So we should manually make it equal to Integer.MAX(2147483647). Most of the cases this is fine, except for one case where you try to divide Integer.MIN by 2, i.e., -2147483648 / 2 = -1073741824. However, 2147483647 / 2 = 1073741823. I have to add one more edge condition that if the divisor is 2, we just do the bitwise operation: right shift. Another node is Integer.MAX / Integer.MIN = 0 (not -1).

Code (Java):

public class Solution {
    public int divide(int dividend, int divisor) {
        if(divisor == 0)
            return 0;
        if(divisor == 1)
            return dividend;
        if(dividend == divisor)
            return 1;
        if(divisor == 2)
            return dividend >> 1;
            
        boolean sign = false;
        if( (dividend > 0 && divisor < 0) ||
            (dividend < 0 && divisor > 0) )
            sign = true;
            
        if(dividend == Integer.MAX_VALUE && divisor == Integer.MIN_VALUE)
            return 0;
        
        dividend = dividend == Integer.MIN_VALUE ? Integer.MAX_VALUE : Math.abs(dividend);
        divisor = divisor == Integer.MIN_VALUE ? Integer.MAX_VALUE : Math.abs(divisor);
        int result = (int) Math.floor(Math.pow(Math.E, Math.log(dividend) - Math.log(divisor)));
        return sign ? -result : result;
    }
}

Code (C++):

class Solution {
public:
    int divide(int dividend, int divisor) {
        if(divisor == 0)
            return 0;
        if(divisor == 1)
            return dividend;
        if(dividend == divisor)
            return 1;
        if(divisor == 2)
            return dividend >> 1;
        
        bool sign = false;
        if( (dividend > 0 && divisor < 0) ||
            (dividend < 0 && divisor > 0))
            sign = true;
            
        if(dividend == numeric_limits<int>::max() 
            && divisor == numeric_limits<int>::min())
            return 0;
        
        dividend = dividend == numeric_limits<int>::min() ? 
                numeric_limits<int>::max() : abs(dividend);
        divisor = divisor == numeric_limits<int>::min() ? 
                numeric_limits<int>::max() : abs(divisor);
        
        int result = (int) floor(exp(log(dividend) - log(divisor)));
        return sign ? -result : result;
    }
};

(Container With Most Water)

Given n non-negative integers a_{1}, a_{2}, \dots, a_{n}, where each represents a point at coordinate (i, a_{i}). n vertical lines are drawn such that the two endpoints of line i is at (i, a_{i}) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Note: You may not slant the container.

Thoughts:
Mathematically, the solution to the problem is given by \arg\max_{i<j} \min(a_{i},a_{j})\cdot(j-i). We take a "closing into the center" approach. Starting with i = 0, j = n - 1. We initialize the largest area as \min(a_{i},a_{j})\cdot(n-1). Next, we try want to move. We have two options: increase i or decrease j. Let me state a lemma first:
\forall i<k<j, \text{Area}(i,k) < \text{Area}(i,j) if a_{i} < a_{j}.
Proof:

  • If a_{k} \leq a_{i}, then \text{Area}(i,k) = a_{k}\cdot(k-i) < a_{i}\cdot(j-i) = \text{Area}(i,j).
  • If a_{k} > a_{i}, then \text{Area}(i,k) = a_{i}\cdot(k-i) < a_{i}\cdot(j-i) = \text{Area}(i,j).

This tells us if a_{i} < a_{j} and we increase i by 1, we can rule out the \text{Area}(i,i+1) since it must be smaller than \text{Area}(i,j). Similarly, we can decrease j by 1 if a_{i} \leq a_{j}. This gives us the iterative structure of the program. We stop until i meets j. Therefore this is a O(n) algorithm.

Code (C++):

class Solution {
public:
    int maxArea(vector<int> &height) {
        int i =0;
        int j = height.size() - 1;
        int best = min(height[i], height[j]) * (j-i);
        if(height[i] < height[j])
            i++;
        else
            j--;
            
        while(i < j) {
            int area = min(height[i], height[j]) * (j-i);
            if(area  > best)
                best = area;
            
            if(height[i] < height[j])
                i++;
            else
                j--;
        }
        return best;        
    }
};

Code (Java):

public class Solution {
    public int maxArea(int[] height) {
        int i = 0;
        int j = height.length - 1;
        int best = Math.min(height[i], height[j]) * (j-i);

        if(height[i] < height[j])
            i++;
        else
            j--;
            
        while(i < j) {
            int area = Math.min(height[i], height[j]) * (j-i);
            if(area > best)
                best = area;
            
            if(height[i] < height[j])
                i++;
            else
                j--;
        }
        
        return best;
    }
}

All posssible k combinations of numbers out of 1 to n (Combinations)

Given two integers n and k, return all possible combinations of k numbers out of 1 \dots n.
INPUT: n = 4, k = 2
OUTPUT: [[2,4], [3,4], [2,3], [1,2], [1,3], [1,4]]

Thoughts:
Using recursion and backtracking. We keep adding elements recursively until the size of partial solution exceeds k.

Code (C++):

class Solution {
public:
    vector<vector<int> > combine(int n, int k) {
        vector<int> partial;
        vector<vector<int> > sol;
        combineRecursion(n, k, partial, sol);
        return sol;
    }
    
    void combineRecursion(int n, int k, vector<int> partial,
        vector<vector<int> >& sol) {
        if(partial.size() == k) {
            if(find(sol.begin(), sol.end(), partial) == sol.end()) {
                sort(partial.begin(), partial.end());
                sol.push_back(partial);
            }
        } else if(partial.size() > k) {
            return;
        } else {
            for(int i = n; i >= 1; --i) {
                vector<int> partial_sol(partial);
                partial_sol.push_back(i);
                combineRecursion(i-1, k, partial_sol, sol);
            }
        }
    }
};

Code (Java):

import java.util.ArrayList;
import java.util.Collections;
public class Solution {
    public ArrayList<ArrayList<Integer>> combine(int n, int k) {
        ArrayList<ArrayList<Integer>> sol = new ArrayList<ArrayList<Integer>>();
        recursion(n,k,new ArrayList<Integer>(), sol);
        return sol;
    }
    
    private void recursion(int n, int k, ArrayList<Integer> partial,
        ArrayList<ArrayList<Integer>> sol) {
        if(partial.size() == k && !sol.contains(partial)) {
            Collections.sort(partial);
            sol.add(partial);
        } else if(partial.size() > k) {
            return;
        } else {
            for(int i = n; i >= 1; --i) {
                ArrayList<Integer> partial_sol = new ArrayList<Integer>();
                partial_sol.addAll(partial);
                partial_sol.add(i);
                recursion(i-1, k, partial_sol, sol);
            }
        }
    }
}

Number of distinct ways to climb a stair case (Climbing Stairs)

You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Thoughts:
This is just Fibonacci numbers. The number of distinct ways for n steps are the sum of distinct ways for n-1 (because we can move 1 step first, then move the rest n - 1 steps) and distinct ways for n - 2 (because we can move 2 steps first, there are two ways to do it: move 1 steps twice and move 2 steps once, the former is a duplicate for the n - 1 case so we should eliminate).

Code (Java):
Recursive version:

public class Solution {
    public int climbStairs(int n) {
        if(n == 0 || n == 1)
            return 1;
        else
	    return climbStairs(n-1) + climbStairs(n-2);
    }
}

Code (Java):
Iterative version:

public class Solution {
    public int climbStairs(int n) {
        if(n == 0 || n == 1)
            return 1;
        int steps_n_2 = 1;
        int steps_n_1 = 1;
        for(int i = 2; i <= n; ++i) {
            int steps_n = steps_n_1 + steps_n_2;
            steps_n_2 = steps_n_1;
            steps_n_1 = steps_n;
        }
        return steps_n_1;
    }
}

Adding two linked-list representations of numbers (Add Two Numbers)

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
IUNPUT: (2 -> 4 -> 3) + (5 -> 6 -> 4) (i.e. 342 + 465)
OUTPUT: 7 -> 0 -> 8 (i.e. 342 + 465 = 807)

Thoughts:
We just add element by element, as the way we manually do addition. We need to take care of two things:

  1. We should not forge the carry, especially when we have one more digit just for the carry. (e.g., 5 + 7 = 12, the ‘1’ in 12 is due to the carry from last digit)
  2. We should be careful about the fact that these two numbers might not be of the same digits. (e.g., 7 + 3456)

Code (Java):

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int carry = 0;
        ListNode l3 = null;
        ListNode iter = null;
        while(l1 != null || l2 != null) {
            int v1 = l1 == null ? 0 : l1.val;
            int v2 = l2 == null ? 0 : l2.val;
            int sum = (v1 + v2 + carry) % 10;
            carry = (v1 + v2 + carry) / 10;
            
            ListNode node = new ListNode(sum);
            node.next = null;
            if(l3 == null) {
                iter = node;
                l3 = node;
            } else {
                iter.next = node;
                iter = node;
            }
            
            l1 = l1 == null? null : l1.next;
            l2 = l2 == null? null : l2.next;
        }
        if(carry != 0) {
            ListNode node = new ListNode(carry);
            node.next = null;
            iter.next = node;
            iter = node;
        }
        return l3;
    }
}

Code (C++):

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
        int carry = 0;
        ListNode *l3 = NULL;
        ListNode *iter = NULL;
        while(l1 != NULL || l2 != NULL) {
            int v1 = l1 == NULL ? 0 : l1->val;
            int v2 = l2 == NULL ? 0 : l2->val;
            int sum = (v1 + v2 + carry) % 10;
            carry = (v1 + v2 + carry) / 10;
            
            ListNode *node = new ListNode(sum);
            if(l3 == NULL) {
                iter = node;
                l3 = node;
            } else {
                iter->next = node;
                iter = node;
            }
            
            l1 = l1 == NULL? NULL : l1->next;
            l2 = l2 == NULL? NULL : l2->next;
        }
        if(carry != 0) {
            ListNode *node = new ListNode(carry);
            node->next = NULL;
            iter->next = node;
            iter = node;
        }
        return l3;
    }
};

Previous Older Entries