Buttercola: September 2014

Tuesday, September 30, 2014

LintCode: Recover Rotated Sorted Array

Given a rotated sorted array, recover it to sorted array in-place.

Example

[4, 5, 1, 2, 3] -> [1, 2, 3, 4, 5]

Challenge Expand

Clarification Expand

Tags Expand

Solution:
The key to the problem is to reverse the list. There are three steps. Take the example of [4, 5, 1, 2, 3].
Step 1: [4, 5] -> [5, 4]
Step 2: [1, 2, 3] -> [3, 2, 1]
Step 3: [5, 4, 3, 2, 1] -> [1, 2, 3, 4, 5]

Code (Java):

/**
 * Copyright: NineChapter
 * - Algorithm Course, Mock Interview, Interview Questions
 * - More details on: http://www.ninechapter.com/
 */
 
import java.util.ArrayList;
 
 
public class Solution {
    /**
     * @param nums: The rotated sorted array
     * @return: The recovered sorted array
     */
    private void reverse(ArrayList<Integer> nums, int start, int end) {
        for (int i = start, j = end; i < j; i++, j--) {
            int temp = nums.get(i);
            nums.set(i, nums.get(j));
            nums.set(j, temp);
        }
    }
 
    public void recoverRotatedSortedArray(ArrayList<Integer> nums) {
        for (int index = 0; index < nums.size() - 1; index++) {
            if (nums.get(index) > nums.get(index + 1)) {
                reverse(nums, 0, index);
                reverse(nums, index + 1, nums.size() - 1);
                reverse(nums, 0, nums.size() - 1);
                return;
            }
        }
    }
}

Leetcode: Clone Graph

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

OJ's undirected graph serialization:

Nodes are labeled uniquely.

We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.

As an example, consider the serialized graph {0,1,2#1,2#2,2}.

The graph has a total of three nodes, and therefore contains three parts as separated by #.

First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
Second node is labeled as 1. Connect node 1 to node 2.
Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.

Visually, the graph looks like the following:

Code (Java):

/**
 * Definition for undirected graph.
 * class UndirectedGraphNode {
 *     int label;
 *     List<UndirectedGraphNode> neighbors;
 *     UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
 * };
 */
public class Solution {
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        if (node == null) {
            return null;
        }
         
        Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<UndirectedGraphNode, UndirectedGraphNode>();
        Queue<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>();
         
        // create the new node
        UndirectedGraphNode newNode = new UndirectedGraphNode(node.label);
        map.put(node, newNode);
         
        queue.offer(node);
         
        while (!queue.isEmpty()) {
            UndirectedGraphNode curr = queue.poll();
            List<UndirectedGraphNode> neighborNodes = curr.neighbors;
             
            for (UndirectedGraphNode neighbor : neighborNodes) {
                if (!map.containsKey(neighbor)) {
                    UndirectedGraphNode copy = new UndirectedGraphNode(neighbor.label);
                    map.put(neighbor, copy);
                    map.get(curr).neighbors.add(copy);
                    queue.offer(neighbor);
                } else {
                    map.get(curr).neighbors.add(map.get(neighbor));
                }
            }
        }
         
        return newNode;
    }
}

Update on 9/18/15:

/**
 * Definition for undirected graph.
 * class UndirectedGraphNode {
 *     int label;
 *     List<UndirectedGraphNode> neighbors;
 *     UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
 * };
 */
public class Solution {
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        if (node == null) {
            return null;
        }
         
        UndirectedGraphNode newNode = new UndirectedGraphNode(node.label);
         
        Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>();
        Queue<UndirectedGraphNode> queue = new LinkedList<>();
         
        queue.offer(node);
        map.put(node, newNode);
         
        while (!queue.isEmpty()) {
            UndirectedGraphNode curr = queue.poll();
            List<UndirectedGraphNode> neighbors = curr.neighbors;
             
            for (UndirectedGraphNode neighbor : neighbors) {
                if (!map.containsKey(neighbor)) {
                    UndirectedGraphNode newNeighbor = new UndirectedGraphNode(neighbor.label);
                    map.put(neighbor, newNeighbor);
                    map.get(curr).neighbors.add(newNeighbor);
                    queue.offer(neighbor);
                } else {
                    UndirectedGraphNode newNeighbor = map.get(neighbor);
                    map.get(curr).neighbors.add(newNeighbor);
                }
            }
        }
         
        return newNode;
    }
}

/**
 * Definition for Undirected graph.
 * class UndirectedGraphNode {
 *     int label;
 *     List<UndirectedGraphNode> neighbors;
 *     UndirectedGraphNode(int x) {
 *         label = x;
 *         neighbors = new ArrayList<UndirectedGraphNode>();
 *     }
 * }
 */
 
public class Solution {
    /**
     * @param node: A undirected graph node
     * @return: A undirected graph node
     */
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        // write your code here
        if (node == null) {
            return null;
        }
         
        Map<UndirectedGraphNode, UndirectedGraphNode> nodeMap = new HashMap<>();
         
        // step 1: clone the vertex
        Queue<UndirectedGraphNode> queue = new LinkedList<>();
        Set<UndirectedGraphNode> set = new HashSet<>();
         
        queue.offer(node);
         
        while (!queue.isEmpty()) {
            UndirectedGraphNode currNode = queue.poll();
             
            // copy the vertex
            nodeMap.put(currNode, new UndirectedGraphNode(currNode.label));
                 
             for (UndirectedGraphNode neighbor : currNode.neighbors) {
                 if (!nodeMap.containsKey(neighbor)) {
                     queue.offer(neighbor);
                 }
             }
        }
         
        // step 2: copy the edges
        for (UndirectedGraphNode originalNode : nodeMap.keySet()) {
            for (UndirectedGraphNode neighbor : originalNode.neighbors) {
                nodeMap.get(originalNode).neighbors.add(nodeMap.get(neighbor));
            }
        }
         
        return nodeMap.get(node);
    }
}

Monday, September 29, 2014

Leetcode: Scramble String

Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.

Below is one possible representation of s1 = "great":

    great
   /    \
  gr    eat
 / \    /  \
g   r  e   at
           / \
          a   t

To scramble the string, we may choose any non-leaf node and swap its two children.

For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat".

    rgeat
   /    \
  rg    eat
 / \    /  \
r   g  e   at
           / \
          a   t

We say that "rgeat" is a scrambled string of "great".

Similarly, if we continue to swap the children of nodes "eat" and "at", it produces a scrambled string "rgtae".

    rgtae
   /    \
  rg    tae
 / \    /  \
r   g  ta  e
       / \
      t   a

We say that "rgtae" is a scrambled string of "great".

Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.

Understand the problem:

public class Solution {
    public boolean isScramble(String s1, String s2) {
        if (s1.length() != s2.length()) {
            return false;
        }
         
        if (s1.length() == 1 && s2.length() == 1) {
            if (s1.charAt(0) == s2.charAt(0)) {
                return true;
            } else {
                return false;
            }
        }
         
        char[] array1 = s1.toCharArray();
        char[] array2 = s2.toCharArray();
        Arrays.sort(array1);
        Arrays.sort(array2);
        if (!Arrays.toString(array1).equals(Arrays.toString(array2))) {
            return false;
        }
         
         
        for (int i = 1; i < s1.length(); i++) {
            String s11 = s1.substring(0, i);
            String s12 = s1.substring(i);
            String s21 = s2.substring(0, i);
            String s22 = s2.substring(i);
             
            if (isScramble(s11, s21) && isScramble(s12, s22)) {
                return true;
            }
             
            s21 = s2.substring(0, s2.length() - i);
            s22 = s2.substring(s2.length() - i);
             
            if (isScramble(s11, s22) && isScramble(s12, s21)) {
                return true;
            }
        }
         
        return false;
    }
}

Friday, September 26, 2014

Leetcode: N-Queens II

Follow up for N-Queens problem.

Now, instead outputting board configurations, return the total number of distinct solutions.

Understand the problem:
This is an extension of the N-Queen I problem, but just asks for returning the number of solutions.

Solution:

public class Solution {
    private int result = 0;
    public int totalNQueens(int n) {
        if (n == 0 || n == 2 || n == 3) {
            return 0;
        }
        int[] cols = new int[n];
        totalNQueensHelper(n, 0, cols);
         
        return result;
    }
     
    private void totalNQueensHelper(int n, int row, int[] cols) {
        if (row == n) {
            result++;
            return;
        }
         
        for (int j = 0; j < n; j++) {
            if (isValid(j, row, cols)) {
                cols[row] = j; 
                totalNQueensHelper(n, row + 1, cols);
            }
        }
    }
     
    private boolean isValid(int col, int rows, int[] cols) {
        for (int i = 0; i < rows; i++) {
            if (cols[i] == col || rows - i == Math.abs(cols[i] - col)) {
                return false;
            }
        }
        return true;
    }
}

Thursday, September 25, 2014

Leetcode: Longest Valid Parentheses

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

For "(()", the longest valid parentheses substring is "()", which has length = 2.

Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

Understand the problem:
The problem asks for finding the length of the longest valid parentheses substring. Note that it is substring not subsequence.

