Jobs

Interviews

Discussions

Find Minimum in Rotated Sorted Array II

Hard

Asked by:

More companies

30 views

Topics:

ArraysBinary Search

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,4,4,5,6,7] might become:

[4,5,6,7,0,1,4] if it was rotated 4 times.
[0,1,4,4,5,6,7] if it was rotated 7 times.

Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Given the sorted rotated array nums that may contain duplicates, return the minimum element of this array.

You must decrease the overall operation steps as much as possible.

Example 1:

Input: nums = [1,3,5]
Output: 1

Example 2:

Input: nums = [2,2,2,0,1]
Output: 0

Constraints:

n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
nums is sorted and rotated between 1 and n times.

Follow up: This problem is similar to Find Minimum in Rotated Sorted Array, but nums may contain duplicates. Would this affect the runtime complexity? How and why?

Try coding it in LeetCode

Find Minimum in Rotated Sorted Array II

Hard

Asked by:

30 views

Topics:

ArraysBinary Search

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,4,4,5,6,7] might become:

[4,5,6,7,0,1,4] if it was rotated 4 times.
[0,1,4,4,5,6,7] if it was rotated 7 times.

Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Given the sorted rotated array nums that may contain duplicates, return the minimum element of this array.

You must decrease the overall operation steps as much as possible.

Example 1:

Input: nums = [1,3,5]
Output: 1

Example 2:

Input: nums = [2,2,2,0,1]
Output: 0

Constraints:

n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
nums is sorted and rotated between 1 and n times.

Follow up: This problem is similar to Find Minimum in Rotated Sorted Array, but nums may contain duplicates. Would this affect the runtime complexity? How and why?

Try coding it in LeetCode

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:

Can the input array contain duplicate values, and if so, how should they be handled?
What is the expected return value if the input array is empty or null?
Are the numbers in the array integers, or could they be floating-point numbers?
Is the array guaranteed to be rotated? In other words, could it already be sorted in ascending order?
Is there a constraint on the range of integer values within the array?

Brute Force Solution

Approach

The brute force approach to finding the minimum value in a rotated sorted list involves checking every single number. We simply go through the list, number by number, and remember the smallest one we've seen so far. At the end, the smallest number we remembered is the answer.

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

Look at the first number in the list. This is our current smallest number.
Now, look at the next number in the list.
If this new number is smaller than our current smallest number, replace our current smallest number with this new number.
Keep doing this for every number in the list: comparing each number to our current smallest number and replacing it if necessary.
Once you've looked at every number in the list, the 'current smallest number' you have is the minimum value in the entire list.

Code Implementation

def find_minimum_brute_force(numbers):
    # Initialize minimum with the first element
    current_minimum = numbers[0]

    for index in range(1, len(numbers)):
        # Compare current element with the current minimum
        if numbers[index] < current_minimum:

            # Update current_minimum if a smaller element is found
            current_minimum = numbers[index]

    return current_minimum

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array of size n exactly once. In each iteration, it performs a constant-time comparison to find the minimum element encountered so far. Therefore, the time complexity is directly proportional to the number of elements in the array, resulting in O(n).

Space Complexity

O(1) – The provided brute force algorithm only uses a single variable to store the current smallest number encountered during iteration. The amount of space used for this variable remains constant irrespective of the size (N) of the input array. Therefore, the auxiliary space complexity is O(1), indicating constant space usage.

Optimal Solution

Approach

The core idea is to use a divide-and-conquer approach. We repeatedly cut the search space in half by strategically examining elements to guide our search towards the minimum, even when the numbers are potentially duplicated.

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

Start by looking at the first and last number in the given set of numbers.
If the last number is bigger than the first number, then the numbers are already sorted, and the first number is the smallest.
If the last number is the same as the first number, remove one of the duplicate numbers from consideration and start again.
Otherwise, look at the number in the middle.
If the middle number is bigger than the last number, the smallest number must be somewhere after the middle, so focus only on that part of the set.
If the middle number is smaller than the last number, the smallest number must be the middle or somewhere before it, so focus only on that part of the set.
Keep repeating this process of elimination until only one number is left. That number will be the smallest.

