Find Minimum in Rotated Sorted Array in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Find minimum in rotated sorted array - simple case

What is the output of the following Go code that finds the minimum element in a rotated sorted array?

DSA Go

package main
import "fmt"

func findMin(nums []int) int {
    left, right := 0, len(nums)-1
    for left < right {
        mid := left + (right-left)/2
        if nums[mid] > nums[right] {
            left = mid + 1
        } else {
            right = mid
        }
    }
    return nums[left]
}

func main() {
    arr := []int{4,5,6,7,0,1,2}
    fmt.Println(findMin(arr))
}

A 0

B 1

C 4

D 7

💡 Hint

Think about how the binary search narrows down the smallest element in a rotated array.

The code uses binary search to find the smallest element. Since the array is rotated, the smallest element is the pivot point. The code compares middle and right elements to decide which half to search next. The minimum is 0.

❓ Predict Output

intermediate

Find minimum in rotated sorted array - no rotation

What is the output of the following Go code when the array is not rotated?

DSA Go

package main
import "fmt"

func findMin(nums []int) int {
    left, right := 0, len(nums)-1
    for left < right {
        mid := left + (right-left)/2
        if nums[mid] > nums[right] {
            left = mid + 1
        } else {
            right = mid
        }
    }
    return nums[left]
}

func main() {
    arr := []int{1,2,3,4,5,6,7}
    fmt.Println(findMin(arr))
}

A 4

B 7

C 1

D 0

💡 Hint

If the array is sorted and not rotated, the first element is the smallest.

Since the array is sorted and not rotated, the smallest element is the first element, which is 1.

🔧 Debug

advanced

Identify the error in minimum finder for rotated array

What error does the following Go code produce when trying to find the minimum in a rotated sorted array?

DSA Go

package main
import "fmt"