Solution 1: Using DP
For those kinds of "longest substring" problems, it is usually to use DP solution. This problem is kind of special using the DP solution.
1. Define dp[n], whereas dp[i] means the length of the longest valid parentheses substrings STARTING FROM i to str.length() - 1.
2. Transit function.
-- If the str[i] = ')', dp[i] = 0, because there will no well-formed parentheses starting from ')'.
-- If the str[i] = '(', we check dp[i + 1], the longest valid parentheses starting from i + 1, and jump to the index j = i + dp[i + 1] + 1. e.g.
( ( ) ( ) )
i j
So if j is within the length of the string and str[j] == ')', dp[i] = dp[i + 1] + 2. In addition, dp[i] += dp[j + 1], because what if after j the parentheses are still valid.

3. Initial state: dp[n - 1] = 0
4. Final state: It is quite special here. We cannot check dp[0] because dp[i] stands for the length of longest valid parentheses starting from i. So the longest substring may not starts from str[0]. As a result, we must check if dp[i] is the largest. So the final state is max(dp[i]).

Code (Java):

public class Solution {
    public int longestValidParentheses(String s) {
        if (s == null || s.length() < 2) {
            return 0;
        }
         
        int[] dp = new int[s.length()];
        int maxLen = 0;
         
        for (int i = s.length() - 2; i >= 0; i--) {
            if (s.charAt(i) == '(') {
                int j = i + dp[i + 1] + 1;
                if (j < s.length() && s.charAt(j) == ')') {
                    dp[i] = dp[i + 1] + 2;
                    if (j + 1 < s.length()) {
                        dp[i] += dp[j + 1];
                    }
                }
            }
             
            maxLen = Math.max(maxLen, dp[i]);
        }
         
        return maxLen;
    }
}

Solution 2: Using a stack

public class Solution {
    public int longestValidParentheses(String s) {
        if (s == null || s.length() < 2) {
            return 0;
        }
         
        Stack<Integer> stack = new Stack<Integer>();
        int max = 0;
        int start = 0;
         
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(i);
            } else {
                if (stack.isEmpty()) {
                    start = i + 1;
                } else {
                    stack.pop();
                    if (stack.isEmpty()) {
                        max = Math.max(max, i - start + 1);
                    } else {
                        max = Math.max(max, i - stack.peek());
                    }
                }
            }
        }
         
        return max;
    }
}

Leetcode: Median of Two Sorted Arrays

There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Understand the problem:
The problem gives two sorted array, A and B. Find out the median of the two sorted arrays.
Note that the time complexity is required to be O(log(m+n)).

An initial thought was firstly merge the two arrays, then median is the number on A.length + B.length - 1 / 2. However, merging will take O(m + n) time, which however the algorithm asks for a solution in log time. So it is naturally to think about the binary search.

One thing must take note is the definition of the median of a sorted array. Note that the return number is double in the problem. So if the array length is even, e.g. 1, 2, 3, 4. The median is the average of 2 and 3, i.e., 2 + 3 / 2 = 2.5

Solution:
http://fisherlei.blogspot.com/2012/12/leetcode-median-of-two-sorted-arrays.html
http://www.lifeincode.net/programming/leetcode-median-of-two-sorted-arrays-java/

The problem is equivalent to find the kth element in the two sorted array. The key is to decide how to eliminate part of the array each recursion.

Code (Java):

public class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1 == null || nums2 == null) {
            return 0.f;
        }
         
        int n1 = nums1.length;
        int n2 = nums2.length;
         
        if ((n1 + n2) % 2 == 1) {
            return findMedianHelper(nums1, nums2, (n1 + n2) / 2 + 1);
        } else {
            return (findMedianHelper(nums1, nums2, (n1 + n2) / 2) + 
                    findMedianHelper(nums1, nums2, (n1 + n2) / 2 + 1)) / 2;
        }
    }
     
    private double findMedianHelper(int[] nums1, int[] nums2, int k) {
        if (nums1 == null || nums1.length == 0) {
            return nums2[k - 1];
        }
         
        if (nums2 == null || nums2.length == 0) {
            return nums1[k - 1];
        }
         
        if (k == 1) {
            return Math.min(nums1[0], nums2[0]);
        }
         
        int n1 = nums1.length;
        int n2 = nums2.length;
         
        if (nums1[n1 / 2] > nums2[n2 / 2]) {
            if ((n1 / 2 + n2 / 2 + 1) >= k) {
                return findMedianHelper(Arrays.copyOfRange(nums1, 0, n1 / 2), nums2, k);
            } else {
                return findMedianHelper(nums1, Arrays.copyOfRange(nums2, n2 / 2 + 1, n2), 
                                        k - (n2 / 2 + 1));
            }
        } else {
            if ((n1 / 2 + n2 / 2 + 1) >= k) {
                return findMedianHelper(nums1, Arrays.copyOfRange(nums2, 0, n2 / 2), k);
            } else {
                return findMedianHelper(Arrays.copyOfRange(nums1, n1 / 2 + 1, n1), 
                                        nums2, k - (n1 / 2 + 1));
            }
        }
    }
}<b>
<span style="font-family: "arial" , "helvetica" , sans-serif;">Edit on 4/27/20:</span></b>

