The O(n) Club: Peak Index in a Mountain Array: Because Who Has Time to Climb the Whole Thing?

The O(n) Club: Peak Index in a Mountain Array—Because Who Has Time to Climb the Whole Thing?

⚡ TL;DR

You’re staring at an array that goes up, then down. Want the peak index? Sure, you could walk the whole mountain with a for loop (O(n)), but let’s take the binary search chopper instead (O(log n)). Quick and classy:

for (int i = 1; i < arr.length - 1; i++) {
    if (arr[i] > arr[i - 1] && arr[i] > arr[i + 1]) return i;
}
// But honestly, that's for people who enjoy leg cramps.

🧠 How Devs Usually Mess This Up

Common beginner move: write a linear scan, check each element, and call it a day. Simple? Sure. Efficient? No. Even worse, some try classic binary search, get lost in a forest of monotonicity, and wonder why their peak-finding compass explodes. Fun fact: you can’t binary search a zig-zag—unless you know the trick.

🔍 What’s Actually Going On

Imagine a cartoon mountain: brave hikers clambering up the left, tumbling down the right. At any index mid, peek at arr[mid] versus arr[mid+1]. If you’re still climbing, go right. If you’re heading down or perched up top, go left. It’s binary search, but sideways. Each guess cuts your problem in half until you’re at the top and living your best summit life.

🛠️ PseudoCode

• Start: start = 0; end = arr.length - 1
• While start < end:
  • Calculate mid = start + (end - start) / 2
  • If arr[mid] < arr[mid + 1], you’re on the up-slope: start = mid + 1
  • Else, you’re over the hill: end = mid
• Loop ends when start == end. Congratulations, you found the golden peak index.
• Return start. Yes, it really is that simple if you don’t overthink.

💻 The Code

public int peakIndexInMountainArray(int[] arr) {
    int start = 0, end = arr.length - 1;
    while (start < end) {
        int mid = start + (end - start) / 2;
        if (arr[mid] < arr[mid + 1]) {
            start = mid + 1;
        } else {
            end = mid;
        }
    }
    return start;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Index Danger: Don’t let your mid + 1 slip off the cliff. Loop condition keeps mid safe from the abyss.
• Forget About Checking ‘Is this mid the peak?’ The binary search loop hands you the peak on a silver platter.
• Single Peak Assurance: There’s only one. Multiple peaks? Not in this mountain range.
• Time: O(log n). Because fast code is happy code.
• Space: O(1). No backpacks. Just slick pointer moves.

🧠 Interviewer Brain-Tattoo

“If the path changes slope, follow the gradient—don’t hike in circles looking for the summit.”