DSA-064 · Slope-guided search retaining some strict peak

Find a Peak Element

Core · Java 21 · Version 1 · editorial draft

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

Understand the problem

Return any index of a strict peak in a nonempty int array whose adjacent values are unequal. A peak is larger than every existing immediate neighbor; conceptual values outside both ends are below all int values.

nums is nonnull with 1..100,000 elements and nums[i]!=nums[i+1] for every adjacent pair. Equal nonadjacent values are allowed. Adjacent inequality is an unchecked precondition.
Return any local strict-peak index, not necessarily the first peak or global maximum. Endpoints need only exceed their one real neighbor; a singleton is a peak even at Integer.MIN_VALUE.
Do not write the array. Null throws NullPointerException and empty input throws IllegalArgumentException. The outside −infinity values are conceptual: do not store them in an int or subtract values to compare a slope.

Examples

Input: [1,2,1,3,5,6,4]
Output: Any of 1 or 5; optimized returns 5
The slope at mid=3 is rising, so a peak exists to the right even though another peak lies to the left.
Input: [3,2,1]
Output: 0
The left endpoint is a peak relative to conceptual −infinity on its outside.
Input: [MIN]
Output: 0
No representable int sentinel is needed; endpoint existence is defined through missing neighbors.

Before you start

Local maxima versus global maximum
Adjacent-unequal arrays and conceptual outside boundaries

Recognize the structure

The array itself is not sorted, and the slope signs need not form a globally monotone predicate. The search works through an existence invariant: the selected side is guaranteed to contain some peak because it faces an uphill boundary and eventually must turn down or reach an endpoint.

Try before revealing

Hint 1

A rising edge guarantees some peak in the uphill direction before the array ends.

Hint 2

The active interval’s outside edges should face downward away from it.

Hint 3

Compare mid with mid+1, keep the uphill side, and stop when one index remains.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Test each position’s existing neighbors

Scan positions and return the first index larger than its left neighbor when present and its right neighbor when present. For [1,2,1,3], index 1 satisfies both comparisons and is returned. This O(n)-time baseline can choose a different valid peak than the slope-guided O(log n) method.

Improve the baseline

Search a nonempty closed interval

Set left=0,right=n−1. At its outside edges maintain nums[left]>nums[left−1] when left>0, and nums[right]>nums[right+1] when right<n−1; missing outside neighbors are conceptual −infinity.

Use an uphill direction

With left<right, mid<right so mid+1 is safe. If nums[mid]<nums[mid+1], retain [mid+1,right]; its new left edge points uphill from the discarded side.

Retain the downward side otherwise

Adjacent inequality makes the other case strictly falling. Retain [left,mid], whose new right edge is greater than the discarded mid+1. When the interval becomes one point, both edge inequalities prove it is a strict peak.

Why it is correct

Peak existence in the active interval

A maximum value inside the finite active interval exceeds any existing adjacent neighbor inside it because adjacent values are unequal. The maintained outside-edge inequalities ensure a boundary maximum also beats its neighbor just outside. Thus at least one strict peak exists in the interval.

Preserve outside-edge conditions

A rising mid→mid+1 creates the required greater-left-neighbor condition for new left=mid+1 while preserving the old right condition. A falling edge creates the greater-right-neighbor condition for new right=mid while preserving the old left condition.

Converge to a valid witness

Each update strictly shrinks the closed interval because mid<right. At left==right, the single element satisfies both maintained outside inequalities, so it is a peak. No monotone-slope assumption or global-maximum claim is needed.

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 peak(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[mid + 1]) left = mid + 1;
            else right = mid;
        }
        return left;
    }
    public static int baseline(int[] nums) {
        Objects.requireNonNull(nums, "nums");
        if (nums.length == 0) throw new IllegalArgumentException("empty array");
        for (int i = 0; i < nums.length; i++)
            if ((i == 0 || nums[i] > nums[i - 1]) && (i + 1 == nums.length || nums[i] > nums[i + 1])) return i;
        throw new IllegalArgumentException("adjacent-unequal precondition violated");
    }
}

Read the meaningful blocks

Guard mid+1 structurally

left<right guarantees mid<right<n; reading nums[mid+1] needs no separate endpoint special case.

Compare, do not subtract

nums[mid]<nums[mid+1] is safe across int extremes. A difference can overflow and reverse the apparent slope.

Return an index

The converged index is one valid witness. A test expecting the baseline’s first peak or the largest value would impose an unsupported requirement.

Complexity

Optimized time O(log n), workspace O(1), no mutation. The adjacent-unequal property is a precondition; scanning to validate it would add O(n) work.

The baseline uses O(n) time and O(1) space. Returning all peaks requires linear output/work in the worst case; logarithmic search returns only one.

Exact-state walkthroughs

Reveal normal and boundary traces

Multiple peaks: retain one uphill region

Input: [1,2,1,3,5,6,4] · Returned index: 5

Step 1 of 5: Initialize a closed candidate interval.

The interval contains some strict peak and has downhill-facing outside boundaries.

Peak — interval retaining some strict peak

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

index 01retained element
index 12retained element
index 21retained element
index 33retained element
index 45retained element
index 56retained element
index 64retained element

Highlight marks the last probed element, which may have just been discarded. The retained interval contains some strict peak; it need not contain the global maximum and slopes need not be monotone.

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

