DSA-063 · Retain the minimum using the right boundary

Minimum in Rotated Sorted Array

Core · Java 21 · Version 1 · editorial draft

Java reference and baseline verified on JDK 21: 4393 deterministic checks. Learner drafts are not executed.

Understand the problem

Return the smallest value in a nonempty rotation of a strictly increasing int array. Use logarithmic search without changing the input.

nums is nonnull and contains 1..100,000 distinct ints forming a rotation of a strictly increasing sequence. Zero rotation and all int extremes are valid. Distinctness/order are unchecked preconditions.
Return the minimum value, not its index or a rotation count. Null throws NullPointerException; an empty array throws IllegalArgumentException in both methods.
Input entries remain unchanged. The active interval [left,right] is closed and always contains the minimum index. Duplicate-valued rotations require a different contract and may need linear work.

Examples

Input: [4,5,6,7,0,1,2]
Output: 0
nums[mid]=7 exceeds right value 2, so the minimum is strictly after mid.
Input: [1,2,3]
Output: 1
An already sorted interval keeps its left side, eventually leaving index 0.
Input: [2,3,4,1]
Output: 1
When mid is larger than the right endpoint, discard through mid; the final candidate is the last index.

Before you start

Rotation of a strictly increasing array
Closed nonempty candidate intervals

Recognize the structure

The rightmost value acts as a reference for which side of the rotation break contains mid. Unlike exact search, equality with a target is irrelevant; a midpoint may itself be the minimum and must sometimes remain in the candidate interval.

Try before revealing

Hint 1

The minimum must stay in one nonempty closed interval.

Hint 2

Compare nums[mid] to the current nums[right], not to a target.

Hint 3

If mid is higher, move left past it; otherwise retain it with right=mid.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Scan for the smallest value

Initialize minimum=nums[0] and take Math.min over all values. For [4,5,1,2,3], the running record becomes 4,4,1,1,1. This O(n)-time, O(1)-space baseline works on arbitrary nonempty arrays, while the logarithmic method relies on the rotation and distinctness promises.

Improve the baseline

Keep a nonempty closed interval

Begin at left=0,right=n−1 and loop only while left<right. The answer is an element index, so there is no after-end boundary.

A high midpoint precedes the minimum

If nums[mid]>nums[right], the segment from mid to right crosses the descending break. The minimum lies in [mid+1,right], so left=mid+1.

A low midpoint remains possible

Otherwise nums[mid]<nums[right] under distinctness and mid<right. The suffix [mid,right] is sorted, so its smallest member is mid; the global minimum lies in [left,mid]. Keep mid with right=mid, then return nums[left].

Why it is correct

Initialization

The nonempty full array contains its unique minimum; 0<=left<=right<n.

Preservation across the break

If mid exceeds the right value, the minimum occurs after mid. Otherwise the right suffix contains no descending break, so no index after mid can beat nums[mid]; excluding only that later suffix preserves the minimum.

Convergence

With left<right, mid<right. Setting left=mid+1 or right=mid strictly shrinks the interval while retaining the unique minimum. The remaining index identifies the minimum value, and input fields were never written.

Complete Java reference and baseline

Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.

import java.util.Objects;

public final class Solution {
    public static int findMin(int[] nums) {
        Objects.requireNonNull(nums, "nums");
        if (nums.length == 0) throw new IllegalArgumentException("empty array");
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[right]) left = mid + 1;
            else right = mid;
        }
        return nums[left];
    }
    public static int baseline(int[] nums) {
        Objects.requireNonNull(nums, "nums");
        if (nums.length == 0) throw new IllegalArgumentException("empty array");
        int minimum = nums[0];
        for (int value : nums) minimum = Math.min(minimum, value);
        return minimum;
    }
}

Read the meaningful blocks

Reject empty before indexing

The public API handles an empty array explicitly instead of relying on an accidental nums[0] exception.

Compare with the current right value

The reference boundary changes with the interval. This direct comparison distinguishes whether the break lies to the midpoint’s right.

Keep mid when lowering right

right=mid−1 is invalid here: mid might be the actual minimum. The method returns a value after convergence, not the search index.

Complexity

Time O(log n) for nonempty distinct rotated input and O(1) auxiliary space. Empty/null rejection is constant work; rotation validation is a caller precondition.

The baseline takes O(n) time and O(1) space. Allowing duplicates can force O(n) search because equal midpoint/right values do not identify the minimum’s side.

