Alkesh

LeetCode - Search in Rotated Sorted Array II

Problem statement

There is an integer array nums sorted in non-decreasing order (not necessarily with distinct values).

Before being passed to your function, nums is rotated at an unknown pivot index k (0 <= k < nums.length) such that the resulting array is [nums[k], nums[k + 1], ..., nums[n - 1], nums[0], nums[1], ..., nums[k - 1]] (0-indexed). For example, [0, 1, 2, 4, 4, 4, 5, 6, 6, 7] might be rotated at pivot index 5 and become [4, 5, 6, 6, 7, 0, 1, 2, 4, 4].

Given the array nums after the rotation and an integer target, return true if target is in nums, or false if it is not in nums.

You must decrease the overall operation steps as much as possible.

Problem statement taken from: https://leetcode.com/problems/search-in-rotated-sorted-array-ii/.

Example 1:

Input: nums = [2, 5, 6, 0, 0, 1, 2], target = 0
Output: true

Example 2:

Input: nums = [2, 5, 6, 0, 0, 1, 2], target = 3
Output: false

Constraints:

- 1 <= nums.length <= 10^5
- -2^31 <= nums[i] <= 2^31 - 1
- 0 <= k <= 10^5

Explanation

The solution for this problem is similar to the previous Search in Rotated Sorted Array. The only difference is that due to the presence of duplicates, nums[low] == nums[mid] is a possibility and we have to deal with this case separately.

Let's jump directly to the algorithm.

// search function
- if low > high
    - return -1

- set mid = low + (high - low) / 2

- if nums[mid] == key
    - return true

- if nums[low] == nums[mid + 1] && nums[high] == nums[mid]
    - low++
    - high--
    - search(nums, low, high, key)

if nums[low] <= nums[mid]
    - if key >= nums[low] && key <= nums[mid]
        - return search(nums, low, mid - 1, key)

    - return search(nums, mid + 1, high, key)

if key >= nums[mid] && key <= nums[high]
    - return search(nums, mid + 1, high, key)

- return search(nums, low, mid - 1, key)

Let's check out our solutions in C++, Golang, and Javascript.

C++ solution

class Solution {
public:
    bool searchUtil(vector<int>& nums, int low, int high, int target) {
        if(low > high) {
            return false;
        }

        int mid = low + (high - low)/2;

        if(nums[mid] == target){
            return true;
        }

        if(nums[low] == nums[mid] && nums[high] == nums[mid]){
            low++;
            high--;
            return searchUtil(nums, low, high, target);
        }

        if(nums[low] <= nums[mid]){
            if(target >= nums[low] && target <= nums[mid]){
                return searchUtil(nums, low, mid - 1, target);
            }

            return searchUtil(nums, mid + 1, high, target);
        }

        if(target >= nums[mid] && target <= nums[high]){
            return searchUtil(nums, mid + 1, high, target);
        }

        return searchUtil(nums, low, mid - 1, target);
    }

    bool search(vector<int>& nums, int target) {
        bool result = searchUtil(nums, 0, nums.size() - 1, target);
        return result;
    }
};

Golang solution

func searchUtil(nums []int, low, high, target int) bool {
    if low > high {
        return false
    }

    mid := low + (high - low) / 2

    if nums[mid] == target {
        return true
    }

    if nums[low] == nums[mid] && nums[high] == nums[mid] {
        low++
        high--
        return searchUtil(nums, low, high, target)
    }

    if nums[low] <= nums[mid] {
        if target >= nums[low] && target <= nums[mid] {
            return searchUtil(nums, low, mid - 1, target)
        }

        return searchUtil(nums, mid + 1, high, target)
    }

    if target >= nums[mid] && target <= nums[high] {
        return searchUtil(nums, mid + 1, high, target);
    }

    return searchUtil(nums, low, mid - 1, target);
}

func search(nums []int, target int) bool {
    return searchUtil(nums, 0, len(nums) - 1, target)
}

Javascript solution

var searchUtil = function(nums, low, high, target) {
    if(low > high) {
        return false;
    }

    let mid = low + (high - low)/2;

    if(nums[mid] == target){
        return true;
    }

    if(nums[low] == nums[mid] && nums[high] == nums[mid]){
        low++;
        high--;
        return searchUtil(nums, low, high, target);
    }

    if(nums[low] <= nums[mid]){
        if(target >= nums[low] && target <= nums[mid]){
            return searchUtil(nums, low, mid - 1, target);
        }

        return searchUtil(nums, mid + 1, high, target);
    }

    if(target >= nums[mid] && target <= nums[high]){
        return searchUtil(nums, mid + 1, high, target);
    }

    return searchUtil(nums, low, mid - 1, target);
};

var search = function(nums, target) {
    return searchUtil(nums, 0, nums.length - 1, target);
};

Let's dry run the problem.

Input: nums = [2, 5, 6, 0, 0, 1, 2], target = 3

// search function
Step 1: searchUtil(nums, 0, nums.size() - 1, target)
        searchUtil(nums, 0, 6, 0)

// searchUtil function
Step 2: low > high
        0 > 6
        false

Step 3: mid = low + (high - low)/2
            = 0 + (6 - 0)/2
            = 0 + 6/2
            = 3

Step 4: if nums[mid] == target
           nums[3] == 3
           0 == 3
           false

Step 5: if nums[low] == nums[mid] && nums[high] == nums[mid]
           nums[0] == nums[3] && nums[6] == nums[3]
           2 == 0 && 2 == 0
           false

Step 6: if nums[low] <= nums[mid]
           nums[0] <= nums[3]
           2 <= 0
           false

Step 7: if target >= nums[mid] && target <= nums[high]
           3 >= nums[3] && 3 <= nums[6]
           3 >= 0 && 3 <= 2
           false

Step 8: searchUtil(nums, low, mid - 1, target)
        searchUtil(nums, 0, 2, 3)

// searchUtil function
Step 9: low > high
        0 > 2
        false

Step 10: mid = low + (high - low)/2
             = 0 + (2 - 0)/2
             = 0 + 2/2
             = 1

Step 11: if nums[mid] == target
            nums[1] == 3
            5 == 3
            false

Step 12: if nums[low] == nums[mid] && nums[high] == nums[mid]
            nums[0] == nums[1] && nums[2] == nums[1]
            2 == 5 && 6 == 5
            false

Step 13: if nums[low] <= nums[mid]
            nums[0] <= nums[1]
            2 <= 5
            true

            if target >= nums[low] && target <= nums[mid]
               3 >= nums[0] && 3 <= nums[1]
               3 >= 2 && 3 <= 5
               true

               return searchUtil(nums, low, mid - 1, target)
                      searchUtil(nums, 0, 1 - 1, 3)
                      searchUtil(nums, 0, 0, 3)

// searchUtil function
Step 14: if low > high
            0 > 0
            false

Step 15: mid = low + (high - low)/2
             = 0 + (0 - 0)/2
             = 0 + 0/2
             = 0

Step 16: if nums[mid] == target
            nums[0] == 3
            2 == 3
            false

Step 17: if nums[low] == nums[mid] && nums[high] == nums[mid]
            nums[0] == nums[0] && nums[0] == nums[0]
            2 == 2 && 2 == 2
            true

            low++
            low = 1

            high--
            high = -1

            return searchUtil(nums, low, high, target)
                   searchUtil(nums, 1, -1, 3)

// searchUtil function
Step 14: if low > high
            1 > -1
            true

            return false

// We go back from Step 14 to Step 9 to Step 2 to Step 1 because of recursion

We return the answer as false.
Share this post!