Showing posts with label Binary Search. Show all posts
Showing posts with label Binary Search. Show all posts

Thursday, May 24, 2018

744. Find Smallest Letter Greater Than Target

Given a list of sorted characters letters containing only lowercase letters, and given a target letter target, find the smallest element in the list that is larger than the given target.

Letters also wrap around. For example, if the target is target = 'z' and letters = ['a', 'b'], the answer is 'a'.

Examples:
Input:
letters = ["c", "f", "j"]
target = "a"
Output: "c"

Input:
letters = ["c", "f", "j"]
target = "c"
Output: "f"

Input:
letters = ["c", "f", "j"]
target = "d"
Output: "f"

Input:
letters = ["c", "f", "j"]
target = "g"
Output: "j"

Input:
letters = ["c", "f", "j"]
target = "j"
Output: "c"

Input:
letters = ["c", "f", "j"]
target = "k"
Output: "c"

Note:
letters has a length in range [2, 10000].
letters consists of lowercase letters, and contains at least 2 unique letters.
target is a lowercase letter.

Solution:

1. From Note we know the array is not empty so there must be a solution.

2. We check the last char in the array. If target is greater or equal than the last char, the answer is the first char in the array.

3. Use binary search to find the fist element that is greater than target in this array.

Time complexity is O(logn).


Code:

class Solution {
    public char nextGreatestLetter(char[] letters, char target) {
        if (target >= letters[letters.length - 1]) {
            return letters[0];
        }
        int start = 0;
        int end = letters.length - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (letters[mid] > target) {
                end = mid;
            }
            else {
                start = mid;
            }
        }
        if (letters[start] > target) {
            return letters[start];
        }
        return letters[end];
    }
}

Tuesday, August 8, 2017

74. Search a 2D Matrix

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
  • Integers in each row are sorted from left to right.
  • The first integer of each row is greater than the last integer of the previous row.
For example,
Consider the following matrix:
[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
Given target = 3, return true.



Solution:

This is a binary search problem.

We map the two dimensional coordinates to one dimensional number.

Thus, the time complexity can be optimized to O(log(mn)).



Code:


public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0) {
            return false;
        }
        if (matrix[0] == null || matrix[0].length == 0) {
            return false;
        }
        int m = matrix.length;
        int n = matrix[0].length;
        int start = 0;
        int end = m * n - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (matrix[mid / n][mid % n] <= target) {
                start = mid;
            }
            else {
                end = mid;
            }
        }
        if (matrix[end / n][end % n] == target) {
            return true;
        }
        if (matrix[start / n][start % n] == target) {
            return true;
        }
        return false;
    }
}

Monday, June 26, 2017

240. Search a 2D Matrix II

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
  • Integers in each row are sorted in ascending from left to right.
  • Integers in each column are sorted in ascending from top to bottom.
For example,
Consider the following matrix:
[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]
Given target = 5, return true.
Given target = 20, return false.



Solution:

The row is in ascending order and the column is also in ascending order.

So we can start from the bottom left.

If the target is smaller than the current point, the matching point can only be in the above area.

We go up.

If the target is target than the current point, the matching point can only be int he right area.

We go right.

The time complexity is O(m + n) and the space complexity is O(1).



Code:


public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0) {
            return false;
        }
        if (matrix[0] == null || matrix[0].length == 0) {
            return false;
        }
        int m = matrix.length;
        int n = matrix[0].length;
        
        int x = m - 1;
        int y = 0;
        while (x >= 0 && x < m && y >= 0 && y < n) {
            if (matrix[x][y] == target) {
                return true;
            }
            else if (matrix[x][y] < target) {
                y++;
            }
            else {
                x--;
            }
        }
        return false;
    }
}

Wednesday, June 21, 2017

167. 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 and you may not use the same element twice.
Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2



Solution:

Since the input is sorted, we can apply two pointers to find the answer.

One pointer points to the start of the array and the other points to the end of the array.

If the sum of the numbers pointed by these two points equals to target, we find the answer.

If the sum is smaller than target, we advance the first pointer.

Otherwise we decrease the second one.

The time complexity is O(n) and the space complexity is O(1).



Code:


public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int i = 0;
        int j = numbers.length - 1;
        while (i < j) {
            int sum = numbers[i] + numbers[j];
            if (sum == target) {
                return new int[] {i + 1, j + 1};
            }
            else if (sum > target) {
                j--;
            }
            else {
                i++;
            }
        }
        return new int[] {-1, -1};
    }
}

410. Split Array Largest Sum

Given an array which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays. Write an algorithm to minimize the largest sum among these m subarrays.
Note:
If n is the length of array, assume the following constraints are satisfied:
  • 1 ≤ n ≤ 1000
  • 1 ≤ m ≤ min(50, n)
Examples: 
Input:
nums = [7,2,5,10,8]
m = 2

Output:
18

Explanation:
There are four ways to split nums into two subarrays.
The best way is to split it into [7,2,5] and [10,8],
where the largest sum among the two subarrays is only 18.



Solution:

Assume that we have already split the array which satisfy the condition.

Let's say sub array sub is the one have the maximum sum of all sub arrays.

We know the sum of this array bound satisfies:

1. bound >= the largest element of the array.

2. bound <= the sum of the array.

Therefore, we can use binary search to find the first occurrence of bound that in the above range that can be splitter into m partitions.

The time complexity is O(nlogn) and the space complexity is O(1).



Code:


public class Solution {
    public int splitArray(int[] nums, int m) {
        int start = 0;
        int end = 0;
        for (int num : nums) {
            start = Math.max(start, num);
            end += num;
        }
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (isValid(nums, mid, m)) {
                end = mid;
            }
            else {
                start = mid;
            }
        }
        return isValid(nums, start, m) ? start : isValid(nums, end, m) ? end : -1;
    }
    
    public boolean isValid(int[] nums, int bound, int m) {
        int count = 1;
        int sum = 0;
        for (int num : nums) {
            sum += num;
            if (sum > bound) {
                count++;
                sum = num;
                if (count > m) {
                    return false;
                }
            }
        }
        return true;
    }
}

34. Search for a Range

Given an array of integers sorted in ascending order, find the starting and ending position of a given target value.
Your algorithm's runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].



Solution:

Apply two binary searches.

The first search is to find the first occurrence of target.

If we find a match, we include it and search to the left.

The second search is to find the last occurrence of target.

If we find a match, we include it and search to the right.

The time complexity is O(logn) and the space complexity is O(n).



Code:


public class Solution {
    public int[] searchRange(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return new int[] {-1, -1};
        }
        int start = 0;
        int end = nums.length - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] >= target) {
                end = mid;
            }
            else {
                start = mid;
            }
        }
        int first = -1;
        int last = -1;
        if (nums[start] == target) {
            first = start;
        }
        else if (nums[end] == target) {
            first = end;
        }
        else {
            return new int[] {first, last};
        }
        
        start = 0;
        end = nums.length - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] <= target) {
                start = mid;
            }
            else {
                end = mid;
            }
        }
        if (nums[end] == target) {
            last = end;
        }
        else if (nums[start] == target) {
            last = start;
        }
        return new int[] {first, last};
    }
}

Wednesday, June 14, 2017

349. Intersection of Two Arrays

Given two arrays, write a function to compute their intersection.
Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2].
Note:
  • Each element in the result must be unique.
  • The result can be in any order.



Solution:

Method 1: HashSet

Put all elements from nums1 to the HashSet.

Check every element in nums2.

If it is in the HashSet, this element is an intersection element.

The time complexity is O(n) and the space complexity is O(n);



Code:


public class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        HashSet<Integer> set = new HashSet<>();
        for (int num : nums1) {
            set.add(num);
        }
        HashSet<Integer> intersect = new HashSet<>();
        for (int num : nums2) {
            if (set.contains(num)) {
                intersect.add(num);
            }
        }
        int res[] = new int[intersect.size()];
        int i = 0;
        for (int key : intersect) {
            res[i++] = key;
        }
        return res;
    }
}



Method 2: Two Pointers

