Xuanyi Fu Blog
0%

Find Peak Element(s)

Posted on Edited on
Symbols count in article: 9.4k

LC162 Find one Peak Element in 1D Array

[Codewars] Find All Peak Elements in 1D Array

LC1901 Find one Peak Element in 2D Matrix

Find Peak Element in 1D Array

LC162 Find one Peak Element in 1D Array

A peak element is an element a[n] in the array a such that:

  • when n == 0, a[n] > a[n + 1]
  • when n == a.size(), a[n] > a_[n - 1]
  • otherwise a[n] > a[n - 1] and a[n] > a[n + 1]

1D Peak-Finding Algorithm Demystify

Subarray Peak Condition

Prove the Existence of the Peak Element

In the Constraints of LC162, we could find that nums[i] != nums[i + 1], which means there is no continuous duplicated value in test cases. For example, array like [1,2,2,3,4] is not valid in this problem.

This constraint is critical because it indicates there always exists a peak in such an array. Let us prove this:

  • We could always find a max element in the array.
  • Because nums[i] != nums[i + 1], the max element we found must meet the condition a[n] > a[n-1] && a[n] > a[n + 1].
  • If the max element is on the boundary, this also holds becasue of the condition nums[-1] = nums[n] = -∞.
  • The max element must be a peak.
  • Thus, there must be a peak in such an array.

But this conclusion may not hold in a specific range of such array. Consider the subarray [2,1] of [1,9,1,3,2,1]. [2,1] may have 2 as its peak if it is an array as its own, whereas being a subarray, it has no peak.

Derive the Subarray Peak Condition

Let us consider how to guarantee there is a peak in the subarray:

  • there must be a max element in the subarray.
  • if the max element lies in the middle of the subarray, we are good. It must be greater than its adjacents, which makes it a peak.
  • if the max element lies on the boundary of the subarray, then we are in trouble. We do not know whether the max element is greater than the elements out of this subarray.

Therefore, if we want to make sure there will be a peak in a subarray, we must impose the condition that: 

1
2
3
4
5
6
7
8
         ┌───────────────┐
         │   SUBARRAY    │
     ┌───┼──┬─────────┬──┼───┐
     │f-1│f │         │l │l+1│
...  │   │  │         │  │   │ ...
     └───┼──┴─────────┴──┼───┘
         │   SUBARRAY    │
         └───────────────┘
  • the first element f in the subarray must be greater than the element f - 1 on the left of it.
  • the last element l in the subarray must be greater than the element l + 1 on the right of it.

This condition will be referred as “subarray peak condition.”

A Smell of Greedy

There could be multiple peaks in an array. For example, given the array [1,2,1,2,1], all 2s in the array could be considered as a peak.

However, LC162 requires finding only one of the possible peaks. This gives a sense of “greedy”.

Time Complexity Indicates the Solution

Besides, LC162 requires that the algorithm runs in O(log n) time. This indicates that “divide and conquer” might be used.

Get Them All Together!

Inspired by the O(log n) time complexity, let us divide the subarray into three parts, like what we always do in binary search, lower bound, or other equivalence.

1
2
3
4
5
6
7
8
│        A        │ B │        C        │
│◄───────────────►│◄─►│◄───────────────►│
│                 │   │                 │
├───┬───┬─────┬───┼───┼───┬─────┬───┬───┤
│   │   │     │(m+│(m+│(m+│     │   │   │
│ m │ 1 │ ... │n)/│n)/│n)/│ ... │n-1│ n │
│   │   │     │2-1│ 2 │2+1│     │   │   │
└───┴───┴─────┴───┴───┴───┴─────┴───┴───┘

  • Given that the subarray [m .. n] meet the “subarray peak condition” mentioned before.

  • if (m+n)/2 is less than (m+n)/2 - 1, then we could know for sure that the range [m, (m+n)/2) has a peak in it. We are greedy, then we do not care about the range [(m+n)/2, n) anymore, even if there could be a peak in it.

  • if (m+n)/2 is less than (m+n)/2 + 1, then we could know for sure that the range [(m+n)/2 + 1, n) has a peak in it. Again, we are greedy. We do not care about the other range.

  • Otherwise, we have (m+n)/2 > (m+n)/2 - 1 && (m+n)/2 > (m+n)/2 + 1, which indicates that we have found the answer!

