Thursday, May 21, 2015

[LeetCode] Minimum Size Subarray Sum

Minimum Size Subarray Sum

Given an array of n positive integers and a positive integer s, find the minimal length of a subarray of which the sum ≥ s. If there isn't one, return 0 instead.
For example, given the array [2,3,1,2,4,3] and s = 7,
the subarray [4,3] has the minimal length under the problem constraint.
click to show more practice.
More practice:
If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).
Naive solutions:
1). The most naive solution will take O(n^3) time using constant space, since there are O(n^2) subarrays nums[i...j] (inclusive), and computing the sum for each subarray takes O(j - i + 1) time.
2). An optimized solution (compared with the above one) takes O(n^2) time using constant space. We divide O(n^2) subarrays into n groups by their lengths. For each group, we can compute all the sums in O(n) time by removing the first element in the previous sum and adding a new element in the end.
3). Alternatively, we can first compute all the prefix sums, where prefixSum[i] denotes the sum of the first i integers, i >= 0. Under this notation, the index for the prefixSum array ranges from 0 to n. Then we can simply iterative over all O(n^2) pairs, and the sum of all the elements in the subarray nums[i...j]  (inclusive) is simply prefixSum[j] - prefixSum[i - 1]. This takes O(n^2) time and extra O(n) space.
Below are more interesting and elegant solutions.
Solution 1: O(n) running time, and extra O(n) space.
We first compute all the prefix sums, where prefixSum[i] denotes the sum of the first i integers, i >= 0. Under this notation, the index for the prefixSum array ranges from 0 to n.
Next, we move two pointers i and j. For each i, we find the minimum length of a subarray starting from i + 1 (inclusive) of which the sum >= s. The key observation is that j is non-decreasing, which implies an algorithm with O(n) running time.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
public class Solution {
    private int buildPrefixSum(int[] nums, int[] prefixSum) {
        prefixSum[0] = 0;
        for (int i = 0; i < nums.length; i++) {
            prefixSum[i + 1] = prefixSum[i] + nums[i];
        }
        return prefixSum[nums.length];
    }
    
    private int twoPointerIncrementalSearch(
        int s, 
        int[] prefixSum
    ) {
        int minLen = prefixSum.length - 1;
        int i = 0;
        int j = 1;
        while (
            i < prefixSum.length - 1 
            && j < prefixSum.length
        ) {
            if (prefixSum[j] - prefixSum[i] < s) {
                j++;
            } else {
                if (minLen > j - i) {
                    minLen = j - i;
                } 
                i++;
            }
        }
        return minLen;
    }
    
    public int minSubArrayLen(int s, int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        
        int[] prefixSum = new int[nums.length + 1];
        int totalSum = buildPrefixSum(nums, prefixSum);
        if (totalSum < s) {
            return 0;
        }
        
        return twoPointerIncrementalSearch(s, prefixSum);
    }
}

Solution 2: O(n) running time, and constant space.
For each i, we find the minimum length of a subarray starting from i (inclusive) of which the sum >= s. The key observation is that we can update the current sum of all the elements in the subarray nums[i ... j] (inclusive) in constant time each step, and furthermore, j is non-decreasing, which implies an algorithm with O(n) running time.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public class Solution {
   public int minSubArrayLen(int s, int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        
        int totalSum = 0;
        for (int num : nums) {
            totalSum += num;
        }
        if (totalSum < s) {
            return 0;
        }
        
        int i = 0;
        int j = 0;
        int currSum = nums[0];
        int minLen = nums.length;
        while (i < nums.length) {
            if (currSum >= s) {
                if (minLen > j - i + 1) {
                    minLen = j - i + 1;
                }
                currSum -= nums[i];
                i++;
            } else {
                j++;
                if (j >= nums.length) {
                    break;
                }
                currSum += nums[j];
            }
        }
        return minLen;
    }
}

Solution 3: O(n log n) running time, and extra O(n) space.
We first compute all the prefix sums, where prefixSum[i] denotes the sum of the first i integers, i >= 0. Under this notation, the index for the prefixSum array ranges from 0 to n.
Next, for each index i, we find the minimum length of a subarray starting from i + 1 (inclusive) of which the sum >= s, using binary search. Hence, the overall running time is O(n log n). 
Remarks: A slight improvement in terms of performance will be narrowing down the range of the binary search even further. Instead of searching from i to end, one can search from j to end, where j > i. One needs to change the following binarySearch() function signature to incorporate this improvement.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
public class Solution {
    private int buildPrefixSum(int[] nums, int[] prefixSum) {
        prefixSum[0] = 0;
        for (int i = 0; i < nums.length; i++) {
            prefixSum[i + 1] = prefixSum[i] + nums[i];
        }
        return prefixSum[nums.length];
    }
    