Sort two arrays.

Use two pointers from the beginning of two arrays.

Advance one pointer if it points to a smaller number.

If two pointer points to same value elements, this number is an intersection element.

The time complexity is O(nlogn).



Code:


public class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        HashSet<Integer> intersect = new HashSet<>();
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int i = 0;
        int j = 0;
        while (i < nums1.length && j < nums2.length) {
            if (nums1[i] < nums2[j]) {
                i++;
            }
            else if (nums1[i] > nums2[j]) {
                j++;
            }
            else {
                intersect.add(nums1[i]);
                i++;
                j++;
            }
        }
        i = 0;
        int res[] = new int[intersect.size()];
        for (int key : intersect) {
            res[i++] = key;
        }
        return res;
    }
}



Method 3: Binary Search

Sort one array.

Go through the other array.

For every element, use binary search to check if it is in the sorted array.

The time complexity is O(nlogn).



Code:


public class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        HashSet<Integer> intersect = new HashSet<>();
        Arrays.sort(nums2);
        for (int num : nums1) {
            if (search(nums2, num)) {
                intersect.add(num);
            }
        }
        int[] res = new int[intersect.size()];
        int i = 0;
        for (int key : intersect) {
            res[i++] = key;
        }
        return res;
    }
    public boolean search(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return false;
        }
        int start = 0;
        int end = nums.length - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] >= target) {
                end = mid;
            }
            else {
                start = mid;
            }
        }
        return nums[start] == target || nums[end] == target;
    }
}

Sunday, June 11, 2017

300. Longest Increasing Subsequence

Given an unsorted array of integers, find the length of longest increasing subsequence.
For example,
Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.
Your algorithm should run in O(n2) complexity.
Follow up: Could you improve it to O(n log n) time complexity?



Solution:

Method 1: Dynamic Programming

We use LIS[I] to denote the max LIS that end at nums[i] including nums[i].

It is the max of all (LIS[j] + 1), where j < i, if nums[i] > nums[j].

The time complexity is O(n2) and the space complexity is O(n).



Code:


public class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int max = 1;
        int[] LIS = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            LIS[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    LIS[i] = Math.max(LIS[i], LIS[j] + 1);
                }
            }
            max = Math.max(max, LIS[i]);
        }
        return max;
    }
}



Method 2: DP + Binary Search

The idea is to maintain an array that array[i] means the smallest number that can form an increasing sequence with length i.

For example,  [4, 5, 6, 3]

len = 1   :      [4], [5], [6], [3]    => tails[1] = 3
len = 2   :      [4, 5], [5, 6]         => tails[2] = 5
len = 3   :      [4, 5, 6]                => tails[3] = 6

Therefore, we create an array tails with length + 1.

Traverse all numbers from the input array.

For each number num, use binary search to find the first index in tails where tails[i] >= num.

Replace tails[i] with num.

After traversing, go backward and find the first valid index, which is the longest length.

The time complexity is O(nlogn) and the space complexity is O(n).



Code:


public class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] tails = new int[nums.length + 1];
        Arrays.fill(tails, Integer.MAX_VALUE);
        tails[0] = Integer.MIN_VALUE;
        
        int max = 0; // input can be [].
        for (int num : nums) {
            int index = findFirst(tails, num);
            tails[index] = num;
            max = Math.max(max, index);
        }
        return max;
    }
    
    public int findFirst(int[] nums, int target) {
        int start = 1;
        int end = nums.length - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] < target) {
                start = mid;
            }
            else {
                end = mid;
            }
        }
        if (nums[start] >= target) {
            return start;
        }
        return end;
    }
}

Wednesday, June 7, 2017

35. Search Insert Position

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You may assume no duplicates in the array.
Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0



Solution 1:

Use binary search to find the first occurrence that nums[index] >= target.

We can insert the target at index.

Corner case:

1. target < first element. We insert at index 0.

2. target > last element. We insert at index nums.length.

The time complexity is O(logn) and the space complexity is O(1).



Code:


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



Solution 2:

Use binary search to find the last occurrence that nums[index] < target.

