NUHMAN.com

Introduction

LeetCode 153 asks us to find the minimum element in a rotated sorted array. The array was originally sorted in increasing order but then rotated at some unknown pivot. Our task is to efficiently find the minimum element in the array. The problem guarantees that the array contains no duplicates.

This problem can be solved efficiently using a binary search approach, taking advantage of the sorted nature of the array, even though it has been rotated.

Problem Statement

Given a rotated sorted array nums, find the minimum element.

Function Signature:

go

func findMin(nums []int) int

Approach

Key Idea:

The main idea behind solving this problem is to use binary search. A rotated sorted array has two parts:

• The left part is sorted.
• The right part is also sorted.

Given that the array is sorted, the minimum element will always be at the point where the sorted order breaks. The pivot point in the array (the point where the rotation occurs) divides the array into two sorted subarrays. The key observation is that the minimum element is the point where the first subarray ends and the second subarray starts.

We can use binary search to find this minimum element by repeatedly comparing the middle element with the rightmost element of the array:

• If the middle element is greater than the rightmost element, then the minimum is to the right of the middle element.
• If the middle element is less than or equal to the rightmost element, then the minimum is to the left or is the middle element itself.

By adjusting the search range accordingly, we can find the minimum element in O(log n) time, where n is the number of elements in the array.

Go Implementation

go

package main

import "fmt"

func findMin(nums []int) int {
    left, right := 0, len(nums)-1
    
    // Perform binary search
    for left < right {
        mid := left + (right - left) / 2
        
        // If middle element is greater than right element, the minimum must be on the right half
        if nums[mid] > nums[right] {
            left = mid + 1
        } else {
            // Otherwise, the minimum must be on the left half or at mid
            right = mid
        }
    }
    
    // Left and right will eventually point to the minimum element
    return nums[left]
}

func main() {
    // Example usage
    nums := []int{4, 5, 6, 7, 0, 1, 2}
    result := findMin(nums)
    fmt.Println("Minimum Element:", result) // Output: 0
}

Explanation of the Code:

1. Initialization:

• We initialize two pointers: left at index 0 and right at the last index of the array.

1. Binary Search Loop:

• While left < right, we compute the middle index mid of the current search range.

1. Checking the Middle Element:

• If nums[mid] > nums[right], it means the minimum element lies to the right of mid because the right side is not sorted. Therefore, we move the left pointer to mid + 1.
• Otherwise, the minimum element lies to the left of mid, including mid itself, so we move the right pointer to mid.

1. Termination Condition:

• The loop terminates when left == right, and at this point, the minimum element is nums[left].

1. Example:

• For the array nums := []int{4, 5, 6, 7, 0, 1, 2}, the binary search finds that the minimum element is 0.

Time and Space Complexity

OperationComplexityTimeO(log n)SpaceO(1)

• Time Complexity:
• The binary search reduces the search space by half at each step, so the time complexity is O(log n), where n is the length of the array.
• Space Complexity:
• We are using only a few variables (pointers), so the space complexity is O(1).

Example

Input:

go

nums := []int{4, 5, 6, 7, 0, 1, 2}

Output:

0

Explanation:

1. First iteration:

• left = 0, right = 6, mid = 3, nums[mid] = 7, nums[right] = 2
• Since nums[mid] > nums[right], the minimum must be on the right half. Therefore, left = mid + 1 = 4.

1. Second iteration:

• left = 4, right = 6, mid = 5, nums[mid] = 1, nums[right] = 2
• Since nums[mid] < nums[right], the minimum must be on the left half or at mid. Therefore, right = mid = 5.

1. Third iteration:

• left = 4, right = 5, mid = 4, nums[mid] = 0, nums[right] = 1
• Since nums[mid] < nums[right], the minimum must be on the left half or at mid. Therefore, right = mid = 4.

At this point, left == right and we return nums[left] = 0.

Final result: 0.

Why This Approach Works

• Efficiency: This binary search approach works in O(log n) time, which is much more efficient than a linear scan that would take O(n) time.
• Utilizing Rotation Property: The key insight is that the minimum element lies at the pivot where the sorted order breaks, and this property allows us to use binary search to find it.

Conclusion

LeetCode 153 is a great example of how binary search can be applied to rotated sorted arrays. By carefully adjusting the search range based on the values of the middle and right elements, we can efficiently find the minimum element in logarithmic time.