Peak Element in Rotated Array — Problem Statement & Solution Guide

ArraysMediumModified Binary Search

TimeO(log n)

SpaceO(1)

Quick Answer & Algorithm Key Takeaway

Master coding challenges related to Arrays and solve the Peak Element in Rotated Array problem optimally.

TopicArrays

PatternModified Binary Search

TimeO(log n)

SpaceO(1)

Problem Description

Given an array nums of distinct integers that was initially sorted in strictly increasing order and then rotated at an unknown pivot, locate the index of a peak element. An element is a peak if it is strictly larger than its immediate left and right neighbors. For the first element, the left neighbor is considered –∞; for the last element, the right neighbor is –∞. At least one peak is guaranteed to exist. Return any valid peak index. Your solution must run in O(log n) time, i.e., use a modified binary search.

DSA Pattern Breakdown

"Peak Element in Rotated Array"

medium

WHY DOES IT MATTER?

The peak‑in‑rotated‑array pattern teaches candidates to exploit hidden order in seemingly chaotic data, a skill crucial for optimizing search, load‑balancing, and fault‑tolerance algorithms.

OPTIMIZATION CHALLENGE

The breakthrough is recognizing that comparing nums[mid] with its right neighbour tells us which half is strictly increasing, allowing us to discard the opposite half—turning a linear scan into a logarithmic search.

REAL-WORLD CONNECTION

Think of a circular buffer of timestamps where the newest entry wraps around; locating the most recent (peak) entry without scanning the entire buffer mirrors this problem and is essential for high‑throughput logging systems.

During the interview, write the binary‑search loop first, then add the neighbour checks; keep the invariant that the search interval always contains a peak, which eliminates off‑by‑one errors.

COMPLEXITY AT A GLANCE

⏱ Time:O(log n)

💾 Space:O(1)

Core Theory — Why This Approach?

When an originally sorted array is rotated, the monotonic property is broken at the pivot, creating two sorted sub‑arrays. A peak element is any index whose value exceeds both neighbours; because the array is circularly monotonic except at the pivot, at least one such peak always exists – the maximum element is a guaranteed peak. A naïve scan compares each element with its neighbours in O(n) time, which is acceptable for small inputs but becomes a bottleneck for massive data streams or when the interview expects logarithmic performance. The optimal paradigm leverages binary search on the rotated sorted structure: by examining the middle element and its relative ordering with neighbours, we can discard half of the search space each step, achieving O(log n) time while using O(1) extra space.

Interview Questions on This Problem

Q1How would you modify the binary‑search solution if the array could contain duplicate values?

With duplicates, the strict ordering guarantee disappears, so when nums[mid]==nums[right] we cannot decide which side is sorted; we shrink the search window by decrementing right (or incrementing left) by one, preserving O(n) worst‑case but still O(log n) on average.

Q2Explain why the maximum element in a rotated sorted array is always a peak, and how that insight simplifies the algorithm.

The maximum element has no larger neighbour on either side; its left neighbour is smaller (by strict increase) and its right neighbour is either smaller or –∞ at the array end, satisfying the peak condition. This lets us target the global maximum via binary search on the slope direction rather than checking every element.

Q3In a distributed system where each node holds a segment of a rotated array, how could you find a global peak with minimal inter‑node communication?

Each node locally finds its segment’s peak and reports its boundary values; a coordinator then performs a binary‑search‑like merge on the boundary pairs to locate the segment containing the global maximum, requiring only O(log k) messages for k nodes.

Examples

Example 1

Input

[4,5,6,7,0,1,2]

Output

Explanation: The array was [0,1,2,4,5,6,7] before rotation. Scanning the array, element 7 (at index 3) is larger than both neighbours 6 and 0, so index 3 is a peak.

Example 2

Input

[30,40,50,10,20]

Output

Explanation: Element 50 (at index 2) is greater than its left neighbour 40 and right neighbour 10, satisfying the peak condition. Hence the answer is 2.

Example 3

Input

[2,1]

Output

Explanation: For the first element we treat the left neighbour as –∞. Since 2 > –∞ and 2 > 1, index 0 is a valid peak.

Constraints

1 <= nums.length <= 100000
-1000000000 <= nums[i] <= 1000000000
All nums[i] are distinct
nums is a rotation of a strictly increasing sequence

Optimal Approach & Strategy

Apply binary search on the rotated array, using the relative order of mid and mid+1 to decide which half must contain a peak, and shrink the interval until the peak index is found.

Brute Force Approach

Iterate through the array once, checking each element against its neighbours; return the first index that satisfies the peak condition.

Code Solutions

Language:

JavaScript Solution

Time: O(log n)

function findPeakElement(nums){
    if(nums.length===0) return -1;
    let l=0, r=nums.length-1;
    while(l<r){
        const mid = Math.floor((l+r)/2);
        if(nums[mid] < nums[mid+1]) l = mid+1;
        else r = mid;
    }
    return l;
}

const fs = require('fs');
const input = fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
let idx=0;
const n = input[idx++]||0;
const nums = input.slice(idx, idx+n);
console.log(findPeakElement(nums));

#include <bits/stdc++.h>
using namespace std;

int findPeakElement(const vector<int>& nums) {
    if(nums.empty()) return -1;
    int l=0, r=nums.size()-1;
    while(l<r){
        int mid = l + (r-l)/2;
        if(nums[mid] < nums[mid+1]) l = mid+1;
        else r = mid;
    }
    return l;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; if(!(cin>>n)) return 0;
    vector<int> nums(n);
    for(int i=0;i<n;++i) cin>>nums[i];
    cout<<findPeakElement(nums);
    return 0;
}

import java.io.*;
import java.util.*;

public class Main {
    public static int findPeakElement(int[] nums) {
        if(nums.length==0) return -1;
        int l=0, r=nums.length-1;
        while(l<r){
            int mid = l + (r-l)/2;
            if(nums[mid] < nums[mid+1]) l = mid+1;
            else r = mid;
        }
        return l;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = br.readLine();
        if(line == null || line.isEmpty()) return;
        int n = Integer.parseInt(line.trim());
        int[] nums = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0;i<n;i++) nums[i]=Integer.parseInt(st.nextToken());
        System.out.println(findPeakElement(nums));
    }
}

import sys

def find_peak_element(nums):
    if not nums:
        return -1
    l, r = 0, len(nums)-1
    while l < r:
        mid = (l + r)//2
        if nums[mid] < nums[mid+1]:
            l = mid + 1
        else:
            r = mid
    return l

def main():
    data = sys.stdin.read().strip().split()
    if not data:
        return
    n = int(data[0])
    nums = list(map(int, data[1:1+n]))
    print(find_peak_element(nums))

if __name__ == "__main__":
    main()

function findPeakElement(nums){
    if(nums.length===0) return -1;
    let l=0, r=nums.length-1;
    while(l<r){
        const mid = Math.floor((l+r)/2);
        if(nums[mid] < nums[mid+1]) l = mid+1;
        else r = mid;
    }
    return l;
}

const fs = require('fs');
const input = fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
let idx=0;
const n = input[idx++]||0;
const nums = input.slice(idx, idx+n);
console.log(findPeakElement(nums));

Asked in Top Tech Interviews

Microsoft

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.