Find Minimum in Rotated Sorted Array

▶

Steps

setup

Initialize pointers

Set left pointer to 0 and right pointer to the last index of the array. Calculate the length of the array.

💡 Initialization sets the boundaries for the binary search over the entire array.

Line:

left, right = 0, len(nums) - 1
n = len(nums)

💡 The entire array is the initial search space for the minimum element.

compare

Calculate mid index

Calculate mid as the floor of (left + right) / 2, which is 2. Identify previous and next indices relative to mid.

💡 Midpoint divides the current search space to check for the pivot point.

Line:

mid = (left + right) // 2
prev = (mid - 1 + n) % n
next_ = (mid + 1) % n

💡 Mid index 2 points to element 5, which will be compared with neighbors to detect pivot.

compare

Check if mid element is smaller than previous element

Compare nums[mid] (5) with nums[prev] (4). Since 5 is not smaller than 4, this condition is false.

💡 If mid element is smaller than previous, it is the minimum pivot; checking this first helps detect pivot quickly.

Line:

if nums[mid] < nums[prev]:
    return nums[mid]

💡 Mid element is not the pivot point because it is not smaller than its previous element.

compare

Check if mid element is greater than next element

Compare nums[mid] (5) with nums[next_] (1). Since 5 is greater than 1, the next element is the minimum pivot.

💡 If mid element is greater than next, the next element is the minimum pivot; this detects the rotation point.

Line:

if nums[mid] > nums[next_]:
    return nums[next_]

💡 The pivot is found at index 3 with value 1, the minimum element.

prune

Move left pointer to mid + 1

Since mid element (5) is greater than or equal to left element (3), move left pointer to mid + 1 (3) to search right half.

💡 This step narrows the search space when pivot is not found at mid or next element.

Line:

if nums[mid] >= nums[left]:
    left = mid + 1

💡 When mid is greater or equal to left, minimum must be in right half.

compare

Update mid after moving left pointer

Calculate new mid as (3 + 4) // 2 = 3. Identify previous and next indices for mid=3.

💡 Recalculate mid to continue searching in the reduced search space.

Line:

mid = (left + right) // 2
prev = (mid - 1 + n) % n
next_ = (mid + 1) % n

💡 Mid now points to index 3, which is the suspected pivot location.

compare

Check if mid element is smaller than previous element at new mid

Compare nums[mid] (1) with nums[prev] (5). Since 1 is smaller than 5, mid is the minimum element.

💡 This confirms the pivot point where the rotation happened.

Line:

if nums[mid] < nums[prev]:
    return nums[mid]

💡 Minimum element found at index 3 with value 1.

prune

Return minimum element found at mid

Return the element at mid index 3, which is 1, as the minimum element.

💡 Returning the pivot element completes the search.

Line:

return nums[mid]

💡 Minimum element 1 is confirmed and returned.

prune

Final state with answer

The algorithm ends with the minimum element 1 found at index 3 in the array.

💡 Final confirmation of the answer and total steps taken.

Line:

return nums[mid]

💡 The minimum element is at index 3 with value 1.

prune

Summary and conclusion

The minimum element 1 is found at index 3, confirming the pivot detection and binary search narrowing.

💡 Understanding the final position of pointers and the minimum element solidifies the algorithm's correctness.

💡 The algorithm efficiently finds the minimum element in a rotated sorted array by detecting the pivot.

def find_min(nums):
    left, right = 0, len(nums) - 1  # STEP 1
    n = len(nums)  # STEP 1
    while left <= right:  # STEP 2 onward
        mid = (left + right) // 2  # STEP 2,6
        prev = (mid - 1 + n) % n  # STEP 2,6
        next_ = (mid + 1) % n  # STEP 2,6
        if nums[mid] < nums[prev]:  # STEP 3,7
            return nums[mid]  # STEP 7,8
        if nums[mid] > nums[next_]:  # STEP 4
            return nums[next_]  # STEP 4
        if nums[mid] >= nums[left]:  # STEP 5
            left = mid + 1  # STEP 5
        else:
            right = mid - 1
    return nums[0]

📊

Find Minimum in Rotated Sorted Array - Watch the Algorithm Execute, Step by Step

Watching each pointer movement and comparison helps you understand how the algorithm efficiently detects the pivot point where the rotation happened, revealing the minimum element.

lo

3

0

4

1

5

2

1

3

hi

2

4

Next: lo=0 hi=4

lo

3

0

4

1

mid

5

2

1

3

hi

2

4

mid[2]=5 - mid element is 5

Next: lo=0 hi=4

lo

3

0

4

1

mid

5

2

1

3

hi

2

4

mid[2]=5 - 5 >= 4, not pivot

Next: lo=0 hi=4

lo

3

0

4

1

mid

5

2

1

3

hi

2

4

mid[2]=5 - 5 > 1, pivot found at next index

Next: lo=0 hi=4

3

0

4

1

mid

5

2

lo

1

3

hi

2

4

mid[2]=5 - 5 >= 3, move left to mid+1=3

Next: lo=3 hi=4

3

0

4

1

5

2

lo/mid

1

3

hi

2

4

mid[3]=1 - mid element is 1

Next: lo=3 hi=4

3

0

4

1

5

2

lo/mid

1

3

hi

2

4

mid[3]=1 - 1 < 5, pivot found at mid

Next: lo=3 hi=4

3

0

4

1

5

2

lo/mid

1

3

hi

2

4

mid[3]=1 - minimum element 1 returned

Next: lo=3 hi=4

3

0

4

1

5

2

lo/mid

1

3

hi

2

4

mid[3]=1 - final answer

Next: lo=3 hi=4

3

0

4

1

5

2

lo/mid

1

3

hi

2

4

mid[3]=1 - final answer confirmed