public class Solution {
    /*
     * @param A: An integer array
     * @param B: An integer array
     * @return: a double whose format is *.5 or *.0
     */
    public double findMedianSortedArrays(int[] A, int[] B) {
        // write your code here
        int n = A.length + B.length;
         
        if (n % 2 == 1) {
            return findMedianSortedArraysHelper(A, 0, B, 0, n / 2 + 1);
        } else {
            return ((double) findMedianSortedArraysHelper(A, 0, B, 0, n / 2) + 
                findMedianSortedArraysHelper(A, 0, B, 0, n / 2 + 1)) / 2;
        }
    }
     
    private int findMedianSortedArraysHelper(int[] A, int startOfA, int[] B, int startOfB, int k) {
        if (startOfA >= A.length) {
            return B[startOfB + k - 1];
        }
         
        if (startOfB >= B.length) {
            return A[startOfA + k - 1];
        }
         
        if (k == 1) {
            return Math.min(A[startOfA], B[startOfB]);
        }
         
        int halfOfA = startOfA + k / 2 - 1 >= A.length ? 
            Integer.MAX_VALUE : A[startOfA + k / 2 - 1];
        int halfOfB = startOfB + k / 2 - 1 >= B.length ?
            Integer.MAX_VALUE : B[startOfB + k / 2 - 1];
             
        if (halfOfA < halfOfB) {
            return findMedianSortedArraysHelper(A, startOfA + k / 2, B, startOfB, k - k / 2);
        } else {
            return findMedianSortedArraysHelper(A, startOfA, B, startOfB + k / 2, k - k / 2);
        }
    }
}

The complexity is log(k), where k is the kth elements after merged of the two arrays. For this particular problem, the k = (n + m) / 2.

So why the complexity is logk? It's because for each time we can eliminate k/2 data in O(1) time. So overall the complexity is logk.

Leetcode: Insertion Sort List

Sort a linked list using insertion sort.
Understand the problem:
The crux of the problem is to understand what is the insertion sort. Basically, the idea of the insertion sort is for a partially sorted list, say, A[] = {1 3 4 5}, and we wanna insert 2 to the list at an appropriate position. In general, the idea of the insertion sort is for a given point i, we wanna make sure its left noes are well sorted. How to achieve this? compare A[i] with A[i -1], if less, swap.

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 insertionSortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
         
        ListNode newHead = new ListNode(Integer.MIN_VALUE);
        ListNode prev = newHead;
        ListNode curr = head;
         
        while (curr != null) {
            prev = newHead;
            ListNode next = curr.next;
             
            while (prev.next != null && prev.next.val < curr.val) {
                prev = prev.next;
            }
             
            curr.next = prev.next;
            prev.next = curr;
             
            curr = next;
        }
         
        return newHead.next;
    }
 
}

Leetcode: Sort List

Sort a linked list in O(n log n) time using constant space complexity.
Understand the problem:
The problem is very straight-forward. The only requirement is O(n logn) time complexity, so it indicates to use quick sort or merge sort.

In this question we choose the merge sort because quick sort requires many swap operations, which are relatively complicated in the linked list structure.

Solution:

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
         
        // find the middle point
        ListNode slow = head;
        ListNode fast = head;
         
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
         
        ListNode leftHead = head;
        ListNode rightHead = slow.next;
         
        slow.next = null;
         
        // recursively merge
        leftHead = sortList(leftHead);
        rightHead = sortList(rightHead);
         
        ListNode mergeHead = merge(leftHead, rightHead);
         
        return mergeHead;
    }
     
    private ListNode merge(ListNode leftHead, ListNode rightHead) {
        ListNode newHead = new ListNode(0);
        ListNode curr = newHead;
         
        while (leftHead != null || rightHead != null) {
            if (leftHead == null) {
                curr.next = rightHead;
                break;
            }
             
            if (rightHead == null) {
                curr.next = leftHead;
                break;
            }
             
            if (leftHead.val <= rightHead.val) {
                curr.next = leftHead;
                leftHead = leftHead.next;
                curr = curr.next;
            } else {
                curr.next = rightHead;
                rightHead = rightHead.next;
                curr = curr.next;
            }
        }
         
        return newHead.next;
    }
}

Summary:
The take-away message for this problem is to be very familiar with common sorting algorithms.

Wednesday, September 24, 2014

Leetcode: Copy List with Random Pointer

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

Understand the problem:
The crux to understand the problem is the deep copy of the list. If the linked list has only next reference, copying could be quite straight-forward. However, with the existence of random pointer, the new copied linked list has no idea where it should point to, because the node pointed by the random pointer at the old linked list is not the same reference in the new linked list.