We have a new range from the previous step that still meets the “subarray peak condition”. Perform the previous step recursively until the range shrinks into an empty range. Then we have our answer to the problem.

Implementation

This binary-search-like algorithm requires random access of an array to achieve the O(log n) time complexity. Let us pick an imperative, low-level language for convenience. C++ might be a good choice.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
namespace {
template<typename RandomAccessIt>
RandomAccessIt findPeakElementImpl(RandomAccessIt first, 
                                   RandomAccessIt last, 
                                   RandomAccessIt begin, 
                                   RandomAccessIt end) {
  const auto mid = first + (last - first) / 2;
  
  if((mid + 1 < end) && (*mid < *(mid + 1))) {
    return findPeakElementImpl(mid + 1, last, begin, end);
  } else if((mid - 1 >= first) && (*mid < *(mid - 1))) {
    return findPeakElementImpl(first, mid, begin, end);
  } else {
    return mid;
  }
}
}

class Solution {
public:
  int findPeakElement(vector<int>& nums) {
    return findPeakElementImpl(nums.begin(), 
                               nums.end(), 
                               nums.begin(), 
                               nums.end()) 
           - nums.begin();
  }
};

Find All Peak Elements in 1D Array

[Codewars] Find All Peak Elements in 1D Array

Difference between the Leetcode version

  • There could be continuous duplicated values in the array. [1,1,1,1,1] is considered as a valid test case.
  • No such assumption that nums[-1] = nums[n] = -∞. Thus, the first and the last element could never be a peak. In the array [3,1,2], 3 and 2 is not peak anymore.
  • The conclusion “ there always exists a peak” we had for the previous Leetcode does not hold here. Thus, the “ subarray peak condition” we have before does not work in this problem. In the array [1,1,1,1], there is no peak.
  • Plateaus should be treated carefully. [1,2,2,2,1] has a plateau [2,2,2]. In this case, the plateau’s leading element 2 with index 1 should be taken as the peak.
  • We have to find all peaks in the array. We have to access every element in the array to achieve this, which means our solution is at least O(n). We could not be greedy like we did in the previous problem.

Linear search with Pipeline

There is no greedy and divide and conquer trick we could perform on this problem to find all peaks. A trivial linear search with extra care with the plateaus could work pretty well.

Take [3, 2, 3, 6, 6, 1, 2, 3, 2, 1, 2, 3] as an example.

  1. The problem requires not only peaks, but also the indices of peaks. Let’s mark every element with an index first. Zip all elements with its index, we have:
    [(0,3),(1,2),(2,3),(3,6),(4,6),(5,1),(6,2),(7,3),(8,2),(9,1),(10,2),(11,3)]

  2. Now we have the indices, we are safe to cancel all continuous duplicates without losing the information of their indices.

[(0,3),(1,2),(2,3),(3,6),(5,1),(6,2),(7,3),(8,2),(9,1),(10,2),(11,3)]

  1. Take every three elements in the array put them into an array of array.

[[(0,3),(1,2),(2,3)],[(1,2),(2,3),(3,6)],[(2,3),(3,6),(5,1)],[(3,6),(5,1),(6,2)],[(5,1),(6,2),(7,3)],[(6,2),(7,3),(8,2)],[(7,3),(8,2),(9,1)],[(8,2),(9,1),(10,2)],[(9,1),(10,2),(11,3)]]

  1. Check the middle element in every 3-element array. Keep it if it is a peek.

[[(2,3),(3,6),(5,1)],[(6,2),(7,3),(8,2)]]

  1. Extract the middle tuple from the result.

[(3,6),(7,3)]

Pipeline Implementation

A functional programming language will suit this pipeline-like solution pretty well. Let’s choose Haskell for this problem.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
module PickPeak.JorgeVS.Kata where
import Data.List (groupBy)
data PickedPeaks = PickedPeaks { pos :: [Int], peaks :: [Int]} deriving (Eq, Show)
pickPeaks :: [Int] -> PickedPeaks
pickPeaks = uncurry PickedPeaks
          . unzip
          . map takeSnd
          . filter hasPeak
          . take3
          . cancelContinousDuplicates
          . zip [0..] 
            where
              cancelContinousDuplicates = map head . groupBy (\l r -> snd l == snd r)
              take3 [] = []
              take3 ls@(x:xs) = (take 3 ls) : (take3 xs)
              hasPeak [(_, x), (_, y), (_, z)] = y > x && y > z
              hasPeak _ = False
              takeSnd = head . tail

