Difficulty: 🟡 Medium
Topics: Array, Stack, Sorting, Monotonic Stack

Solution

LeetCode 2345 - Finding the Number of Visible Mountains

Problem Understanding

Each mountain is represented by a peak point (x, y). Because the mountain is a right-angled isosceles triangle with slopes +1 and -1, its shape is completely determined by its peak.

For a mountain with peak (x, y):

The left boundary touches the x-axis at x - y
The right boundary touches the x-axis at x + y

So every mountain can be represented as an interval:

$$[x - y,\ x + y]$$

A mountain is considered visible if its peak is not inside or on the boundary of another mountain.

That means mountain A hides mountain B if:

$$A.left \le B.left \quad \text{and} \quad A.right \ge B.right$$

In interval terms, one interval fully contains the other.

The input is an array peaks, where each element contains the coordinates of a mountain peak. The output is the number of mountains that remain visible after considering all overlaps and containments.

The constraints are important:

Up to 10^5 mountains
Coordinates up to 10^5

An O(n^2) solution would require checking every pair of mountains and would be too slow. We need something closer to O(n log n).

There are several tricky edge cases:

Completely identical mountains, such as [[1,3],[1,3]]
Mountains that only touch on the border
Mountains nested inside larger mountains
Mountains with the same left boundary but different right boundaries

The statement explicitly says that peaks lying on the border are also considered hidden, so equality matters during containment checks.

Approaches

Brute Force Approach

The most direct solution is to compare every mountain with every other mountain.

First, convert every mountain into an interval:

$$[left,\ right] = [x-y,\ x+y]$$

Then for each mountain i, scan all other mountains j and check whether:

$$left_j \le left_i \quad \text{and} \quad right_j \ge right_i$$

If such a mountain exists, then mountain i is hidden.

This works because interval containment exactly matches the geometric visibility condition.

However, this approach requires checking every pair of mountains, resulting in O(n^2) time complexity. With n = 100000, this becomes far too slow.

Optimal Approach

The key insight is that interval containment can be detected efficiently after sorting.

Suppose we sort mountains by:

Increasing left boundary
Decreasing right boundary when left boundaries are equal

Why decreasing right boundary for ties?

Consider:

[1,10]
[1,7]

The larger interval must come first, otherwise the smaller interval could incorrectly appear visible before we process the larger containing interval.

After sorting, we sweep from left to right while tracking the maximum right boundary seen so far.

If the current mountain's right boundary is less than or equal to the maximum right boundary already encountered, then some earlier mountain completely contains it, so it is hidden.

We also need special handling for duplicate mountains because identical mountains hide each other. If a mountain appears more than once, none of those copies are visible.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Compare every mountain against every other mountain
Optimal	O(n log n)	O(n)	Sort intervals and sweep once

Algorithm Walkthrough

Convert every mountain into an interval.

For each peak (x, y):

$$left = x - y$$

$$right = x + y$$

Store these intervals for later processing. 2. Count duplicate intervals.

If the same interval appears multiple times, then all copies are invisible because their peaks lie on each other.

A frequency map lets us identify duplicates quickly. 3. Sort the intervals.

Sort using:

Increasing left
Decreasing right for ties

This ordering guarantees that larger containing intervals appear before smaller nested intervals when they share the same left boundary. 4. Sweep through the sorted intervals.

Maintain:

max_right, the largest right boundary seen so far

For each interval:

If right <= max_right, the interval is contained inside a previously processed mountain
Otherwise, it is potentially visible

Exclude duplicates.

Even if an interval is not contained by another interval, it is still invisible if its frequency is greater than one. 6. Count valid visible mountains.

Increment the answer only when:

The interval is not contained
The interval is unique

Why it works

After sorting, every possible containing mountain appears before the mountains it could contain. The sweep invariant is that max_right always represents the furthest right endpoint among all previously processed mountains.

If the current interval's right endpoint does not exceed max_right, then a previous interval fully contains it. Since the previous interval also starts no later than the current one due to sorting, containment is guaranteed.

Duplicate intervals are handled separately because equal intervals mutually hide each other.

Python Solution

from typing import List
from collections import Counter

class Solution:
    def visibleMountains(self, peaks: List[List[int]]) -> int:
        intervals = []
        
        for x, y in peaks:
            left = x - y
            right = x + y
            intervals.append((left, right))
        
        freq = Counter(intervals)
        
        intervals.sort(key=lambda interval: (interval[0], -interval[1]))
        
        visible_count = 0
        max_right = float("-inf")
        
        for left, right in intervals:
            if right > max_right:
                if freq[(left, right)] == 1:
                    visible_count += 1
                
                max_right = right
        
        return visible_count

The implementation begins by converting each mountain into its interval representation. This simplifies the geometric problem into an interval containment problem.

A Counter stores the frequency of each interval so duplicates can be identified efficiently.

The intervals are then sorted by increasing left endpoint and decreasing right endpoint. This ordering is essential because it guarantees that larger intervals are processed before smaller contained intervals when their left boundaries match.

During the sweep, max_right tracks the furthest right endpoint encountered so far. If the current interval extends beyond max_right, then it is not contained inside any previous mountain.

Before counting it as visible, the implementation checks that the interval occurs exactly once. Duplicate intervals are excluded because identical mountains hide each other.

Go Solution

package main

import (
	"sort"
)