    private int binarySearch(int i, int s, int[] prefixSum) {
        int low = i;
        int high = prefixSum.length - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (prefixSum[mid] - prefixSum[i] < s) {
                low = mid + 1;
            } else {
                if (
                    mid > 0 && 
                    prefixSum[mid - 1] - prefixSum[i] < s
                ) {
                    return mid - i;
                }
                high = mid - 1;
            }
        }
        return prefixSum.length;
    }
    
    public int minSubArrayLen(int s, int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        
        int[] prefixSum = new int[nums.length + 1];
        int totalSum = buildPrefixSum(nums, prefixSum);
        if (totalSum < s) {
            return 0;
        }
        
        int minLen = prefixSum.length - 1;
        for (int i = 0; i < prefixSum.length; i++) {
            int len = binarySearch(i, s, prefixSum);
            if (minLen > len) {
                minLen = len;
            }
        }
        return minLen;
    }
}
Posted by at No comments:

Tuesday, May 19, 2015

[LeetCode] Linked List Cycle II

Linked List Cycle II

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
Follow up:
Can you solve it without using extra space?
Solution 1: Hash, linear running time with extra linear space.
Since here we only need to determine whether an element exists, HashSet is preferable. The advantage of this approach is its simplicity, while it uses extra linear space.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * Definition for singly-linked list
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        HashSet<ListNode> set = new HashSet<ListNode>();
        ListNode p = head;
        
        while (p != null) {
            if (set.contains(p)) {
                return p;
            } 
            set.add(p);
            p = p.next;
        }
        
        return null;
    }
}
Solution 2: Two pointers, quadratic running time in the worst case.
In this solution, we first decide whether it has a cycle by using two pointers, the slower pointer, which moves one step at a time, and the faster pointer, which moves two steps at a time. If there is a cycle, these two pointers will collide inside the cycle.
Next, we use two new pointers: one pointer will move from the head to the beginning of the cycle, and the second pointer will simply move along the cycle from the collision point. The beginning of the cycle will be the first node such that when the second pointer moves along the cycle, it will collide with the beginning of the cycle.
Assuming the length of the cycle is L, the running time will be L(n - L), where n is the total length of the list. That is, it has quadratic running time in the worst case.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;

        do {
            if (fast == null || fast.next == null) {
                return null;
            }
            slow = slow.next;
            fast = fast.next.next;
        } while (slow != fast);
    
        ListNode collision = fast;        
        ListNode p = head;
        
        while (p != null) {
            ListNode q = collision;
            do {
                if (q == p) {
                    return p;
                }
                q = q.next;
            } while (q != collision);
            p = p.next;
        }
        
        return null;
    }
}
Solution 3: Two pointers, linear running time.
This is the optimal solution. However, it is not as obvious as the above ones.
The key observation is that we move two pointers at a pace of 1 step and 2 steps, called as the slower pointer and the faster pointer, respectively, then the first collision point of these two pointers, if it exists, has the "same" distance as the head node to the beginning of the cycle.
To see this, assume that the length of the list outside (resp. inside) the cycle is k (resp. L). Then when the slower pointer arrives at the beginning of the cycle, it has marched k steps, while the faster pointer has marched 2k steps. The latter implies that the faster pointer is k % L steps ahead of the slower pointer (and ahead of the beginning of the cycle as well). In other words, the slower pointer is (L - k % L) steps ahead of the faster pointer. Note that each time, the faster pointer is one step closer to the slower pointer, so after (L - k % L) times of marching, they will meet, more importantly, they are meeting for the first time, since it is the first time for the slower pointer marching inside the cycle (note that L - k % L <= L). It is easy to see that they first collide at the point that is (L - k % L) steps ahead of the beginning of the cycle (that is where the slower pointer will be, hence the faster one). In other words, the first collision point of the slower pointer and the faster pointer is k % L steps behind the beginning of the cycle.
Now, we use two new pointers, both marching at a pace of 1 step at a time. We march one of them from the head of the list, and the other from the above collision point. We call them the outsideCycle pointer and the insideCycle pointer, respectively. When the outsideCycle pointer first enters the cycle, it has marched k steps, so is the insideCycle pointer. Where will the insideCycle pointer be? Well, initially, the insideCycle pointer lies at the first collision point of the slower pointer and the faster pointer, where the collision point is k % L steps behind the beginning of the cycle. With k more steps marched, the insideCycle pointer will lie exactly at the beginning of the cycle.
Hence, we've found the beginning of the cycle.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * Definition for singly-linked list
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        
        do {
            if (fast == null || fast.next == null) {
                return null;
            }
            slow = slow.next;
            fast = fast.next.next;
        } while (slow != fast);
        
        ListNode outsideCycle = head;
        ListNode insideCycle = fast;
        
        while (outsideCycle != insideCycle) {
            outsideCycle = outsideCycle.next;
            insideCycle = insideCycle.next;
        }
        
        return insideCycle;
    }
}
Posted by at No comments:

Saturday, May 16, 2015

[LeetCode] Course Schedule

Course Schedule

