Buttercola: October 2014

Friday, October 31, 2014

Leetcode: Decode Ways

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.

For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).

The number of ways decoding "12" is 2.

Code (Java):

public class Solution {
    public int numDecodings(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
         
        int[] dp = new int[s.length()];
         
        if (s.charAt(0) >= '1' && s.charAt(0) <= '9') {
            dp[0] = 1;
        } else {
            return 0;
        }
         
        if (s.length() <= 1) {
            return 1;
        }
         
        // Initialize dp[1]
        if (s.charAt(1) >= '1' && s.charAt(1) <= '9') {
            dp[1] = 1;
        }
        if (isValid(s.substring(0, 2))) {
            dp[1] += 1;
        }
         
         
        for (int i = 2; i < s.length(); i++) {
            if (s.charAt(i) >= '1' && s.charAt(i) <= '9') {
                dp[i] = dp[i - 1];
            }
             
            if (isValid(s.substring(i - 1, i + 1))) {
                dp[i] += dp[i - 2];
            }
        }
         
        return dp[s.length() - 1];
    }
     
    private boolean isValid(String str) {
        if (str.charAt(0) == 0) {
            return false;
        }
         
        int val = Integer.valueOf(str);
         
        if (val >= 10 && val <= 26) {
            return true;
        } else {
            return false;
        }
    }
}

Update on 2/8/16:

public class Solution {
    public int numDecodings(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
         
        if (s.charAt(0) == '0') {
            return 0;
        }
         
        int[] dp = new int[s.length() + 1];
        dp[0] = 1;
        dp[1] = 1;
         
        for (int i = 2; i <= s.length(); i++) {
            if (s.charAt(i - 1) != '0') {
                dp[i] = dp[i - 1];
            }
             
            if (isValid(s.substring(i - 2, i))) {
                dp[i] += dp[i - 2];
            }
        }
         
        return dp[s.length()];
    }
     
    private boolean isValid(String s) {
        if (s.charAt(0) == '0') {
            return false;
        }
         
        int num = Integer.parseInt(s);
        if (num >= 1 && num <= 26) {
            return true;
        }
         
        return false;
    }
}

Tuesday, October 28, 2014

Leetcode: Surrounded Regions

Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

For example,

X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X

Understand the problem:
The marginal 'O' cannot be surrounded. In addition, the adjacent 'O' to the marginal 'O' cannot be surrounded as well. So We can mark those 'O' as the other characters, like 'D'. Then mark the other 'O's as 'X', and mark 'D' as 'O'.

Recursive Solution:
We start from the marginal points, and if it is 'O', we check its neighbored points.

Code (Java):

public class Solution {
    public void solve(char[][] board) {
        if (board == null || board.length == 0) {
            return;
        }
         
        int m = board.length;
        int n = board[0].length;
         
        // check the first and last rows
        for (int i = 0; i < n; i++) {
            solveHelper(0, i, m, n, board);
            solveHelper(m - 1, i, m, n, board);
        }
         
        for (int i = 1; i < m - 1; i++) {
            solveHelper(i, 0, m, n, board);
            solveHelper(i, n - 1, m, n, board);
        }
         
        // fill
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                } else if (board[i][j] == 'D') {
                    board[i][j] = 'O';
                }
            }
        }
    }
     
    private void solveHelper(int row, int col, int m, int n, char[][] board) {
        if (row < 0 || row >= m || col < 0 || col >= n || board[row][col] != 'O') {
            return;
        }
         
        board[row][col] = 'D';
         
        solveHelper(row - 1, col, m, n, board);
        solveHelper(row + 1, col, m, n, board);
        solveHelper(row, col - 1, m, n, board);
        solveHelper(row, col + 1, m, n, board);
         
    }
}

BFS Solution:

