Search in Rotated Sorted Array II

Medium

Amazon

1 view

Topics:

ArraysBinary Search

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
-10⁴ <= nums[i] <= 10⁴
nums is guaranteed to be rotated at some pivot.
-10⁴ <= target <= 10⁴

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?

Search in Rotated Sorted Array II

Medium

Amazon

1 view

Topics:

ArraysBinary Search

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
-10⁴ <= nums[i] <= 10⁴
nums is guaranteed to be rotated at some pivot.
-10⁴ <= target <= 10⁴

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?

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 the numbers in `nums` and `target` can take?
Can the input array `nums` be empty, or contain null values?
If the target value appears multiple times in the rotated array, is it sufficient to return `true` as soon as I find it once?
How should the rotation be defined if the input `nums` is empty?
Is `nums` guaranteed to be sorted before the rotation?

Brute Force Solution

Approach

The simplest way to solve this search problem is to just look at every single number and see if it's the one we're looking for. It's like looking for a specific book on a shelf by checking every book one by one.

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

Start at the beginning of the list of numbers.
Look at the first number and see if it's the number we're searching for.
If it is, we're done! We found it.
If it's not, move on to the next number in the list.
Keep checking each number, one after another, until we either find the number we're looking for or we reach the end of the list.
If we get to the end of the list and haven't found the number, it means the number isn't in the list at all.

Code Implementation

def search_in_rotated_sorted_array_brute_force(numbers, target):
    # Iterate through each number in the list
    for current_index in range(len(numbers)):

        # If we find the target, return True
        if numbers[current_index] == target:
            return True

    # If target is not found after iterating, return False
    return False

Big(O) Analysis

Time Complexity

O(n) – The provided solution iterates through the array once, examining each element to see if it matches the target. In the worst-case scenario, the target is the last element or is not present in the array, requiring the algorithm to check all 'n' elements. Therefore, the time complexity is directly proportional to the size of the input array, resulting in O(n) complexity.

Space Complexity

O(1) – The provided solution iterates through the input array without using any additional data structures. It only uses a constant amount of extra space for loop indices or temporary variables needed for comparison, irrespective of the size of the input array (N). Therefore, the space complexity is constant.

Optimal Solution

Approach

The problem is finding if a number exists in a sorted list that has been rotated. The optimal strategy uses a clever way to narrow down the search area in each step, quickly focusing on where the number might be, instead of checking every number.

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

Begin by looking at the middle number in the list.
If the middle number is what you're looking for, you're done!
If the beginning number, the middle number, and the end number are all the same, you can't tell how the list is sorted, so move the start and end one position closer to the middle to shrink the search space.
Otherwise, decide if the left part of the list (from start to middle) is sorted in ascending order.
If the left part is sorted, check if the number you're looking for falls between the beginning and middle numbers. If it does, focus your search on the left part; if not, search the right part.
If the left part is NOT sorted, then the right part must be sorted. Check if the number you're looking for falls between the middle and end numbers. If it does, focus your search on the right part; if not, search the left part.
Repeat this process of narrowing down the search area until you find the number or the search area becomes empty (meaning the number isn't in the list).

Code Implementation

def search_in_rotated_sorted_array_ii(numbers, target):
    start_index = 0
    end_index = len(numbers) - 1

    while start_index <= end_index:
        middle_index = (start_index + end_index) // 2

        if numbers[middle_index] == target:
            return True

        # Handle the case where we can't determine sorted side
        if numbers[start_index] == numbers[middle_index] == numbers[end_index]:
            start_index += 1
            end_index -= 1

            continue

        # Check if the left side is sorted
        if numbers[start_index] <= numbers[middle_index]:

            # Target is in the left sorted portion
            if numbers[start_index] <= target < numbers[middle_index]:
                end_index = middle_index - 1

            # Target is in the right unsorted portion
            else:
                start_index = middle_index + 1

        # Left side is not sorted, so the right side must be
        else:
            # This means the right side is sorted
            # Target is in the right sorted portion
            if numbers[middle_index] < target <= numbers[end_index]:
                start_index = middle_index + 1

            # Target is in the left unsorted portion
            else:

                end_index = middle_index - 1

    return False

Big(O) Analysis

Time Complexity

O(n) – The core algorithm performs a modified binary search. While it often halves the search space similar to binary search, the critical step is when nums[low] == nums[mid] == nums[high]. In this scenario, the algorithm resorts to incrementing the low pointer and decrementing the high pointer by one, effectively shrinking the search space by one element in each direction. In the worst-case scenario (e.g., an array with many duplicate elements), this degeneration can lead to a linear scan. Thus, in the worst case, the time complexity degrades to O(n), where n is the number of elements in the input array.

Space Complexity

O(1) – The algorithm uses a constant amount of extra space. It only requires a few variables to store the start, middle, and end indices during the search process. The space needed for these variables does not depend on the size of the input array, N, therefore the space complexity is constant.

Edge Cases

Case	How to Handle
Empty array	Return false immediately since the target cannot be found in an empty array.
Null array	Return false immediately since null array is invalid input.
Array with one element, target matches	Check if the single element equals the target and return true.
Array with one element, target does not match	Check if the single element equals the target and return false.
Array with all identical values, target matches	The while loop may need to iterate through the entire array, but it should correctly identify the target.
Array with all identical values, target does not match	The while loop will iterate through the entire array and return false.
Rotation point is at the beginning or end of the array (effectively no rotation).	The binary search should function correctly on the effectively sorted array.
Large array size to check for potential performance issues	Binary search has logarithmic time complexity, so it scales well with large arrays.