func visibleMountains(peaks [][]int) int {
	type Interval struct {
		left  int
		right int
	}

	intervals := make([]Interval, 0, len(peaks))
	freq := make(map[Interval]int)

	for _, peak := range peaks {
		x, y := peak[0], peak[1]

		interval := Interval{
			left:  x - y,
			right: x + y,
		}

		intervals = append(intervals, interval)
		freq[interval]++
	}

	sort.Slice(intervals, func(i, j int) bool {
		if intervals[i].left == intervals[j].left {
			return intervals[i].right > intervals[j].right
		}
		return intervals[i].left < intervals[j].left
	})

	visibleCount := 0
	maxRight := -1

	for _, interval := range intervals {
		if interval.right > maxRight {
			if freq[interval] == 1 {
				visibleCount++
			}
			maxRight = interval.right
		}
	}

	return visibleCount
}

The Go solution follows the same logic as the Python implementation. A custom Interval struct is used so intervals can serve as keys in a map for frequency counting.

Go's sort.Slice is used to implement the custom sorting order. Since coordinates are positive and bounded, using -1 as the initial maxRight value is safe.

Unlike Python tuples, Go requires a struct type to use compound keys cleanly in a map.

Worked Examples

Example 1

Input:

peaks = [[2,2],[6,3],[5,4]]

Step 1: Convert to intervals

Mountain	Peak	Interval
0	(2,2)	[0,4]
1	(6,3)	[3,9]
2	(5,4)	[1,9]

Step 2: Sort intervals

Sorted order:

Interval
[0,4]
[1,9]
[3,9]

Step 3: Sweep

Initial state:

max_right = -inf
visible = 0

Interval	Condition	Action	max_right	visible
[0,4]	4 > -inf	Visible	4	1
[1,9]	9 > 4	Visible	9	2
[3,9]	9 <= 9	Hidden	9	2

Final answer:

Example 2

Input:

peaks = [[1,3],[1,3]]

Step 1: Convert to intervals

Mountain	Interval
0	[-2,4]
1	[-2,4]

Frequency:

[-2,4] -> 2

Step 2: Sort

Interval
[-2,4]
[-2,4]

Step 3: Sweep

Interval	right > max_right	Unique?	Counted?
[-2,4]	Yes	No	No
[-2,4]	No	No	No

Final answer:

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting dominates the runtime
Space	O(n)	Frequency map and interval storage

The algorithm performs a single sort operation on n intervals, which costs O(n log n). The subsequent sweep is linear.

Additional memory is required for:

The interval array
The frequency map

Both scale linearly with the number of mountains.

Test Cases

from typing import List

class Solution:
    def visibleMountains(self, peaks: List[List[int]]) -> int:
        from collections import Counter

        intervals = []

        for x, y in peaks:
            intervals.append((x - y, x + y))

        freq = Counter(intervals)

        intervals.sort(key=lambda interval: (interval[0], -interval[1]))

        visible = 0
        max_right = float("-inf")

        for left, right in intervals:
            if right > max_right:
                if freq[(left, right)] == 1:
                    visible += 1
                max_right = right

        return visible

sol = Solution()

assert sol.visibleMountains([[2,2],[6,3],[5,4]]) == 2  # provided example
assert sol.visibleMountains([[1,3],[1,3]]) == 0  # duplicate mountains

assert sol.visibleMountains([[1,1]]) == 1  # single mountain
assert sol.visibleMountains([[1,2],[2,1]]) == 1  # one mountain contains another
assert sol.visibleMountains([[1,2],[3,2]]) == 2  # non-overlapping mountains
assert sol.visibleMountains([[2,3],[2,2]]) == 1  # same left boundary
assert sol.visibleMountains([[5,5],[5,5],[5,5]]) == 0  # all duplicates
assert sol.visibleMountains([[1,5],[2,4],[3,3],[4,2]]) == 1  # nested mountains
assert sol.visibleMountains([[1,1],[3,1],[5,1]]) == 3  # all visible
assert sol.visibleMountains([[10,2],[12,2],[11,3]]) == 1  # large mountain hides others

Test	Why
`[[2,2],[6,3],[5,4]]`	Validates the primary example
`[[1,3],[1,3]]`	Ensures duplicates are excluded
`[[1,1]]`	Smallest valid input
`[[1,2],[2,1]]`	Tests direct containment
`[[1,2],[3,2]]`	Tests independent visible mountains
`[[2,3],[2,2]]`	Tests equal left boundaries
`[[5,5],[5,5],[5,5]]`	Tests multiple duplicates
`[[1,5],[2,4],[3,3],[4,2]]`	Tests deep nesting
`[[1,1],[3,1],[5,1]]`	Tests all mountains visible
`[[10,2],[12,2],[11,3]]`	Tests border containment behavior

Edge Cases

Duplicate Mountains

When two or more mountains have identical peaks, they produce identical intervals. According to the problem statement, mountains whose peaks lie on another mountain's border are not visible. Identical mountains therefore hide each other.

A common mistake is counting one copy as visible because it appears first during sorting. The implementation avoids this by storing interval frequencies and only counting intervals that appear exactly once.

Same Left Boundary

Consider intervals like:

[1,10]
[1,7]

If sorted incorrectly, the smaller interval might be processed first and mistakenly counted as visible.

Sorting by increasing left boundary and decreasing right boundary guarantees that the larger interval appears first, allowing the sweep logic to correctly identify the smaller interval as hidden.

Border Containment

The problem states that peaks lying on the border are also hidden. This means equality matters.

For example:

[1,9]
[3,9]

The second interval ends exactly where the first interval ends. It is still considered hidden.

This is why the algorithm uses:

right > max_right

instead of:

right >= max_right

Equality must be treated as containment.