There are a total of n courses you have to take, labeled from 0 to n - 1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?
For example:
2, [[1,0]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.
2, [[1,0],[0,1]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.
Note:
The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
click to show more hints.
Hints:
  1. This problem is equivalent to finding if a cycle exists in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses.
  2. Topological Sort via DFS - A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort.
  3. Topological sort could also be done via BFS.
Solution: We keep track of vertices currently in recursion stack of function for DFS traversal. If a vertex is encountered again, then there is a cycle.
Furthermore, we keep track of nodes that have been the root for DFS traversal, to avoid duplicate testing, and more importantly, infinite loop.

public class Solution {
    ArrayList<ArrayList<Integer>> list;
    
    public boolean DFS(int i, boolean[] visited, boolean[] recStack) {
        visited[i] = true;
        recStack[i] = true;
        for (int j : list.get(i)) {
            if (recStack[j]) {
                return false;
            }
            if (!visited[j] && !DFS(j, visited, recStack)) {
                return false;
            }
        }
        recStack[i] = false;
        return true;
    }
    
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int n = numCourses;
        list = new ArrayList<ArrayList<Integer>>();
        for (int i = 0; i < n; i++) {
            list.add(new ArrayList<Integer>());
        }
        for (int[] pair : prerequisites) {
            list.get(pair[1]).add(pair[0]);
        }
        boolean[] visited = new boolean[n];
        boolean[] recStack = new boolean[n];
        Arrays.fill(visited, false);
        Arrays.fill(recStack, false);
        for (int i = 0; i < n; i++) {
            if (!visited[i] && !DFS(i, visited, recStack)) {
                return false;
            }
        }
        return true;
    }
}
Posted by at No comments:

[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?
Solution: It is easy to derive that (i, j) -> (j, n - 1 - i) -> (n - 1 - i, n - 1 - j) -> (n - 1 - j, i), where the range of i is [0, n/2), while the range of j is [i, n - 1 - i).
Alternatively, one can visualize this layer by layer. We first do this for the out-most layer, where we are rotating n - 1 elements (not n elements) of each of the top-most row, the right-most column, the bottom-most row, and the left-most column. And we conduct this element-wise by only using one extra temporary variable. After this is done, one may view it as a sub-problem of size (n - 1) x (n - 1), which can be solved in a similar manner.
public class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        for (int i = 0; i < n / 2; i++) {
            for (int j = i; j < n - 1 - i; j++) {
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[n - 1 - j][i];
                matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j];
                matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i];
                matrix[j][n - 1 - i] = tmp;
            }
        }
        return;
    }
}
Posted by at No comments:

Sunday, May 3, 2015

[LeetCode] Reverse Linked List II

Reverse Linked List II

Reverse a linked list from position m to n. Do it in-place and in one-pass.
For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,
return 1->4->3->2->5->NULL.
Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.
Solution: Maintain three parts: head to t1, h2 to t2, and h3 to null.
Lines 14 - 22 find t1 and t2.
Lines 23 - 31 find h2 and h3.
Note that if m is 1, then the first part is empty.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode p = head;
        ListNode t1 = null;
        int cnt = 1;
        while (cnt != m) {
            t1 = p;
            p = p.next;
            cnt++;
        }
        ListNode t2 = p;
        ListNode h2 = p;
        ListNode h3 = p.next;
        while (cnt != n) {
            p = h3;
            h3 = h3.next;
            p.next = h2;
            h2 = p;
            cnt++;
        }
        t2.next = h3;
        if (m == 1) {
            return h2;
        } else {
            t1.next = h2;
            return head;
        }
    }
}
Posted by at No comments:

[LeetCode] Jump Game

Jump Game

Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.
For example:
A = [2,3,1,1,4], return true.
A = [3,2,1,0,4], return false.
Solution: Greedy. Maintain the current max reach, and update it as necessary.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
public class Solution {
    public boolean canJump(int[] nums) {
        int maxDist = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i <= maxDist) {
                maxDist = Math.max(i + nums[i], maxDist);
            }
        }
        return (maxDist >= nums.length - 1);
    }
}
Another version. We update a batch this time.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
public class Solution {
    public boolean canJump(int[] nums) {
        if (nums.length <= 1) {
            return true;
        }
        int maxDist = 0;
        int i = 0;
        while (i < nums.length && i <= maxDist) {
            for (int j = i; j <= i + nums[i] && j < nums.length; j++) {
                maxDist = Math.max(maxDist, j + nums[j]);
            }
            i = Math.max(i + nums[i], i + 1);
        }
        return (maxDist >= nums.length - 1);
    }
}
Posted by at No comments:

[LeetCode] Gray Code

Gray Code

The gray code is a binary numeral system where two successive values differ in only one bit.
Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.
For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:
00 - 0
01 - 1
11 - 3
10 - 2
Note:
For a given n, a gray code sequence is not uniquely defined.
For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.
For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.
Solution: The observation is that graycode(n) is a concatenation of the following two sequences:
1. 0 + graycode(n - 1).
2. 1 + graycode(n - 1) (reverse order).  
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
public class Solution {
    public List<Integer> grayCode(int n) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        if (n == 0) {
            list.add(0);
            return list;
        }
        List<Integer> li = grayCode(n - 1);
        list.addAll(li);
        int m = 1 << (n - 1);
        for (int i = li.size() - 1; i >= 0; i--) {
            list.add(m + li.get(i));
        }
        return list;
    }
}
Posted by at No comments:
Subscribe to: Posts (Atom)