Search in Rotated Sorted Array

Medium

Walmart

0 views

Topics:

ArraysBinary Search

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
-10⁴ <= nums[i] <= 10⁴
All values of nums are unique.
nums is an ascending array that is possibly rotated.
-10⁴ <= target <= 10⁴

Search in Rotated Sorted Array

Medium

Walmart

0 views

Topics:

ArraysBinary Search

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
-10⁴ <= nums[i] <= 10⁴
All values of nums are unique.
nums is an ascending array that is possibly rotated.
-10⁴ <= target <= 10⁴

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values that can be present in the `nums` array?
Can the `nums` array be empty? If so, what should I return?
Can the `target` value be outside of the range of values within `nums`?
Are there any duplicate numbers in the `nums` array? If so, how should that affect the search?
Is the array guaranteed to be rotated (i.e., not already fully sorted), or could it be just a regular sorted array?

Brute Force Solution

Approach

Think of searching for a specific number in a book where the pages are almost in order, but a section has been shifted. The brute force method simply looks at every single number in the book one by one until you find the number you're looking for or you've checked them all.

Here's how the algorithm would work step-by-step:

Start with the very first number in the book.
Check if this number is the one you're trying to find.
If it is, you're done! You've found it.
If it's not, move on to the next number in the book.
Repeat this process, checking each number one at a time, until you find the number you're looking for or until you reach the end of the book.

Code Implementation

def search_in_rotated_sorted_array_brute_force(numbers, target):
   # Iterate through each number in the array.
   for current_index in range(len(numbers)):
       # Check if the current number matches the target.
       if numbers[current_index] == target:
           return current_index

   # If the target is not found in the array,
   # return -1 to indicate it's not present.
   return -1

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The provided brute force approach iterates through each element of the input array once. In the worst-case scenario, we might need to examine every single element before finding the target or determining that it's not present. Therefore, the time complexity is directly proportional to the number of elements, n, in the input array. Consequently, the algorithm performs approximately 'n' operations, resulting in a linear time complexity of O(n).

Space Complexity

O(1) – The brute force approach iterates through the input array without using any additional data structures that scale with the input size, N, where N is the number of elements in the rotated sorted array. It only requires a constant amount of extra space for variables like the current index being examined. Therefore, the space complexity remains constant regardless of the input size. The auxiliary space used is independent of N, leading to O(1) space complexity.

Optimal Solution

Approach

The problem deals with finding a specific value in a list that was originally sorted but then rotated. Instead of checking each list item individually, we leverage the fact that at least *part* of the list remains sorted to guide our search more efficiently.

Here's how the algorithm would work step-by-step:

Start by looking at the middle item in the list.
Check if the middle item is the value we're looking for. If it is, we're done!
If the middle item isn't the value, we need to figure out which half of the list to focus on.
Determine if the left side of the list (from the start to the middle) is sorted. If it is, compare the value we are looking for to the values at the start and middle of this left side.
If the value we are looking for falls within the range of this sorted left side, we continue our search only on the left side. Otherwise, focus on the right side.
If the left side wasn't sorted, that means the right side must be sorted. Now we do the same check as before but on the right side. Compare the value we are looking for to the values at the middle and end of the right side.
If the value we are looking for falls within the range of this sorted right side, we continue our search only on the right side. Otherwise, focus on the left side.
Repeat this process, each time focusing on a smaller and smaller section of the list until you either find the value or determine it isn't in the list.

Code Implementation

def search_in_rotated_sorted_array(nums, target):
    left_pointer = 0
    right_pointer = len(nums) - 1

    while left_pointer <= right_pointer:
        middle_pointer = (left_pointer + right_pointer) // 2

        if nums[middle_pointer] == target:
            return middle_pointer

        # Check if the left side is sorted
        if nums[left_pointer] <= nums[middle_pointer]:
            # If target is in the sorted left portion.
            if nums[left_pointer] <= target < nums[middle_pointer]:
                right_pointer = middle_pointer - 1

            # Otherwise, target is in the unsorted right.
            else:
                left_pointer = middle_pointer + 1

        # The left side is not sorted, so the right side must be.
        else:
            # If the target is in the sorted right portion
            if nums[middle_pointer] < target <= nums[right_pointer]:
                # Target is located on the right side.
                left_pointer = middle_pointer + 1

            # Otherwise, the target is in the unsorted left portion.
            else:
                # Target must be on the left side.
                right_pointer = middle_pointer - 1

    # Target is not in the array.
    return -1

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(log n) – The algorithm uses a modified binary search approach. In each step, the search space is halved by comparing the target value with the middle element and determining which half of the array to continue searching in. This halving of the search space continues until the target is found or the search space is exhausted. Therefore, the time complexity is logarithmic with respect to the input array size n, resulting in O(log n).

Space Complexity

O(1) – The algorithm described operates using a binary search approach. It only requires storing a few variables to keep track of the start, end, and middle indices of the search range. These variables consume a constant amount of space, independent of the input array's size (N). Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Empty array	Return -1 immediately as the target cannot be found in an empty array.
Array with one element and target matches	Return index 0 if the single element equals the target.
Array with one element and target does not match	Return -1 if the single element does not equal the target.
Array with two elements and target is one of them	Return the index of the element matching the target.
Array with two elements and target is not in the array	Return -1 as the target is not present.
Array rotated such that it is still sorted (no rotation)	Binary search will work as expected on the sorted array.
Target is smaller than the minimum value or larger than the maximum value in the array	The binary search will naturally converge to -1 since the target isn't within the sorted segments.
Array contains duplicate values near the pivot point, potentially masking the rotation	Binary search with comparisons to both left and right elements will correctly narrow down the search space despite duplicates.