Leetcode: Find the Duplicate Number

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Note:

1. You must not modify the array (assume the array is read only).
2. You must use only constant, O(1) extra space.
3. Your runtime complexity should be less than O(n2).
4. There is only one duplicate number in the array, but it could be repeated more than once.

Understand the problem:
The problem was simple if not comes with the constraints. Let's review the constraints. 
1. No change the array -- Otherwise, we could simply use the bucket sorting to put element i to A[i]. 
2. No extra memory -- Otherwise, we could use a hash map to count the freq of each number
3. Runtime complexity less than O(n^2) - Otherwise, we could use the brute-force solution to choose either 2 numbers and see if they are the same.

Solution:
Use binary search. 
http://www.cnblogs.com/grandyang/p/4843654.html

这道题给了我们n+1个数，所有的数都在[1, n]区域内，首先让我们证明必定会有一个重复数，这不禁让我想起了小学华罗庚奥数中的抽屉原理(又叫鸽巢原理), 即如果有十个苹果放到九个抽屉里，如果苹果全在抽屉里，则至少有一个抽屉里有两个苹果，这里就不证明了，直接来做题吧。题目要求我们不能改变原数组，即不能给原数组排序，又不能用多余空间，那么哈希表神马的也就不用考虑了，又说时间小于O(n²)，也就不能用brute force的方法，那我们也就只能考虑用二分搜索法了，我们在区别[1, n]中搜索，首先求出中点mid，然后遍历整个数组，统计所有小于等于mid的数的个数，如果个数大于mid，则说明重复值在[mid+1, n]之间，反之，重复值应在[1, mid-1]之间，然后依次类推，知道搜索完成，此时的low就是我们要求的重复值，参见代码如下：

Code (Java):

public class Solution {
    public int findDuplicate(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        int lo = 1;
        int hi = nums.length - 1;
        
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            int count = countNumbers(nums, mid);
            
            if (count <= mid) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        
        return hi; // Or lo
    }
    
    private int countNumbers(int[] nums, int mid) {
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] <= mid) {
                count++;
            }
        }
        
        return count;
    }
}

Leetocde: Game of Life

ccording to the Wikipedia's article: "The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970."

Given a board with m by n cells, each cell has an initial state live (1) or dead (0). Each cell interacts with its eight neighbors (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article):

1. Any live cell with fewer than two live neighbors dies, as if caused by under-population.
2. Any live cell with two or three live neighbors lives on to the next generation.
3. Any live cell with more than three live neighbors dies, as if by over-population..
4. Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.

Write a function to compute the next state (after one update) of the board given its current state.

Follow up: 

1. Could you solve it in-place? Remember that the board needs to be updated at the same time: You cannot update some cells first and then use their updated values to update other cells.
2. In this question, we represent the board using a 2D array. In principle, the board is infinite, which would cause problems when the active area encroaches the border of the array. How would you address these problems?

Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

Understand the problem:

Since the problem asks for in-place solution. We could mark the 

 -- live-to-dead nodes as 2

 -- dead-to-live nodes as 3

In the second step, mark all 2 as 0 and 3 as 1

Code (Java):

public class Solution {
    public void gameOfLife(int[][] board) {
        if (board == null || board.length == 0) {
            return;
        }
        
        int m = board.length;
        int n = board[0].length;
        
        // If live to dead, mark 2
        // If dead to live, mark 3
        
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int liveNeighbors = getNumLiveNeighbors(i, j, board);
                
                if (board[i][j] == 1) {
                    if (liveNeighbors < 2 || liveNeighbors > 3) {
                        board[i][j] = 2;
                    }
                } else {
                    if (liveNeighbors == 3) {
                        board[i][j] = 3;
                    }
                }
            }
        }
        
        // Step 2: loop-over the board again and mark 2 as 0 and 3 as 1
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 2) {
                    board[i][j] = 0;
                } else if (board[i][j] == 3) {
                    board[i][j] = 1;
                }
            }
        }
    }
    
    private int getNumLiveNeighbors(int row, int col, int[][] board) {
        int result = 0;
        
        int m = board.length;
        int n = board[0].length;
        
        // Up
        if (row - 1 >= 0 && (board[row - 1][col] == 1 || board[row - 1][col] == 2)) {
            result += 1;
        }
        
        // Down
        if (row + 1 < m && (board[row + 1][col] == 1 || board[row + 1][col] == 2)) {
            result += 1;
        }
        
        // Left
        if (col - 1 >= 0 && (board[row][col - 1] == 1 || board[row][col - 1] == 2)) {
            result += 1;
        }
        
        // Right
        if (col + 1 < n && (board[row][col + 1] == 1 || board[row][col + 1] == 2)) {
            result += 1;
        }
        
        // NW
        if (row - 1 >= 0 && col - 1 >= 0 && (board[row - 1][col - 1] == 1 || board[row - 1][col - 1] == 2)) {
            result += 1;
        }
        
        // NE
        if (row - 1 >= 0 && col + 1 < n && (board[row - 1][col + 1] == 1 || board[row - 1][col + 1] == 2)) {
            result += 1;
        }
        
        // SW
        if (row + 1 < m && col - 1 >= 0 && (board[row + 1][col - 1] == 1 || board[row + 1][col - 1] == 2)) {
            result += 1;
        }
        
        // SE
        if (row + 1 < m && col + 1 < n && (board[row + 1][col + 1] == 1 || board[row + 1][col + 1] == 2)) {
            result += 1;
        }
        
        return result;
    }
}

 