Code Implementation

def find_minimum_in_rotated_sorted_array_ii(numbers):
    start_index = 0
    end_index = len(numbers) - 1

    while start_index < end_index:
        # If already sorted, the first element is the minimum.
        if numbers[end_index] > numbers[start_index]:
            return numbers[start_index]

        # Remove duplicate elements to shrink the search space.
        if numbers[start_index] == numbers[end_index]:
            end_index -= 1

            continue

        middle_index = (start_index + end_index) // 2

        # The minimum must be in the right half.
        if numbers[middle_index] > numbers[end_index]:
            start_index = middle_index + 1

        # The minimum must be in the left half or is the middle.
        else:
            end_index = middle_index

    return numbers[start_index]

Big(O) Analysis

Time Complexity

O(n) – In the best case, where the array is already sorted (nums[left] < nums[right]), we return the first element, resulting in O(1) complexity. However, in the worst-case scenario with many duplicate elements (nums[left] == nums[right]), we might repeatedly reduce the search space by only one element in each step (left++ or right--). This could degenerate into a linear search where we examine each of the 'n' elements in the array at least once, especially when the duplicates are clustered. Therefore, the worst-case time complexity is O(n).

Space Complexity

O(1) – The algorithm operates in place by comparing and adjusting the start and end pointers of the input array. No auxiliary data structures like temporary arrays or hash maps are used. The only extra space required is for a few variables to store indices and perform comparisons, and the space used remains constant irrespective of the input size N.

Edge Cases

Case	How to Handle
Empty array	Return a default value such as positive infinity or throw an exception as there is no minimum.
Array with one element	Return the single element directly as it's trivially the minimum.
Array is not rotated (already sorted in ascending order)	The binary search should still converge to the first element as the minimum.
Array with all identical elements	The algorithm should correctly handle the case where the left and right values are equal, potentially requiring linear search within that range.
Array with many duplicate elements concentrated in a small section	The algorithm's efficiency might degrade to O(n) in the worst-case scenario where many elements are the same, and a linear search is needed.
Integer overflow during midpoint calculation	Use `mid = left + (right - left) / 2` to avoid potential integer overflow.
Very large array (memory constraints)	The binary search algorithm already has logarithmic space complexity, making it suitable for large arrays, but external memory solutions could be considered if the array exceeds available memory.
Array rotated such that the minimum element is at the very beginning or very end	The binary search logic must correctly handle these rotation extremes to find the true minimum.

Empty array

How to Handle:

Return a default value such as positive infinity or throw an exception as there is no minimum.

Array with one element

How to Handle:

Return the single element directly as it's trivially the minimum.

Array is not rotated (already sorted in ascending order)

How to Handle:

The binary search should still converge to the first element as the minimum.

Array with all identical elements

How to Handle:

The algorithm should correctly handle the case where the left and right values are equal, potentially requiring linear search within that range.

Array with many duplicate elements concentrated in a small section

How to Handle:

The algorithm's efficiency might degrade to O(n) in the worst-case scenario where many elements are the same, and a linear search is needed.

Integer overflow during midpoint calculation

How to Handle:

Use `mid = left + (right - left) / 2` to avoid potential integer overflow.

Very large array (memory constraints)

How to Handle:

The binary search algorithm already has logarithmic space complexity, making it suitable for large arrays, but external memory solutions could be considered if the array exceeds available memory.

Array rotated such that the minimum element is at the very beginning or very end

How to Handle:

The binary search logic must correctly handle these rotation extremes to find the true minimum.

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:

Can the input array contain duplicate values, and if so, how should they be handled?
What is the expected return value if the input array is empty or null?
Are the numbers in the array integers, or could they be floating-point numbers?
Is the array guaranteed to be rotated? In other words, could it already be sorted in ascending order?
Is there a constraint on the range of integer values within the array?

Brute Force Solution