Solution:
One straight-forward solution to address this problem is to use a hashed map. The key and value is the old and new node in the linked list. So for the random pointer points to a old node, we can map it to the new node.

/**
 * Definition for singly-linked list with a random pointer.
 * class RandomListNode {
 *     int label;
 *     RandomListNode next, random;
 *     RandomListNode(int x) { this.label = x; }
 * };
 */
public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        if (head == null) {
            return null;
        }
         
        HashMap<RandomListNode, RandomListNode> hashMap = new HashMap<RandomListNode, RandomListNode>();
         
        RandomListNode p = head;
        RandomListNode newHead = new RandomListNode(head.label);
        RandomListNode q = newHead;
         
        hashMap.put(head, newHead);
        p = p.next;
         
        while (p != null) {
            RandomListNode temp = new RandomListNode(p.label);
            q.next = temp;
            q = temp;
            hashMap.put(p, q);
             
            p = p.next;
        }
         
        p = head;
        q = newHead;
         
        while (p != null) {
            if (p.random != null) {
                q.random = hashMap.get(p.random);
            } else {
                q.random = null;
            }
            p = p.next;
            q = q.next;
        }
         
        return newHead;
    }
}

Discussion:
The solution above has time complexity of O(n) since we iterate the linked twice. It has the space complexity O(n) as well since we used a hash map to store the relations between old and new node.

A better approach:
We can solve the problem with only O(1) space complexity. The solution has three steps.
1. copy the node and insert new nodes into the old node.
2. copy the new random pointer
3. break down the linked list and recover the old linked list

Code (Java):

/**
 * Definition for singly-linked list with a random pointer.
 * class RandomListNode {
 *     int label;
 *     RandomListNode next, random;
 *     RandomListNode(int x) { this.label = x; }
 * };
 */
public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        if (head == null) {
            return null;
        }
         
        // step 1: copy node and insert behind
        RandomListNode p = head;
        while (p != null) {
            RandomListNode copy = new RandomListNode(p.label);
            RandomListNode nextNode = p.next;
            p.next = copy;
            copy.next = nextNode;
            p = nextNode;
        }
         
        // step 2: copy random pointers
        p = head;
        while (p != null) {
            RandomListNode nextNode = p.next.next;
            if (p.random != null) {
                p.next.random = p.random.next;
            } else {
                p.next.random = null;
            }
             
            p = nextNode;
        }
         
        // step 3: break down the linked list and recover the original and new linked list
        p = head;
        RandomListNode newHead = p.next;
         
        while (p != null) {
            RandomListNode q = p.next;
            p.next = q.next;
            if (q.next != null) {
                q.next = p.next.next;
            }
             
            p = p.next;
        }
         
        return newHead;
         
    }
}

Leetcode: Gas Station

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.

Return the starting gas station's index if you can travel around the circuit once, otherwise return -1.

Note:
The solution is guaranteed to be unique.

Understand the problem:
For the car can go from station i to station i + 1, it should be guaranteed that remain + gas[i] >= cost[i]. So the most straight-forward solution is to try to start from each station. We can imagine that the solution would have O(n^2) complexity.

A better approach:
Since we know that the solution is guaranteed to be unique. If we found we cannot make it to the next station, we start from next station. Then we can solve this problem in linear time.

Code (Java):

public class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        if (gas == null || gas.length == 0 || cost == null || cost.length == 0) {
            return -1;
        }
         
        int sum = 0;
        int total = 0;
        int startIdx = 0;
         
        for (int i = 0; i < gas.length; i++) {
            sum += (gas[i] - cost[i]);
            total += (gas[i] - cost[i]);
             
            if (sum < 0) {
                sum = 0;
                startIdx = i + 1;
            }
        }
         
        return total >= 0 ? startIdx % gas.length : -1;
    }
}

Leetcode: 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?

Understand the problem:
This is a assigning candy problem. There are basically two requirements. First of all, each child must have at least one candy. Secondly, children with a higher rating get more candies than their lower rating neighbor. We can take several examples to show this problem.
For 1 2 3 3 3
1 2 3 1 1 , so sum = 8

For 1 2 3 2 3
1 2 3 1 2 so sum = 9

Note that we cannot sort the array, since we must maintain the neighbor relationships between each child. So we can naturally think of using DP to solve this problem.

A DP Solution:

Define a DP array, dp[N], where as dp[i] means number of candies for child i.
Transit function: rank[i] > rank[i - 1], dp[i] = dp[i - 1] + 1. If rank[i] == rank[i - 1], dp[i] = 1. If rank[i] < rank[i -1], it is hard to make a decision since if dp[i - 1] = 1, we cannot let child[i] have 0 candy. So we must go back to plus 1 for all its previous visited children until meet the requirements again.

