The O(n) Club: Find Peak Element: Java’s Favorite Uphill Battle

The O(n) Club: Find Peak Element — Java’s Favorite Uphill Battle

⚡ TL;DR

Need a peak in your int[]? Just look for any nums[i] that’s bigger than its neighbors. Brute force means O(n) climbing every hill. Binary search calls the helicopter: O(log n). Example for caffeine-charged mortals:

// Brute force: mountain goat edition
for (int i = 0; i < nums.length; i++) {
    if ((i == 0 || nums[i] > nums[i - 1]) &&
        (i == nums.length - 1 || nums[i] > nums[i + 1])) {
        return i; // Treat yourself to a coffee break
    }
}
return -1; // Java’s way of saying "you broke math"

🧠 How Devs Usually Mess This Up

Everyone expects a majestic solo peak — surprise, there can be many! Also, someone always forgets the poor edge elements. (Yes, nums[0] would like some attention.) Or you do O(n) work thinking you’re being clever. Spoiler: binary search isn’t just for sorted arrays. Trust issues, right?

🔍 What’s Actually Going On

Imagine your array as a line of cranky toddlers on a field trip. Any one kid taller than the immediate neighbors is a peak — and there’s guaranteed to be at least one because the universe is kind that way. Classic binary search just keeps walking toward the louder, taller toddler. The array’s edges? Treat them as being next to an invisible bottomless pit of sadness (a.k.a. negative infinity), so yes, the ends can be peaks too.

🛠️ PseudoCode

• Start at Both Ends:
  left = 0; right = nums.length - 1;
  Prepare to zig-zag through the mountain range.
• Binary Search Time:
  • Find the mid: mid = (left + right) / 2;
  • Is nums[mid] < nums[mid + 1]? Hike right (left = mid + 1;)! Otherwise, trudge left (right = mid;).

  if (nums[mid] < nums[mid + 1]) {
      left = mid + 1;
  } else {
      right = mid;
  }

  Repeat until left and right collide like two tired hikers.
• Conquered:
  They meet at a peak. Return left (or right, whatever keeps you awake).

💻 The Code

public int findPeakElement(int[] nums) {
    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;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Multiple peaks? You just get a peak, not necessarily the highest. We’re not hiking Everest, just any local maximum.
• Edge drama: Both ends can be peaks. Treat boundaries with respect or suffer the wrath of edge cases.
• Big-O reality: Binary search is O(log n) and O(1) space — unless you get recursive happy. Brute force? Enjoy your O(n) regrets.

🧠 Interviewer Brain-Tattoo

“Binary search: it’s not just for sorted stuff. Peaks happen — and so do silly mistakes.”