Finding the number of visible mountains

Array Stack Sorting Monotonic Stack

37.2% acceptance

Mar 31, 2026

183

You are given a 0-indexed 2D integer array peaks where peaks[i] = [xi, yi] states that mountain i has a peak at coordinates (xi, yi). A mountain can be described as a right-angled isosceles triangle, with its base along the x-axis and a right angle at its peak. More formally, the gradients of ascending and descending the mountain are 1 and -1 respectively. A mountain is considered visible if its peak does not lie within another mountain (including the border of other mountains). Return the number of visible mountains.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn visible_mountains(peaks: Vec<Vec<i32>>) -> i32 {
    // Convert each peak (x, y) to interval [x-y, x+y] (base of the triangle)
    // A mountain is hidden if its interval is contained within another mountain's interval
    // Also need to handle duplicate peaks (both become invisible)
    let n = peaks.len();
    let mut intervals: Vec<(i32, i32, usize)> = peaks.iter().enumerate()
      .map(|(i, p)| (p[0] - p[1], p[0] + p[1], i))
      .collect();
    // Sort by left ascending, then by right descending
    intervals.sort_by(|a, b| a.0.cmp(&b.0).then(b.1.cmp(&a.1)));
    
    // Check for duplicates (same interval)
    let mut dup = vec![false; n];
    for i in 1..intervals.len() {
      if intervals[i].0 == intervals[i-1].0 && intervals[i].1 == intervals[i-1].1 {
        dup[i] = true;
        dup[i-1] = true;
      }
    }
    
    let mut count = 0;
    let mut max_right = i32::MIN;
    for i in 0..intervals.len() {
      if intervals[i].1 <= max_right {
        // This interval is contained in a previous one
        continue;
      }
      max_right = intervals[i].1;
      if !dup[i] {
        count += 1;
      }
    }
    count
  }
}