First Bad Version

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

/* The isBadVersion API is defined in the parent class VersionControl.

      boolean isBadVersion(int version); */

/*

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

*/

public class Solution extends VersionControl {

    public int firstBadVersion(int n) {

        if (n <= 0) {

            return 0;

        }

        int left = 1;

        int right = n;

        while (left + 1 < right) {

            int mid = left + (right - left) / 2;

            if (isBadVersion(mid)) {

                right = mid;

            } else {

                left = mid;

            }

        }

        if (isBadVersion(left)) {

            return left;

        }

        return right;

    }

}

Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

Example

sqrt(3) = 1

sqrt(4) = 2

/*

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

*/

public class Solution {

    public int mySqrt(int x) {

        if (x == 0) {

            return 0;

        }

        int left = 0;

        int right = x;

        while (left + 1 < right) {

            int mid = left + (right - left) / 2;

            if (mid < x / mid) {

                left = mid;

            } else {

                right = mid;

            }

        }

        if (right <= x / right) {

            return right;

        }

        return left;

    }

}

Search in Rotated Sorted Array

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

/*

The sorted array is rotated. Then there must be two sorted sub arrays. When do the binary search, we should discuss the target is in which part.

For example, given [4,5,6,7,0,1,2], there are two sorted parts, [4,5,6,7] and [0,1,2]

If nums[mid] < target, there will be three conditions:

1. nums[mid] and target are both in [0,1,2]

2. nums[mid] and target are both in [4,5,6,7]

3. nums[mid] is in [0,1,2] and target is in [4,5,6,7]

Then when do the binary search, the search scope can be reduced by making left = mid in condition 1,2 or right = mid in condition 3.

It is similar when nums[mid] > target.

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

*/

public class Solution {
    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int left = 0;
        int right = nums.length - 1;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                if (nums[mid] <= nums[right] && 
                    target > nums[right]) {
                    right = mid;
                } else {
                    left = mid;
                }
            } else if (nums[mid] > target) {
                if (nums[mid] > nums[right] && 
                    target <= nums[right]) {
                    left = mid;
                } else {
                    right = mid;
                }
            } else {
                return mid;
            }
        }
        if (nums[left] == target) {
            return left;
        }
        if (nums[right] == target) {
            return right;
        }
        return -1;
    }
}

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