Sliding Window

A sliding window could also address this problem. Take [3, 2, 3, 6, 6, 1] for example.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 │            FIRST ELM CANNOT       │
 ▼                │ │ BE A PEAK      ▼
┌▼┌─┬─┬─┬─┬─┐    ┌▼┐▼┌─┬─┬─┬─┐    ┌─┐▼┌─┬─┬─┬─┐
│3│2│3│6│6│1│    │3│2│3│6│6│1│    │3│2│3│6│6│1│
└─┴─┴─┴─┴─┴─┘    └─┴─┴─┴─┴─┴─┘    └─┴─┴─┴─┴─┴─┘

 2 > 3 && 2 > 3       │           3 > 2 && 3 > 6
   │ │  FAILED        ▼                │ │ FAILED
┌─┐▼┐▼┌─┬─┬─┐    ┌─┬─┐▼┌─┬─┬─┐    ┌─┬─┐▼┐▼┌─┬─┐
│3│2│3│6│6│1│    │3│2│3│6│6│1│    │3│2│3│6│6│1│
└─┴─┴─┴─┴─┴─┘    └─┴─┴─┴─┴─┴─┘    └─┴─┴─┴─┴─┴─┘

       │         *last = *first   6 > 3 && 6 > 1, PEAK FOUND
       ▼                │ │              │   │
┌─┬─┬─┐▼┌─┬─┐    ┌─┬─┬─┐▼┐▼┌─┐    ┌─┬─┬─┐▼┌─┐▼┐
│3│2│3│6│6│1│    │3│2│3│6│6│1│    │3│2│3│6│6│1│
└─┴─┴─┴─┴─┴─┘    └─┴─┴─┴─┴─┴─┘    └─┴─┴─┴─┴─┴─┘

           │     LAST ELM CANNOT BE A PEAK
           ▼                │ │
┌─┬─┬─┬─┬─┐▼┐    ┌─┬─┬─┬─┬─┐▼┐▼
│3│2│3│6│6│1│    │3│2│3│6│6│1│    FINISHED
└─┴─┴─┴─┴─┴─┘    └─┴─┴─┴─┴─┴─┘
  1. All the elements in the window are equal.
  2. The window is marked as two pointers, first and last.
  3. The window is initialized with size 0.
  4. if last is end because the last element of the array cannot be a peak, we have to stop there.
  5. if first is begin because the first element of the array cannot be a peak, we move first one step forward.
  6. if the range size between first and last is less than 1, we must move last one step forward.
  7. we continue to move last forward if *last == *first to cancel all continuous duplications. But we have to make sure last != end
  8. check first again first - 1 and last to examine whether it is a peak.
  9. reset first to last, continue the loop.

Sliding Window Implementation

C++ should play the role this time.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
PeakData pick_peaks(const std::vector<int> &v) {
  auto result = PeakData{};
  auto first = v.begin();
  auto last = v.begin();

  while(last != v.end()){
    if(first == v.begin()){
      ++first;
      continue;
    }

    if(last - first < 1){
      ++last;
      continue;
    }

    // first != v.begin() 
    // && last != v.end()
    // && last - first >= 1
    if(*last == *first) {
      ++last;
      continue;
    }

    // && *last != *first
    if(*first > *(first - 1) && *first > *last){
      result.pos.push_back(first - v.begin());
      result.peaks.push_back(*first);
    }

    first = last;
  }

  return result;
}

Find one Peak Element in 2D Matrix

LC1901 Find one Peak Element in 2D Matrix

It is similar to LC162 Find one Peak Element in 1D Array but in an m x n matrix.

  • No two adjacent cells are equal
  • An outer perimeter surrounds the matrix with values that is less than every element in the matrix.
  • Only one peak is required.
  • The algorithm should run in O(m log(n)) or O(n log(m)), which indicates a divide and conquer with linear search.

Submatrix peak condition

We could still conclude the existence of peak element in the matrix:

  1. There are no equal adjacent cells.
  2. There exists a max element in the matrix.
  3. Suppose the matrix element does not lie on the boundary of the matrix. Given that “there are no equal adjacent cells”, the max element must be greater than all its adjacent. Therefore, it is a peak.
  4. Suppose the matrix element lies on the boundary of the matrix. An outer perimeter surrounds the matrix with the value of -1. -1 is less than all elements in the matrix. The max element is still greater than all elements surrounding it. Therefore, it is a peak. 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
