DSA Minimum in a Rotated Array with Duplicates

The problem

A rotated array is a sorted array cut once and swapped in two parts. Finding the minimum in a rotated array with duplicates asks for the smallest value in such an array. Values may repeat.

The minimum sits where the rising order drops, or at the start when there is no drop. The array is never empty. The cases below are the ones this article solves.

cases = [
    ([2, 2, 2, 0, 1], 0),
    ([1, 0, 1, 1, 1], 0),
    ([10, 1, 10, 10, 10], 1),
    ([3, 3, 1, 3], 1),
    ([1, 1, 1, 1, 1], 1),
]
for nums, expected in cases:
    print("nums", nums, "minimum:", expected)

Every case is heavy with repeats. The last case holds one value five times, so any of its positions is a correct answer.

Intuition: reuse the search for distinct values

The first idea reuses the binary search that works when all values differ. It compares the middle value with the right end and halves the range. A larger middle sends the search right, and anything else sends it left.

def find_min_distinct(nums):
    lo = 0
    hi = len(nums) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] > nums[hi]:
            lo = mid + 1
        else:
            hi = mid
    return nums[lo]

print("distinct values [4, 5, 6, 7, 0, 1, 2]:", find_min_distinct([4, 5, 6, 7, 0, 1, 2]))
print("with duplicates [3, 3, 1, 3]:", find_min_distinct([3, 3, 1, 3]))
print("true minimum of [3, 3, 1, 3]:", min([3, 3, 1, 3]))

The rule fails on the second array. The middle and right values agree at 3, and the rule reads that agreement as safety on the left. The drop hides behind the repeats, and the search walks past the 1.

Brute force: scan every value

The brute force compares each value against the smallest seen so far. One pass always finds the minimum, duplicates or not. A counter records the comparisons.

def brute_min(nums):
    best = nums[0]
    comparisons = 0
    for value in nums[1:]:
        comparisons += 1
        if value < best:
            best = value
    return best, comparisons

cases = [[2, 2, 2, 0, 1], [1, 0, 1, 1, 1], [10, 1, 10, 10, 10], [3, 3, 1, 3], [1, 1, 1, 1, 1]]
for nums in cases:
    minimum, comparisons = brute_min(nums)
    print("nums", nums, "minimum:", minimum, "comparisons:", comparisons)

The scan never misses. It also never saves anything. Every value pays a comparison even when the first half of the array already proves the answer.

The optimal solution: halve when possible, shrink when blind

The fix keeps the halving search and adds one move for the blind case. When the middle and right values are equal, the search drops the right end by one step. That one sentence is the whole change.

Dropping the right end is safe there. Its equal twin stays in range at the middle, so no value is lost. Every other comparison still halves the range as before.

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

cases = [
    ([2, 2, 2, 0, 1], 0),
    ([1, 0, 1, 1, 1], 0),
    ([10, 1, 10, 10, 10], 1),
    ([3, 3, 1, 3], 1),
    ([1, 1, 1, 1, 1], 1),
]
for nums, expected in cases:
    result = find_min(nums)
    print("nums", nums, "->", result, "expected:", expected, "match:", result == expected)

All five cases pass, including the two shapes that broke the distinct-value rule. The search degrades honestly. An array of one repeated value shrinks step by step instead of halving.

Walkthrough: the search on [1, 0, 1, 1, 1]

The range opens over the whole array. The first probe lands on a repeat and cannot tell which side hides the drop. The trace prints the range, the two compared values, and the move at each step.

def traced_min(nums):
    lo = 0
    hi = len(nums) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        print("range", lo, "to", hi, "- middle value", nums[mid], "right value", nums[hi], end=" ")
        if nums[mid] > nums[hi]:
            print("-> drop is right of the middle")
            lo = mid + 1
        elif nums[mid] < nums[hi]:
            print("-> drop is at or left of the middle")
            hi = mid
        else:
            print("-> values agree, shrink the right end")
            hi -= 1
    return nums[lo]

print("minimum:", traced_min([1, 0, 1, 1, 1]))

The shrink costs one step and buys certainty. Once the right end moves off the repeat, the ordinary comparisons take over and the range halves to the 0.

Complexity

On distinct values the range halves every step, so the time is O(log n). On arrays built from one repeated value, every step shrinks by one, so the worst-case time is O(n).

The search stores only its two range ends, so its extra space is O(1). The counts below run the counted search on a rotated distinct array and on an all-equal array at three sizes.

def counted_min(nums):
    lo = 0
    hi = len(nums) - 1
    comparisons = 0
    while lo < hi:
        mid = (lo + hi) // 2
        comparisons += 1
        if nums[mid] > nums[hi]:
            lo = mid + 1
        elif nums[mid] < nums[hi]:
            hi = mid
        else:
            hi -= 1
    return nums[lo], comparisons

for size in [16, 256, 4096]:
    base = list(range(size))
    rotated = base[size // 3:] + base[:size // 3]
    _, distinct_steps = counted_min(rotated)
    _, equal_steps = counted_min([7] * size)
    print("size:", size, "- distinct comparisons:", distinct_steps, " all-equal comparisons:", equal_steps)

The distinct column grows by a step or two per doubling of size. The all-equal column grows with the size itself. Duplicates, not size, decide which column an input lands in.

Edge cases and pitfalls

A single value is its own minimum. An unrotated array answers its first value. A drop on the last step puts the minimum at the final index.

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

for nums in [[5], [2, 1], [1, 2], [1, 2, 2, 3], [2, 3, 4, 1], [7, 7, 7]]:
    print("nums", nums, "minimum:", find_min(nums))

One pitfall hides in the halving step. When the middle beats the right end, the drop sits strictly right of the middle, so the left end jumps past it. Moving the left end only to the middle can stall the loop when the middle already equals the left end, because the range stops shrinking.