Insert at index + 1.

Corner case:

1. target <= first element. We insert at index 0.

2. target < last element. We insert at index nums.length.

The time complexity is O(logn) and the space complexity is O(1).


Code:


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

275. H-Index II

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



Solution:

The idea is to use binary search to find the first occurrence satisfy:

citations[index] >= citations.length - index.

This condition means there are citations[index] papers have at least citations[index] citations.

The time complexity is O(logn) and the space complexity is O(n).



Code:


public class Solution {
    public int hIndex(int[] citations) {
        if (citations == null || citations.length == 0) {
            return 0;
        }
        // find first occurance that citations[index] >= citations.length - index
        int n = citations.length;
        int start = 0;
        int end = n - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (citations[mid] >= n - mid) {
                end = mid;
            }
            else {
                start = mid;
            }
        }
        if (citations[start] >= n - start) {
            return n - start;
        }
        if (citations[end] >= n - end) {
            return n - end;
        }
        return 0;
    }
}

Sunday, May 28, 2017

33. 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.



Solution:

The idea is use binary search to find the target.

When we have mid, we check:

1. If nums[start] < nums[mid]

  a). target >= nums[start] && target < nums[mid]. ==> search from start to mid.

  b). target < nums[start] || target >= nums[mid]. ==> search from mid to end (still a rotated sorted array)

2. If nums[start] >= nums[mid]

  a).  target > nums[mid] && target <= nums[end]. ==> search from mid to end.

  b). target <= nums[mid] || target > nums[end]. ==> search from start to mid. (still a rotated sorted array)

Thus, the time complexity is still O(logn).



Code:


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

Thursday, May 25, 2017

278. 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.



Solution:

Use binary search to check version x.

If version x is invalid, we check from version 1 to version x.

If version x is valid, we check from version x to version n.

Time complexity is O(logn).


Code:


/* The isBadVersion API is defined in the parent class VersionControl.
      boolean isBadVersion(int version); */

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int start = 1;
        int end = n;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (isBadVersion(mid)) {
                end = mid;
            }
            else {
                start = mid;
            }
        }
        return isBadVersion(start) ? start : end;
    }
}

Thursday, May 11, 2017

374. Guess Number Higher or Lower

We are playing the Guess Game. The game is as follows:
I pick a number from 1 to n. You have to guess which number I picked.
Every time you guess wrong, I'll tell you whether the number is higher or lower.
You call a pre-defined API guess(int num) which returns 3 possible results (-1, 1, or 0):
-1 : My number is lower
 1 : My number is higher
 0 : Congrats! You got it!
Example:
n = 10, I pick 6.

Return 6.



Solution:

Classic binary search problem.

The time complexity is O(logn).



Code:


/* The guess API is defined in the parent class GuessGame.
   @param num, your guess
   @return -1 if my number is lower, 1 if my number is higher, otherwise return 0
      int guess(int num); */

public class Solution extends GuessGame {
    public int guessNumber(int n) {
        int start = 1;
        int end = n;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (guess(mid) < 0) {
                end = mid;
            }
            else {
                start = mid;
            }
        }
        
        if (guess(end) == 0) {
            return end;
        }
        return start;
    }
}

Monday, May 8, 2017

162. Find Peak Element

A peak element is an element that is greater than its neighbors.
Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.
The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.
You may imagine that num[-1] = num[n] = -∞.
For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.
Note:
Your solution should be in logarithmic complexity.



Solution:

The problem description indicates we can imagine nums[-1] and nums[n] are -INF. That is to say there must be at least one peak in the array.

Therefore, we use binary search to find any peak in the array.

If in any point, we find it is less than its right. We know there must be a peak to the right.

Otherwise, we know there must be a peak to the left.

The time complexity is O(logn).



Code:


public class Solution {
    public int findPeakElement(int[] nums) {
        int start = 0;
        int end = nums.length - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] < nums[mid + 1]) {
                start = mid;
            }
            else {
                end = mid;
            }
        }
        if (nums[start] > nums[end]) {
            return start;
        }
        return end;
    }
}