┌─┬─┬─┬─┬─┬─┬─┬─┐  ┌─┬─┬─┬─┬─┬─┬─┬─┐  ┌─┬─┬─┬─┬─┬─┬─┬─┐
│-│-│-│-│-│-│-│-│  │-│-│-│-│-│-│-│-│  │-│-│-│-│-│-│-│-│
├─┼─┼─┼─┼─┼─┼─┼─┤  ├─┼─┼─┼─┼─┼─┼─┼─┤  ├─┼─┼─┼─┼─┼─┼─┼─┤
│-│ │ │x│ │ │ │-│  │-│ │ │ │ │ │ │-│  │-│ │ │ │ │ │ │-│
├─┼─┼─┼─┼─┼─┼─┼─┤  ├─┼─┼─┼─┼─┼─┼─┼─┤  ├─┼─┼─┼─┼─┼─┼─┼─┤
│-│ │x│M│x│ │ │-│  │-│ │ │x│ │ │ │-│  │-│x│ │ │ │ │ │-│
├─┼─┼─┼─┼─┼─┼─┼─┤  ├─┼─┼─┼─┼─┼─┼─┼─┤  ├─┼─┼─┼─┼─┼─┼─┼─┤
│-│ │ │x│ │ │ │-│  │-│ │x│M│x│ │ │-│  │-│M│x│ │ │ │ │-│
├─┼─┼─┼─┼─┼─┼─┼─┤  ├─┼─┼─┼─┼─┼─┼─┼─┤  ├─┼─┼─┼─┼─┼─┼─┼─┤
│-│-│-│-│-│-│-│-│  │-│-│-│-│-│-│-│-│  │-│-│-│-│-│-│-│-│
└─┴─┴─┴─┴─┴─┴─┴─┘  └─┴─┴─┴─┴─┴─┴─┴─┘  └─┴─┴─┴─┴─┴─┴─┴─┘

┌─┬─┬─┬─┬─┬─┬─┬─┐
│-│-│-│-│-│-│-│-│    - -> -1
├─┼─┼─┼─┼─┼─┼─┼─┤    M -> the max element
│-│x│ │ │ │ │ │-│    x -> adjacent elements
├─┼─┼─┼─┼─┼─┼─┼─┤
│-│M│x│ │ │ │ │-│    ALL FOUR POSSIBLE POSITIONS
├─┼─┼─┼─┼─┼─┼─┼─┤
│-│x│ │ │ │ │ │-│    FOR THE MAX ELEMENT
├─┼─┼─┼─┼─┼─┼─┼─┤
│-│-│-│-│-│-│-│-│
└─┴─┴─┴─┴─┴─┴─┴─┘

Like LC162. This time we try to derive the condition for the existence of a peak in a submatrix within column [first, last).

  1. There exists a max element in the submatrix.
  2. Suppose the max element does not lie on the boundary of the submatrix. As proved above, it is a peak.
  3. Suppose the max element lies on the upper or lower boundary of the submatrix. As proved above, it is a peak.
  4. Suppose the max element lies on the left boundary of the submatrix. We assert that if there exists an element in boundary, such that the element is greater than the max element(s) in its left adjacent column, then the max element must be a peak. Let us prove it:
    • The max element must be greater than or equal to the element which is greater than the max element(s) in its left adjacent column.
      The max element must be greater than or equal all elements in its left adjacent column.
    • The max element is greater than its left element.
    • There are no equal adjacent cells. The max element is greater than its upper, lower, and right elements.
    • Thus, the max element is a peak.
  5. Suppose the max element lies on the right boundary of the submatrix. We have a similar condition to that of the left boundary.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
       first        last
         │ SUBMATRIX │
         ├─┬─┬─┬─┬─┬─┤
         │-│-│-│-│-│-│
     ┌─┐ ├─┼─┼─┼─┼─┼─┤
     │1│ │2│ │ │ │ │ │
     ├─┤ ├─┼─┼─┼─┼─┼─┤
     │5│ │1│ │ │ │ │ │
     ├─┤ ├─┼─┼─┼─┼─┼─┤
