Leetcode - Unique Paths

Unique Paths

 

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).
How many possible unique paths are there?

Above is a 3 x 7 grid. How many possible unique paths are there?

Note: m and n will be at most 100.

Solution #1: (Recursive, O(n^2), Time Limit Exceeded...)

// recursive
public class Solution {
    public int uniquePaths(int m, int n) {
        return backtrack(0, 0, m, n);
    }
    
    private int backtrack(int row, int col, int m, int n) {
        // to the target
        if(row == m - 1 && col == n - 1)
            return 1;
        // out of range
        if(row > m - 1 || col > n - 1)
            return 0;
            
        // move down + move right
        return backtrack(row + 1, col, m, n) + backtrack(row, col + 1, m, n);
    }
}

Solution #2: loop, O(n^2) space & time

// loop, similar as min path sum, O(n^2) time & space
public class Solution {
    public int uniquePaths(int m, int n) {
        int[][] res = new int[m][n];
        
        // init left
        for(int i = 0; i < m; i++) {
            res[i][0] = 1;
        }
        // init top
        for(int j = 0; j < n; j++) {
            res[0][j] = 1;
        }
        
        // add values
        for(int i = 1; i < m; i++) {
            for(int j = 1; j < n; j++) {
                res[i][j] = res[i - 1][j] + res[i][j - 1];
            }
        }
        
        return res[m - 1][n - 1];
    }
}

Solution #3: loop, O(n^2) time, O(n) space

// loop, similar as min path sum, O(n^2) time, O(n) space
public class Solution {
    public int uniquePaths(int m, int n) {
        int[] res = new int[n];
        
        // init array
        for(int j = 0; j < n; j++) {
            res[j] = 1;
        }
        
        // add values
        for(int i = 1; i < m; i++) {
            // reset the head to 1 (simulate the next row head)
            // similar to set all left most elements in a 2D array to 1
            res[0] = 1;
            for(int j = 1; j < n; j++) {
                res[j] = res[j - 1] + res[j];
            }
        }
        
        return res[n - 1];
    }
}

Many thanks to:
http://cuijing.org/interview/leetcode/summary-of-dynamic-programming-in-leetcode.html
&
http://yucoding.blogspot.com/2013/04/leetcode-question-116-unique-path-i.html

Leetcode - Minimum Path Sum

Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.

Solution #1:

// DP, O(n^2) time, O(n^2) space
public class Solution {
    public int minPathSum(int[][] grid) {
        int row = grid.length;
        int col = grid[0].length;
        
        int[][] res = new int[row][col];
        // init
        res[0][0] = grid[0][0];
        
        // left
        for(int i = 1; i < row; i++) {
            res[i][0] = res[i - 1][0] + grid[i][0];
        }
        // top
        for(int j = 1; j < col; j++) {
            res[0][j] = res[0][j - 1] + grid[0][j];
        }
        
        // rest elements
        for(int i = 1; i < row; i++) {
            for(int j = 1; j < col; j++) {
                res[i][j] = grid[i][j] + Math.min(res[i - 1][j], res[i][j - 1]);
            }
        }
        
        return res[row - 1][col - 1];
    }
}

Solution #2:

// DP, O(n^2) time, O(n) space
public class Solution {
    public int minPathSum(int[][] grid) {
        int row = grid.length;
        int col = grid[0].length;
        
        int[] res = new int[col];
        // init
        Arrays.fill(res, Integer.MAX_VALUE);
        res[0] = 0;
        
        // rest elements
        for(int i = 0; i < row; i++) {
            // init the 0th sum = old 0th element + the new 0th element
            // just init the 0th column every time dynamically
            res[0] = res[0] + grid[i][0];
            
            // loop through each element of each row
            for(int j = 1; j < col; j++) {
                res[j] = grid[i][j] + Math.min(res[j], res[j - 1]);
            }
        }
        
        return res[col - 1];
    }
}

Many thanks to: http://fisherlei.blogspot.com/2012/12/leetcode-minimum-path-sum.html

Leetcode - Maximum Subarray

Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.

click to show more practice.

More practice: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

 1. Solution #1, O(n)
Just simply loop from left to right and return the max val.

// O(n)
public class Solution {
    public int maxSubArray(int[] A) {
        int sum = 0;
        int maxSum = Integer.MIN_VALUE;
        for(int i = 0; i < A.length; i++) {
            sum += A[i];
            maxSum = Math.max(maxSum, sum);
            // re-set sum when < 0 (no need to keep neg value)
            if(sum < 0) sum = 0;
        }
        return maxSum;
    }
}

2. Solution #2, Divide and conquer, O(n) also?
The max range can be in the left half, or in the right half, or across the mid of the array, so we just divide it to tree parts and recursive until we get the max value of each part, and then get the largest value.

// Devide and Conquer
public class Solution {
    public int maxSubArray(int[] A) {
        int maxSum = Integer.MIN_VALUE;
        return findMaxSub(A, 0, A.length - 1, maxSum);
    }
    
    // recursive to find max sum 
    // may appear on the left or right part, or across mid(from left to right)
    public int findMaxSub(int[] A, int left, int right, int maxSum) {
        if(left > right)    return Integer.MIN_VALUE;
        
        // get max sub sum from both left and right cases
        int mid = (left + right) / 2;
        int leftMax = findMaxSub(A, left, mid - 1, maxSum);
        int rightMax = findMaxSub(A, mid + 1, right, maxSum);
        maxSum = Math.max(maxSum, Math.max(leftMax, rightMax));
        
        // get max sum of this range (case: across mid)
        // so need to expend to both left and right using mid as center
        // mid -> left
        int sum = 0, midLeftMax = 0;
        for(int i = mid - 1; i >= left; i--) {
            sum += A[i];
            if(sum > midLeftMax)    midLeftMax = sum;
        }
        // mid -> right
        int midRightMax = 0; sum = 0;
        for(int i = mid + 1; i <= right; i++) {
            sum += A[i];
            if(sum > midRightMax)    midRightMax = sum;
        }
        
        // get the max value from the left, right and across mid
        maxSum = Math.max(maxSum, midLeftMax + midRightMax + A[mid]);
        
        return maxSum;
    }
}

Thanks to : http://fisherlei.blogspot.com/2012/12/leetcode-maximum-subarray.html