Jobs

Interviews

Discussions

Search in Rotated Sorted Array II

Medium

Microsoft

0 views

Topics:

ArraysBinary Search

You are given a rotated sorted array nums which may contain duplicate values. The array was originally sorted in non-decreasing order, but it was rotated at an unknown pivot index k (where 0 <= k < nums.length). Your task is to determine if a given target value is present in the rotated array.

For example, consider the array nums = [2, 5, 6, 0, 0, 1, 2]. If the target is 0, your function should return true. If the target is 3, your function should return false.

Details:

The array nums can contain duplicate values, which affects how the binary search is performed.
The array is guaranteed to be rotated at some pivot.
You should aim to minimize the overall number of operations.

Explain your approach, considering the impact of duplicates on the time complexity. Provide the optimal solution, analyze its time and space complexity, and explain how it handles edge cases.

Search in Rotated Sorted Array II

Medium

Microsoft

0 views

Topics:

ArraysBinary Search

For example, consider the array nums = [2, 5, 6, 0, 0, 1, 2]. If the target is 0, your function should return true. If the target is 3, your function should return false.

Details:

The array nums can contain duplicate values, which affects how the binary search is performed.
The array is guaranteed to be rotated at some pivot.
You should aim to minimize the overall number of operations.

Explain your approach, considering the impact of duplicates on the time complexity. Provide the optimal solution, analyze its time and space complexity, and explain how it handles edge cases.

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.

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

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

Space Complexity

Optimal Solution

Approach

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

Space Complexity

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.