Leetcode: Move Zeroes

Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.

For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].

Note:

1. You must do this in-place without making a copy of the array.
2. Minimize the total number of operations.

Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

Understand the problem:
Since the problem requires to maintain the relative order of the array, we cannot simply swap the numbers in the array. 

One simple way is very similar to remove the duplicated numbers in the array. In the first pass, we move all the non-zero elements upfront and fill out all the zero slots. Then we just need to append 0s at the end of the array.

Code (Java):

public class Solution {
    public void moveZeroes(int[] nums) {
        if (nums == null || nums.length == 0) {
            return;
        }
        
        int i = 0;
        int j = 0;
        
        // Step 1: compress the nums array by filling out the 0s
        while (i < nums.length) {
            if (nums[i] != 0) {
                nums[j] = nums[i];
                j++;
                i++;
            } else {
                i++;
            }
        }
        
        // Append 0s to the end
        while (j < nums.length) {
            nums[j] = 0;
            j++;
        }
    }
}

Leetcode: Wiggle Sort

Given an unsorted array nums, reorder it in-place such that nums[0] <= nums[1] >= nums[2] <= nums[3]....

For example, given nums = [3, 5, 2, 1, 6, 4], one possible answer is [1, 6, 2, 5, 3, 4].

Understand the problem:
A[0] <= A[1] >= A[2] <= A[3] >= A[4] <= A[5]
So we could actually observe that there is pattern that
A[even] <= A[odd],
A[odd] >= A[even].

Therefore we could go through the array and check this condition does not hold, just swap.

Code (Java):

public class Solution {
    public void wiggleSort(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return;
        }
        
        for (int i = 0; i < nums.length - 1; i++) {
            if (i % 2 == 0) {
                if (nums[i] > nums[i + 1]) {
                    swap(nums, i, i + 1);
                }
            } else {
                if (nums[i] < nums[i + 1]) {
                    swap(nums, i, i + 1);
                }
            }
        }
    }
    
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

Leetcode: Find the Celebrity

Suppose you are at a party with n people (labeled from 0 to n - 1) and among them, there may exist one celebrity. The definition of a celebrity is that all the other n - 1people know him/her but he/she does not know any of them.

Now you want to find out who the celebrity is or verify that there is not one. The only thing you are allowed to do is to ask questions like: "Hi, A. Do you know B?" to get information of whether A knows B. You need to find out the celebrity (or verify there is not one) by asking as few questions as possible (in the asymptotic sense).

You are given a helper function bool knows(a, b) which tells you whether A knows B. Implement a function int findCelebrity(n), your function should minimize the number of calls to knows.

Note: There will be exactly one celebrity if he/she is in the party. Return the celebrity's label if there is a celebrity in the party. If there is no celebrity, return -1.

Understand the problem:
The problem can be transformed as a graph problem. We count the in-degree and out-degree for each person. Then find out the person with in-degree n - 1 and out-degree 0. 

Code (Java):

/* The knows API is defined in the parent class Relation.
      boolean knows(int a, int b); */

public class Solution extends Relation {
    public int findCelebrity(int n) {
        if (n <= 1) {
            return -1;
        }
        
        int[] inDegree = new int[n];
        int[] outDegree = new int[n];
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i != j && knows(i, j)) {
                    outDegree[i]++;
                    inDegree[j]++;
                }
            }
        }
        
        for (int i = 0; i < n; i++) {
            if (inDegree[i] == n - 1 && outDegree[i] == 0) {
                return i;
            }
        }
        
        return -1;
    }
}