public class Solution {
    Queue<Integer> queue = new LinkedList<Integer>();
    public void solve(char[][] board) {
        if (board == null || board.length == 0) {
            return;
        }
         
        int m = board.length;
        int n = board[0].length;
         
        for (int i = 0; i < n; i++) {
            solveHelper(0, i, m, n, board);
            solveHelper(m - 1, i, m, n, board);
        }
         
        for (int i = 1; i < m - 1; i++) {
            solveHelper(i, 0, m, n, board);
            solveHelper(i, n - 1, m, n, board);
        }
         
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                } else if (board[i][j] == 'D') {
                    board[i][j] = 'O';
                }
            }
        }
    }
     
    private void solveHelper(int row, int col, int m, int n, char[][] board) {
        fill(row, col, m, n, board);
         
        while (!queue.isEmpty()) {
            int cord = queue.poll();
            int x = cord / n;
            int y = cord % n;
             
            fill(x - 1, y, m, n, board);
            fill(x + 1, y, m, n, board);
            fill(x, y - 1, m, n, board);
            fill(x, y + 1, m, n, board);
        }
    }
     
    private void fill(int row, int col, int m, int n, char[][] board) {
        if (row < 0 || row >= m || col < 0 || col >= n || board[row][col] != 'O') {
            return;
        } 
         
        board[row][col] = 'D';
         
        queue.offer(row * n + col);
    }
}

Thursday, October 9, 2014

Leetcode: Maximal Rectangle

Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.

Understand the problem:
The problem itself is straight-forward. We can easily think of iterating all elements of the matrix, and for each element, we find the largest possible rectangles containing all ones.
So we can expect that the time complexity would be O(m * n * m * n).

A better Solution:
We could maintain a dp matrix[m][n], where each row means the the height of 1's. Then scan each element of the matrix and update the height.

At last, for each row, we know the histogram of each row, of which the value is the height of each element of that row. Then we can use the method Max rectangle of histogram to find out the largest rectangle.

dp[i][j] - the maximal height for row i and column j.

The initial value of the DP matrix is the first row
for (int i = 0; i < n; i++) {
dp[0][i] = matrix[0][i];
}

The transit function is:
if (matrix[i][j]) == 0, dp[i][j] = 0;
if (matrix[i][j]) == 1, dp[i][j] = dp[i - 1][j] + 1;

The final state is to check the Math.max( max, maxRectangleHistogram(matrix[i]) )

For example,
The input matrix is:
0 0 1 0
0 1 1 0
0 1 1 0
0 0 0 1

So the DP matrix is
0 0 1 0 1
0 1 2 0 2
0 2 3 0 4
0 0 0 1 1

So the output is 4.

Code (Java):

public class Solution {
    public int maximalRectangle(char[][] matrix) {
        if (matrix == null || matrix.length == 0) {
            return 0;
        }
         
        int m = matrix.length;
        int n = matrix[0].length;
         
        int[][] dp = new int[m][n];
         
        // initialization
        for (int i = 0; i < n; i++) {
            dp[0][i] = matrix[0][i] - '0';
        }
         
        for (int i = 1; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] != '0') {
                    dp[i][j] = dp[i - 1][j] + 1;
                }
            }
        }
         
        // find the max rectanlge histogram
        int max = 0;
        for (int i = 0; i < m; i++) {
            int localSum = maxRectangleHistogram(dp[i]);
            max = Math.max(max, localSum);
        }
         
        return max;
    }
     
    private int maxRectangleHistogram(int[] height) {
        if (height.length == 1) {
            return height[0];
        }
         
        Stack<Integer> stack = new Stack<Integer>();
        int[] height2 = new int[height.length + 1];
        height2 = Arrays.copyOf(height, height.length + 1);
         
        int i = 0;
        int maxArea = 0;
        while (i < height2.length) {
            if (stack.isEmpty() || height2[i] > height2[stack.peek()]) {
                stack.push(i);
                i++;
            } else {
                int index = stack.pop();
                int localMax = 0;
                if (stack.isEmpty()) {
                    localMax = height2[index] * i;
                } else {
                    localMax = height2[index] * (i - stack.peek() - 1);
                }
                maxArea = Math.max(maxArea, localMax);
            }
        }
        return maxArea;
    }
}

Wednesday, October 8, 2014

Leetcode: Valid number

Validate if a given string is numeric.

Some examples:
"0" => true
" 0.1 " => true
"abc" => false
"1 a" => false
"2e10" => true

Note: It is intended for the problem statement to be ambiguous. You should gather all requirements up front before implementing one.

