Galaxy Temperature Peaks — Problem Statement & Solution Guide

ArraysMediumModified binary search

TimeO(log n)

SpaceO(1)

Problem Description

Given an integer array temps that is monotonic on each side of a single maximum element, either strictly increasing then strictly decreasing or strictly decreasing then strictly increasing, locate and return the index of that maximum. The array contains at least one element and exactly one peak. Your algorithm must run in logarithmic time and use constant extra space.

DSA Pattern Breakdown

"Galaxy Temperature Peaks"

medium

WHY DOES IT MATTER?

Unimodal peak finding is a fundamental pattern for optimization problems where a single optimum exists, such as maximizing profit, latency, or signal strength. Mastering this pattern teaches you to exploit monotonicity, a skill that translates to many real‑world binary‑search scenarios.

OPTIMIZATION CHALLENGE

The breakthrough is recognizing that a single comparison (mid vs mid+1) tells you which half contains the peak, allowing you to discard the other half entirely. This eliminates the need for linear scans or extra data structures.

REAL-WORLD CONNECTION

Think of a mountain ridge in a distributed sensor network: each sensor reports altitude, rising to the summit then falling. Locating the summit by probing only half the sensors at a time mirrors binary search on a unimodal array, reducing communication overhead dramatically.

When coding, always guard against out‑of‑bounds when accessing mid+1; use a while loop with low < high and compute mid = low + (high‑low)/2. Return low (or high) after the loop – both converge to the peak index.

COMPLEXITY AT A GLANCE

⏱ Time:O(log n)

💾 Space:O(1)

Core Theory — Why This Approach?

The array described is a classic unimodal sequence – it strictly increases up to a single peak and then strictly decreases, or the reverse. A naïve linear scan will locate the peak by checking each neighbor, but that incurs O(n) time, which becomes prohibitive for massive telemetry logs or real‑time sensor streams where latency matters. The optimal solution leverages binary search on the monotonic halves: by comparing the middle element with its neighbor you can determine which side the peak resides on, discarding the opposite half each iteration. This divide‑and‑conquer approach preserves the logarithmic bound because each step halves the search space, and it requires only a few index variables, yielding O(1) auxiliary space.

Interview Questions on This Problem

Q1How would you modify the binary‑search solution if the array could contain plateaus (equal adjacent values) around the peak?

Treat equal neighbors as part of the increasing side; move the low pointer right when nums[mid] <= nums[mid+1] and move high left otherwise, ensuring you still converge on the leftmost maximum.

Q2A fintech platform stores daily price volatility in a unimodal array. How can you guarantee O(log n) retrieval of the day with maximum volatility while handling streaming updates?

Maintain the array immutable for each batch; for each new batch run the binary‑search on the refreshed segment. If updates are incremental, use a segment tree that stores local peaks, allowing O(log n) query and O(log n) update.

Q3In a high‑growth startup, you need to find the peak temperature in a distributed log where each node holds a sorted slice of the overall unimodal sequence. What strategy would you use?

First perform a parallel binary search on each slice to locate local candidates, then a coordinator performs a final binary search across the boundary values, achieving overall O(log n) time with minimal cross‑node communication.

Examples

Example 1

Input

[2,5,9,12,11,7,3]

Output

Explanation: The sequence rises from 2 to 12 and then falls. The largest value 12 is at index 3, so the answer is 3.

Example 2

Input

[40,35,30,25,27,33,38]

Output

Explanation: The array starts decreasing from 40, reaches a minimum at index 3, then rises. The maximum element 40 is at index 0, which is the peak.

Example 3

Input

[1,3,5,7,9,8,6,4,2]

Output

Explanation: Values increase up to 9 at index 4 and then decrease. Hence the peak index is 4.

Constraints

1<=temps.length<=200000
-1000000000<=temps[i]<=1000000000
All elements are distinct
Exactly one peak exists

Optimal Approach & Strategy

Use binary search: compare mid with mid+1, move the high pointer left if mid is greater, otherwise move the low pointer right, converging on the peak.

Brute Force Approach

Linearly scan the array and return the index where an element is greater than both its neighbors (or the array ends).

Verified Code Solutions

Language:

JavaScript Solution

Time: O(log n)

/**
 * @param {number[]} temps
 * @return {number}
 */
var findPeakIndex = function(temps) {
    let left = 0, right = temps.length - 1;
    
    while (left < right) {
        const mid = Math.floor((left + right) / 2);
        
        if (temps[mid] < temps[mid + 1]) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    
    return left;
};

// Driver code
const temps = [2, 5, 9, 12, 11, 7, 3];
console.log(findPeakIndex(temps));

#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    int findPeakIndex(vector<int>& temps) {
        int left = 0, right = temps.size() - 1;
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            
            if (temps[mid] < temps[mid + 1]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        return left;
    }
};

int main() {
    vector<int> temps = {2, 5, 9, 12, 11, 7, 3};
    Solution sol;
    cout << sol.findPeakIndex(temps) << endl;
    return 0;
}

import java.util.*;

class Solution {
    public int findPeakIndex(int[] temps) {
        int left = 0, right = temps.length - 1;
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            
            if (temps[mid] < temps[mid + 1]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        return left;
    }
}

public class Main {
    public static void main(String[] args) {
        int[] temps = {2, 5, 9, 12, 11, 7, 3};
        Solution sol = new Solution();
        System.out.println(sol.findPeakIndex(temps));
    }
}

from typing import List

class Solution:
    def findPeakIndex(self, temps: List[int]) -> int:
        left, right = 0, len(temps) - 1
        
        while left < right:
            mid = (left + right) // 2
            
            if temps[mid] < temps[mid + 1]:
                left = mid + 1
            else:
                right = mid
        
        return left

# Driver code
if __name__ == "__main__":
    temps = [2, 5, 9, 12, 11, 7, 3]
    sol = Solution()
    print(sol.findPeakIndex(temps))

/**
 * @param {number[]} temps
 * @return {number}
 */
var findPeakIndex = function(temps) {
    let left = 0, right = temps.length - 1;
    
    while (left < right) {
        const mid = Math.floor((left + right) / 2);
        
        if (temps[mid] < temps[mid + 1]) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    
    return left;
};

// Driver code
const temps = [2, 5, 9, 12, 11, 7, 3];
console.log(findPeakIndex(temps));

Asked in Top Tech Interviews

Amazon

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.

Galaxy Temperature Peaks Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Constraints

More Arrays

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Galaxy Temperature Peaks — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Asked in Top Tech Interviews

Solve in Interative Editor