So we can see that it is actually very complicated using this way. At worst case where the array in sorted in descending order, we need to update all its previous visited children. So the time complexity is O(n^2) in the worst case.

A better solution:

public class Solution {
    public int candy(int[] ratings) {
        if (ratings == null || ratings.length == 0) {
            return 0;
        }
         
        int[] candy = new int[ratings.length];
        Arrays.fill(candy, 1);
         
        for (int i = 1; i < ratings.length; i++) {
            if (ratings[i] > ratings[i - 1]) {
                candy[i] = candy[i - 1] + 1;
            }
        }
         
        for (int i = ratings.length - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                candy[i] = Math.max(candy[i], candy[i + 1] + 1);
            }
        }
         
        int sum = 0;
        for (int i = 0; i < ratings.length; i++) {
            sum += candy[i];
        }
         
        return sum;
    }
}

Leetcode: Sum Root to Leaf Numbers

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

For example,

    1
   / \
  2   3

The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.

Return the sum = 12 + 13 = 25.

Understand the problem:
The problem asks for the sum of all root-to-leaf numbers. The problem itself is not hard to understand. Use DFS is the natural way. The only thing to note is the overflow problem, so we may use a long long to store the intermediate results.

Solution:

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    long pathSum = 0;
    public int sumNumbers(TreeNode root) {
 
        sumNumbersHelper(root, 0);
         
        return (int)pathSum;
    }
     
    private void sumNumbersHelper(TreeNode root, long curSum) {
        if (root == null) {
            return;
        }
         
        curSum = curSum * 10 + root.val;
         
        if (root.left == null && root.right == null) {
            pathSum += curSum;
        }
 
        sumNumbersHelper(root.left, curSum);
        sumNumbersHelper(root.right, curSum);
    }
}

Update on 10/8/14:

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int sumNumbers(TreeNode root) {
 
        return sumNumbersHelper(root, 0);
    }
     
    private int sumNumbersHelper(TreeNode root, int preSum) {
        if (root == null) {
            return 0;
        }
         
        int curSum = root.val + preSum * 10;
         
        if (root.left == null && root.right == null) {
            return curSum;
        }
         
        return sumNumbersHelper(root.left, curSum) + sumNumbersHelper(root.right, curSum);
    }
}

Leetocde: Best Time to Buy and Sell Stock III

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Understand the problem:
The problem is an extension to the previous question. The mainly difference is you can complete two transactions at most. So the logic is like:

0 transactions
1 transactions: buy -> sell
2 transactions: buy -> sell -> buy -> sell

Naive Solution:
We can divide the array into two halves, and calculate the maximal profit with only one transaction at each half. So the overall time complexity would be O(n^2).

DP Solution:
We can define two DP arrays. The first DP array, called left[n] denotes the maximal profit from 0 to i, where as the second DP array, called right[n] denotes the maximal profits from n -1 to i. So the maximal profit is to add them up.

Code (Java):

public class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
         
        int[] left = new int[prices.length];
        int[] right = new int[prices.length];
         
        process(prices, left, right);
         
        int maxProfit = 0;
        for (int i = 0; i < prices.length; i++) {
            maxProfit = Math.max(maxProfit, left[i] + right[i]);
        }
         
        return maxProfit;
    }
     
    private void process(int[] prices, int[] left, int[] right) {
        // find out the maximal profit from 0 to i
        int min = prices[0];
        for (int i = 1; i < prices.length; i++) {
            left[i] = Math.max(left[i - 1], prices[i] - min);
             
            min = Math.min(min, prices[i]);
        }
         
        // Find out the maximal profit from n - 1 to i
        int max = prices[prices.length -1];
        for (int i = prices.length - 2; i >= 0; i--) {
            right[i] = Math.max(right[i + 1], max - prices[i]);
             
            max = Math.max(max, prices[i]);
        }
    }
}

Updates on 10/13/14:
Since the question asks for at most two transactions. For day i, we can get the maximal profit from [0, i], and the maximal profit from [i, end]. Finding the maximal profit from day [0, i] is relative easier to understand. Use a dp_left[i] stands for maximal profit from day 0 to day i. Getting the best profit from profit from day [i, end] is a bit trickier. If we still scan in forward order, for each element i, we need to scan all its following elements, so the complexity would be O(n ^ 2). If we scan from end in backward order, we need to only scan the array once. Then the maximal profit is the maximal sum of the two arrays given a day.

Leetcode: Best Time to Buy and Sell Stock II

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Understand the problem:
This is an extension of the problem I. This mainly difference is you can buy and sell as many times as you want, but you need to sell the current stock before you buy again, i.e, each time you can only hold at most one stock.

