Find a Peak Element II LeetCode solution in JavaScript

1
/**
2
 * @param {number[][]} mat
3
 * @return {number[]}
4
 */
5
var findPeakGrid = function (mat) {
6
  /**
7
   * Helper function to find max value in a given list
8
   * Time: O(n)
9
   * Memory: O(1)
10
   */
11
  function maxValueIdx(array) {
12
    let maxIdx = 0;
13
    for (let i = 0; i < array.length; i++) {
14
      if (array[i] > array[maxIdx]) {
15
        maxIdx = i;
16
      }
17
    }
18
    return maxIdx;
19
  }
20

21
  // Helper pointers for Binary Search
22
  let left = 0;
23
  let right = mat.length - 1;
24

25
  while (left < right) {
26
    const midRowIdx = parseInt((left + right) / 2, 10);
27

28
    // Find index with highest value in the mid row
29
    let colIdx = maxValueIdx(mat[midRowIdx]);
30

31
    // If value in the next row is higher - current value is not a pick - check right subgroup
32
    if (mat[midRowIdx][colIdx] < mat[midRowIdx + 1][colIdx]) {
33
      left = midRowIdx + 1;
34
      // If value in the next row is not higher - current value might be a pick - check left subgroup
35
    } else {
36
      right = midRowIdx;
37
    }
38
  }
39

40
  // After completing binary search last value will be pointing to a peak item.
41
  // Complexity:
42
  // Time: Binary Search to find row * Linear search to find max value in a row
43
  // Time: O(log(N) * M) where N - number of rows, M - number of cells
44
  // Memory: O(1)
45
  return [left, maxValueIdx(mat[left])];
46
};