Analysis:
Time O(n^2).
Space O(n).

A O(n) time O(1) Space Solution:
Use two pointers, left starts from 0, and right starts from n - 1.
Check if knows(left, right). If yes, left++. Else, right--.
After the first step, we could find out the potential candidate. 
In the second step, we validate the candidate by iterating through all the person again. Each one must know the candidate while the candidate must not know anyone else. 

Code (Java):

/* The knows API is defined in the parent class Relation.
      boolean knows(int a, int b); */

public class Solution extends Relation {
    public int findCelebrity(int n) {
        if (n <= 1) {
            return -1;
        }
        
        int left = 0;
        int right = n - 1;
        
        // Step 1: Find the potential candidate
        while (left < right) {
            if (knows(left, right)) {
                left++;
            } else {
                right--;
            }
        }
        
        // Step 2: Validate the candidate
        int candidate = right;
        for (int i = 0; i < n; i++) {
            if (i != candidate && (!knows(i, candidate) || knows(candidate, i))) {
                return -1;
            }
        }
        
        return candidate;
    }
}

Leetcode: H-Index II

ollow up for H-Index: What if the citations array is sorted in ascending order? Could you optimize your algorithm?

Hint:

1. Expected runtime complexity is in O(log n) and the input is sorted.

Understand the problem:
Since the problem asks for a O(log n) solution, we can think of using a binary search. 

Code (Java):

public class Solution {
    public int hIndex(int[] citations) {
        if (citations == null || citations.length == 0) {
            return 0;
        }
        
        int lo = 0;
        int hi = citations.length - 1;
        int len = citations.length;
        
        while (lo + 1 < hi) {
            int mid = lo + (hi - lo) / 2;
            
            if (citations[mid] == len - mid) {
                return len - mid;
            } else if (citations[mid] < len - mid) {
                lo = mid;
            } else {
                hi = mid;
            }
        }

        if (citations[lo] >= len - lo) {
            return len - lo;
        }
        
        if (citations[hi] >= len - hi) {
            return len - hi;
        }
        
        return 0;
    }
}

Leetcode: H-Index

Given an array of citations (each citation is a non-negative integer) of a researcher, write a function to compute the researcher's h-index.

According to the definition of h-index on Wikipedia: "A scientist has index h if h of his/her N papers have at least h citations each, and the other N − h papers have no more thanh citations each."

For example, given citations = [3, 0, 6, 1, 5], which means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 citations respectively. Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, his h-index is 3.

Note: If there are several possible values for h, the maximum one is taken as the h-index.

Hint:

1. An easy approach is to sort the array first.
2. What are the possible values of h-index?
3. A faster approach is to use extra space.

Understand the problem:
The key of the problem is to understand the definition of the H-index.
H-index is the number of h papers, in which each paper has at least h citations. 
e.g. If there are 2 papers, and each of the 2 papers has at least 2 citations, the h-index is 2. 

So the naive solution is to sort the array in reverse order, i.e, citations from high to low. 
If citation[i] >= i + 1, continue to next. 
Else, return i. 

There is one corner case is if we cannot stop in the loop iteration, we return the number of papers. 

Code (Java):

public class Solution {
    public int hIndex(int[] citations) {
        if (citations == null || citations.length == 0) {
            return 0;
        }
        
        Arrays.sort(citations);
        // Reverse the array
        int m = 0;
        int n = citations.length - 1;
        while (m < n) {
            swap(citations, m, n);
            m++;
            n--;
        }
        
        int len = citations.length;
        
        int i = 0;
        for (i = 0; i < len; i++) {
            if (i + 1 > citations[i]) {
                return i;
            }
        }
        
        return i;
    }
    
    private void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
}

A O(n) time solution:
Since the problem requires for a O(n) time solution, we can consider using the bucket sort. 
The number of buckets is N + 1, in which each bucket holds the number of papers of which the citation is i. Note the last bucket will store the number of papers in which citations is greater or equal to N. 

Code (Java):

public class Solution {
    public int hIndex(int[] citations) {
        if (citations == null || citations.length == 0) {
            return 0;
        }
        
        int n = citations.length;
        int[] buckets = new int[n + 1];
        
        // Step 1: Accmulate the number of citations for each bucket
        for (int i = 0; i < n; i++) {
            if (citations[i] <= n) {
                buckets[citations[i]]++; 
            } else {
                buckets[n]++;
            }
        }
        
        // Step 2: iterate the citations from right to left.
        int numPapers = 0;
        for (int i = n; i >= 0; i--) {
            numPapers += buckets[i];
            if (numPapers >= i) {
                return i;
            }
        }
        
        return 0;
    }
}

Leetcode: Missing Number

Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.

For example,
Given nums = [0, 1, 3] return 2.

Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

Understand the problem:
Since the problem suggests to use O(n) time complexity and constant space complexity, we can easily think of using the idea of bucket sorting. 

For each number, we need to check if i == num[i], if not, we need to swap the number to its corresponding bucket. At last, we iterate the array again and find out the missing number. 

There is one corner case to consider: if the array after the bucketing is [0, 1, 2], then the missing number is 3. That is because we have N numbers ranging from 0 to N, the last bucket stores N - 1. So we need to return nums.length.

Code (Java):

public class Solution {
    public int missingNumber(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        // Step 1: iterate the array and swap according to the buckets
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            if (num != i && num < nums.length && num != nums[num]) {
                swap(nums, i, num);
                i--;
            }
        }
        
        // Step 2: iterate again to find out the missing number
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != i) {
                return i;
            }
        }
        
        return nums.length;
    }
    
    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

Leetcode: Majority Element II

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.

Hint:

1. How many majority elements could it possibly have?
2. Do you have a better hint? Suggest it!

Understand the problem:
Since the problem suggest to use O(1) space solution, we cannot use a hash map to store the visited elements. 

How many elements could it possiblly have? Since the majority number is more than n / 3, the maximal majority elements are 2. 

So we could maintain two candidates and the counters for the candidates, respectively. The rest of the method is the same of the Moore vote algorithm. Note that we need to re-validate again at the end because it is possible that the array does not have any majority elements. 

Code (Java):

public class Solution {
    public List<Integer> majorityElement(int[] nums) {
        List<Integer> result = new ArrayList<Integer>();
        
        if (nums == null || nums.length == 0) {
            return result;
        }
        
        if (nums.length == 1) {
            result.add(nums[0]);
            return result;
        }
        
        int candidate1 = nums[0];
        int candidate2 = 0;
        
        int count1 = 1;
        int count2 = 0;
        
        for (int i = 1; i < nums.length; i++) {
            int num = nums[i];
            if (candidate1 == num) {
                count1++;
            } else if (candidate2 == num) {
                count2++;
            } else if (count1 == 0) {
                candidate1 = num;
                count1 = 1;
            } else if (count2 == 0) {
                candidate2 = num;
                count2 = 1;
            } else {
                count1--;
                count2--;
            }
        }
        
        count1 = 0;
        count2 = 0;
        
        for (int num : nums) {
            if (num == candidate1) {
                count1++;
            } else if (num == candidate2) {
                count2++;
            }
        }
        
        if (count1 > nums.length / 3) {
            result.add(candidate1);
        }
        
        if (count2 > nums.length / 3) {
            result.add(candidate2);
        }
        
        return result;
    }
}

Leetcode: Contains Duplicate II

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the difference between i and j is at most k.

Code (Java):

public class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        if (nums == null || nums.length <= 1 || k <= 0) {
            return false;
        }
        
        Map<Integer, Integer> map = new HashMap<>();
        
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) {
                int preIndex = map.get(nums[i]);
                if (i - preIndex <= k) {
                    return true;
                } else {
                    map.put(nums[i], i);
                }
            } else {
                map.put(nums[i], i);
            }
        }
        
        return false;
    }
}

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Set<Integer> hashSet = new HashSet<>();
        
        for (int i = 0; i < nums.length; i++) {
            if (hashSet.contains(nums[i])) {
                return true;
            }
            
            hashSet.add(nums[i]);
            
            if (hashSet.size() > k) {
                hashSet.remove(nums[i - k]);
            }
        }
        
        return false;
    }
}

Leetcode: Contains Duplicate

Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

Understand the problem:
Use a hash set.

Code (Java):

public class Solution {
    public boolean containsDuplicate(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return false;
        }
        
        Set<Integer> set = new HashSet<Integer>();
        
        for (int num : nums) {
            if (set.contains(num)) {
                return true;
            } else {
                set.add(num);
            }
        }
        
