Find Minimum in Rotated Sorted Array in DSA Python - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to start binary search with the correct left pointer.

DSA Python

def find_min(nums):
    left = [1]
    right = len(nums) - 1
    while left < right:
        mid = (left + right) // 2
        if nums[mid] > nums[right]:
            left = mid + 1
        else:
            right = mid
    return nums[left]

Drag options to blanks, or click blank then click option'

A0

B1

Clen(nums)

D-1

Attempts:

3 left

💡 Hint

Common Mistakes

Starting left pointer at 1 or negative index causes missing elements.

Starting left pointer at length of array causes index error.

The left pointer should start at index 0 to cover the entire array.

2fill in blank

medium

Complete the code to correctly update the left pointer when mid element is greater than right element.

DSA Python

def find_min(nums):
    left = 0
    right = len(nums) - 1
    while left < right:
        mid = (left + right) // 2
        if nums[mid] > nums[right]:
            left = [1]
        else:
            right = mid
    return nums[left]

Drag options to blanks, or click blank then click option'

Amid

Bleft + 1

Cright

Dmid + 1

Attempts:

3 left

💡 Hint

Common Mistakes

Setting left to mid causes infinite loop when left == mid.

Setting left to right or left + 1 without condition causes wrong results.

If nums[mid] > nums[right], the minimum must be to the right of mid, so left moves to mid + 1.

3fill in blank

hard

Fix the error in updating the right pointer when mid element is less than or equal to right element.

DSA Python

def find_min(nums):
    left = 0
    right = len(nums) - 1
    while left < right:
        mid = (left + right) // 2
        if nums[mid] > nums[right]:
            left = mid + 1
        else:
            right = [1]
    return nums[left]

Drag options to blanks, or click blank then click option'

Amid + 1

Bright - 1

Cmid

Dleft

Attempts:

3 left

💡 Hint

Common Mistakes

Setting right to mid + 1 skips mid and may miss minimum.

Setting right to right - 1 can cause infinite loop or miss minimum.

When nums[mid] <= nums[right], the minimum can be at mid, so right moves to mid.

4fill in blank

hard

Fill both blanks to create a dictionary comprehension that maps each number to its square only if the number is less than 5.

DSA Python

nums = [1, 3, 5, 7, 9]
squares = [1]: [2] for num in nums if num < 5

Drag options to blanks, or click blank then click option'

Anum

Bnum**2

Cnum*2

Dnum + 1

Attempts:

3 left

💡 Hint

Common Mistakes

Using multiplication by 2 instead of square.

Using addition instead of square for values.

The dictionary comprehension uses num as key and num squared as value for nums less than 5.

5fill in blank

hard

Fill all three blanks to create a dictionary comprehension that maps uppercase letters to their ASCII values only if the ASCII value is greater than 65.

DSA Python

letters = ['a', 'B', 'C', 'd', 'E']
ascii_map = [1]: [2] for letter in letters if ord(letter) [3] 65

Drag options to blanks, or click blank then click option'

Aletter.upper()

Bord(letter)

C>

D<

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<' instead of '>' in the condition.

Using letter instead of letter.upper() as key.

The comprehension maps uppercase letters to their ASCII values where ASCII is greater than 65.

Practice

1. What is the main goal when finding the minimum in a rotated sorted array like [4, 5, 6, 7, 0, 1, 2]?

easy

A. To find the smallest number where the rotation happened

B. To find the largest number in the array

C. To sort the array again

D. To count how many times the array was rotated

Solution

1. Step 1: Understand the rotated sorted array

   A rotated sorted array is originally sorted but then shifted. The smallest number is where the rotation happened.

2. Step 2: Identify the minimum element

   The minimum element is the smallest number, marking the rotation point.

3. Final Answer:

   To find the smallest number where the rotation happened -> Option A

4. Quick Check:

   Minimum = smallest number at rotation [OK]

Hint: Minimum is the smallest number where order breaks [OK]

Common Mistakes:

• Looking for the largest number instead
• Trying to sort the array again
• Counting rotations instead of finding minimum

2. Which of the following Python code snippets correctly initializes variables to find the minimum in a rotated sorted array nums using binary search?

