Leetcode 33: Search in Rotated Sorted Array

Problem statement

Suppose an array sorted in ascending order has been rotated at an unknown pivot.

(For example, the array [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2].)

Search for a given target value. If it exists in the array, return its index; otherwise, return -1.

You may assume the array contains no duplicate elements.

Your algorithm must have O(log n) time complexity.

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0 Output: 4 Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3 Output: -1

Approach

The required time complexity means we have to use binary search. The key is deciding when to search left and when to search right. Observation reveals that when the middle value is greater than head, the left side is in descending order; when it is less than tail, the right side is in descending order.

Code

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

Leetcode 540: Single Element in a Sorted Array

Problem statement

Given a sorted array of integers in which every element appears twice except for one that appears once, find that single element.

Example 1:

Input: [1,1,2,3,3,4,4,8,8] Output: 2 Example 2:

Input: [3,3,7,7,10,11,11] Output: 10

Note: Your solution should run in O(log n) time and O(1) space.

Approach

This problem is easily confused with Leetcode 136, Single Number. Note the requirement for O(log n) time complexity, which means using binary search or a similar method. The extra information here is that the array is sorted. We need to use that information to decide how to adjust the left and right boundaries.

The main pattern is this: if nums[mid] ==nums[mid], the answer must be in the second half when mid is even, and in the first half when mid is odd.

Reference solution

class Solution {
    public int singleNonDuplicate(int[] nums) {
        int lo = 0, hi = nums.length - 1;
        
        while(lo < hi ){
            int mid = lo + (hi - lo)/2;
            if( mid % 2 == 1){
                if(nums[mid]== nums[mid - 1]) {
                    lo = mid + 1;
                }
                else{
                    hi = mid -1;
                }
            }
            else{
                if(nums[mid] == nums[mid -1]){
                    hi = mid -2;
                }
                else{
                    lo = mid;
                }
            }
        }
        
        return nums[hi];
    }
}

Leetcode 1060: Missing Element in Sorted Array

Problem statement:

Given a sorted array A of unique numbers, find the Kth missing number starting from the leftmost element of the array.

Example 1:

Input: A = [4,7,9,10], K = 1 Output: 5 Explanation: The first missing number is 5. Example 2:

Input: A = [4,7,9,10], K = 3 Output: 8 Explanation: The missing numbers are [5,6,8,…], so the third missing number is 8. Example 3:

Input: A = [1,2,4], K = 3 Output: 6 Explanation: The missing numbers are [3,5,6,7,…], so the third missing number is 6.

Constraints:

1 <= A.length <= 50000 1 <= A[i] <= 1e7 1 <= K <= 1e8

Approach

Use simple arithmetic to find the interval containing the missing number, then calculate it from the preceding number.

Reference solution

class Solution {
    public int missingElement(int[] nums, int k) {
        for(int i = 0; i < nums.length - 1; i++){
            if(nums[i+ 1] - nums[i] - 1 >= k){
                return nums[i] + k;
            }
            k = k - (nums[i+ 1] - nums[i] - 1);
        }
        
        return nums[nums.length - 1] + k;
    }
}

This problem can also be solved using binary search.