Merge Sorted Array

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1 and nums2 are m and n respectively.

/*
If we compare two elements from the start of two arrays and put the smaller one to the start of array the nums1, then in the worst case, all the elements in nums1 should move backward in every comparison. Time complexity will be O(m*n)

So we compare two elements from the end of two arrays and put the larger one to the end of the array nums1. Here's end is m+n, for the length of nums1 could be larger than or equal to m+n. We only need to begin at m+n and insert forward after each comparison.
time:O(n), space:O(1)
*/
public class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int index = m + n - 1;
        int i1 = m - 1;
        int i2 = n - 1;
        while (i1 >= 0 && i2 >= 0) {
            if (nums1[i1] > nums2[i2]) {
                nums1[index--] = nums1[i1--];
            } else {
                nums1[index--] = nums2[i2--];
            }
        }
        while (i2 >= 0) {
            nums1[index--] = nums2[i2--];
        }
    }
}

Remove Duplicates from Sorted Array

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

For example,
Given input array nums = [1,1,2],

Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn't matter what you leave beyond the new length.

/*

We don't care about what we leave beyond new length , hence we can use a pointer to keep track of the position and update the array.

time: O(n), space:O(1)

*/

public class Solution {

    public int removeDuplicates(int[] nums) {

        if (nums == null || nums.length == 0) {

            return 0;

        }

        int slow = 1;

        for (int fast = 1; fast < nums.length; fast++) {

            if (nums[fast] != nums[slow - 1]) {

                nums[slow] = nums[fast];

                slow++;

            }

        }

        return slow;

    }

}

/*

Follow up1: what if duplicates are allowed at most twice?

For example,
Given sorted array nums = [1,1,1,2,2,3],

Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3. It doesn't matter what you leave beyond the new length.

*/

//time: O(n), space:O(1)

public class Solution {

    public int removeDuplicates(int[] nums) {

        if (nums == null || nums.length == 0) {

            return 0;

        }

        int slow = 2;

        for (int fast = 2; fast < nums.length; fast++) {

            if (nums[fast] > nums[slow - 2]) {

                nums[slow] = nums[fast];

                slow++;

            }

        }

        return slow;

    }

}

/*

Follow up2: what if duplicates are allowed at most k times(k>0)?

For example,
Given k = 3 and sorted array nums = [1,1,2,4,4,4,4,4]

Your function should return length = 6, with the first six elements of nums being 1, 1, 2, 4, 4 and 4. It doesn't matter what you leave beyond the new length.

*/

//time: O(n), space:O(1)

public class Solution {

    public int removeDuplicates(int[] nums, int k) {

        if (nums == null || nums.length == 0 || k <= 0) {

            return 0;

        }

        int slow = k;

        for (int fast = k; fast < nums.length; fast++) {

            if (nums[fast] > nums[slow - k]) {

                nums[slow] = nums[fast];

                slow++;

            }

        }

        return slow;

    }

}

/*

Follow up3: what if duplicates are not allowed?

For example,
Given sorted array nums = [1,1,2,3,4,4]

Your function should return length = 2, with the first two elements of nums being 2 and 3. It doesn't matter what you leave beyond the new length.

*/

//time: O(n), space:O(1)

public class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int slow = 0;
        int fast = 0;
        int ind = 0;
        for (fast = 0; fast < nums.length; fast++) {
            if (nums[fast] > nums[slow]) {
                if (fast == slow + 1) {
                    nums[ind++] = nums[slow];
                } 
                slow = fast;
            }
        }
        if (slow + 1 == fast) {
            return ind + 1;
        }
        return ind;
    }

}

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.

Example 1:

Input: [7, 1, 5, 3, 6, 4]
Output: 5

max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)

Example 2:

Input: [7, 6, 4, 3, 1]
Output: 0

In this case, no transaction is done, i.e. max profit = 0.

/*
Every day, we should record the current lowest price and only need to compute the profit at this day based on the current lowest price. If the profit is bigger than the previous max profit, update the max profit. 

time:O(n), space:O(1)
*/

public class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
        int max = 0;
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < prices.length; i++) {
            min = Math.min(min, prices[i]);
            max = Math.max(max, prices[i] - min);
        }
        return max;
    }
}

Two Sum II

Given an array of integers, find how many pairs in the array such that their sum is bigger than a specific target number. Please return the number of pairs.

Example

Given numbers = [2, 7, 11, 15], target = 24. Return 1. (11 + 15 is the only pair)

/*

The naive way is to use two for-loops to iterate every two-element pair and compute if the sum is bigger than the target.

time: O(n^2), space:O(1)

The better way is to use two pointers. 

time:O(nlogn), space:O(1)

*/

public class Solution {

    public int twoSum2(int[] nums, int target) {

        if (nums == null || nums.length == 0) {

            return 0;

        }

        Arrays.sort(nums);

        int left = 0;

        int right = nums.length - 1;

        int count = 0;

        while (left < right) {

            if (nums[left] + nums[right] <= target) {

                left++;

            } else {

                count += right - left;

                right--;

            }

        }

        return count;

    }

}

Two Sum Closest

Given an array nums of n integers, find two integers in nums such that the sum is closest to a given number, target.

Return the difference between the sum of the two integers and the target.

Example

Given array nums = [-1, 2, 1, -4], and target = 4.

The minimum difference is 1. (4 - (2 + 1) = 1).

/*

The naive way is to find every two-element pair and calculate the difference between the sum and target. Save the minimum difference.

time:O(n^2), space:O(1)

One better way is to sort the array first and then use two pointers.

time: O(nlogn), space: O(1)

*/

public class Solution {

    public int twoSumCloset(int[] nums, int target) {

        int minDiff = Integer.MAX_VALUE;

        if (nums == null || nums.length < 2) {

            return minDiff;

        }

        Arrays.sort(nums);

        int start = 0;

        int end = nums.length - 1;

        while (start < end) {

            int diff = nums[start] + nums[end] - target;

            if (diff > 0) {

                end--;

            } else if (diff < 0) {

                start++;

            } else {

                return 0;

            }

            if (Math.abs(diff) < minDiff) {

                minDiff = Math.abs(diff);

            }

        }

        return minDiff;

    }

}

4Sum

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note: The solution set must not contain duplicate quadruplets.

For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

/*
The naive way is to search every four-element pair and check if the sum equals to the target.
time:O(n^4), space:O(1)

The better way is to use two pointers.
time:O(n^3), space:O(1)
*/

public class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        if (nums == null || nums.length < 4) {
            return ans;
        }
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 3; i++) {
            if (i > 0 && nums[i] == nums[i-1]) {
                continue;
            }
            for (int j = nums.length - 1; j > 2; j--) {
                if (j < nums.length - 1 && nums[j] == nums[j + 1]) {
                    continue;
                }
                int left = i + 1;
                int right = j - 1;
                while (left < right) {
                    int sum = nums[i] + nums[left] + 
                              nums[right] + nums[j];
                    if (sum < target) {
                        left++;
                    } else if (sum > target) {
                        right--;
                    } else {
                        List<Integer> row = new ArrayList<>();
                        row.add(nums[i]);
                        row.add(nums[left]);
                        row.add(nums[right]);
                        row.add(nums[j]);
                        ans.add(row);
                        left++;
                        right--;
                        while (left < right && nums[left] ==                                        nums[left-1]) {
                            left++;
                        }
                        while (left < right && nums[right] ==                                      nums[right + 1]) {
                            right--;
                        }
                    }
                }
            } 
        } 
        return ans;
    }
}

3Sum Closest

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

    For example, given array S = {-1 2 1 -4}, and target = 1.

    The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

/*
The naive way is to search every three-element pair and define a variable to store the sum of the pair which is closest to the target.
time:O(n^3), space:O(1)

The better way is to use two pointers. Like 3Sum.
The variable 'closestSum' can not be initialized to Integer.MAX_VALUE, for 'Math.abs(closestSum - target)' will out of range when the target is negative. 
time:O(n^2), space:O(1)
*/

public class Solution {
    public int threeSumClosest(int[] nums, int target) {
        if (nums == null || nums.length < 3) {
            return Integer.MAX_VALUE;
        }
        Arrays.sort(nums);
        int closestSum = nums[0] + nums[1] + nums[2];
        for(int i = 0; i < nums.length - 2; i++) {
            int left = i + 1;
            int right = nums.length - 1;
            while(left < right){
                int sum = nums[i] + nums[left] + nums[right];
                if (sum == target) {
                    return target;
                } else if (sum < target) {
                    left++;
                } else {
                    right--;
                }
                if (Math.abs(sum - target) < 
                    Math.abs(closestSum - target)) {
                    closestSum = sum;
                }
            }
        } 
        return closestSum;
    }
}

3Sum

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

For example, given array S = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

/*
The naive way is to search every three-element pair, to check if the sum equals to 0. 
time:O(n^3),  space:O(1)

The better way is to use two pointers to do optimization, for some pairs can be directly skipped.
time:O(n^2),  space:O(1)
*/

public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        if (nums == null || nums.length < 3) {
            return ans;
        }
        Arrays.sort(nums);
        for(int i = 0; i < nums.length - 2 && nums[i] <= 0; i++) {
            if(i > 0 && nums[i-1] == nums[i]) {
                continue;
            }
            int left = i + 1;
            int right = nums.length - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum < 0) {
                    left++;
                } else if (sum > 0) {
                    right--;
                } else {
                    List<Integer> list = new ArrayList<Integer>();
                    list.add(nums[i]);
                    list.add(nums[left]);
                    list.add(nums[right]);
                    ans.add(list);
                    left++;
                    right--;
                    while (left < right && nums[right] == 
                           nums[right + 1]) {
                        right--;
                    }
                    while (left < right && nums[left] == 
                           nums[left - 1]) {
                        left++;
                    }
                }
            }
        }
        return ans;
    }
}

Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution.
Example:Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

//HashMap, time:O(n), space:O(n)

public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        if (numbers == null || numbers.length == 0) {
            return new int[0];
        }
        int[] res = new int[2];
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < numbers.length; i++) {
            if (map.containsKey(target - numbers[i])) {
                res[0] = map.get(target - numbers[i]);
                res[1] = i;
                break;
            }
            map.put(numbers[i], i);
        }
        return res;
    }
}


/* follow-up1: if the input array is already sorted. */

// two pointers, time:O(n), space:O(1)

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

/*
In the method of two pointers, when the sum is smaller or bigger than the target, the left pointer only pluses one or the right pointer only minuses one. Here we can do some optimization. When the sum is smaller than the target, the left pointer actually can point to the smallest number which equals to or bigger than (target - numbers(right)). When the sum is bigger than the target, the right pointer can point to the biggest number which equals to or smaller than (target - numbers(left)). Because it is the sorted array, we can use binary search to implement this. 

binary search, time:O(logN), space:O(1)
*/

public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        if (numbers == null || numbers.length == 0) {
            return new int[0];
        }
        int[] ans = new int[2];
        int left = 0;
        int right = numbers.length - 1;
        while (left < right) {
            int sum = numbers[left] + numbers[right];
            if (sum < target) {
                left = binarySearch(numbers, target - 
                       numbers[right], left + 1, right - 1);
            } else if (sum > target) {
                right = binarySearch(numbers, target -                                       numbers[left], left + 1, right - 1);
            } else {
                ans[0] = left;
                ans[1] = right;
                break;
            }
        }
        return ans;
    }
    public int binarySearch(int[] nums, int target, 
                            int left, int right) {
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid;
            } else if (nums[mid] > target){
                right = mid;
            } else {
                return mid;
            }
        }
        if (nums[left] >= target) {
            return left;
        }
        return right;
    } 
}


/* follow-up2: if the input array has duplicate numbers, return the indices of two numbers of all the possibilities.
such as: nums = [1,3,5,2,2,3], target = 5,
return:[[1,3],[1,4],[3,5],[4,5]]

Use HashMap, key is number, value is List<Integer> which stores the indices of numbers. And the indices of duplicate numbers will be stored in the same List. 

time:O(n^2), space:O(n)
*/
public class Solution {
    public List<List<Integer>> twoSum(int[] nums, int target) {
List<List<Integer>> ans = new ArrayList<>();
if (nums == null || nums.length == 0) {
           return ans;
}
Map<Integer, List<Integer>> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(target - nums[i])) {
               for (Integer index : map.get(target - nums[i])){
                   List<Integer> list = new ArrayList<>();
                  list.add(index);
                  list.add(i);
                  ans.add(list);
               }
           }
           if (map.containsKey(nums[i])) {
map.get(nums[i]).add(i);
           } else {
List<Integer> list = new ArrayList<>();
list.add(i);
map.put(nums[i], list);
           }
}
return ans;
    }
}