Skip to content

699. Falling Squares 👍

  • Time: $O(n\log n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
 public:
  vector<int> fallingSquares(vector<vector<int>>& positions) {
    vector<int> ans;
    map<pair<int, int>, int> xsToHeight;  // {(xStart, xEnd), height}
    int maxHeight = INT_MIN;

    for (const vector<int>& p : positions) {
      const int left = p[0];
      const int sideLength = p[1];
      const int right = left + sideLength;
      // Find the first range that intersects with [left, right).
      auto it = xsToHeight.upper_bound({left, right});
      if (it != xsToHeight.begin() && (--it)->first.second <= left)
        ++it;
      int maxHeightInRange = 0;
      vector<tuple<int, int, int>> ranges;
      while (it != xsToHeight.end() && it->first.first < right) {
        const int l = it->first.first;
        const int r = it->first.second;
        const int h = it->second;
        if (l < left)
          ranges.emplace_back(l, left, h);
        if (right < r)
          ranges.emplace_back(right, r, h);
        maxHeightInRange = max(maxHeightInRange, h);
        it = xsToHeight.erase(it);
      }
      const int newHeight = maxHeightInRange + sideLength;
      xsToHeight[{left, right}] = newHeight;
      for (const auto& [l, r, h] : ranges)
        xsToHeight[{l, r}] = h;
      maxHeight = max(maxHeight, newHeight);
      ans.push_back(maxHeight);
    }

    return ans;
  }
};