154. Find Minimum in Rotated Sorted Array II

HardArrayBinary Search
Leetcode Link

Problem Description

The problem presents an array that has been sorted in ascending order but then has been rotated between 1 and n times. Rotating the array means moving the last element to the front. For example, if we have an array [1, 2, 3, 4, 5] and rotate it once, it becomes [5, 1, 2, 3, 4]. The task is to find the minimum element in this rotated array efficiently, even though the array may contain duplicates.

Intuition

Given that the array is initially sorted before the rotations, we can use binary search to find the minimum element. Here's the thought process:

  • If the middle element is greater than the rightmost element, the smallest value must be to the right of the middle. This is because the elements are originally sorted in ascending order, so if there's a large number in the middle, the array must have been rotated at some point after that number.
  • If the middle element is less than the rightmost element, the smallest value must be at the middle or to the left of the middle.
  • If the middle element equals the rightmost element, we can't determine the position of the minimum element, but we can safely reduce the search space by ignoring the rightmost element since even if it is the minimum, it will exist as a duplicate elsewhere in the list.

The solution consistently halves the search interval, which means that the time complexity would be better than linear - in fact, it's O(log n) in the best case. However, when duplicates are present, and we encounter the same values at both the middle and end of our search range, we must decrease our search range in smaller steps, which in the worst case could result in an O(n) time complexity when all elements are duplicates. The approach is both practical and efficient for most cases.

Learn more about Binary Search patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Solution Approach

The solution uses a classic binary search pattern to find the minimum element. The key insight of binary search is to repeatedly divide the search interval in half. If the interval can be divided, it suggests that through a comparison in each step, one can eliminate half of the remaining possibilities. Here's how it is applied in this context:

  • We start by setting two pointers, left at 0 and right at len(nums) - 1, to represent the search space's bounds.
  • While left is less than right, we are not done searching:
    • We calculate mid by taking the average of left and right, effectively dividing the search space in half.
    • If nums[mid] > nums[right], we know that the smallest value must be to the right of mid, so we set left to mid + 1.
    • If nums[mid] < nums[right], we then know that the smallest value is either at mid or to its left. So, we move right to mid.
    • If nums[mid] is equal to nums[right], we cannot be certain where the smallest value is, but we can reduce the search space by decrements right by 1. This is because even if nums[right] is the smallest value, it will not be lost as the property of the array being sorted (aside from the rotation) means a duplicate must exist to the left.
  • Once left equals right, the loop terminates and left (or right, since they are equal) points to the smallest element.

The code handles the presence of duplicates gracefully, ensuring the search space is narrowed even when the value of nums[mid] is equal to nums[right]. While binary search usually has an O(log n) complexity, this variant's complexity can degrade to O(n) in the worst-case scenario when there are many identical elements.

The reason why this approach is efficient is because it strives to minimize the number of elements considered at each step, allowing for an early exit in many cases as compared to a brute-force linear search that would always take O(n) time.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the two traversal algorithms (BFS and DFS) can be used to find whether two nodes are connected?

Example Walkthrough

Let's consider the rotated sorted array nums = [4, 5, 6, 7, 0, 1, 2] and walk through how the solution approach finds the minimum element.

  1. Set the left pointer to 0 and the right pointer to 6, since len(nums) - 1 = 6. Our array now looks like this: 4, 5, 6, 7, 0, 1, 2, with left pointing to 4 and right pointing to 2.

  2. Since left is less than right, we calculate the middle index mid = (left + right) // 2, which is (0 + 6) // 2 = 3. The value at this index is 7.

  3. Now we compare the middle element nums[mid] with nums[right]:

    • nums[mid] is 7 and nums[right] is 2. Since 7 > 2, we know the smallest element is to the right of mid. We set left to mid + 1, which makes left 4.

  4. The array between indices 4 and 6 is now our search space: 0, 1, 2. We repeat step 2 and find a new middle at mid = (4 + 6) // 2 = 5. The number at index 5 is 1.

  5. We now compare the nums[mid] with nums[right] again:

    • nums[mid] is 1 and nums[right] is 2. Since 1 < 2, we know the smallest element is at mid or to the left of mid. We move right to mid, making right 5.

  6. Our search space is now just [0, 1]. Calculating mid gives us (4 + 5) // 2 = 4. At nums[mid], we have a 0.

  7. We compare nums[mid] with nums[right]:

    • nums[mid] is 0 and nums[right] is 1. Since 0 < 1, we continue to narrow the search and move right to mid, leaving us with right being 4.

  8. With both left and right pointing to the same index, which is 4, the loop terminates. We have left equals right equals 4, and nums[left] or nums[right] gives us the minimum element, which is 0.

In this example, we successfully found the minimum element of the rotated sorted array using the binary search method, demonstrating the efficiency of the approach. The key takeaway is the decision-making at each step to reduce the search space, which is much quicker than a linear search especially when dealing with a larger array.

Solution Implementation