So the process is like: buy -> sell -> buy -> sell, etc...

Solution:
We can apply the greedy algorithm, i.e, the local maximal profit will result in the global maximal profit. The basic idea is to seek out a local ascending series. Buy at the lowest point and sell at the highest point, (the next point will go down). Be careful about the last profit where there are only ascending points.

Code (Java):

public class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
         
        int maxProfit = 0;
        int minBuy = 0;
         
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] < prices[i - 1]) {
                maxProfit += prices[i - 1] - prices[minBuy];
                minBuy = i;
            }
        }
         
        if (prices[minBuy] < prices[prices.length - 1]) {
            maxProfit += prices[prices.length - 1] - prices[minBuy];
        }
         
        return maxProfit;
    }
}

A DP Solution:
Since this problem asks for the maximal profit, we may also consider the DP solution.

Define a DP array, dp[n], where dp[i] means the maximal profit at day i
Initial state: dp[0] = 0 means we buy and sell at the first day
Transit function. dp[i] = dp[i - 1] + prices[i] - prices[i - 1], where prices[i] > prices[i - 1], dp[i] = dp[i - 1], where prices[i] <= prices[i - 1]

Final state: Check dp[n]

Code (java):

public class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
         
        int[] dp = new int[prices.length];
         
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i - 1]) {
                dp[i] = dp[i - 1] + prices[i] - prices[i - 1];
            } else {
                dp[i] = dp[i - 1];
            }
        }
         
        return dp[prices.length - 1];
    }
}

Leetcode: Best Time to Buy and Sell Stock

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Understand the problem:

The problem means that you can buy and stock at some day and sell it another day, and make the profit maximal. If you cannot make a profit, you can also not buy at all. Note that you are able to buy/sell at most once.

The basic idea for this question is to maintain the maximal profit, which is the difference of sell and buy prices. One way is to maintain a minimum buy price and compare the current price with that, compute the profit and update the maximal profit.

Code (Java):

public class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
         
        int minIn = prices[0];
        int maxProfit = 0;
         
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] - minIn > maxProfit) {
                maxProfit = prices[i] - minIn;
            }
             
            if (prices[i] < minIn) {
                minIn = prices[i];
            }
        }
         
        return maxProfit;
    }
}

Summary:
The take-away message for such kind of application problems is to understand the problem first, then generalize a "model" that can solve the problem.

Tuesday, September 23, 2014

Leetcode: Distinct Subsequences

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.

Understand the problem:
The problem gives two strings, S and T, count the number of distinct subsequences of T in S. The problem is a bit of ambiguous. It actually asks that how many distinct subsequences of S which is equal to T.

Be aware of subsequence and substring. A subsequence of a string is a subset of the string but couldn't disturb the relative positions of the original characters. The main difference between a substring and subsequence is substring must include continuous characters of the original string, whereas subsequence does not need to be, just maintain the relative order of the selected characters.

DP Solution:
This is a classic DP problem, so we can think of solving this problem using the DP approach.

Define a DP matrix, dp[S.length() + 1][T.length() + 1], whereas dp[i][j] means the number of distinct subsequences from string S[0, i] to string T[0, j].
Initial state: dp[0][0] = 1, dp[0][j] = 0, dp[i][0] = 1
Transit function: For S.charAt(i) == T.charAt(j), dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1]. For different, dp[i][j] = dp[i - 1][j]
Final state: dp[S.length()][T.length()]

# r a b b i t

# 1 0 0 0 0 0 0

r 1 1 0 0 0 0 0

a 1 1 1 0 0 0 0

b 1 1 1 1 0 0 0

b 1 1 1 2 1 0 0

b 1 1 1 3 3 0 0

i 1 1 1 3 3 3 0

t 1 1 1 3 3 3 3

Code (Java):

public class Solution {
    public int numDistinct(String S, String T) {
        if (S == null || S.length() == 0 || T == null) {
            return 0;
        }
         
        int[][] dp = new int[S.length() + 1][T.length() + 1];
        dp[0][0] = 1;
         
        for (int i = 1; i <= S.length(); i++) {
            dp[i][0] = 1;
        }
         
        for (int i = 1; i <= S.length(); i++) {
            for (int j = 1; j <= T.length(); j++) {
                if (S.charAt(i - 1) == T.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
         
        return dp[S.length()][T.length()];
         
    }
}

Summary:
For DP related problems, it is crucial to figure out how to define the dp matrix and the transit function.

Update on 4/10/19:

public class Solution {
    /**
     * @param S: A string
     * @param T: A string
     * @return: Count the number of distinct subsequences
     */
    public int numDistinct(String S, String T) {
        if (T == null || T.length() == 0) {
            return 1;
        }
         
        int[] dp = new int[T.length() + 1];
        dp[0] = 1;
         
        for (int i = 1; i <= S.length(); i++) {
            dp[0] = 1;
            for (int j = T.length(); j >= 1; j--) {
                if (S.charAt(i - 1) == T.charAt(j - 1)) {
                    dp[j] = dp[j - 1] + dp[j];
                } 
            }
        }
         
        return dp[T.length()];
    }
}

Leetcode: Populating Next Right Pointers in Each Node II

Follow up for problem "Populating Next Right Pointers in Each Node".

What if the given tree could be any binary tree? Would your previous solution still work?

Note:

You may only use constant extra space.

For example,
Given the following binary tree,

After calling your function, the tree should look like:

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \    \
    4-> 5 -> 7 -> NULL

Understand the problem:
This is a follow-up problem of the problem 1. The mainly difference is now the tree is not perfect binary tree any more. Note that you are still required to use constant extra space.
So if space is not a problem, we may still use a queue to do a BFS.

Solution:
Since now each node may not have its left or right child, the previous approach may not work. The key of the solution is to find a valid next node.

Code (Java):

/**
 * Definition for binary tree with next pointer.
 * public class TreeLinkNode {
 *     int val;
 *     TreeLinkNode left, right, next;
 *     TreeLinkNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void connect(TreeLinkNode root) {
        if (root == null) {
            return;
        }
         
        if (root.left != null && root.right != null) {
            root.left.next = root.right;
        }
         
        TreeLinkNode p = root;
         
        while (p.next != null && p.next.left == null && p.next.right == null) {
            p = p.next;
        }
         
         
        if (root.right != null && p.next != null) {
            if (p.next.left != null) {
                root.right.next = p.next.left;
            } else if (p.next.right != null){
                root.right.next = p.next.right;
            }
        } else if (root.left != null && p.next != null) {
            if (p.next.left != null) {
                root.left.next = p.next.left;
            } else if (p.next.right != null) {
                root.left.next = p.next.right;
            }
        }
         
        connect(root.right);
        connect(root.left);
    }
}

Discussion:
The only tricks here is to go to its right child first then its left right, i.e, connect right pointers at each level backward. That is because we wanna find the first valid node. We can use an example to illustrate this. If we go to the left child before right one,

Input:	{2,1,3,0,7,9,1,2,#,1,0,#,#,8,8,#,#,#,#,7}
Output:	{2,#,1,3,#,0,7,9,1,#,2,1,0,#,7,#}
Expected:	{2,#,1,3,#,0,7,9,1,#,2,1,0,8,8,#,7,#}

Why? That is because when we are at Node 7, we figure out the p pointer points to node 9. However, since now 9 is not connected to 1 yet, so node 7's right child, 0 cannot point to node 1's left child, which is 8. That is why we must traverse the right node first to make 9 connects to 1 before we check the node 7.

Update on 9/18/15:

/**
 * Definition for binary tree with next pointer.
 * public class TreeLinkNode {
 *     int val;
 *     TreeLinkNode left, right, next;
 *     TreeLinkNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void connect(TreeLinkNode root) {
        if (root == null) {
            return;
        }
         
        if (root.left != null && root.right != null) {
            root.left.next = root.right;
        }
         
        if (root.next != null) {
            TreeLinkNode p = root;
            while (p.next != null && p.next.left == null && p.next.right == null) {
                p = p.next;
            }
             
            if (p.next != null) {
                p = p.next;
            }
             
            if (root.right != null) {
                if (p.left != null) {
                    root.right.next = p.left;
                } else if (p.right != null) {
                    root.right.next = p.right;
                }
            } else if (root.left != null) {
                if (p.left != null) {
                    root.left.next = p.left;
                } else if (p.right != null) {
                    root.left.next = p.right;
                }
            }
        }
         
        connect(root.right);
        connect(root.left);
    }
}

Update on 2/8/16:
Constant space solution:

/**
 * Definition for binary tree with next pointer.
 * public class TreeLinkNode {
 *     int val;
 *     TreeLinkNode left, right, next;
 *     TreeLinkNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void connect(TreeLinkNode root) {
        if (root == null) {
            return;
        }
         
        TreeLinkNode curr = root;
        TreeLinkNode dummyNode = new TreeLinkNode(0);
        TreeLinkNode pre = dummyNode;
         
        while (curr != null) {
            TreeLinkNode p = curr;
            while (p != null) {
                if (p.left != null) {
                    pre.next = p.left;
                    pre = pre.next;
                }
                 
                if (p.right != null) {
                    pre.next = p.right;
                    pre = pre.next;
                }
                 
                p = p.next;
                 
                if (p == null) {
                    curr = dummyNode.next;
                    pre = dummyNode;
                    dummyNode.next = null;
                }
            }
        }
         
    }
}