Exact-state walkthroughs

Reveal normal and boundary traces

Midpoint comparison finds a late pivot

Input: [2,3,4,1] · Minimum value: 1

Step 1 of 4: Initialize a closed candidate interval.

The unique minimum remains in the nonempty active interval.

Minimum — retained closed interval

Candidate element interval: [0, 3]. Phase: search.

index 02retained element
index 13retained element
index 24retained element
index 31retained element

Highlight marks the last probed element, which may have just been discarded. The closed interval retains the minimum; the returned result is its value.

State after this step
Variable	Value
values	`[2,3,4,1]`
left	`0`
right	`3`
bounds	`"closed"`
phase	`"search"`

See the affected Java block

 1 import java.util.Objects;
 2 
 3 public final class Solution {
 4     public static int findMin(int[] nums) {
 5         Objects.requireNonNull(nums, "nums");
 6         if (nums.length == 0) throw new IllegalArgumentException("empty array");
 7         int left = 0, right = nums.length - 1;
 8         while (left < right) {
 9             int mid = left + (right - left) / 2;
10             if (nums[mid] > nums[right]) left = mid + 1;
11             else right = mid;
12         }
13         return nums[left];
14     }
15     public static int baseline(int[] nums) {
16         Objects.requireNonNull(nums, "nums");
17         if (nums.length == 0) throw new IllegalArgumentException("empty array");
18         int minimum = nums[0];
19         for (int value : nums) minimum = Math.min(minimum, value);
20         return minimum;
21     }
22 }
23

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Initialize a closed candidate interval.
The unique minimum remains in the nonempty active interval.
values
[2,3,4,1]
left
0
right
3
bounds
"closed"
phase
"search"
Mid is above the right boundary, so minimum lies later.
The chosen interval remains nonempty and retains the unique minimum. mid<old right makes the comparison safe.
values
[2,3,4,1]
left
2
right
3
bounds
"closed"
phase
"search"
before
[0,3]
mid
1
probeValue
3
comparisonValue
1
moveRight
true
Mid is above the right boundary, so minimum lies later.
The chosen interval remains nonempty and retains the unique minimum. mid<old right makes the comparison safe.
values
[2,3,4,1]
left
3
right
3
bounds
"closed"
phase
"search"
before
[2,3]
mid
2
probeValue
4
comparisonValue
1
moveRight
true
Return the documented value, index, boundary, range, or rate.
The final result follows the problem-specific contract; the inputs were never mutated.
result
1

Already sorted array

Input: [1,2,3] · Minimum value: 1

Step 1 of 4: Initialize a closed candidate interval.

The unique minimum remains in the nonempty active interval.

Minimum — retained closed interval

Candidate element interval: [0, 2]. Phase: search.

index 01retained element
index 12retained element
index 23retained element

Highlight marks the last probed element, which may have just been discarded. The closed interval retains the minimum; the returned result is its value.

State after this step
Variable	Value
values	`[1,2,3]`
left	`0`
right	`2`
bounds	`"closed"`
phase	`"search"`

See the affected Java block

 1 import java.util.Objects;
 2 
 3 public final class Solution {
 4     public static int findMin(int[] nums) {
 5         Objects.requireNonNull(nums, "nums");
 6         if (nums.length == 0) throw new IllegalArgumentException("empty array");
 7         int left = 0, right = nums.length - 1;
 8         while (left < right) {
 9             int mid = left + (right - left) / 2;
10             if (nums[mid] > nums[right]) left = mid + 1;
11             else right = mid;
12         }
13         return nums[left];
14     }
15     public static int baseline(int[] nums) {
16         Objects.requireNonNull(nums, "nums");
17         if (nums.length == 0) throw new IllegalArgumentException("empty array");
18         int minimum = nums[0];
19         for (int value : nums) minimum = Math.min(minimum, value);
20         return minimum;
21     }
22 }
23

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Initialize a closed candidate interval.
The unique minimum remains in the nonempty active interval.
values
[1,2,3]
left
0
right
2
bounds
"closed"
phase
"search"
Keep mid because it may be the minimum.
The chosen interval remains nonempty and retains the unique minimum. mid<old right makes the comparison safe.
values
[1,2,3]
left
0
right
1
bounds
"closed"
phase
"search"
before
[0,2]
mid
1
probeValue
2
comparisonValue
3
moveRight
false
Keep mid because it may be the minimum.
The chosen interval remains nonempty and retains the unique minimum. mid<old right makes the comparison safe.
values
[1,2,3]
left
0
right
0
bounds
"closed"
phase
"search"
before
[0,1]
mid
0
probeValue
1
comparisonValue
2
moveRight
false
Return the documented value, index, boundary, range, or rate.
The final result follows the problem-specific contract; the inputs were never mutated.
result
1