1class Solution:
2    def findMin(self, nums: List[int]) -> int:
3        # Initialize the left and right pointers to the start and end of the list respectively
4        left, right = 0, len(nums) - 1
5      
6        # Continue searching while the left pointer is less than the right pointer
7        while left < right:
8            # Find the middle index by using bitwise right shift operation (equivalent to integer division by 2)
9            mid = (left + right) >> 1
10          
11            # If the middle element is greater than the element at the right pointer...
12            if nums[mid] > nums[right]:
13                # ... the smallest value must be to the right of mid, so move the left pointer to mid + 1
14                left = mid + 1
15            # If the middle element is less than the element at the right pointer...
16            elif nums[mid] < nums[right]:
17                # ... the smallest value is at mid or to the left of mid, so move the right pointer to mid
18                right = mid
19            # If the middle element is equal to the element at the right pointer...
20            else:
21                # ... we can't be sure of the smallest, but we can reduce the search space by decrementing right pointer
22                right -= 1
23      
24        # When the left pointer equals the right pointer, we've found the minimum, so return the element at left pointer
25        return nums[left]
26
1class Solution {
2    public int findMin(int[] nums) {
3        int left = 0; // Initialize the left boundary of the search
4        int right = nums.length - 1; // Initialize the right boundary of the search
5
6        // Perform a modified binary search
7        while (left < right) {
8            // Compute the middle index of the current search interval
9            int mid = (left + right) >>> 1;
10
11            // If the middle element is greater than the rightmost element,
12            // the smallest value must be in the right part of the array.
13            if (nums[mid] > nums[right]) {
14                left = mid + 1;
15            }
16            // Else if the middle element is less than the rightmost element,
17            // the smallest value must be in the left part of the array.
18            else if (nums[mid] < nums[right]) {
19                right = mid;
20            } 
21            // If elements at mid and right are equal, we can't be sure of the smallest element's position,
22            // but we can safely discard the rightmost element as the answer could still be to the left of it.
23            else {
24                right--;
25            }
26        }
27
28        // After the loop, the left index will point to the smallest element in the rotated array
29        return nums[left];
30    }
31}
32
1#include <vector>
2
3class Solution {
4public:
5    int findMin(std::vector<int>& nums) {
6        // Initialize the search boundaries.
7        int left = 0;
8        int right = nums.size() - 1;
9
10        // Continue searching as long as the left boundary is less than the right boundary.
11        while (left < right) {
12            // Find the middle index.
13            int mid = left + (right - left) / 2; // Avoid potential overflow
14
15            // If the middle element is greater than the right-most element,
16            // the smallest value is to the right of mid; hence, update 'left'.
17            if (nums[mid] > nums[right]) {
18                left = mid + 1;
19            }
20            // If the middle element is less than the right-most element,
21            // the smallest value is at mid or to the left of mid; hence, update 'right'.
22            else if (nums[mid] < nums[right]) {
23                right = mid;
24            }
25            // If the middle element is equal to the right-most element,
26            // we can't decide the side of the minimum element, decrease 'right' to skip this duplicate.
27            else {
28                --right;
29            }
30        }
31
32        // After the loop finishes, 'left' will point to the smallest element.
33        return nums[left];
34    }
35};
36
1/**
2 * Find the minimum value in a rotated sorted array.
3 * The array may contain duplicates.
4 * This function uses a binary search approach.
5 * @param nums An array of numbers, rotated sorted order, possibly containing duplicates
6 * @returns The minimum value found in the array
7 */
8function findMin(nums: number[]): number {
9    // Initialize pointers for the binary search
10    let leftIndex = 0;
11    let rightIndex = nums.length - 1;
12
13    // Perform binary search
14    while (leftIndex < rightIndex) {
15        // Calculate the middle index of the current search range
16        const midIndex = leftIndex + Math.floor((rightIndex - leftIndex) / 2);
17
18        // If the middle element is greater than the rightmost element, the minimum is to the right
19        if (nums[midIndex] > nums[rightIndex]) {
20            leftIndex = midIndex + 1;
21        }
22        // If the middle element is less than the rightmost element, the minimum is to the left or at midIndex
23        else if (nums[midIndex] < nums[rightIndex]) {
24            rightIndex = midIndex;
25        }
26        // If the middle element is equal to the rightmost element, we can't decide where the minimum is, move the right pointer left
27        else {
28            rightIndex--;
29        }
30    }
31
32    // At the end of the loop, leftIndex is the smallest value
33    return nums[leftIndex];
34}
35
Not Sure What to Study? Take the 2-min Quiz：

Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?

Time and Space Complexity

The provided code snippet is designed to find the minimum element in a rotated sorted array, handling duplicates. The algorithm employs a binary search technique.

Time Complexity:

The worst-case time complexity of this code is O(n). In the average and best case, where the majority of elements are not duplicates, it approaches O(log n). However, in the worst case, when the algorithm must decrement the right pointer one by one due to the presence of identical elements at the end of the array (else: right -= 1), the complexity degrades to O(n). This happens when duplicates are present and cannot be ruled out by a regular binary search.

Space Complexity:

The space complexity of the code is O(1). No additional space is utilized that is dependent on the input size; only a constant amount of extra space is used for variables like left, right, and mid.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)

Recommended Readings

Binary Search Speedrun

Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