Finding the Number of Visible Mountains - Practice Coding Problems

Finding the Number of Visible Mountains - Problem

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.

Input & Output

Example 1 — Basic Visibility

$ Input: peaks = [[2,1],[2,2],[1,4]]

› Output: 2

💡 Note: Mountain at (2,1) has base [1,3], mountain at (2,2) has base [0,4], mountain at (1,4) has base [-3,5]. The first mountain is completely contained within the second (same left boundary but smaller right), so only 2 mountains are visible.

Example 2 — All Visible

$ Input: peaks = [[1,3],[1,1],[2,2]]

› Output: 3

💡 Note: Mountain bases are [-2,4], [0,2], [0,4]. No mountain completely contains another, so all 3 are visible.

Example 3 — Duplicate Peaks

$ Input: peaks = [[0,1],[1,0]]

› Output: 1

💡 Note: Both peaks (0,1) and (1,0) create the same base range [-1,1] and [1,1]. Since they represent the same mountain shape, only 1 is counted as visible.

Constraints

1 ≤ peaks.length ≤ 10⁵
peaks[i].length == 2
1 ≤ xi, yi ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input Peaks

Mountain peaks at coordinates (x,y)

Base Conversion

Convert to base intervals [x-y, x+y]

Visibility Check

Count mountains not contained by others

Key Takeaway

🎯 Key Insight: Transform 2D mountain peaks into 1D interval containment problem using base ranges

Asked in

G Google 12 f Facebook 8 a Amazon 6

The key insight is converting mountain peaks to base intervals and recognizing this as an interval containment problem. A mountain with peak (x,y) spans base [x-y, x+y]. The optimal monotonic stack approach sorts intervals and maintains visible mountains efficiently. Time: O(n log n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Monotonic Stack Approach	O(n log n)	O(n)	Use stack to maintain visible mountains while processing in sorted order
Brute Force - Check All Pairs	O(n²)	O(1)	For each mountain, check if it's contained within any other mountain
Sort and Sweep	O(n log n)	O(n)	Sort mountains by base range and use sweep line to find visible mountains

Monotonic Stack Approach — Algorithm Steps

Step 1: Convert peaks to intervals and sort by left boundary, then by width descending
Step 2: Use stack to track visible mountains with increasing right boundaries
Step 3: For each interval, pop stack while current interval contains stack top
Step 4: Add current interval to stack if it extends beyond stack top

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort Intervals

Process intervals in sorted order by left boundary

Stack Operations

Pop contained intervals, push extending ones

Count Stack

Final stack size is number of visible mountains

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int left, right;
} Interval;

int compareIntervals(const void* a, const void* b) {
    Interval* ia = (Interval*)a;
    Interval* ib = (Interval*)b;
    if (ia->left != ib->left) {
        return ia->left - ib->left;
    }
    return (ia->left - ia->right) - (ib->left - ib->right);
}

int solution(int peaks[][2], int n) {
    if (n == 0) {
        return 0;
    }
    
    Interval intervals[1000];
    int intervalCount = 0;
    
    // Convert to intervals (simple approach)
    for (int i = 0; i < n; i++) {
        intervals[intervalCount].left = peaks[i][0] - peaks[i][1];
        intervals[intervalCount].right = peaks[i][0] + peaks[i][1];
        intervalCount++;
    }
    
    qsort(intervals, intervalCount, sizeof(Interval), compareIntervals);
    
    Interval stack[1000];
    int stackSize = 0;
    
    for (int i = 0; i < intervalCount; i++) {
        // Pop all intervals that are contained by current interval
        while (stackSize > 0 && stack[stackSize - 1].right <= intervals[i].right) {
            stackSize--;
        }
        
        // Add current interval if it's not contained by stack top
        if (stackSize == 0 || intervals[i].right > stack[stackSize - 1].right) {
            stack[stackSize] = intervals[i];
            stackSize++;
        }
    }
    
    return stackSize;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int peaks[1000][2];
    int n = 0;
    
    char* ptr = line + 1;
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            peaks[n][0] = atoi(ptr);
            while (*ptr && *ptr != ',') ptr++;
            ptr++;
            peaks[n][1] = atoi(ptr);
            while (*ptr && *ptr != ']') ptr++;
            ptr++;
            n++;
        } else {
            ptr++;
        }
    }
    
    printf("%d\n", solution(peaks, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Sorting takes O(n log n), stack operations are O(n) total

⚡ Linearithmic

Space Complexity

O(n)

Stack stores at most n intervals, plus interval array

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Monotonic Stack Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler