Sort Colors

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note:
You are not suppose to use the library's sort function for this problem.

/*

A rather straight forward solution is a two-pass algorithm using counting sort. First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's.

Also, we can use three pointers with one pass solution. In each step during the iteration, we do either of three things. Swap with the left, swap with the right, or move forward.

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

*/

public class Solution {

    public void sortColors(int[] nums) {

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

            return;

        }

        int left = 0;

        int right = nums.length - 1;

        int i = 0;

        while (i <= right) {

            if (nums[i] == 1) {

                i++;

            } else if (nums[i] == 0) {

                swap(nums, left, i); 

                left++;

                i++;

            } else {

                swap(nums, right, i);

                right--;

            }

        }

    }

    public void swap(int[] nums, int a, int b) {

        int tmp = nums[a];

        nums[a] = nums[b];

        nums[b] = tmp;

    }

}

Minimum Window Substring

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

For example,
S = "ADOBECODEBANC"
T = "ABC"

Minimum window is "BANC".

Note:
If there is no such window in S that covers all characters in T, return the empty string "".

If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

/*

Set an array to record the number of each character in string t. Use two pointers to iterate string s, when the substring in string s contains string t, if the length of the substring is smaller than the previous recorded length, update the minimum window substring. Then move forward the left pointer and continue to check if the new substring contains string t.

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

*/

public class Solution {

    public String minWindow(String s, String t) {

        if (s == null || s.length() == 0 || t == null) {

            return "";

        }

        int[] map = new int[256];

        for (char ch : t.toCharArray()) {

            map[ch]++; 

        }

        int i = 0;

        int j = 0;

        int count = t.length();

        int length = Integer.MAX_VALUE;

        String res = "";

        for (i = 0; i < s.length() - t.length() + 1; i++) {

            while (j < s.length() && count > 0) {

                if (map[s.charAt(j)]-- > 0) {

                    count--;

                }

                j++;

            }

            if (count == 0 && j - i < length) {

                length = j - i;

                res = s.substring(i, j);

            }

            if (map[s.charAt(i)]++ == 0) {

                count++;

            }

        }

        return res;

    }

}

Linked List Cycle II

Given a linked list, return the node where the cycle begins.

If there is no cycle, return null.

For example:

Given -21->10->4->5, tail connects to node index 1，return 10

/**
 * Definition for ListNode.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int val) {
 *         this.val = val;
 *         this.next = null;
 *     }
 * }
 */ 

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

public class Solution {
    public ListNode detectCycle(ListNode head) { 
        if (head == null) {
            return head;
        }
        ListNode slow = head;
        ListNode fast = head.next;
        while (slow != fast) {
            if (fast == null || fast.next == null) {
                return null;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        while (head != slow.next) {
            head = head.next;
            slow = slow.next;
        }
        return head;
    }
}

Window Sum

Given a list of integers, and a window size k, the window slides from left to right. Calculate the sum of integers in the window in each slide.

For example:
Given: A = [1,2,2,-3,4,0,3], k = 3. 
Return: [5, 1, 3, 1, 7]

/*
Two pointers, maintain a window whose size is k.
time:O(n), space:O(1)
*/

import java.util.*;

public class Solution {
    public static List<Integer> GetSum(List<Integer> A, int k) {
        ArrayList<Integer> res  = new ArrayList<>();
        if (A == null || A.size() == 0 || k <= 0) {
            return res;
        }
        int i = 0, j = 0;
        int sum = 0;
        for (i = 0; i < A.size() - k + 1; i++) {
            while (j < A.size() && j - i < k) {
                sum += A.get(j);
                j++;
            }
            res.add(sum);
            sum -= A.get(i);
        }
        return res;
    }

    public static void main(String[] args) {
        List<Integer> A = new ArrayList<>();
        A.add(1);
        A.add(1);
        A.add(2);
        A.add(-4);
        A.add(5);
        A.add(0);
        List<Integer> ans = GetSum(A, 7);
        for (Integer i : ans) {
            System.out.print(i + " ");
        }
    }
}

Valid Palindrome

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

For example,
"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not a palindrome.

/*

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

*/

public class Solution {
    public boolean isPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return true;
        }
        int left = 0;
        int right = s.length() - 1;
        while (left < right) {
            while (left < right &&                                                      !Character.isLetterOrDigit(s.charAt(left))) {
                left++;
            }
            while (left < right &&                                                      !Character.isLetterOrDigit(s.charAt(right))) {
                right--;
            }
            if (Character.toLowerCase(s.charAt(left)) !=                             Character.toLowerCase(s.charAt(right))) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

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

}

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