...  │3│ │8│ │ │ │ │ │ ...
     ├─┤ ├─┼─┼─┼─┼─┼─┤
     │7│ │5│ │ │ │ │ │
     ├─┤ ├─┼─┼─┼─┼─┼─┤
     │2│ │1│ │ │ │ │ │
     └─┘ ├─┼─┼─┼─┼─┼─┤
         │-│-│-│-│-│-│
         ├─┴─┴─┴─┴─┴─┤
         │ SUBMATRIX │

     8 IS GREATER THAN THE MAX ELEMENT OF
     ITS LEFT COLUMN. THE COLUMN OF 8 MEETS
     THE __SUBMATRIX PEAK CONDITION__

Therefore, the “ submatrix peak condition” could be described as below: There exists a peak in the submatrix [first, last) when both of the following conditions hold

  • There exists an element in the first column such that the element is greater than the max element of the first - 1 column. Otherwise, first must be 0.
  • There exists an element in the last - 1 column such that the element is greater than the max element of the last column. Otherwise, last must be the number of matrix columns.

Greedy, Divide and Conquer Algorithm Again

Let us design our algorithm.

  • We start with first == 0 and last == number of columns.
  • We pick the middle column mid between last and first.
  • We find the max element in the mid column
  • If the max element we found is less than the element on its left, then the column mid - 1 meets the “submatrix peak condition”. A peak in the [first, mid) submatrix exists. We continue our search in the [first, mid) submatrix.
  • If the max element we found is less than the element on its right, then the column mid + 1 meets the “submatrix peak condition”. There exists a peak in the [mid + 1, last) submatrix. We continue our search in the [mid + 1, last) submatrix.
    Otherwise, the max element we found is greater than both its left and right elements. It is a peak.

Implementation

Point for Matrix Coordinate

All elements in the matrix are located by a pair of integers. It is a bad practice to pass two primitives around. We’d better associate them together and give them a name.

Furthermore, we could provide some utility functions to return the left and right points of a given point.

1
2
3
4
5
6
7
8
9
10
11
struct Point {
  const int x_, y_;

  Point Left() const {
    return Point{x_, y_ - 1};
  }

  Point Right() const {
    return Point{x_, y_ + 1};
  }
};

MatrixAdapter for Boundary Conditions

An outer perimeter surrounds the matrix with the value -1. We must avoid the cumbersome boundary-checking procedures because they are always a good source of bugs. The best practice is implementing a wrapper around the original matrix. Let the wrapper handle the access to the element in the matrix. Besides, we need to find the row index of the max element in a given column. For convenience, we implement this helper function as a member function.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class MatAdapter {
  using RawMat = std::vector<std::vector<int>>;
public:
  explicit MatAdapter(const RawMat &rawMat) : mat_{rawMat} {}

  int At(size_t x, size_t y) const {
    if(x < 0
    || y < 0
    || mat_.empty()
    || mat_.front().empty()
    || x >= mat_.size()
    || y >= mat_.front().size()) {
      return -1;
    }

    return mat_[x][y];
  }

  int At(Point pt) const {
    return At(pt.x_, pt.y_);
  }

  int findMaxRowInMatAtCol(int col) const {
    int max = INT32_MIN;
    int maxIdx = -1;
    for(size_t i = 0; i < mat_.size(); ++i) {
      if(max < mat_[i][col]){
        maxIdx = i;
        max = mat_[i][col];
      }
    }
    return maxIdx;
  }

private:
  const RawMat &mat_;
};

findPeakGridRec, the Recursive Algorithm

There is not too much I have to explain. The code explains itself.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Point findPeakGridRec(int first, int last, const MatAdapter& mat) {
  const auto midCol = first + (last - first) / 2;
  const auto maxRow = mat.findMaxRowInMatAtCol(midCol);
  const auto maxPt = Point{maxRow, midCol};
  const auto leftPt = maxPt.Left();
  const auto rightPt = maxPt.Right();
  const auto maxVal = mat.At(maxPt);

  if(maxVal < mat.At(leftPt)) {
    return findPeakGridRec(first, midCol, mat);
  } else if(maxVal < mat.At(rightPt)) {
    return findPeakGridRec(midCol + 1, last, mat);
  } else {
    return maxPt;
  }
}

Put them all together

Finally, make an entrance of the algorithm with the templates provided by Leetcode.

1
2
3
4
std::vector<int> findPeakGrid(std::vector<std::vector<int>>& mat) {
  const auto maxPt = findPeakGridRec(0, mat.front().size(), MatAdapter{mat});
  return {maxPt.x_, maxPt.y_};
}