Monthly Archives: July 2016

https://leetcode.com/problems/the-skyline-problem/

A city’s skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Now suppose you are given the locations and height of all the buildings as shown on a cityscape photo (Figure A), write a program to output the skyline formed by these buildings collectively (Figure B).

The geometric information of each building is represented by a triplet of integers [Li, Ri, Hi], where Li and Ri are the x coordinates of the left and right edge of the ith building, respectively, and Hi is its height. It is guaranteed that 0 ≤ Li, Ri ≤ INT_MAX, 0 < Hi ≤ INT_MAX, and Ri - Li > 0. You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0.

For instance, the dimensions of all buildings in Figure A are recorded as: [ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ] .

The output is a list of “key points” (red dots in Figure B) in the format of [ [x1,y1], [x2, y2], [x3, y3], ... ] that uniquely defines a skyline. A key point is the left endpoint of a horizontal line segment. Note that the last key point, where the rightmost building ends, is merely used to mark the termination of the skyline, and always has zero height. Also, the ground in between any two adjacent buildings should be considered part of the skyline contour.

For instance, the skyline in Figure B should be represented as:[ [2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0] ].

Solution. I finally understood this problem. The basic idea is that for each column, we should dissemble it into [left, height], [right, -height] and sort by x axis. After we have these points, we loop each point. As long as we see if the max height is changed, we add this point in the result list.

First of all, we have input [l1, r1, h1], [l2, r2, l2], etc. We transform it to [l1, h1], [r1, -h1], [l2, h1], [r2, -h2], etc.

For example, the input is [2 9 10], [3 7 15], [5 12 12]

Then we have transformation points[] = [2, 10], [9, -10], [3, 15], [7, -15], [5, 12], [5, -12]

Then we sort it according to x axis, we have: points[] =  [2, 10], [3, 15], [5, 12], [7, -15], [9, 10], [12, -12]

Ok, after we got this, let’s start our cool algorithm. The idea is to use TreeMap. Key is height, value is the number of this height. We loop all the point in points[], if height(point[1]) is greater than 0, we increase the count of this height.

If height is less than 0, we decrease count of this height. If count is zero, we remove it.

After this process, we check to see if the maxHeight in TreeMap(which is lastKey() has changed. If it changed, we add this point to result.

An exception is this case: [0, 2, 3], [2, 5, 3].

Points will be [0, 3], [2, -3], [2, 3], [5, 0]. In this way, it will
have result: [0, 3], [2, 0], [2, 3], [5, 0]. But we should actually have result [0, 3], [5, 0]
Instead, we should sort like [0, 3], [2, 3], [2, -3], [5, 0]. In this way, it will output result [0, 3], [5, 0]

public static List<int[]> getSkyline(int[][] buildings) {
    // 1. Build point elements
    List<int[]> points = new ArrayList<>();
    for (int[] build : buildings) {
        points.add(new int[]{build[0], build[2]});
        points.add(new int[]{build[1], -build[2]});
    }
    /** 2. sort the points according to x axis.
     If the input is [0, 2, 3], [2, 5, 3]. Then points will be [0, 3], [2, -3], [2, 3], [5, 0]. In this way, it will
     have result: [0, 3], [2, 0], [2, 3], [5, 0]
     Instead, we should sort like [0, 3], [2, 3], [2, -3], [5, 0]. In this way, it will output result [0, 3], [5, 0]
     **/
    points.sort((p1, p2) -> p1[0] == p2[0] ? p2[1] - p1[1] : p1[0] - p2[0]);
    // 3. Go through points and find the key point, using TreeMap and maxValue
    int max = 0;
    TreeMap<Integer, Integer> tm = new TreeMap<>(); // (key = Height, value = count)
    tm.put(0, 1);
    List<int[]> ans = new ArrayList<>();
    for (int[] point : points) {
        int height = point[1];
        int count = tm.getOrDefault(Math.abs(height), 0);
        if (height > 0) {
            tm.put(height, count + 1);
        }
        else if (count == 1){
            tm.remove(-height);
        }
        else {
            tm.put(-height, count - 1);
        }
        int newMax = tm.lastKey();
        if (max != newMax) {
            ans.add(new int[]{point[0], newMax});
            max = newMax;
        }
    }
    return ans;
}

Check my code on github.

leetcode 140.

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].

Solution. Below code is my classical permutation solution:

public static List<String> wordBreak2(String s, Set<String> wordDict) {
    List<String> ans = new ArrayList<>();
    helper2(s, wordDict, "", ans, 0);
    return ans;
}

// this is the tradition, classical permutation. But it won't memorize the part result.
public static void helper2(String s, Set<String> wordDict, String curr, List<String> ans, int pos) {
    if (pos == s.length()) {
        ans.add(curr.substring(1, curr.length()));
        return;
    }
    for (String word : wordDict) {
        if (pos + word.length() <= s.length() && s.substring(pos, pos + word.length()).equals(word)) {
            helper2(s, wordDict, curr + " " + word, ans, pos + word.length());
        }
    }
}

But it didn’t pass the hot-discussed [a, aa, aaa, …, ], “aaa…aba…aaaaa” test case. The reason is because the traditional permutation doesn’t memorize the history. It just simply permutates all possibilities. Up to now, I haven’t been able to figure out how to use the classical permutation solution to memorize the middle result.

A better solution is that helper function returns a list. The returning list will permutate with current word:

This is another classical permutation solution too. The difference is that this solution takes up more space to memorize each String’s answer.

public static List<String> wordBreak(String s, Set<String> wordDict) {
    return helper(s, wordDict, new HashMap<>());
}

// the helper returns a result list. Put this list into hashmap. This can help to memorize the result.
public static List<String> helper(String s, Set<String> wordDict, Map<String, List<String>> mem) {
    if (mem.containsKey(s)) {
        return mem.get(s);
    }
    List<String> ans = new ArrayList<>();
    if (s.length() == 0) {
        ans.add("");
        return ans;
    }
    for (String word : wordDict) {
        if (s.startsWith(word)) {
            List<String> currList = helper(s.substring(word.length()), wordDict, mem);
            for (String subList : currList) {
                ans.add(word + (subList.isEmpty() ? "" : " ") + subList);
            }
        }
    }
    mem.put(s, ans);
    return ans;
}

Check my code on github.

leetcode 147.

Sort a linked list using insertion sort.

Solution. Create a dummyHead. Move the element in head into dummyHead list one by one. The process is like this:

public static ListNode insertionSortList(ListNode head) {
    if (head == null) {
        return head;
    }
    ListNode dummyHead = new ListNode(0);
    while (head != null) {
        // take out head to curr. head move to next
        ListNode curr = head;
        head = head.next;
        // put curr to target position in dummyHead. Put curr between target and target.next
        ListNode target = dummyHead;
        while (target.next != null && target.next.val < curr.val) {
            target = target.next;
        }
        curr.next = target.next;
        target.next = curr;
    }
    return dummyHead.next;
}

Check my code on github.

leetcode 149.

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

Solution. A naive idea is that assume we have line formula y = kx + b. Every 2 points can determines a line by (k, b). Then we build a hashmap which has (k, b) as key, and count as value. We iterate every 2 points and count the number of edges belonging to same line. But this count is not the answer. For example, we have 5 points in same line. Each pair of points will meet 1 time, in this way, total count will be 4 + 3 + 2 + 1 = 10. Actually, we have the formula n * (n – 1) / 2 = count. This solution is a bit overhead. First because k will be double, when we store double in hashmap. There may be a chance that same number have different double value because of 1 or 2 last digit. 2nd, it doesn’t consider the overlapping points.

A nicer solution is from this post. The idea is that it checks each point. For all lines which passing this point, find the line which contains max number of points. After this point is checked, this point won’t involve in future check. The checking process is like below:

Assume:
x = x2 – x1
y = y2 – y1

It simplifies (x, y) = (x, y) / gcd(x, y). When we store this (x, y) / gcd(x, y) as key. This is actually the ration of line made by the 2 points. And we know when we iterate POINTi, any other points with same ration will fall in line passing through POINTi. This facilitates us that we don’t use double. One thing we need to pay attention is that we need to make sure (1, -1) and (-1, 1) go to same line,  and (0, 1) and (0, -1) go to same line. In the original code, the special gcd function can make sure that (1, -1) / gcd(1, -1) and (-1, 1) / gcd(-1, 1) get same value. This is simple, but it hides the logic behind it. I prefer to manually check the sign.

