Skip to content
Hello Python

Minimum of a Rotated Sorted Array

Interview ProblemInterviewMediumArrayBinary Search

Checking your account…

Sign in to save your code and progress across devices. The lesson and problem statement remain public.

Loading the interactive Interview workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Interview workspace

Problem

Implement Solution.findMin(nums). nums contains distinct values and is an ascending array rotated zero or more positions. Return its minimum in O(log n).

Starter code

class Solution:
    def findMin(self, nums):
        pass
Test cases

rotated

{
  "args": [
    [
      3,
      4,
      5,
      1,
      2
    ]
  ]
}

Expected: 1

Wizard outline
  1. Step 1: Initialize Solution.findMin

    Replace the empty starter with the first real state owned by Solution.findMin. A small, named state is easier to verify than a complete algorithm. Establish it before adding the branch or loop that changes it.

  2. Step 2: Pass the Not Rotated case

    Complete the readable core algorithm for one representative Interview case. Compare middle with the right boundary to retain the half containing the rotation minimum.

  3. Step 3: Harden the Rotated boundary

    Repair the reviewed boundary and pass the complete submission contract. nums[middle] > nums[right] proves the rotation drop lies to the right. Otherwise the interval from middle through right is sorted and middle is no greater than its suffix, so no later value can beat middle.

Footguns and prerequisites
  • When nums[middle] <= nums[right], middle itself may be the minimum and must remain.
  • arrays strings two pointers sliding window
Reviewed references
Practice prerequisites
  • Find the First True Boundary(opens in a new tab)

    Find the First True Boundary isolates every index before left is known false, while every index at or after right is known true or the sentinel len(flags). That focused state discipline is required when implementing find minimum rotated as a complete Interview Problem.

Recommended approach and implementation

Binary search a closed interval; if middle exceeds right, minimum is strictly right of middle, otherwise keep middle and discard its right suffix.

Why it works: nums[middle] > nums[right] proves the rotation drop lies to the right. Otherwise the interval from middle through right is sorted and middle is no greater than its suffix, so no later value can beat middle.

class Solution:
    def findMin(self, nums):
        """
        Checkpoint 1: initialize the state owned by this Interview contract.
        Checkpoint 2: assemble the primary transition without hiding the boundary.
        """
        left, right = 0, len(nums) - 1
        while left < right:
            middle = (left + right) // 2
            if nums[middle] > nums[right]:
                left = middle + 1
            else:
                right = middle
        return nums[left]
Similar exercises