Scale Engineer

Search in Rotated Sorted Array

Med
#0033Time: O(n)Space: O(1)50 companies
Algorithms
Binary Search
Data structures
Array
Companies
AccoliteAdobeAmazonApple

Prompt

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= 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,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(log n) runtime complexity.

 

Example 1:

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

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

Example 3:

Input: nums = [1], target = 0
Output: -1

 

Constraints:

  • 1 <= nums.length <= 5000
  • -104 <= nums[i] <= 104
  • All values of nums are unique.
  • nums is an ascending array that is possibly rotated.
  • -104 <= target <= 104

Approaches

2 approaches with complexity analysis and trade-offs.

The most straightforward approach is to perform a linear scan of the array. We can iterate through each element from the beginning to the end and check if it matches the target value. If a match is found, we return its index. If we traverse the entire array without finding the target, we return -1.

Algorithm

  • Initialize a loop counter i to 0.
  • Iterate through the nums array from i = 0 to nums.length - 1.
  • In each iteration, check if the current element nums[i] is equal to the target.
  • If they are equal, the target is found. Return the current index i.
  • If the loop completes without finding the target, it means the target is not in the array. Return -1.

Walkthrough

This brute-force method ignores the special properties of the rotated sorted array and treats it like any other unsorted list. It's simple to implement but fails to meet the performance requirements for larger datasets.

class Solution {    public int search(int[] nums, int target) {        for (int i = 0; i < nums.length; i++) {            if (nums[i] == target) {                return i;            }        }        return -1;    }}

Complexity

Time

O(n)

Space

O(1)

Trade-offs

Pros

  • Very simple to understand and implement.

  • Works correctly for any array, regardless of its properties.

Cons

  • Inefficient for large arrays as it may require scanning the entire array.

  • Does not meet the O(log n) time complexity requirement specified in the problem description.

Solutions

public class Solution {    public int Search(int[] nums, int target) {        int n = nums.Length;        int left = 0, right = n - 1;        while (left < right) {            int mid = (left + right) >> 1;            if (nums[0] <= nums[mid]) {                if (nums[0] <= target && target <= nums[mid]) {                    right = mid;                } else {                    left = mid + 1;                }            } else {                if (nums[mid] < target && target <= nums[n - 1]) {                    left = mid + 1;                } else {                    right = mid;                }            }        }        return nums[left] == target ? left : -1;    }}

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