Approach

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

Look at the first number in the list. This is our current smallest number.
Now, look at the next number in the list.
If this new number is smaller than our current smallest number, replace our current smallest number with this new number.
Keep doing this for every number in the list: comparing each number to our current smallest number and replacing it if necessary.
Once you've looked at every number in the list, the 'current smallest number' you have is the minimum value in the entire list.

Code Implementation

def find_minimum_brute_force(numbers):
    # Initialize minimum with the first element
    current_minimum = numbers[0]

    for index in range(1, len(numbers)):
        # Compare current element with the current minimum
        if numbers[index] < current_minimum:

            # Update current_minimum if a smaller element is found
            current_minimum = numbers[index]

    return current_minimum

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Start by looking at the first and last number in the given set of numbers.
If the last number is bigger than the first number, then the numbers are already sorted, and the first number is the smallest.
If the last number is the same as the first number, remove one of the duplicate numbers from consideration and start again.
Otherwise, look at the number in the middle.
If the middle number is bigger than the last number, the smallest number must be somewhere after the middle, so focus only on that part of the set.
If the middle number is smaller than the last number, the smallest number must be the middle or somewhere before it, so focus only on that part of the set.
Keep repeating this process of elimination until only one number is left. That number will be the smallest.

Code Implementation

def find_minimum_in_rotated_sorted_array_ii(numbers):
    start_index = 0
    end_index = len(numbers) - 1

    while start_index < end_index:
        # If already sorted, the first element is the minimum.
        if numbers[end_index] > numbers[start_index]:
            return numbers[start_index]

        # Remove duplicate elements to shrink the search space.
        if numbers[start_index] == numbers[end_index]:
            end_index -= 1

            continue

        middle_index = (start_index + end_index) // 2

        # The minimum must be in the right half.
        if numbers[middle_index] > numbers[end_index]:
            start_index = middle_index + 1

        # The minimum must be in the left half or is the middle.
        else:
            end_index = middle_index

    return numbers[start_index]

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty array	Return a default value such as positive infinity or throw an exception as there is no minimum.
Array with one element	Return the single element directly as it's trivially the minimum.
Array is not rotated (already sorted in ascending order)	The binary search should still converge to the first element as the minimum.
Array with all identical elements	The algorithm should correctly handle the case where the left and right values are equal, potentially requiring linear search within that range.
Array with many duplicate elements concentrated in a small section	The algorithm's efficiency might degrade to O(n) in the worst-case scenario where many elements are the same, and a linear search is needed.
Integer overflow during midpoint calculation	Use `mid = left + (right - left) / 2` to avoid potential integer overflow.
Very large array (memory constraints)	The binary search algorithm already has logarithmic space complexity, making it suitable for large arrays, but external memory solutions could be considered if the array exceeds available memory.
Array rotated such that the minimum element is at the very beginning or very end	The binary search logic must correctly handle these rotation extremes to find the true minimum.

Empty array

How to Handle:

Return a default value such as positive infinity or throw an exception as there is no minimum.

Array with one element

How to Handle:

Return the single element directly as it's trivially the minimum.

Array is not rotated (already sorted in ascending order)

How to Handle:

The binary search should still converge to the first element as the minimum.

Array with all identical elements

How to Handle:

The algorithm should correctly handle the case where the left and right values are equal, potentially requiring linear search within that range.

Array with many duplicate elements concentrated in a small section

How to Handle:

The algorithm's efficiency might degrade to O(n) in the worst-case scenario where many elements are the same, and a linear search is needed.

Integer overflow during midpoint calculation

How to Handle:

Use `mid = left + (right - left) / 2` to avoid potential integer overflow.

Very large array (memory constraints)

How to Handle:

The binary search algorithm already has logarithmic space complexity, making it suitable for large arrays, but external memory solutions could be considered if the array exceeds available memory.

Array rotated such that the minimum element is at the very beginning or very end

How to Handle:

The binary search logic must correctly handle these rotation extremes to find the true minimum.