easy

A. start, end = len(nums), 0

B. start = 1; end = len(nums)

C. start, end = 0, len(nums) - 1

D. start = -1; end = len(nums) + 1

Solution

1. Step 1: Understand binary search initialization

   Binary search uses start at 0 and end at last index (length - 1).

2. Step 2: Check each option

   start, end = 0, len(nums) - 1 correctly sets start=0 and end=len(nums)-1. Others have invalid ranges.

3. Final Answer:

   start, end = 0, len(nums) - 1 -> Option C

4. Quick Check:

   Binary search range = start=0, end=length-1 [OK]

Hint: Start at 0, end at last index for binary search [OK]

Common Mistakes:

• Setting start or end outside valid index range
• Using length instead of length - 1 for end
• Starting from 1 instead of 0

3. What will be the output of the following code snippet?

def find_min(nums):
    start, end = 0, len(nums) - 1
    while start < end:
        mid = (start + end) // 2
        if nums[mid] > nums[end]:
            start = mid + 1
        else:
            end = mid
    return nums[start]

print(find_min([3, 4, 5, 1, 2]))

medium

A. 2

B. 3

C. 5

D. 1

Solution

1. Step 1: Trace the binary search steps

   Initial array: [3,4,5,1,2], start=0, end=4 - mid=2, nums[mid]=5, nums[end]=2, 5>2 so start=mid+1=3 - now start=3, end=4 - mid=3, nums[mid]=1, nums[end]=2, 1<=2 so end=mid=3 - start=3, end=3, loop ends

2. Step 2: Return minimum element

   nums[start]=nums[3]=1 is the minimum.

3. Final Answer:

   1 -> Option D

4. Quick Check:

   Minimum found = 1 [OK]

Hint: Compare mid and end to adjust search [OK]

Common Mistakes:

• Returning nums[mid] instead of nums[start]
• Not updating start or end correctly
• Confusing > and < in condition

4. The following code is intended to find the minimum in a rotated sorted array, but it has a bug. What is the bug?

def find_min(nums):
    start, end = 0, len(nums) - 1
    while start <= end:
        mid = (start + end) // 2
        if nums[mid] > nums[end]:
            start = mid + 1
        else:
            end = mid
    return nums[start]

medium

A. The loop condition should be start < end, not start <= end

B. The return statement should be nums[end], not nums[start]

C. The mid calculation is incorrect

D. The if condition should compare nums[mid] with nums[start]

Solution

1. Step 1: Analyze the loop condition

   The loop uses start <= end, which can cause infinite loop or index errors because start can pass end.

2. Step 2: Correct loop condition for binary search

   Using start < end ensures the loop stops when start meets end, correctly locating minimum.

3. Final Answer:

   The loop condition should be start < end, not start <= end -> Option A

4. Quick Check:

   Loop condition must be start < end [OK]

Hint: Use start < end for binary search loops [OK]

Common Mistakes:

• Using <= causes infinite loops or wrong indexes
• Changing mid calculation unnecessarily
• Comparing with wrong array element

5. Given a rotated sorted array that may contain duplicates, such as [2, 2, 2, 0, 1, 2], which modification to the binary search approach helps correctly find the minimum?

hard

A. Sort the array first before searching

B. When nums[mid] == nums[end], reduce end by 1 to skip duplicate

C. Always move start to mid + 1 when nums[mid] >= nums[end]

D. Return nums[0] directly as minimum

Solution

1. Step 1: Understand duplicates affect comparison

   When nums[mid] equals nums[end], we cannot decide which side minimum is on because duplicates hide order.

2. Step 2: Skip duplicate by reducing end

   Reducing end by 1 removes one duplicate and narrows search without missing minimum.

3. Final Answer:

   When nums[mid] == nums[end], reduce end by 1 to skip duplicate -> Option B

4. Quick Check:

   Handle duplicates by shrinking end [OK]

Hint: If mid equals end, reduce end by 1 to handle duplicates [OK]

Common Mistakes:

• Assuming no duplicates and using normal binary search
• Sorting array first wastes time
• Returning first element without checking