Search in Rotated Sorted Array II LeetCode Solution

Problem – Search in Rotated Sorted Array II LeetCode Solution

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.

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 <= 5000
  • -104 <= nums[i] <= 104
  • nums is guaranteed to be rotated at some pivot.
  • -104 <= target <= 104

Follow up: This problem is similar to Search in Rotated Sorted Array, but nums may contain duplicates. Would this affect the runtime complexity? How and why?

Search in Rotated Sorted Array II LeetCode Solution in Python

# If the length of the given array list is 1, then check the first element and return accordingly
if len(nums)==1:
    if nums[0]!=target:
        return False
    else:
        return True

left=0
right=len(nums)-1
# binary search 
while(left<=right):

    # shifting to remove duplicate elements
    while left<right and nums[left] == nums[left+1]:
        left+=1
    while left<right and nums[right] == nums[right-1]:
        right-=1

    # step 1 calculate the mid    
    mid=(left+right)//2

    #step 2
    if nums[mid]==target:
        return True

    #step 3
    elif nums[left]<=nums[mid]:
        if nums[mid]>=target and nums[left]<=target:
            right=mid-1
        else:
            left=mid+1

    # step 4
    else:
        if target>=nums[mid] and target<=nums[right]:
            left=mid+1
        else:
            right=mid-1

# step 5
return False

Search in Rotated Sorted Array II LeetCode Solution in C++

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        int l = 0;
        int r = nums.size() - 1;
        
        while(l <= r)
        {
            int mid = l + (r-l) / 2;
            if (nums[mid] == target)
                return true;
			// with duplicates we can have this contdition, just update left & right
            if((nums[l] == nums[mid]) && (nums[r] == nums[mid]))
            {
                l++;
                r--;
            }
			// first half
			// first half is in order
            else if(nums[l] <= nums[mid])
            {
				// target is in first  half
                if((nums[l] <= target) && (nums[mid] > target))
                    r = mid - 1;
                else
                    l = mid + 1;
            }
			// second half
			// second half is order
			// target is in second half
            else
            {
                if((nums[mid] < target) && (nums[r]>= target))
                    l = mid + 1;
                else
                    r = mid - 1;
            }
        }
        return false;
    }
};

Search in Rotated Sorted Array II LeetCode Solution in Java

    public boolean search(int[] nums, int target) {
        int start = 0, end = nums.length - 1, mid = -1;
        while(start <= end) {
            mid = (start + end) / 2;
            if (nums[mid] == target) {
                return true;
            }
            //If we know for sure right side is sorted or left side is unsorted
            if (nums[mid] < nums[end] || nums[mid] < nums[start]) {
                if (target > nums[mid] && target <= nums[end]) {
                    start = mid + 1;
                } else {
                    end = mid - 1;
                }
            //If we know for sure left side is sorted or right side is unsorted
            } else if (nums[mid] > nums[start] || nums[mid] > nums[end]) {
                if (target < nums[mid] && target >= nums[start]) {
                    end = mid - 1;
                } else {
                    start = mid + 1;
                }
            //If we get here, that means nums[start] == nums[mid] == nums[end], then shifting out
            //any of the two sides won't change the result but can help remove duplicate from
            //consideration, here we just use end-- but left++ works too
            } else {
                end--;
            }
        }
        
        return false;
    }
Search in Rotated Sorted Array II LeetCode Solution Review:

In our experience, we suggest you solve this Search in Rotated Sorted Array II LeetCode Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Search in Rotated Sorted Array II LeetCode Solution

Find on Leetcode

Conclusion:

I hope this Search in Rotated Sorted Array II LeetCode Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.

Keep Learning!

More Coding Solutions >>

LeetCode Solutions

Hacker Rank Solutions

CodeChef Solutions

Leave a Reply

Your email address will not be published.