Singleton minimum int

Input: [-2147483648] · Minimum value: -2147483648

Step 1 of 2: Initialize a closed candidate interval.

The unique minimum remains in the nonempty active interval.

Minimum — retained closed interval

Candidate element interval: [0, 0]. Phase: search.

index 0-2147483648retained element

Highlight marks the last probed element, which may have just been discarded. The closed interval retains the minimum; the returned result is its value.

State after this step
Variable	Value
values	`[-2147483648]`
left	`0`
right	`0`
bounds	`"closed"`
phase	`"search"`

See the affected Java block

 1 import java.util.Objects;
 2 
 3 public final class Solution {
 4     public static int findMin(int[] nums) {
 5         Objects.requireNonNull(nums, "nums");
 6         if (nums.length == 0) throw new IllegalArgumentException("empty array");
 7         int left = 0, right = nums.length - 1;
 8         while (left < right) {
 9             int mid = left + (right - left) / 2;
10             if (nums[mid] > nums[right]) left = mid + 1;
11             else right = mid;
12         }
13         return nums[left];
14     }
15     public static int baseline(int[] nums) {
16         Objects.requireNonNull(nums, "nums");
17         if (nums.length == 0) throw new IllegalArgumentException("empty array");
18         int minimum = nums[0];
19         for (int value : nums) minimum = Math.min(minimum, value);
20         return minimum;
21     }
22 }
23

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Initialize a closed candidate interval.
The unique minimum remains in the nonempty active interval.
values
[-2147483648]
left
0
right
0
bounds
"closed"
phase
"search"
Return the documented value, index, boundary, range, or rate.
The final result follows the problem-specific contract; the inputs were never mutated.
result
-2147483648

Test the contract

Input: [MIN]
Output: MIN
Singleton and value extreme.
Input: [1,2,3]
Output: 1
Zero rotation.
Input: [2,1]
Output: 1
Two-element rotation.
Input: [3,1,2]
Output: 1
Mid itself is minimum.
Input: []
Output: IllegalArgumentException
Declared empty policy.

Common mistakes and counterexamples

Use right=mid−1 on the lower branch

Counterexample: [3,1,2] has mid at the minimum; discarding it loses the answer.

Retain mid with right=mid.

Read nums[0] before checking empty

Counterexample: An empty API call would throw an accidental bounds exception.

Declare and implement IllegalArgumentException for empty input.

Return left when asked for a value

Counterexample: [4,5,1,2,3] converges to index 2 but the required result is 1.

Return nums[left]; expose a separate index API for rotation counts.

Treat equal right/mid values as decisive under duplicates

Counterexample: [1,1,1,0,1] can hide the minimum in the discarded side.

Use the distinct precondition or a separately proved duplicate-aware routine.

Follow-ups

Permit duplicates.

When nums[mid]==nums[right], right can be reduced by one without losing all minimum witnesses. This only removes one candidate in ambiguous cases, so worst-case time becomes O(n).

Return the minimum index or rotation count.

Return the converged left index instead of its value. Specify rotation direction and how duplicate minima would affect uniqueness before broadening the contract.

Use the minimum to search for a target.

Split the rotation at that index into two sorted segments and choose the segment whose value range can contain the target. Preserve consistent half-open or closed bounds inside the second search.

Your Java attempt

Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.

Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.

Approach, code, and test notes (20,000 characters maximum)

No unsaved text changes · 108/20,000 characters

Self-review

I preserve a nonempty interval containing the minimum.I know why one branch excludes mid and the other retains it.I return the requested value and distinguish it from an index.

Use the checklist to test your explanation. Checks apply to this visit.

Related foundations

Binary search: candidate intervals and monotone feasibility

Keep practicing

Open focused practice

AceYourInterviews · 2026-10-16 · Original teaching content and implementations authored for AceYourInterviews. Standard problem names do not imply company-frequency or external platform-difficulty claims.