Jobs

Interviews

Discussions

Search in Rotated Sorted Array

Medium

Nvidia

2 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

What is the most efficient way to search for an integer in this rotated array? What is the Big O runtime?

Search in Rotated Sorted Array

Medium

Nvidia

2 views

Topics:

ArraysBinary Search

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

What is the most efficient way to search for an integer in this rotated array? What is the Big O runtime?

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 in the `nums` array? Can I expect negative numbers, zeros, or extremely large positive numbers?
What should I return if the target is not found in the array? Is -1 the expected return value in that case?
Can the input array be empty or null? If so, how should I handle those edge cases?
Are there any duplicate values present in the array? If so, how should duplicates affect my search?
If the array is rotated multiple times and the target appears in multiple locations, can I return any valid index?

Brute Force Solution

Approach

We need to find a specific number within a collection of numbers that are sorted, but the order might have been shifted. The brute force method involves checking each number one by one to see if it's the one we're looking for.

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

Take the number you are searching for.
Start at the beginning of the collection of numbers.
Compare the number you are searching for to the first number in the collection.
If they are the same, you've found it!
If they are not the same, move on to the next number in the collection.
Repeat this comparison process, moving through each number in the collection one by one.
Continue until you either find the number you are searching for or you've checked every number in the entire collection.
If you reach the end of the collection without finding the number, it means the number isn't present.

Code Implementation

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

    # If the target is not found, return -1.
    return -1

Big(O) Analysis

Time Complexity

O(n) – The provided algorithm iterates through the input array once, comparing each element to the target value. In the worst-case scenario, the target element is the last element in the array or is not present at all, requiring a full traversal of all 'n' elements. Therefore, the time complexity grows linearly with the size of the input array.

Space Complexity

O(1) – The provided brute force algorithm iterates through the input array, comparing each element to the target value. It doesn't use any auxiliary data structures like lists, hash maps, or recursion. The algorithm only requires a constant amount of extra space to store variables such as the index of the current element being checked and the target value being searched for. Therefore, the space complexity is O(1), indicating constant space usage irrespective of the input array size N.

Optimal Solution

Approach

The key is to realize that even though the entire list is rotated, at least one half will always be sorted. We can use a modified version of a common searching method to quickly narrow down where the target number might be.

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

Find the middle number in the list.
Check if the target number is the middle number. If so, you're done!
Figure out which half of the list (left or right of the middle) is sorted normally.
If the target number could be located in the sorted half, focus your search on that half. Otherwise, focus on the other half.
Repeat the process of finding the middle, checking if it's the target, and deciding which half to focus on until you find the target or determine it's not in the list.

Code Implementation

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

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

        if numbers[middle_pointer] == target:
            return middle_pointer

        # Check if the left side is sorted.
        if numbers[left_pointer] <= numbers[middle_pointer]:

            # The target is within the sorted left side.
            if numbers[left_pointer] <= target < numbers[middle_pointer]:
                right_pointer = middle_pointer - 1

            # The target is on the unsorted right side.
            else:
                left_pointer = middle_pointer + 1

        # The right side is sorted.
        else:
            # The target is within the sorted right side.
            if numbers[middle_pointer] < target <= numbers[right_pointer]:
                left_pointer = middle_pointer + 1

            # The target is on the unsorted left side.
            else:
                right_pointer = middle_pointer - 1

    return -1

Big(O) Analysis

Time Complexity

O(log n) – The algorithm uses a modified binary search approach. In each iteration, the search space is halved by comparing the target 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 size n.

Space Complexity

O(1) – The algorithm, as described, uses a modified binary search approach. It primarily relies on updating index pointers (e.g., start, middle, end) to narrow down the search range within the input array. No auxiliary data structures like temporary arrays, hash maps, or sets are created, and the recursive calls do not lead to a significant call stack depth as the problem is solved iteratively (or can be solved iteratively). Therefore, the space required remains constant irrespective of the input array's size (N).

Edge Cases

Case	How to Handle
Empty input array (nums is null or has zero length)	Return -1 immediately because the target cannot be found in an empty array.
Array with one element, and the target matches that element	Return 0, the index of the single element, since the target is found.
Array with one element, and the target does not match that element	Return -1, since the target is not found in the array.
Array with all identical values, but the target is not that value	The binary search will eventually narrow down to a region with no match, returning -1.
Array with all identical values, and the target is that value	Binary search should correctly locate an index containing the target value and return it.
Array is rotated such that it is effectively not rotated (i.e., still sorted in ascending order)	Binary search will work as expected on the already sorted array.
Target is smaller than the smallest element in the array and larger than the largest	Binary search will narrow down the search space and return -1 because the target is outside the sorted range.
Integer overflow during midpoint calculation: (low + high) / 2	Calculate the midpoint as low + (high - low) / 2 to prevent potential integer overflow.

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 in the `nums` array? Can I expect negative numbers, zeros, or extremely large positive numbers?
What should I return if the target is not found in the array? Is -1 the expected return value in that case?
Can the input array be empty or null? If so, how should I handle those edge cases?
Are there any duplicate values present in the array? If so, how should duplicates affect my search?
If the array is rotated multiple times and the target appears in multiple locations, can I return any valid index?

Brute Force Solution

Approach

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

Take the number you are searching for.
Start at the beginning of the collection of numbers.
Compare the number you are searching for to the first number in the collection.
If they are the same, you've found it!
If they are not the same, move on to the next number in the collection.
Repeat this comparison process, moving through each number in the collection one by one.
Continue until you either find the number you are searching for or you've checked every number in the entire collection.
If you reach the end of the collection without finding the number, it means the number isn't present.

Code Implementation

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

    # If the target is not found, return -1.
    return -1

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Find the middle number in the list.
Check if the target number is the middle number. If so, you're done!
Figure out which half of the list (left or right of the middle) is sorted normally.
If the target number could be located in the sorted half, focus your search on that half. Otherwise, focus on the other half.
Repeat the process of finding the middle, checking if it's the target, and deciding which half to focus on until you find the target or determine it's not in the list.

Code Implementation

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

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

        if numbers[middle_pointer] == target:
            return middle_pointer

        # Check if the left side is sorted.
        if numbers[left_pointer] <= numbers[middle_pointer]:

            # The target is within the sorted left side.
            if numbers[left_pointer] <= target < numbers[middle_pointer]:
                right_pointer = middle_pointer - 1

            # The target is on the unsorted right side.
            else:
                left_pointer = middle_pointer + 1

        # The right side is sorted.
        else:
            # The target is within the sorted right side.
            if numbers[middle_pointer] < target <= numbers[right_pointer]:
                left_pointer = middle_pointer + 1

            # The target is on the unsorted left side.
            else:
                right_pointer = middle_pointer - 1

    return -1

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array (nums is null or has zero length)	Return -1 immediately because the target cannot be found in an empty array.
Array with one element, and the target matches that element	Return 0, the index of the single element, since the target is found.
Array with one element, and the target does not match that element	Return -1, since the target is not found in the array.
Array with all identical values, but the target is not that value	The binary search will eventually narrow down to a region with no match, returning -1.
Array with all identical values, and the target is that value	Binary search should correctly locate an index containing the target value and return it.
Array is rotated such that it is effectively not rotated (i.e., still sorted in ascending order)	Binary search will work as expected on the already sorted array.
Target is smaller than the smallest element in the array and larger than the largest	Binary search will narrow down the search space and return -1 because the target is outside the sorted range.
Integer overflow during midpoint calculation: (low + high) / 2	Calculate the midpoint as low + (high - low) / 2 to prevent potential integer overflow.