Coding

Search in rotated sorted array-II

Asked at

DP WorldPPPragmatic Play

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

Given an integer array nums, sorted in ascending order (may contain duplicate values) and a target value k. Now the array is rotated at some pivot point unknown to you. Return True if k is present and otherwise, return False.

Input : nums = [7, 8, 1, 2, 3, 3, 3, 4, 5, 6], k = 3 Output: True Explanation: The element 3 is present in the array. So, the answer is True.

Input : nums = [7, 8, 1, 2, 3, 3, 3, 4, 5, 6], k = 10 Output: False Explanation:The element 10 is not present in the array. So, the answer is False.

Input : nums = [7, 8, 1, 2, 3, 3, 3, 4, 5, 6], k = 7

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums is guaranteed to be rotated at some pivot.
-104 <= k <= 104

cpp

class Solution {
public:
    bool searchInARotatedSortedArrayII(vector<int> &nums, int k)  {
      
    }
};

java

class Solution {
    public boolean searchInARotatedSortedArrayII(int[] nums, int k) {
      
    }
}

python

class Solution:
    def searchInARotatedSortedArrayII(self, nums, k):

javascript

class Solution {
    searchInARotatedSortedArrayII(nums, k) {
       
    }
}

csharp

public class Solution {
    public bool searchInARotatedSortedArrayII(List<int> nums, int k)  {
      
    }
}

func searchInARotatedSortedArrayII(nums []int, k int) bool {
	//your code goes here
}

Stuck? Show a way to structure it+

01Check the middle for target.
02When low, middle, and high values are equal, shrink both boundaries.
03Otherwise identify a sorted half.
04Test whether target lies in that half.
05Continue until found or empty.

Reference answer

Use the rotated-array search from the distinct-value version, with one essential ambiguity rule. If nums[low], nums[mid], and nums[high] are all equal, neither half can be identified as strictly sorted, so increment low and decrement high. Otherwise, if the left half is sorted, test whether target lies in its inclusive range and choose the proper half; if not, use the symmetric right-half rule. Always check nums[mid] before deciding branches. Shrinking equal boundaries preserves correctness because those boundary values were already checked against target, but it can discard only one value per iteration. Therefore average behavior is often logarithmic, yet the guaranteed worst case is O(n), for example an array of many equal values with one different pivot. Extra space remains O(1). Explicitly state this degradation instead of claiming O(log n) under duplicates.

Then expect these follow-ups

Give an input that forces O(n) behavior.
Tests: follow-up reasoning
How would you find the minimum with duplicates?
Tests: follow-up reasoning

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question