Another trick is to store String type of (xy) as key. This will save us more work.

Next one is that we need to store the overlapping points.

In the end, we know that the max number of lines in this point is max number of points in a line it found, plus overlapping, plus the point itself.

Below is the code:

public static int maxPoints(Point[] points) {
    HashMap<String, Integer> hm = new HashMap<>();
    int ans = 0;
    for (int i = 0; i < points.length; i++) {
        int overlap = 0, max = 0;
        hm.clear();
        for (int j = i + 1; j < points.length; j++) {
            int x = points[j].x - points[i].x, y = points[j].y - points[i].y;
            if (x == 0 && y == 0) {
                overlap++;
                continue;
            }
            int gcd = gcd(x, y);
            x /= gcd;
            y /= gcd;
            // fix the sign issue. (3, -1) and (-3, 1) should be in same line. (0, -1) and (0, 1) should be in same line.
            if (x < 0 || (x == 0 && y < 0)) {
                x = -x;
                y = -y;
            }
            String key = String.valueOf(x) + String.valueOf(y);
            int value = hm.getOrDefault(key, 0);
            hm.put(key, value + 1);
            max = Math.max(max, value + 1);
        }
        ans = Math.max(ans, max + overlap + 1);
    }
    return ans;
}

public static int gcd(int a, int b) {
    while (b != 0) {
        int tmp = b;
        b = a % b;
        a = tmp;
    }
    return Math.abs(a);
}

Check my code on github.

leetcode 115.

Given a string S and a string T, count the number of distinct subsequences of T in S.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).

Here is an example:
S = "rabbbit", T = "rabbit"

Return 3.

Solution is from here. This one is a dp problem. It is a bit hard to think about.

Let’s say f(S, T) is the number of distinct subsequence between S and T. We have S = S1 S2 S3 S4 S5 S6, T = T1 T2 T3.

First, we know that f(S1 S2 S3 S4 S5 S6, T1 T2 T3) contains f(S1 S2 S3 S4 S5, T1 T2 T3).

Second, we know that if S6 == T3, f(S1 S2 S3 S4 S5 S6, T1 T2 T3) contains f(S1 S2 S3 S4, T1 T2).

In this way, we have the formula to calculate f(S1 S2 S3 S4 S5 S6, T1 T2 T3):

Besides, below is a dp[][] for acdabefbc and abc. Hope this will be helpful to understand. The first line means that an empty string T only has 1 match with string S.

Check my code on github.

public static int numDistinct(String S, String T) {
    int rowNum = T.length() + 1, colNum = S.length() + 1;
    int[][] dp = new int[rowNum][colNum];
    for (int i = 0; i < colNum; i++) {
        dp[0][i] = 1;
    }
    for (int row = 1; row < rowNum; row++) {
        for (int col = 1; col < colNum; col++) {
            dp[row][col] = dp[row][col - 1] + (S.charAt(col - 1) == T.charAt(row - 1) ? dp[row - 1][col - 1] : 0);
        }
    }
    return dp[rowNum - 1][colNum - 1];
}

leetcode 52.

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.

Solution. This is a dp problem. A bit similar to stock problem.

My initial solution is that I only use 2 arrays: localMax[] and globalMax[]. localMax[i] is the max product from nums[0, …, i], and nums[i] has to be included. globalMax[i] is the max product from nums[0, … , i]. So I have the formula:

localMax[i] = max{localMax[i – 1] * arr[i], arr[i]}
globalMax[i] = max{localMax[i], globalMax[i – 1]}

However, this formula won’t pass case [-2, 3, -4]. Because a max value could be derived from a min value times nums[i].

So we need 4 auxiliary arrays: localMax[], localMin[], globalMax[], globalMin[]. The relationship of these arrays will be changed to:

localMax[i] = max{localMax[i – 1] * nums[i], localMin[i – 1] * nums[i], nums[i]}
localMin[i] = min{localMax[i – 1] * nums[i], localMin[i – 1] * nums[i], nums[i]}
globalMax[i] = max{localMax[i], globalMax[i – 1]}
globalMin[i] = min{localMin[i], globalMin[i – 1]}