func findMin(nums []int) int {
    left, right := 0, len(nums)-1
    for left <= right {
        mid := left + (right-left)/2
        if nums[mid] > nums[right] {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return nums[left]
}

func main() {
    arr := []int{4,5,6,7,0,1,2}
    fmt.Println(findMin(arr))
}

A infinite loop

B 0

C 7

D runtime error: index out of range

💡 Hint

Check how the pointers move and if they can go out of bounds.

The code decreases right by 1 even when it might skip the minimum element, causing left to go beyond array length and causing an index out of range error.

🧠 Conceptual

advanced

Why binary search works for finding minimum in rotated sorted array

Why does binary search work to find the minimum element in a rotated sorted array?

A Because the minimum element is always at the middle index

B Because the array is partially sorted and the minimum is the only point where order breaks

C Because the array is fully sorted and binary search always works on sorted arrays

D Because the array contains duplicates that help locate the minimum

💡 Hint

Think about the property of rotated sorted arrays and how order changes.

Binary search works because the rotated array is sorted except at the pivot point where the minimum lies. This break in order helps decide which half to search.

❓ Predict Output

expert

Find minimum in rotated sorted array with duplicates

What is the output of the following Go code that finds the minimum element in a rotated sorted array which may contain duplicates?

DSA Go

package main
import "fmt"

func findMin(nums []int) int {
    left, right := 0, len(nums)-1
    for left < right {
        mid := left + (right-left)/2
        if nums[mid] > nums[right] {
            left = mid + 1
        } else if nums[mid] < nums[right] {
            right = mid
        } else {
            right--
        }
    }
    return nums[left]
}

func main() {
    arr := []int{2,2,2,0,1,2}
    fmt.Println(findMin(arr))
}

A 0

B 1

C 2

D runtime error

💡 Hint

Duplicates require careful handling to avoid skipping the minimum.

The code handles duplicates by reducing right when nums[mid] equals nums[right], ensuring the minimum is found. The minimum is 0.

Practice

1. What is the main idea behind finding the minimum element in a rotated sorted array?

easy

A. Use a hash map to store elements and find minimum

B. Sort the array again to find the minimum

C. Traverse the array linearly to find the smallest element

D. Use binary search to find the point where order breaks

Solution

1. Step 1: Understand the rotated sorted array property

   A rotated sorted array is sorted but rotated at some pivot point, causing a break in order.

2. Step 2: Use binary search to find the break point

   Binary search helps find the point where the order breaks, which is where the minimum element lies.

3. Final Answer:

   Use binary search to find the point where order breaks -> Option D

4. Quick Check:

   Binary search finds minimum efficiently [OK]

Hint: Look for the pivot where order breaks using binary search [OK]

Common Mistakes:

• Trying to sort the array again wastes time
• Using linear search ignores the sorted property
• Using extra space unnecessarily

2. Which Go code snippet correctly initializes variables for binary search to find minimum in a rotated sorted array nums?

easy

A. start, end := -1, len(nums)-1

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

C. start, end := 1, len(nums)

D. start, end := 0, len(nums)

Solution

1. Step 1: Understand array indexing in Go

   Arrays are zero-indexed, so start should be 0 and end should be last index (length - 1).

2. Step 2: Check each option for correct initialization

   start, end := 0, len(nums)-1 correctly sets start=0 and end=len(nums)-1, which is valid for binary search.

3. Final Answer:

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

4. Quick Check:

   Correct index range initialization [OK]

Hint: Start at 0 and end at length minus one for array indices [OK]

Common Mistakes:

• Using length as end index causes out-of-range errors
• Starting at 1 misses the first element
• Negative start index is invalid

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

nums := []int{4,5,6,7,0,1,2}
start, end := 0, len(nums)-1
for start < end {
  mid := (start + end) / 2
  if nums[mid] > nums[end] {
    start = mid + 1
  } else {
    end = mid
  }
}
fmt.Println(nums[start])

medium

A. 0

B. 4

C. 7

D. 2

Solution

1. Step 1: Trace the binary search loop

   Initial start=0, end=6. Mid=(0+6)/2=3, nums[3]=7 > nums[6]=2, so start=4.

2. Step 2: Continue loop until start meets end

   Now start=4, end=6. Mid=(4+6)/2=5, nums[5]=1 <= nums[6]=2, so end=5. Next mid=(4+5)/2=4, nums[4]=0 <= nums[5]=1, so end=4. Loop ends when start=4, end=4.

3. Final Answer:

   0 -> Option A

4. Quick Check:

   Minimum element found at index 4 is 0 [OK]

Hint: Compare mid with end to decide search side [OK]

Common Mistakes:

• Confusing mid calculation causing infinite loop
• Incorrectly updating start or end pointers
• Printing nums[end] instead of nums[start]

4. Identify the bug in this Go code to find minimum in rotated sorted array nums:

start, end := 0, len(nums)-1
for start <= end {
  mid := (start + end) / 2
  if nums[mid] > nums[end] {
    start = mid
  } else {
    end = mid - 1
  }
}
fmt.Println(nums[start])

medium

A. All of the above

B. Loop condition should be start < end, not <=

C. end should be set to mid, not mid - 1

D. start should be set to mid + 1, not mid

Solution

1. Step 1: Analyze loop condition and pointer updates

   The loop uses start <= end which can cause infinite loop when start == end. Also, start = mid does not move start forward properly, and end = mid - 1 skips the mid element incorrectly.

2. Step 2: Correct the loop and pointer updates

   Loop should be start < end. When nums[mid] > nums[end], start = mid + 1 to move forward. Else, end = mid to include mid in next search.

3. Final Answer:

   All of the above -> Option A

4. Quick Check:

   Proper loop and pointer updates avoid infinite loops [OK]

Hint: Use start < end and adjust pointers by +1 or no change [OK]

Common Mistakes:

• Using <= causes infinite loops
• Not moving start pointer forward correctly
• Skipping mid element by subtracting 1 from end

5. Given a rotated sorted array nums that may contain duplicates, which modification is needed in the binary search approach to find the minimum element?

hard

A. Ignore duplicates and apply normal binary search

B. If nums[mid] == nums[end], increase start by 1 to skip duplicate

C. If nums[mid] == nums[end], reduce end by 1 to skip duplicate

D. Sort the array first to handle duplicates

Solution

1. Step 1: Understand duplicates affect binary search

   Duplicates can cause nums[mid] == nums[end], making it unclear which side to search.

2. Step 2: Modify binary search to handle duplicates

   When nums[mid] == nums[end], safely reduce end by 1 to skip duplicate without missing minimum.

3. Final Answer:

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

4. Quick Check:

   Handle duplicates by shrinking search space carefully [OK]

Hint: When equal, reduce end to skip duplicates safely [OK]

Common Mistakes:

• Ignoring duplicates causes wrong results
• Increasing start instead of reducing end misses minimum
• Sorting wastes time and is unnecessary