Skip to content

2345. Finding the Number of Visible Mountains

  • Time: $O(\texttt{sort})$
  • Space: $O(\texttt{sort})$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
 public:
  int visibleMountains(vector<vector<int>>& peaks) {
    int ans = 0;
    int maxRightFoot = 0;

    ranges::sort(peaks, ranges::less{}, [](const vector<int>& peak) {
      return pair<int, int>(peak[0] - peak[1], -peak[0]);
    });

    for (int i = 0; i < peaks.size(); ++i) {
      const bool overlapWithNext =
          i + 1 < peaks.size() && peaks[i] == peaks[i + 1];
      const int currRightFoot = peaks[i][0] + peaks[i][1];
      if (currRightFoot > maxRightFoot) {
        if (!overlapWithNext)
          ++ans;
        maxRightFoot = currRightFoot;
      }
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
  public int visibleMountains(int[][] peaks) {
    int ans = 0;
    int maxRightFoot = 0;

    Arrays.sort(peaks, Comparator.comparingInt((int[] peak) -> peak[0] - peak[1])
                           .thenComparing((int[] peak) -> peak[0], Comparator.reverseOrder()));

    for (int i = 0; i < peaks.length; ++i) {
      final boolean overlapWithNext = i + 1 < peaks.length && Arrays.equals(peaks[i], peaks[i + 1]);
      final int currRightFoot = peaks[i][0] + peaks[i][1];
      if (currRightFoot > maxRightFoot) {
        if (!overlapWithNext)
          ++ans;
        maxRightFoot = currRightFoot;
      }
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
  def visibleMountains(self, peaks: list[list[int]]) -> int:
    ans = 0
    maxRightFoot = 0

    peaks.sort(key=lambda x: (x[0] - x[1], -x[0]))

    for i, peak in enumerate(peaks):
      overlapWithNext = i + 1 < len(peaks) and peak == peaks[i + 1]
      currRightFoot = peak[0] + peak[1]
      if currRightFoot > maxRightFoot:
        if not overlapWithNext:
          ans += 1
        maxRightFoot = currRightFoot

    return ans