Sources Contact Advanced Search Tutorials

An Interest In:

Web News this Week

Search Archive

Some of Our Sources

View All Sources

Help Webnuz

Referal links:

July 17, 2022 07:15 pm GMT

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 = 0Output: true

Example 2:

Input: nums = [2, 5, 6, 0, 0, 1, 2], target = 3Output: 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 (https://alkeshghorpade.me/post/leetcode-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 functionStep 1: searchUtil(nums, 0, nums.size() - 1, target)        searchUtil(nums, 0, 6, 0)// searchUtil functionStep 2: low > high        0 > 6        falseStep 3: mid = low + (high - low)/2            = 0 + (6 - 0)/2            = 0 + 6/2            = 3Step 4: if nums[mid] == target           nums[3] == 3           0 == 3           falseStep 5: if nums[low] == nums[mid] && nums[high] == nums[mid]           nums[0] == nums[3] && nums[6] == nums[3]           2 == 0 && 2 == 0           falseStep 6: if nums[low] <= nums[mid]           nums[0] <= nums[3]           2 <= 0           falseStep 7: if target >= nums[mid] && target <= nums[high]           3 >= nums[3] && 3 <= nums[6]           3 >= 0 && 3 <= 2           falseStep 8: searchUtil(nums, low, mid - 1, target)        searchUtil(nums, 0, 2, 3)// searchUtil functionStep 9: low > high        0 > 2        falseStep 10: mid = low + (high - low)/2             = 0 + (2 - 0)/2             = 0 + 2/2             = 1Step 11: if nums[mid] == target            nums[1] == 3            5 == 3            falseStep 12: if nums[low] == nums[mid] && nums[high] == nums[mid]            nums[0] == nums[1] && nums[2] == nums[1]            2 == 5 && 6 == 5            falseStep 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 functionStep 14: if low > high            0 > 0            falseStep 15: mid = low + (high - low)/2             = 0 + (0 - 0)/2             = 0 + 0/2             = 0Step 16: if nums[mid] == target            nums[0] == 3            2 == 3            falseStep 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 functionStep 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 recursionWe return the answer as false.

Original Link: https://dev.to/_alkesh26/leetcode-search-in-rotated-sorted-array-ii-22b5

Share this article:

View Full Article

Dev To

An online community for sharing and discovering great ideas, having debates, and making friends

More About this Source Visit Dev To