public static int maxProduct(int[] nums) {
    int localMax, localMin, globalMax, globalMin;
    localMax = localMin = globalMax = globalMin = nums[0];
    for (int i = 1; i < nums.length; i++) {
        int localMaxTmp = Math.max(Math.max(localMax * nums[i], localMin * nums[i]), nums[i]);
        int localMinTmp = Math.min(Math.min(localMax * nums[i], localMin * nums[i]), nums[i]);
        localMax = localMaxTmp;
        localMin = localMinTmp;
        globalMax = Math.max(localMax, globalMax);
        globalMin = Math.min(localMin, globalMin);
    }
    return globalMax;
}

public static int maxProductNaiveWay(int[] nums) {
    int[] localMax = new int[nums.length];
    int[] globalMax = new int[nums.length];
    int[] localMin = new int[nums.length];
    int[] globalMin = new int[nums.length];
    localMax[0] = globalMax[0] = localMin[0] = globalMin[0] = nums[0];
    for (int i = 1; i < nums.length; i++) {
        localMax[i] = Math.max(Math.max(localMax[i - 1] * nums[i], localMin[i - 1] * nums[i]), nums[i]);
        localMin[i] = Math.min(Math.min(localMax[i - 1] * nums[i], localMin[i - 1] * nums[i]), nums[i]);
        globalMax[i] = Math.max(localMax[i], globalMax[i - 1]);
        globalMin[i] = Math.min(localMin[i], globalMin[i - 1]);
    }
    return globalMax[nums.length - 1];
}

Check my code on github.

leetcode 6.

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P   A   H   N
A P L S I I G
Y   I   R

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string text, int nRows);

convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".

Solution. An awesome solution is from this post. Basically, it uses a StringBuffer array to build vertical and oblique parts. Let’s say string is “PAHNAPLSIIGYIR” with 4 rows. And we have StringBuffer[] sbs

sbs[0]  P     I     N
sbs[1]  A   L S   I G
sbs[2]  Y A   H R
sbs[3]  P     I

In this way, to build vertical columns PAYP and ISHI, we can use below code:

for (int idx = 0; idx < numRows && i < len; idx++) {   // build vertical part
    sbs[idx].append(s.charAt(i));
}

In order to build oblique columns AL and RI, we can use below code:

for (int idx = numRows - 2; idx >= 1 && i < len; idx--) {  // build oblique part
    sbs[idx].append(s.charAt(i));
}

In the end, we concatenate the sbs[] array to get the result.

public static String convert(String s, int numRows) {
    StringBuffer[] sbs = new StringBuffer[numRows];
    for (int i = 0; i < numRows; i++) {
        sbs[i] = new StringBuffer();
    }
    int i = 0, len = s.length();
    while (i < len) {
        for (int idx = 0; idx < numRows && i < len; idx++, i++) {   // build vertical part
            sbs[idx].append(s.charAt(i));
        }
        for (int idx = numRows - 2; idx >= 1 && i < len; idx--, i++) {  // build oblique part
            sbs[idx].append(s.charAt(i));
        }
    }
    for (int j = 1; j < numRows; j++) {
        sbs[0].append(sbs[j]);
    }
    return sbs[0].toString();
}

Check my code on github.

leetcode 11.

Given n non-negative integers a₁, a₂, …, 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.

Solution. This one has a greed solution which takes O(n) time and O(1) space. Set a left and right pointers to the pillars. Each time, calculate the area height[left] and height[right] can cover. Then, compare the height[left] and height[right], move the shorter pillar toward the center by 1 step.

Take a look at below example. Say we have pillars in both sides with height of h1 and h2.

From case1 and case2, we know, no matter what the right pillar will be, the area size(S2 or S3)will be always smaller than S1. This allow us to move the left pillar to right in order to find a larger size.

From case3 and case4, we know only when we move the pillar to another one which is taller than current pillar, then it would be possible to find a larger size.

My code on github.

public int maxArea(int[] height) {
    int max = 0, left = 0, right = height.length - 1;
    while (left < right) {
        int currArea = (right - left) * Math.min(height[right], height[left]);
        max = Math.max(max, currArea);
        if (height[left] < height[right]) { // move the shorter pillar inside
            left++;
        }
        else {
            right--;
        }
    }
    return max;
}