June 30, 2025

🏔️ Finding a Peak Element in an Array — Efficient Solutions in Java (with Java 21 Best Practices)

📌 Problem Statement

You are given an integer array nums. Your task is to find a peak element and return its index.

A peak element is one that is:

  • strictly greater than its neighbors.

  • i.e., nums[i - 1] < nums[i] > nums[i + 1].

Special Notes:

  • You only need to return any one peak — not all.

  • The array may have multiple peaks.

  • Assume nums[-1] and nums[n] are -∞ (imaginary values outside the array).

🧠 Intuition — What Is the Question Really Asking?

Imagine you're walking along a mountain trail, and someone asks:

“Can you find a point where you're standing on a hilltop, higher than both the person behind you and ahead of you?”

You don’t need the highest mountain, just any place where you're on top compared to your neighbors.

Why is this interesting?

Because instead of checking every point on the trail, you can cleverly skip sections using the idea that:

  • If you're going uphill, a peak must lie ahead.

  • If you're going downhill, a peak must lie behind or at your current position.

This observation is perfect for binary search — we can reduce our search space by half each time.

🧪 Example

Given:

int[] nums = {1, 2, 3, 1};

  • At index 2, nums[2] = 3, and 3 > 2 and 3 > 1 → so index 2 is a peak.

🚶‍♂️ Approach 1: Brute Force (Linear Scan)

Go element by element and check if it's greater than its neighbors.

public static int findPeakLinear(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        boolean leftOk = (i == 0 || nums[i] > nums[i - 1]);
        boolean rightOk = (i == nums.length - 1 || nums[i] > nums[i + 1]);
        if (leftOk && rightOk) return i;
    }
    return -1; // fallback
}

✅ Pros:

  • Very easy to implement

❌ Cons:

  • Time complexity: O(n)

  • Not efficient for large arrays

⚡ Approach 2: Binary Search (Optimal and Recommended)

Use the fact that a peak exists if the slope changes from rising to falling. If nums[mid] < nums[mid + 1], move right. Else, move left.

Java 21 Version

public class PeakFinder {

    public static int findPeakElement(int[] nums) {
        if (nums == null || nums.length == 0)
            throw new IllegalArgumentException("Array must not be null or empty");

        int left = 0, right = nums.length - 1;

        while (left < right) {
            int mid = Math.addExact(left, (right - left) / 2);

            if (nums[mid] < nums[mid + 1]) {
                left = mid + 1; // peak is to the right
            } else {
                right = mid; // peak is to the left or at mid
            }
        }

        return left;
    }
}

⏱️ Time: O(log n)

📦 Space: O(1)

✅ Pros:

  • Very efficient

  • Guarantees a peak due to the problem’s conditions

🧩 Approach 3: Recursive Divide and Conquer

Same logic as binary search, but using recursion:

public class PeakFinder {

    public static int findPeakRecursive(int[] nums) {
        return search(nums, 0, nums.length - 1);
    }

    private static int search(int[] nums, int left, int right) {
        if (left == right) return left;

        int mid = left + (right - left) / 2;

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

📈 Real-World Analogy (Peak Hiker)

Think of yourself as a hiker on a trail:

  • When the path is going up, you know a peak is ahead.

  • When the path goes down, the peak was behind or at your feet.

  • If you're already on a peak, stop walking.

Binary search lets you skip large parts of the trail because you're always choosing the direction that guarantees a peak exists.

🧠 Why Binary Search Works Here

Even though the array is not sorted, you can still apply binary search because:

  • There is always at least one peak.

  • At each step, you can eliminate half the array based on the comparison of nums[mid] and nums[mid+1].

✅ Summary Table

Approach Time Complexity Space Complexity Best Use Case
Linear Scan O(n) O(1) Small inputs or quick demo
Binary Search O(log n) O(1) Optimal, all scenarios ✅
Recursive O(log n) O(log n) When recursion is preferred

💡 Interview Tip

Even if the array isn't sorted, binary search can still be applied in problems where the structure allows elimination of search space — and this is a perfect example.

🛠️ Extras for Practice

  • Modify to find all peak elements

  • Apply a similar approach for a 2D matrix peak problem

  • Implement in a functional style using Java Streams (advanced)

Would you like this content:

  • Exported as HTML for Blogger?

  • Converted to Markdown for Dev.to or GitHub Pages?

  • Embedded with code playground for interactive testing?

Let me know — I can format it to suit your blog setup!

Posted by