Understand the problem:
To understand the problem, several questions need to ask for the interviewer?
Q: How to account for whitespaces in the string?
A: When deciding if a string is numeric, ignore both leading and trailing whitespaces.

Q: Should I ignore spaces in between numbers – such as “1 1”?
A: No, only ignore leading and trailing whitespaces. “1 1” is not numeric.

Q: If the string contains additional characters after a number, is it considered valid?
A: No. If the string contains any non-numeric characters (excluding whitespaces and decimal point), it is not numeric.

Q: Is it valid if a plus or minus sign appear before the number?
A: Yes. “+1” and “-1” are both numeric.

Q: Should I consider only numbers in decimal? How about numbers in other bases such as hexadecimal (0xFF)?
A: Only consider decimal numbers. “0xFF” is not numeric.

Q: Should I consider exponent such as “1e10” as numeric?
A: No. But feel free to work on the challenge that takes exponent into consideration. (The Online Judge problem does take exponent into account.)

Idea:
There are the flows to solve this question:
1. Skip the leading white spaces, if there is any.
2. Skip the + or - sign, if there is any.
3. Skip the first segment of numerical characters.
4. Skip the '.' character if there is any
5. Skip the second segment of numerical characters. e.g 12.14
6. If we consider the exponent character, e and E, skip that one if there is any
7. Skip the + or - sign
8. Skip the numerical characters followed by the E or e.
9. Remove trialing white spaces, if there is any
10. Check if we have reached the end of the string. If yes, return true. Else return false.

Code (Java):

public class Solution {
    public boolean isNumber(String s) {
        int i = 0;
        int n = s.length();
         
        // step 1: skip leading white spaces
        while (i < n && s.charAt(i) == ' ') {
            i++;
        }
         
        // step 2: Skip + or - sign
        if (i < n && (s.charAt(i) == '+' || s.charAt(i) == '-')) {
            i++;
        }
         
        boolean isNumeric = false;
        // step 3: skip the first segement of numeric characters
        while (i < n && Character.isDigit(s.charAt(i))) {
            i++;
            isNumeric = true;
        }
         
        // step 4 and 5 skip the . character and the following numeric characters, if any
        if (i < n && s.charAt(i) == '.') {
            i++;
            while (i < n && Character.isDigit(s.charAt(i))) {
                i++;
                isNumeric = true;
            }
        }
         
        // step 6 and 7 and 8, exponent character and following numeric characters
        if (isNumeric && i < n && (s.charAt(i) == 'e' || s.charAt(i) == 'E')) {
            i++;
            isNumeric = false;
            if (i < n && (s.charAt(i) == '+' || s.charAt(i) == '-')) {
                i++;
            }
            while (i < n && Character.isDigit(s.charAt(i))) {
                i++;
                isNumeric = true;
            }
        }
        // step 9: Remove trailing white spaces
        while (i < n && s.charAt(i) == ' ') {
            i++;
        }
         
        return isNumeric && i == n;
    }
}

Sunday, October 5, 2014

Leetcode: Max points on a line

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

Understand the problem:
the problem gives n points on a 2D plane, find out the maximum number of points that lie on the same line.

Naive Solution:
For every two points i, and j, that form a line, the condition of the third point , say k, lie on the same line is they share the same slope, i.e,
(p_k.y - p_i.y ) (p_j.y - p_i.y)
------------------- = -------------------
(p_k.x - p_i.x) (p_j.x - p_i.x)

which is equal to:
(p_k.y - p_i.y) * (p_j.x - p_i.x) = (p_j.y - p_i.y) * (p_k.x - p_i.x)

There is one corner case that all points are the same. If in this case, the result is length of the points array.

Another tricky point to note is that for points (0,0), (1,1) (0,0), the max number of points are expected to be 3, not 2. So in the inner loop, we don't need to check if k resides in the same points as i and j.

Code (Java):

/**
 * Definition for a point.
 * class Point {
 *     int x;
 *     int y;
 *     Point() { x = 0; y = 0; }
 *     Point(int a, int b) { x = a; y = b; }
 * }
 */