See the affected Java block

 1 import java.util.Objects;
 2 
 3 public final class Solution {
 4     public static int peak(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[mid + 1]) left = mid + 1;
11             else right = mid;
12         }
13         return 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         for (int i = 0; i < nums.length; i++)
19             if ((i == 0 || nums[i] > nums[i - 1]) && (i + 1 == nums.length || nums[i] > nums[i + 1])) return i;
20         throw new IllegalArgumentException("adjacent-unequal precondition violated");
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 interval contains some strict peak and has downhill-facing outside boundaries.
values
[1,2,1,3,5,6,4]
left
0
right
6
bounds
"closed"
phase
"search"
Retain the uphill right side containing a peak.
The chosen interval remains nonempty and retains some strict peak; slopes need not be globally monotone. mid<old right makes the comparison safe.
values
[1,2,1,3,5,6,4]
left
4
right
6
bounds
"closed"
phase
"search"
before
[0,6]
mid
3
probeValue
3
comparisonValue
5
moveRight
true
Retain the left side with a downhill right boundary.
The chosen interval remains nonempty and retains some strict peak; slopes need not be globally monotone. mid<old right makes the comparison safe.
values
[1,2,1,3,5,6,4]
left
4
right
5
bounds
"closed"
phase
"search"
before
[4,6]
mid
5
probeValue
6
comparisonValue
4
moveRight
false
Retain the uphill right side containing a peak.
The chosen interval remains nonempty and retains some strict peak; slopes need not be globally monotone. mid<old right makes the comparison safe.
values
[1,2,1,3,5,6,4]
left
5
right
5
bounds
"closed"
phase
"search"
before
[4,5]
mid
4
probeValue
5
comparisonValue
6
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
5

Decreasing endpoint peak

Input: [3,2,1] · Returned index: 0

Step 1 of 4: Initialize a closed candidate interval.

The interval contains some strict peak and has downhill-facing outside boundaries.

Peak — interval retaining some strict peak

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

index 03retained element
index 12retained element
index 21retained element

Highlight marks the last probed element, which may have just been discarded. The retained interval contains some strict peak; it need not contain the global maximum and slopes need not be monotone.

State after this step
Variable	Value
values	`[3,2,1]`
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 peak(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[mid + 1]) left = mid + 1;
11             else right = mid;
12         }
13         return 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         for (int i = 0; i < nums.length; i++)
19             if ((i == 0 || nums[i] > nums[i - 1]) && (i + 1 == nums.length || nums[i] > nums[i + 1])) return i;
20         throw new IllegalArgumentException("adjacent-unequal precondition violated");
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 interval contains some strict peak and has downhill-facing outside boundaries.
values
[3,2,1]
left
0
right
2
bounds
"closed"
phase
"search"
Retain the left side with a downhill right boundary.
The chosen interval remains nonempty and retains some strict peak; slopes need not be globally monotone. mid<old right makes the comparison safe.
values
[3,2,1]
left
0
right
1
bounds
"closed"
phase
"search"
before
[0,2]
mid
1
probeValue
2
comparisonValue
1
moveRight
false
Retain the left side with a downhill right boundary.
The chosen interval remains nonempty and retains some strict peak; slopes need not be globally monotone. mid<old right makes the comparison safe.
values
[3,2,1]
left
0
right
0
bounds
"closed"
phase
"search"
before
[0,1]
mid
0
probeValue
3
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
0

Singleton at the minimum int

Input: [-2147483648] · Returned index: 0

Step 1 of 2: Initialize a closed candidate interval.

The interval contains some strict peak and has downhill-facing outside boundaries.

Peak — interval retaining some strict peak

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

index 0-2147483648retained element

Highlight marks the last probed element, which may have just been discarded. The retained interval contains some strict peak; it need not contain the global maximum and slopes need not be monotone.

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 peak(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[mid + 1]) left = mid + 1;
11             else right = mid;
12         }
13         return 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         for (int i = 0; i < nums.length; i++)
19             if ((i == 0 || nums[i] > nums[i - 1]) && (i + 1 == nums.length || nums[i] > nums[i + 1])) return i;
20         throw new IllegalArgumentException("adjacent-unequal precondition violated");
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 interval contains some strict peak and has downhill-facing outside boundaries.
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
0

Test the contract

Input: [MIN]
Output: 0
Conceptual missing neighbors.
Input: [1,2]
Output: 1
Increasing endpoint.
Input: [3,2,1]
Output: 0
Decreasing endpoint.
Input: [1,3,1,4,1]
Output: Any strict peak
Multiple answers.
Input: []
Output: IllegalArgumentException
Nonempty policy.

Common mistakes and counterexamples

Assume slope signs are globally sorted

Counterexample: [1,3,2,4,1] alternates rising and falling edges.

Prove an uphill-facing boundary retains some peak, not a first-true slope transition.

Require the global maximum

Counterexample: [1,5,2,9,1] has valid local peaks at both 1 and 3.

Validate strict neighbor inequalities for any returned index.

Permit plateaus under the same proof

Counterexample: [2,2] has no strict peak with both equal adjacent values.

Keep adjacent inequality or define a non-strict plateau-aware variant separately.

Use Integer.MIN_VALUE as a real outside neighbor

Counterexample: A singleton MIN is still a peak, but MIN>MIN would be false.

Guard missing neighbors logically; outside −infinity is below all ints.

Follow-ups

Allow adjacent equal values.

First define strict versus non-strict peaks. Some plateau arrays have no strict peak; a >= variant has different existence and movement guarantees, and plateau boundaries may require additional work.

Return every peak.

Scan existing neighbor pairs in O(n) time and emit all witnesses. Alternating low/high arrays contain Θ(n) peaks, so output size itself rules out logarithmic total work.

Find a 2D peak.

A middle-column maximum can guide search to a neighboring side with a higher value. State the neighborhood definition and prove existence for the selected submatrix; a one-dimensional slope proof is not sufficient.

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 · 106/20,000 characters

Self-review

I use an existence invariant instead of claiming monotone slopes.I guard endpoint comparisons without a representable −infinity sentinel.I test any valid peak and preserve the input.

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.