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

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

Count the number of 2s between 0 and n

Write a method to count the number of 2s between 0 and n.

My initial thoughts:
We need recursion. For a number, we split it into two parts: the MSB and the reminder. For example, 319 has MSB of 3 and reminder of 19.

  1. Count the number of 2s for MSB:
    1. If MSB > 2: We will have 1 or 10 or 100 or 1000, etc 2s. In this case of 319, we have 100 2s (occurring at MSB from 200 to 299).
    2. If MSB == 2: We will have reminder+1 2s. For example if we have n = 219, we have 20 2s (occurring at MSB from 200 to 219).
  2. Count the number of 2s for reminder, two parts:
    1. Recursively count the number of 2s for the tens. For example of n = 319, we’d like to recursively count number of 2s from 1 to 100. We then know we have 3 times that number of 2s. This is like: we know number 12 has a 2, so we know number 12, 112 and 212 have three 2s.
    2. Count the number of 2s causing from the reminder. For example of n = 319, we’d like to recursively count number of 2s from 1 to 19. That counts for the number of 2s appearing from 301 to 319.

My initial codes:

	// Take n = 319 as example
	public static int numberOf2s(int n) {
		if (n < 2)
			return 0;

		int result = 0;
		int power10 = 1;
		while (power10 * 10 < n) {
			power10 *= 10;
		}
		// power10 = 100
		int msb = n / power10; // 3
		int reminder = n % power10; // 19

		// Count # of 2s from MSB
		if (msb > 2)
			// This counts the first 2 from 200 to 299
			result += power10;
		if (msb == 2)
			// If n = 219, this counts the first 2
			// from 200 to 219 (20 of 2s).
			result += reminder + 1;

		// Count # of 2s from reminder
		// This (recursively) counts for # of 2s from 1 to 100
		// msb = 3, so we need to multiply by that.
		result += msb * numberOf2s(power10);
		// This (recursively) counts for # of 2s from 1 to reminder
		result += numberOf2s(reminder);

		return result;
	}

Add two numbers without using of arithmetic operators

Write a function that adds two numbers You should not use + or any arithmetic operators.

My initial thoughts:
We should take care of two things: adding and carry. Addition can be done using XOR(^). Carry can be done using AND(&). The only tricky part is that when we have two bits like 1 and 0 but then we have carry from previous position, then 1 & 0 = 0 suggests no carry but actually 1 + 0 + 1 will produce a carry. So we branch into two case: 1 + 1 will definitely produce a carry no matter what; 1 + 0 + 1 will produce new carry.

My initial codes:

	public static int add(int a, int b) {
		int result = 0;
		int carry = 0;
		for (int i = 0; i < Integer.SIZE; ++i) {
			int bitIAtA = a & (1 << i);
			int bitIAtB = b & (1 << i);
			carry &= (1 << i);
			result |= bitIAtA ^ bitIAtB ^ carry;
			carry |= ((bitIAtA & bitIAtB) << 1 | ((bitIAtA ^ bitIAtB) & carry) << 1);
		}
		return result;
	}

Solution:
To investigate this problem, let’s start off by gaining a deeper understanding of how we add numbers. We’ll work in Base 10 so that it’s easier to see. To add 759 + 674, we would usually add digit[0] from each number, carry the one, add digit[1] from each number, carry the one, etc. You could take the same approach in binary: add each digit, and carry the one as necessary.
Can we make this a little easier? Yes! Imagine we decided to split apart the “addition” and “carry” steps. That is, we do the following:

  1. Add 759 + 674, but “forget” to carry we then get 323
  2. Add 759 + 674 but only do the carrying, rather than the addition of each digit. We then get 1110
  3. Add the result of the first two operations (recursively, using the same process de- scribed in step 1 and 2): 1110 + 323 = 1433

Now, how would we do this in binary?

  1. If we add two binary numbers together but forget to carry, bit[i] will be 0 if bit[i] in a and b are both 0 or both 1. This is an XOR
  2. If we add two numbers together but only carry, we will have a 1 in bit[i] if bit[i-1] in a and b are both 1’s. This is an AND, shifted
  3. Now, recurse until there’s nothing to carry
	public static int add_no_arithm(int a, int b) {
		if (b == 0)
			return a;
		int sum = a ^ b; // add without carrying
		int carry = (a & b) << 1; // carry, but don't add
		return add_no_arithm(sum, carry); // recursion
	}

Find the kth number with prime factors 3, 5 and 7

Design an algorithm to find the kth number such that the only prime factors are 3, 5, and 7.

My initial thoughts:
The k-th number can not be larger than 7^{k}. Therefore we can enumerate all the satisfying numbers by iterating the exponent of 3, 5 and 7 from 0 to k. We then sort those numbers and retrieve the kth. Altogether it’s a O(k^{3}) algorithm.

My initial codes:

	public static int findKthNumber(int k) {
		int top = k;
		List<Integer> data = new ArrayList<Integer>();
		for (int i = 0; i <= top; ++i) {
			for (int j = 0; j <= top; ++j) {
				for (int l = 0; l <= (top + 2 - i - j); ++l) {
					if (l >= 0) {
						int number = (int) (Math.pow(3, i) * Math.pow(5, j) * Math
								.pow(7, l));
						data.add(number);
					}
				}
			}
		}
		Collections.sort(data);
		return data.get(k - 1);
	}

Solution:
Here is the algorithm:

  1. Initialize array magic and queues Q3, Q5 and Q7
  2. Insert 1 into magic.
  3. Insert 1*3, 1*5 and 1*7 into Q3, Q5 and Q7 respectively.
  4. Let x be the minimum element in Q3, Q5 and Q7. Append x to magic.
  5. If x was found in:
    • Q3 -> append x*3, x*5 and x*7 to Q3, Q5 and Q7. Remove x from Q3.
    • Q5 -> append x*5 and x*7 to Q5 and Q7. Remove x from Q5.
    • Q7 -> only append x*7 to Q7. Remove x from Q7.
    • Note: we do not need to append x*3 and x*5 to all lists because they will already be found in another list.

  6. Repeat steps 4 – 6 until we’ve found k elements.
	public static int getKthMagicNumber(int k) {
		if (k <= 0)
			return 0;
		int val = 1;
		Queue<Integer> Q3 = new LinkedList<Integer>();
		Queue<Integer> Q5 = new LinkedList<Integer>();
		Queue<Integer> Q7 = new LinkedList<Integer>();
		Q3.add(3);
		Q5.add(5);
		Q7.add(7);
		for (--k; k > 0; --k) { // We’ve done one iteration already.
			val = Math.min(Q3.peek().intValue(),
					Math.min(Q5.peek().intValue(), Q7.peek().intValue()));
			if (val == Q7.peek()) {
				Q7.remove();
			} else {
				if (val == Q5.peek()) {
					Q5.remove();
				} else { // must be from Q3
					Q3.remove();
					Q3.add(val * 3);
				}
				Q5.add(val * 5);
			}
			Q7.add(val * 7);
		}
		return val;
	}

Previous Older Entries