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

Leetcode - Rotate Image

Rotate Image

You are given an n x n 2D matrix representing an image.
Rotate the image by 90 degrees (clockwise).
Follow up:
Could you do this in-place?

public class Solution {
    public void rotate(int[][] matrix) {
        if(matrix == null)  return;
        int n = matrix.length;
        // n * n matrix
        //int w = matrix[0].length;
        if(n < 2) return;
        
        // rule: i = j'; j = n-1 - i';
        // that is: i' = n-1 -j; j' = i;
        // loop through 1/4 of the matrix
        // a | b
        // c | d
        // four parts
        // Math.ceil : returns the smallest integer >= a number.
        for(int i = 0; i < n/2; i++) {
            for(int j = 0; j < Math.ceil(((double)n)/2.0); j++) {
                int tmp = matrix[i][j];
                
                // c -> a
                matrix[i][j] = matrix[n-1 - j][i];
                // d -> c
                matrix[n-1 - j][i] = matrix[n-1 - i][n-1 - j];
                // b -> d
                matrix[n-1 - i][n-1 - j] = matrix[j][n-1 - i];
                // a -> b (tmp -> b)
                matrix[j][n-1 - i] = tmp;
            }
        }
    }
}

LeetCode - Sort Colors

Sort Colors

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.
Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
Note:
You are not suppose to use the library's sort function for this problem.

click to show follow up.

Follow up:
A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's.
Could you come up with an one-pass algorithm using only constant space?

Solution #1: (two-pass counting sort as the follow up says)

public class Solution {
    public void sortColors(int[] A) {
        if(A == null || A.length == 0 || A.length == 1)  return;
        
        int red = 0, white = 0, blue = 0;
        for(int i = 0; i < A.length; i++) {
            if(A[i] == 0)       red++;
            else if(A[i] == 1)  white++;
            else                blue++;
        }
        
        for(int i = 0; i < red; i++) 
            A[i] = 0;
        for(int i = red; i < red + white; i++)
            A[i] = 1;
        for(int i = red + white; i < A.length; i++)
            A[i] = 2;
    }
}

Solution #2: (one-pass solution)

public class Solution {
    public void sortColors(int[] A) {
        if(A == null || A.length == 0 || A.length == 1)  return;
        
        // one-pass solution
        int red = 0, blue = A.length - 1, tmp, i = 0;
        // stop looping when current >= blue
        while(i <= blue) {
            // if color is red, move to the front
            if(A[i] == 0) {
                // when cur > red, switch
                if(i > red) {
                    tmp = A[red];
                    A[red] = A[i];
                    A[i] = tmp;
                    red++;
                }
                // when cur <= red, no need to switch, just move both to next
                else {
                    i++;
                    red++;
                }
            }
            // if color is blue, move to the end
            else if(A[i] == 2) {
                // when cur < blue, switch
                if(i < blue) {
                    tmp = A[blue];
                    A[blue] = A[i];
                    A[i] = tmp;
                    blue--;
                }
                // when cur >= blue, end the loop
                else {
                    return;
                }
            }
            // if color is white, skip
            else {
                i++;
            }
        }
    }
}

Thanks to http://blog.unieagle.net/2012/10/23/leetcode%E9%A2%98%E7%9B%AE%EF%BC%9Asort-colors/

Leetcode - Candy

Candy

There are N children standing in a line. Each child is assigned a rating value.
You are giving candies to these children subjected to the following requirements:

• Each child must have at least one candy.
• Children with a higher rating get more candies than their neighbors.

What is the minimum candies you must give?

public class Solution {
    public int candy(int[] ratings) {
        int len = ratings.length;
        if(len == 0 || len == 1)    return len;
        
        // start with every child already has one candy
        int min = len;
        int[] candies = new int[len];
        
        // scan from head + 1 to tail, compare each child with their next neighbos's rating
        int cur = 0;
        for(int i = 1; i < len; i++) {
            if(ratings[i - 1] < ratings[i])
                cur++;
            else
                cur = 0;
            candies[i] = cur;
        }
        
        // scan from tail - 1 to head, do the same process as above loop
        cur = 0;
        for(int i = len - 2; i >= 0; i--) {
            if(ratings[i] > ratings[i + 1])
                cur++;
            else
                cur = 0;
            // no need to store another candies array again, just compare each node and store the max 
            // (why max: candy num of this position should match with both left and right neighbors)
            min += Math.max(candies[i], cur);
        }
        
        // add the candy num of the tail position, since the loop for add a sum didn't cover that position
        min += candies[len - 1];
        
        return min;
    }
}

Many thanks to : http://blog.csdn.net/violet_program/article/details/12233949 

Leetcode - Merge Two Sorted Lists

Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Solution:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null || l2 == null)    return l1 == null ? l2 : l1;
        
        // init
        ListNode head;
        if(l1.val < l2.val) {
            head = new ListNode(l1.val);
            l1 = l1.next;
        }
        else {
            head = new ListNode(l2.val);
            l2 = l2.next;
        }
        ListNode node = head;
        
        // loop
        while(l1 != null && l2 != null) {
            if(l1.val < l2.val) {
                node.next = new ListNode(l1.val);
                node = node.next;
                l1 = l1.next;
            }
            else {
                node.next = new ListNode(l2.val);
                node = node.next;
                l2 = l2.next;
            }
        }
        
        while(l1 != null) {
            node.next = new ListNode(l1.val);
            node = node.next;
            l1 = l1.next;
        }
        
        while(l2 != null) {
            node.next = new ListNode(l2.val);
            node = node.next;
            l2 = l2.next;
        }
        
        return head;
    }
}

Leetcode - Remove Duplicates from Sorted List

Remove Duplicates from Sorted List

 

Given a sorted linked list, delete all duplicates such that each element appear only once.
For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.

Solution:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null || head.next == null)   return head;
        
        ListNode node = head;
        
        while(node != null) {
            ListNode tmp = node.next;
            while(tmp != null && node.val == tmp.val) {
                tmp = tmp.next;
            }
            node.next = tmp;
            node = node.next;
        }
        
        return head;
    }
}

Leetcode - Maximum Depth of Binary Tree

Wait to hear back from an onsite interview. May God Bless me!

Maximum Depth of Binary Tree

Given a binary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Solution:
1. Recursive:

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null)    return 0;
        
        return getDepth(root, 1);
    }
    
    public int getDepth(TreeNode node, int depth) {
        int left = depth, right = depth;
        if(node.left != null) left = getDepth(node.left, depth + 1);
        if(node.right != null) right = getDepth(node.right, depth + 1);
        
        return left > right ? left : right;
    }
}

2. Non-recursive:

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null)    return 0;
        
        // Non-recursive, use level order triversal
        ArrayList<TreeNode> q = new ArrayList<TreeNode>();
        q.add(root);
        int depth = 0;
        
        while(!q.isEmpty()) {
            ArrayList<TreeNode> next = new ArrayList<TreeNode>();
            for(TreeNode node : q) {
                if(node.left != null)   next.add(node.left);
                if(node.right != null)  next.add(node.right);
            }
            q = new ArrayList<TreeNode>(next);
            depth++;
        }
        
        return depth;
    }
}