699. Falling Squares LeetCode Solution

In this guide, you will get 699. Falling Squares LeetCode Solution with the best time and space complexity. The solution to Falling Squares problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Falling Squares solution in C++
Falling Squares solution in Java
Falling Squares solution in Python
Additional Resources

699. Falling Squares LeetCode Solution image

Problem Statement of Falling Squares

There are several squares being dropped onto the X-axis of a 2D plane.
You are given a 2D integer array positions where positions[i] = [lefti, sideLengthi] represents the ith square with a side length of sideLengthi that is dropped with its left edge aligned with X-coordinate lefti.
Each square is dropped one at a time from a height above any landed squares. It then falls downward (negative Y direction) until it either lands on the top side of another square or on the X-axis. A square brushing the left/right side of another square does not count as landing on it. Once it lands, it freezes in place and cannot be moved.
After each square is dropped, you must record the height of the current tallest stack of squares.
Return an integer array ans where ans[i] represents the height described above after dropping the ith square.

Example 1:

Input: positions = [[1,2],[2,3],[6,1]]
Output: [2,5,5]
Explanation:
After the first drop, the tallest stack is square 1 with a height of 2.
After the second drop, the tallest stack is squares 1 and 2 with a height of 5.
After the third drop, the tallest stack is still squares 1 and 2 with a height of 5.
Thus, we return an answer of [2, 5, 5].

Example 2:

Input: positions = [[100,100],[200,100]]
Output: [100,100]
Explanation:
After the first drop, the tallest stack is square 1 with a height of 100.
After the second drop, the tallest stack is either square 1 or square 2, both with heights of 100.
Thus, we return an answer of [100, 100].
Note that square 2 only brushes the right side of square 1, which does not count as landing on it.

Constraints:

1 <= positions.length <= 1000
1 <= lefti <= 108
1 <= sideLengthi <= 106

Complexity Analysis

Time Complexity: O(n\log n)
Space Complexity: O(n)

699. Falling Squares LeetCode Solution in C++

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;
  }
};
/* code provided by PROGIEZ */