NUHMAN.com

Introduction

LeetCode 154 extends LeetCode 153 by introducing the possibility of duplicate elements in the rotated sorted array. The problem is the same as LeetCode 153: finding the minimum element in a rotated sorted array. However, here the challenge is that duplicate elements may be present, which can make it trickier to decide the direction of the binary search. We need to carefully handle cases with duplicates to avoid skipping over potential minimums.

Problem Statement

Given a rotated sorted array, possibly with duplicates, find the minimum element.

Function Signature:

go

func findMin(nums []int) int

Approach

Key Idea:

• Like in LeetCode 153, we can use binary search to efficiently find the minimum element. However, when duplicates are present, we cannot always rely on the usual approach of comparing the middle element with the rightmost element to decide which half to search.
• If nums[mid] == nums[right], we cannot definitively determine whether the minimum lies to the left or right. In this case, we simply move the right pointer leftward by one (right--), which effectively reduces the search space by one element. This ensures that we don't miss the minimum even in the presence of duplicates.
• If nums[mid] > nums[right], the minimum element must be in the right half.
• If nums[mid] < nums[right], the minimum element is in the left half or could be at mid.

The binary search will continue until left == right, at which point the element at left (or right, since they are equal at this point) will be the minimum element.

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 the middle element is greater than the right element,
        // the minimum must be in the right half
        if nums[mid] > nums[right] {
            left = mid + 1
        } else if nums[mid] < nums[right] {
            // If the middle element is less than the right element,
            // the minimum could be in the left half or at mid
            right = mid
        } else {
            // If nums[mid] == nums[right], we can't decide which half to search,
            // so we reduce the search space by moving right one step left
            right--
        }
    }
    
    // Left and right will eventually point to the minimum element
    return nums[left]
}

func main() {
    // Example usage
    nums := []int{2, 2, 2, 0, 1}
    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 calculate the mid index.

1. Comparing Elements:

• If nums[mid] > nums[right], it means the minimum must be in the right half of the array. Therefore, we move left to mid + 1.
• If nums[mid] < nums[right], it means the minimum is in the left half or could be at mid. We move right to mid.
• If nums[mid] == nums[right], it indicates that the elements are equal, and we cannot determine which half to discard. So, we reduce the search space by moving the right pointer to right - 1.

1. Termination:

• The loop terminates when left == right, and at this point, nums[left] (or nums[right], since they are equal) is the minimum element.

1. Example:

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

Time and Space Complexity

OperationComplexityTimeO(n)SpaceO(1)

• Time Complexity:
• In the worst case, if all elements are equal (or nearly equal), we may need to examine every element once, resulting in a time complexity of O(n), where n is the length of the array.
• Space Complexity:
• We are only using a few pointers (left, right, mid), so the space complexity is O(1).

Example

Input:

go

nums := []int{2, 2, 2, 0, 1}

Output:

0

Explanation:

1. First iteration:

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

1. Second iteration:

• left = 3, right = 4, mid = 3, nums[mid] = 0, nums[right] = 1
• Since nums[mid] < nums[right], the minimum could be at mid or to the left. Therefore, right = mid = 3.

1. Third iteration:

• left = 3, right = 3, so the loop terminates and nums[left] = 0 is returned.

Final result: 0.

Why This Approach Works

• Efficiency: While the presence of duplicates prevents us from always reducing the search space by half, the approach still ensures that we examine each element at most once, so the worst-case time complexity is O(n).
• Handling Duplicates: By checking if nums[mid] == nums[right], we can handle duplicates gracefully. This reduces the search space by one element at a time, ensuring that we don't miss the minimum.

Conclusion

LeetCode 154 builds on the same approach as LeetCode 153 but introduces the challenge of handling duplicates. By carefully adjusting the search space when duplicates are encountered, we can find the minimum element in the array while still maintaining efficiency. The worst-case time complexity is O(n), making this approach optimal in terms of time and space.