Conceptual Solutions & Library Solutions w/ LeetCode's "Peak Index In Valley Array" Problem ✨

This is part of my series where I explain approaches to solving coding problems. This is to help me articulate my thought process better, and inspire new problem solving approaches for developers!

Problem Statement:

Let's call an array A a mountain if the following properties hold:
A.length >= 3
There exists some 0 < i < A.length - 1 such that A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1]
Given an array that is definitely a mountain, return any i such that A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1].

Somewhat of a doosey right? Don't worry, we'll break this down!

Approach:
We need to look for the point in the array where the mountain stops increasing. We can do this in 3 ways:

1. Scan the array until we reach a point where A[i] > A[i + 1]. This means that the mountain stopped increasing. We can definitely do this with Binary Search (here's a basic overview).
2. The peak index is essentially the max of the array. We can also find that and return its index.

We'll be going over two possible solutions and the trade offs to both.

Solution 1: Recursive Binary Search

// Time complexity: O(log(n))
// Space complexity: O(n)
const peakIndexInMountainArray = (A, low = 0, high = A.length - 1) => {
    if (!A.length) 
        return -1

    const mid = ((low + high) / 2) | 0

    if (A[mid] > A[mid - 1] && A[mid] > A[mid + 1])
        return mid

    if (A[mid] < A[mid - 1]) 
        return peakIndexInMountainArray(A, low, mid)

    if (A[mid] < A[mid + 1])
        return peakIndexInMountainArray(A, mid, high)
}

Explanation:
Here we add optional arguments low and high as a way for us to keep track of the initial low and high values. low is initially 0, and high is A.length -.

Recursive solutions have functions that call themselves over and over again until it finds the solution it needs. In this case, we'll call peakIndexInMountainArray over and over until we find the peak index.

A recursive solution can be one intuitive way of solving this since we're repeating steps for smaller parts of the array. It also provides a readalbe solution that's easy to understand.

1. If the array is empty, return -1 since there's nothing to search

2. Find the midpoint of the array with the distance formula (low + high) / 2 and then truncate the decimal using Bitwise OR:
   

   const mid = ((low + high) / 2) | 0
   

3. If the midpoint is greater than the previous number AND if the midpoint's greater than the next number we found the peak. This would be our base case, which is where we'll stop making recursive calls to the function.
   

   if (A[mid] > A[mid - 1] && A[mid] > A[mid + 1])
       return mid
   

4. If it's less than the previous number, we'll search the lower half recursively with mid becoming the new high point:
   

   if (A[mid] < A[mid - 1]) 
       return peakIndexInMountainArray(A, low, mid)
   

5. If it's less than the next number, we'll search the upper half recursively with mid becoming the new low point:
   

   if (A[mid] < A[mid + 1]) 
       return peakIndexInMountainArray(A, mid, high)
   

With recursive solutions in general, we need to consider what's called "The Call Stack". Each time we call a function, it's pushed into the call stack--This is how we keep track of all our recursive calls which is why the space complexity is O(n). Once we've hit our base case, we can pop the function call from the stack, and pass the solution retrieved from the last call to peakIndexInMountainArray().

Solution 2: Super Fun One Liner!

// Time complexity: O(n)
// Space complexity: O(1)
const peakIndexInMountainArray = A => {
    return A.indexOf(Math.max(...A))
}

Explanation:
We know that the peak index is the max of the array, so this can be a good semantic approach for finding the solution!

1. Since Math.max() takes in multiple arguments We use spread syntax to add all the array values into the method. Then it will give us the max.
2. Now that we have the max, we'll use Array.indexOf() to return the index of the mountain peak.

The cool thing about JavaScript is the ability to come up with fun one liners on top of other solutions! It's good to think of approaches that are independent of library methods in case your interviewer wants to see your understanding of the concept. Library methods not only help one understand JavaScript's functionality, they also help think about these concepts differently and succinctly.

Thanks for reading! As always questions, feedback, and ideas are always encouraged. Happy hacking!