        return false;
    }
}

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

Credits:
Special thanks to @Freezen for adding this problem and creating all test cases.

Understand the problem:
Since the array elements are all positive numbers, we could use a sliding window approach. W first move the front pointer until the sum of the subarray is greater or equal to the target value s, then we calculate the size of the window. Then we try to move the rear pointer and recalculate the window size, until the sum of the window is less than the target s. 

Code (Java):

public class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        if (s <= 0 || nums == null || nums.length == 0) {
            return 0;
        }
        
        int lo = 0;
        int hi = 0;
        int sum = 0;
        int minLen = Integer.MAX_VALUE;
        
        while (hi < nums.length) {
            // Moves the hi pointer
            while (hi < nums.length && sum < s) {
                sum += nums[hi];
                hi++;
            }
            
            // Move the lo pointer
            while (lo <= hi && sum >= s) {
                minLen = Math.min(minLen, hi - lo);
                sum -= nums[lo];
                lo++;
            }
        }
        if (minLen == Integer.MAX_VALUE) {
            return 0;
        } else {
            return minLen;
        }
    }
}

Leetcode: Rotate Array

Rotate an array of n elements to the right by k steps.

For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].

Note:
Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.

Code (Java):

public class Solution {
    public void rotate(int[] nums, int k) {
        if (nums == null || nums.length <= 1 || k <= 0) {
            return;
        }
        
        // Step 1: swap each element of the array
        int i = 0;
        int j = nums.length - 1;
        while (i < j) {
            swap(nums, i, j);
            i++;
            j--;
        }
        
        k %= nums.length; 
        
        // Step 2: swap the first k elements
        i = 0;
        j = k - 1;
        while (i < j) {
            swap(nums, i, j);
            i++;
            j--;
        }
        
        // Step 3: swap the rest of k elements
        i = k;
        j = nums.length - 1;
        while (i < j) {
            swap(nums, i, j);
            i++;
            j--;
        }
    }
    
    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

Leetcode: Two Sum II - Input array is sorted

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

Code(Java):

public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        if (numbers == null || numbers.length < 2) {
            return new int[2];
        }
        
        int lo = 0;
        int hi = numbers.length - 1;
        
        int[] result = new int[2];
        
        while (lo < hi) {
            if (numbers[lo] + numbers[hi] == target) {
                result[0] = lo + 1;
                result[1] = hi + 1;
                return result;
            } else if (numbers[lo] + numbers[hi] > target) {
                hi--;
            } else {
                lo++;
            }
        }
        
        return result;
    }
}

Leetcode: Product of Array Except Self

Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Solve it without division and in O(n).

For example, given [1,2,3,4], return [24,12,8,6].

Follow up:
Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)

Understand the problem:
Note that the problem does not allow to use division and the time complexity should be in O(n). 

One solution is to maintain to arrays, to maintain the product before a[i] and after a[i]. 
i.e, for a[i], we have product of a[0] * a[1] * ... * a[i - 1], and a[n - 1] * ... * a[i + 1]. 
Therefore we can iterate the nums array forward and backward order, respectively.  
And for result[i] = before[i] * after[i].

Code (Java):

public class Solution {
    public int[] productExceptSelf(int[] nums) {
        if (nums == null || nums.length < 2) {
            return new int[0];
        }
        
        int len = nums.length;
        int[] result = new int[len];
        int[] before = new int[len];
        int[] after = new int[len];
        
        before[0] = 1;
        for (int i = 1; i < len; i++) {
            before[i] = before[i - 1] * nums[i - 1];
        }
        
        after[len - 1] = 1;
        for (int i = len - 2; i >= 0; i--) {
            after[i] = after[i + 1] * nums[i + 1];
        }
        
        for (int i = 0; i < len; i++) {
            result[i] = before[i] * after[i];
        }
        
        return result;
    }
}

A constant space solution:
Note the the previous solution requires O(n) space cost. Can we solve the problem by only using constant space? The answer is yes. 

The idea is still the same. The only difference is we do the in-place. First of all, we iterate the nums array in forward and update the partial result. Then iterate the nums array again backward the update the final result. Instead of maintaining a after array, we only need one variable to maintain the after_i. 

Code (Java):