Next: lo=3 hi=4

Key Takeaways

✓ The pivot (minimum) element is detected by comparing mid element with its neighbors, not just by comparing mid with left or right.

This insight is hard to see from code alone because it requires understanding the rotation property and how neighbors reveal the pivot.

✓ Moving the left pointer when mid element is greater or equal to left element effectively discards the sorted left half, focusing search on the rotated right half.

Visualizing pointer movement clarifies why the search space shrinks correctly and efficiently.

✓ The algorithm terminates as soon as the pivot is found, either at mid or next element, avoiding unnecessary full search.

Seeing the early return conditions in action helps understand the algorithm's optimality.

Practice

1. The following code attempts to find the minimum in a rotated sorted array with duplicates. Identify the bug:

def find_min(nums):
    low, high = 0, len(nums) - 1
    while low < high:
        if nums[low] < nums[high]:
            return nums[low]
        mid = (low + high) / 2  # line 6
        if nums[mid] > nums[high]:
            low = mid + 1
        elif nums[mid] < nums[high]:
            high = mid
        else:
            high -= 1
    return nums[low]

What is the bug?

medium

A. Line 6 uses floating point division instead of integer division for mid calculation.

B. The condition nums[low] < nums[high] should be nums[low] <= nums[high].

C. The decrement of high in the else block should be increment of low instead.

D. Returning nums[low] at the end should be returning nums[mid].

Solution

1. Step 1: Examine mid calculation

   Line 6 uses (low + high) / 2 which results in a float in Python 3, causing an error when used as an index.

2. Step 2: Impact of bug

   Using float index causes runtime error or unexpected behavior; integer division (//) is required.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Mid must be integer index [OK]

Hint: Mid index must be integer, not float [OK]

Common Mistakes:

• Using / instead of // for mid
• Returning nums[mid] instead of nums[low]

2. The following code attempts to find the k-th smallest number in an m x n multiplication table. Which line contains a subtle bug that can cause incorrect results for large inputs?

medium

A. Line 4: count = 0

B. Line 6: count += x // i # missing min with n

C. Line 8: if count >= k:

D. Line 13: mid = (low + high) // 2

Solution

1. Step 1: Identify counting logic

   The counting function must cap counts per row by n, since each row has only n elements.

2. Step 2: Analyze line 6

   Line 6 adds x // i without min(n, x // i), causing overcounting when x // i > n, leading to incorrect binary search decisions.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Bug causes wrong counts and incorrect final answer [OK]

Hint: Count per row capped by n to avoid overcounting [OK]

Common Mistakes:

• Forgetting min(n, x//i) in counting
• Incorrect mid calculation

3. Examine the following buggy code that attempts to search a target in a 2D matrix using the staircase search approach starting from the top-left corner. Identify the line containing the subtle bug that causes incorrect behavior or infinite loops.

medium

A. Line 9: Incrementing row when element is less than target

B. Line 7: Using '<' instead of '<=' in while condition

C. Line 11: Decrementing col without boundary check

D. Line 3: Starting at top-left corner instead of top-right

Solution

1. Step 1: Analyze starting point

   Starting at top-left corner breaks the staircase search logic because we cannot eliminate rows or columns correctly.

2. Step 2: Check pointer movements

   Moving row down when current < target and col left when current > target only works if starting at top-right corner.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Starting at top-left causes infinite loops or wrong results [OK]

Hint: Staircase search must start at top-right corner [OK]

Common Mistakes:

• Starting at top-left or bottom-left corner
• Not checking empty matrix
• Moving pointers in wrong directions

4. Suppose the array is no longer sorted but you still need to find the first and last positions of a target value. Which approach is correct and efficient?

hard

A. Use a linear scan to find first and last occurrences directly

B. Sort the array first, then apply modified binary search to find positions

C. Use the same modified binary search approach since it works on any array

D. Use a hash map to store all indices of each value, then retrieve target positions

Solution

1. Step 1: Recognize that binary search requires sorted array

   Without sorting, binary search cannot guarantee correct positions.

2. Step 2: Evaluate alternatives

   Sorting changes indices, so linear scan or hash map are options; linear scan is simplest and O(n).

3. Step 3: Compare efficiency and correctness

   Linear scan finds first and last positions in one pass without modifying array.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Binary search requires sorted input; linear scan works otherwise [OK]

Hint: Binary search needs sorted array; linear scan works otherwise [OK]

Common Mistakes:

• Trying binary search on unsorted array
• Sorting and losing original indices
• Overcomplicating with hash maps

5. Suppose the array can contain duplicate elements and the problem is modified so that elements can be reused multiple times when selecting the k closest elements to x. Which modification to the optimal binary search approach is necessary to handle this variant correctly?

hard

A. Use a priority queue to repeatedly pick the closest element allowing duplicates, instead of binary search.

B. Modify binary search to consider overlapping windows and allow repeated elements in the window.

C. No change needed; the existing binary search on window boundaries works as is.

D. Switch to a dynamic programming approach to track counts of reused elements.

Solution

1. Step 1: Understand reuse of elements

   Allowing reuse means the window concept breaks because elements can appear multiple times, invalidating fixed window binary search.

2. Step 2: Identify suitable approach

   A priority queue (min-heap) can repeatedly select the closest element to x, allowing duplicates and dynamic selection.

3. Step 3: Why other options fail

   Binary search on windows assumes unique elements and fixed windows; DP is unnecessary and inefficient here.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Priority queue supports repeated selection, unlike fixed window binary search [OK]

Hint: Reuse breaks fixed window; priority queue handles duplicates [OK]

Common Mistakes:

• Assuming binary search window works with reuse
• Overcomplicating with DP when simpler heap suffices
• Ignoring duplicates in window boundaries