2345. Finding the Number of Visible Mountains

Approach 1: $O(n)$ space

• Time: $O(\texttt{sort})$
• Space: $O(n)$

C++JavaPython

class Solution {
 public:
  int visibleMountains(vector<vector<int>>& peaks) {
    const vector<pair<int, int>> A = deDuplicates(peaks);
    stack<int> stack;

    for (int i = 0; i < A.size(); ++i) {
      while (!stack.empty() && isHidden(A[stack.top()], A[i]))
        stack.pop();
      if (!stack.empty() && isHidden(A[i], A[stack.top()]))
        continue;
      stack.push(i);
    }

    return stack.size();
  }

 private:
  vector<pair<int, int>> deDuplicates(const vector<vector<int>>& peaks) {
    vector<pair<int, int>> A;
    unordered_map<pair<int, int>, int, PairHash> count;

    for (const vector<int>& peak : peaks)
      ++count[{peak[0], peak[1]}];

    for (const auto& [k, v] : count)
      if (v == 1)
        A.push_back(k);

    ranges::sort(A);
    return A;
  }

  bool isHidden(const pair<int, int>& peak1, const pair<int, int>& peak2) {
    const auto& [x1, y1] = peak1;
    const auto& [x2, y2] = peak2;
    return x1 - y1 >= x2 - y2 && x1 + y1 <= x2 + y2;
  }

  struct PairHash {
    size_t operator()(const pair<int, int>& p) const {
      return p.first ^ p.second;
    }
  };
};

class Solution {
  public int visibleMountains(int[][] peaks) {
    List<Pair<Integer, Integer>> A = deDuplicates(peaks);
    Deque<Integer> stack = new ArrayDeque<>();

    for (int i = 0; i < A.size(); ++i) {
      while (!stack.isEmpty() && isHidden(A.get(stack.peek()), A.get(i)))
        stack.pop();
      if (!stack.isEmpty() && isHidden(A.get(i), A.get(stack.peek())))
        continue;
      stack.push(i);
    }

    return stack.size();
  }

  private List<Pair<Integer, Integer>> deDuplicates(int[][] peaks) {
    List<Pair<Integer, Integer>> A = new ArrayList<>();
    Map<Pair<Integer, Integer>, Integer> count = new HashMap<>();

    for (int[] peak : peaks)
      count.merge(new Pair<>(peak[0], peak[1]), 1, Integer::sum);

    for (Map.Entry<Pair<Integer, Integer>, Integer> entry : count.entrySet())
      if (entry.getValue() == 1)
        A.add(entry.getKey());

    Collections.sort(A, Comparator.comparing(Pair::getKey));
    return A;
  }

  boolean isHidden(Pair<Integer, Integer> peak1, Pair<Integer, Integer> peak2) {
    final int x1 = peak1.getKey();
    final int y1 = peak1.getValue();
    final int x2 = peak2.getKey();
    final int y2 = peak2.getValue();
    return x1 - y1 >= x2 - y2 && x1 + y1 <= x2 + y2;
  }
}

class Solution:
  def visibleMountains(self, peaks: list[list[int]]) -> int:
    count = collections.Counter((x, y) for x, y in peaks)
    peaks = sorted([k for k, v in count.items() if v == 1])
    stack = []

    # Returns True if `peak1` is hidden by `peak2`
    def isHidden(peak1: list[int], peak2: list[int]) -> bool:
      x1, y1 = peak1
      x2, y2 = peak2
      return x1 - y1 >= x2 - y2 and x1 + y1 <= x2 + y2

    for i, peak in enumerate(peaks):
      while stack and isHidden(peaks[stack[-1]], peak):
        stack.pop()
      if stack and isHidden(peak, peaks[stack[-1]]):
        continue
      stack.append(i)

    return len(stack)

Approach 2: $O(1)$ space

• Time: $O(\texttt{sort})$
• Space: $O(\texttt{sort})$

C++

class Solution {
 public:
  int visibleMountains(vector<vector<int>>& peaks) {
    ranges::sort(peaks, [](const vector<int>& a, const vector<int>& b) {
      const int leftFootA = a[0] - a[1];
      const int leftFootB = b[0] - b[1];
      return leftFootA != leftFootB ? leftFootA < leftFootB : a[0] > b[0];
    });

    int maxRightFoot = 0;
    int result = 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 == nullptr)
          ++result;
        maxRightFoot = currRightFoot;
      }
    }

    return result;
  }
};