public class Solution {
    public int[] productExceptSelf(int[] nums) {
        if (nums == null || nums.length < 2) {
            return new int[0];
        }
        
        int[] result = new int[nums.length];
        result[0] = 1;
        
        // before a[i]
        for (int i = 1; i < nums.length; i++) {
            result[i] = result[i - 1] * nums[i - 1];
        }
        
        // after a[i]
        int after = 1;
        for (int i = nums.length - 2; i >= 0; i--) {
            result[i] *= after * nums[i + 1];
            after *= nums[i + 1];
        }
        
        return result;
    }
}

Leetcode: Two Sum III - Data structure design

Design and implement a TwoSum class. It should support the following operations: add and find.

add - Add the number to an internal data structure.
find - Find if there exists any pair of numbers which sum is equal to the value.

For example,

add(1); add(3); add(5);
find(4) -> true
find(7) -> false

Understand the problem:
The problem asks for designing a class TwoSum which supports two operations, add and find. There are two data structures / design decisions to think about. 
 1. Use two pointers. Requires the list to be sorted. 
       -- add: insert an element to a sorted array requires O(logn) + O(n) time. 
       -- find: use two pointers. Takes O(n) time. 

2. Use a hash map. 
       -- Add takes O(1) time. 
       -- Find takes O(n) time. 

Note that we have to use  the map instead of the set because we need to counter the number of duplicates for a number. e.g. add(0), add(0) and find(0). 

Code (Java):

public class TwoSum {
    private Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    
 public void add(int number) {
     if (map.containsKey(number)) {
         int val = map.get(number) + 1;
         map.put(number, val);
     } else {
         map.put(number, 1);
     }
 }

 public boolean find(int value) {
     if (map.isEmpty()) {
         return false;
     }
     Iterator it = map.entrySet().iterator();

     // Itearte over the set
     while (it.hasNext()) {
         Map.Entry pair = (Map.Entry) it.next();
         int firstKey =  (int) pair.getKey();
         int firstValue = (int) pair.getValue();
         
         int secondKey = value - firstKey;
         
         // 0 + 0 = 0
         if (firstKey == secondKey && firstValue >= 2) {
             return true;
         }  else if (firstKey != secondKey && map.containsKey(secondKey)) {
             return true;
         }
     }
     return false;
 }
}

Follow-up: 
What if you add a few, but search very heavily? You need to make sure search only takes O(1) time. Add(num), add num with all the previous added numbers 
search(target), only takes O(1) time. 

Code (Java)

public class FasterSearchSum implements TwoSum {
    Set<Integer> set = new HashSet<>();
    List<Integer> nums = new ArrayList<>();
    
    public void store(int input) {
        if (!nums.isEmpty()) {
            for (int num : nums) {
                set.add(input + num);
            }
        }
        
        nums.add(input);
    }
    
    public boolean test(int val) {
        return set.contains(val);
    }
}

Leetcode: Missing Ranges

Given a sorted integer array where the range of elements are [lower, upper] inclusive, return its missing ranges.

For example, given [0, 1, 3, 50, 75], lower = 0 and upper = 99, return ["2", "4->49", "51->74", "76->99"].

Understand the problem:
The problem itself is not hard at all. The key is to handle several corner cases. e.g. 
 -- If the array is empty, the missing ranges should be from lower to upper, inclusive. 
 -- For the leading missing range, e.g. -2 , [-1], -1. The output should be "-2". Note that the lower bound is inclusive. 
 -- For the trailing missing range, e.g. -2, [-2], 1, the output should be "-1->1". The upper bound is inclusive as well. 

Code (Java):

public class Solution {
    public List<String> findMissingRanges(int[] nums, int lower, int upper) {
        List<String> result = new ArrayList<String>();
        if (nums == null || nums.length == 0) {
            outputToResult(lower, upper, result);
            return result;
        }
        
        // leading missing range
        if (nums[0] - lower > 0) {
            outputToResult(lower, nums[0] - 1, result);
        }
        
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] - nums[i - 1] > 1) {
                outputToResult(nums[i - 1] + 1, nums[i] - 1, result);
            }
        }
        
        // trailing missage ranges
        if (upper - nums[nums.length - 1] > 0) {
            outputToResult(nums[nums.length - 1] + 1, upper, result);
        }
        
        return result;
    }
    
    private void outputToResult(int start, int end, List<String> result) {
        StringBuffer sb = new StringBuffer();
        if (start == end) {
            sb.append(start);
        } else {
            sb.append(start + "->" + end);
        }
        
        result.add(sb.toString());
    }
}

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;
    }
}

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];
    }
}