public class Solution {
    public int maxPoints(Point[] points) {
        if (points == null || points.length == 0) {
            return 0;
        }
         
        if (allPointsAreSame(points)) {
            return points.length;
        }
         
        int max = 0;
        for (int i = 0; i < points.length - 1; i++) {
            for (int j = i + 1; j < points.length; j++) {
                // If points[i] and points[j] are the same point
                if (points[i].x == points[j].x && points[i].y == points[j].y) {
                    continue;
                }
                 
                int curPoints = 2;
                for (int k = 0; k < points.length; k++) {
                    //if (k != i && k != j && !samePoints(points, k, i) && !samePoints(points, k, j) && sameLine(points, i, k, j)) {
                    if (k != i && k != j && sameLine(points, i, k, j)) {
                        curPoints++;
                    }
                }
                 
                max = Math.max(max, curPoints);
             }
        }
        return max;
    }
     
    private boolean allPointsAreSame(Point[] points) {
        for (int i = 1; i < points.length; i++) {
            if (points[0].x != points[i].x || points[0].y != points[i].y) {
                return false;
            }
        }
        return true;
    }
     
    private boolean samePoints(Point[] points, int i, int j) {
        return (points[i].x == points[j].x) && (points[i].y == points[j].y);
    }
     
    private boolean sameLine(Point[] points, int i, int k, int j) {
        Point p_i = points[i];
        Point p_k = points[k];
        Point p_j = points[j];
         
        return (p_k.y - p_i.y) * (p_j.x - p_i.x) == (p_j.y - p_i.y) * (p_k.x - p_i.x);
    }
}

Discussion:
The time complexity of this naive approach is O(n^3), and the space complexity is O(1).

A better Idea:
A better idea could use a hash map. For any straight line starts from point i to point j, we calculate the slope of the line, and check if the slope is in the map before. If contains, value plus 1; else create the new key, value pair and the value is 1.

There are two corner cases need to handle:
1. Two points are the same, meaning point j are the same as point i. Use a counter to save the number of same points as the point i.
2. horizontal line: if points[i]. y == points[j].y, so the slope is 0. And we add 0 as the key. 3. vertical line: if points[i].x == points[j].x, so the slope MAX_INTEGER, and add it as the key.

Code (Java):

/**
 * Definition for a point.
 * class Point {
 *     int x;
 *     int y;
 *     Point() { x = 0; y = 0; }
 *     Point(int a, int b) { x = a; y = b; }
 * }
 */
public class Solution {
    public int maxPoints(Point[] points) {
        if (points == null || points.length == 0) {
            return 0;
        }
         
        int max = 1;
        for (int i = 0; i < points.length - 1; i++) {
            Map<Double, Integer> map = new HashMap<Double, Integer>();
            int samePoints = 0;
            double slope = 0;
            int localMax = 1;
            for (int j = i + 1; j < points.length; j++) {
                // check if point i and j are the same
                if (points[i].x == points[j].x && points[i].y == points[j].y) {
                    samePoints++;
                    continue;
                } else if (points[i].y == points[j].y) {
                    slope = 0.0;
                } else if (points[i].x == points[j].x) {
                    slope = (double) Integer.MAX_VALUE;
                } else {
                    slope = (double) (points[j].y - points[i].y) / (points[j].x - points[i].x);
                }
                 
                 
                if (map.containsKey(slope)) {
                    map.put(slope, map.get(slope) + 1);
                } else {
                    map.put(slope, 2);
                }
            }
            for (Integer num : map.values()) {
                localMax = Math.max(localMax, num);
            }
            localMax += samePoints;
            max = Math.max(max, localMax);
        }
        return max;
    }
}

Discussion:
There are several points need to consider carefully:
1. max, localMax should be initialized as 1. That is because if there is only one point in the input array, the result should be 1, instead of 0.
2. samePoints should be initialized as 0. That is because for the input (0,0), (0,0).
Since localMax and samePoints then are 1. The result is 2. If samePoints are initialized with 1, then the result would be 3.
3. When we calculate the slope, do remember to cast it as double, else it will be integer / integer, and generate the wrong result. This is really a error prone point.
At last, the time complexity of this approach is O(n^2) and the space complexity is O(n).