Scale Engineer

Search in Rotated Sorted Array II

Med
#0081Time: O(N)Space: O(1)8 companies
Algorithms
Binary Search
Data structures
Array
Companies
AdobeAmazonAppleBloomberg

Prompt

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?

Approaches

2 approaches with complexity analysis and trade-offs.

The most straightforward approach is to iterate through each element of the array and check if it matches the target value. This method does not leverage the partially sorted nature of the array.

Algorithm

    1. Start a loop that iterates from the first element (index = 0) to the last element (index = nums.length - 1).
    1. In each iteration, get the current element nums[i].
    1. Compare the current element with the target.
    1. If nums[i] == target, the target is found. Return true.
    1. If the loop finishes without finding any match, return false.

Walkthrough

This brute-force method involves a simple loop that traverses the array from the first element to the last. In each iteration, it compares the current element with the target. If a match is found, the function immediately returns true. If the loop completes without finding the target, it means the target is not in the array, and the function returns false.

class Solution {    public boolean search(int[] nums, int target) {        for (int num : nums) {            if (num == target) {                return true;            }        }        return false;    }}

Complexity

Time

O(N)

Space

O(1)

Trade-offs

Pros

  • Very simple to understand and implement.

  • Guaranteed to work correctly for any input array, regardless of its properties.

Cons

  • Highly inefficient, with a time complexity linear to the size of the array.

  • Fails to utilize the special property of the array (rotated sorted), missing an opportunity for optimization.

Solutions

class Solution {public  boolean search(int[] nums, int target) {    int l = 0, r = nums.length - 1;    while (l < r) {      int mid = (l + r) >> 1;      if (nums[mid] > nums[r]) {        if (nums[l] <= target && target <= nums[mid]) {          r = mid;        } else {          l = mid + 1;        }      } else if (nums[mid] < nums[r]) {        if (nums[mid] < target && target <= nums[r]) {          l = mid + 1;        } else {          r = mid;        }      } else {        --r;      }    }    return nums[l] == target;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem