699. Falling Squares
Approach
Sorted interval map keyed by x-range tracks current heights;
when a square drops, find all overlapping intervals and compute the new height.
Key Techniques
Array problems involve manipulating elements stored in a contiguous block of memory. Key techniques include two-pointer traversal, prefix sums, sliding windows, and in-place partitioning. In C#, arrays are zero-indexed and fixed in size — use List<T> when you need dynamic resizing.
Segment trees support range queries (sum, min, max, GCD) and point updates in O(log n). Build in O(n) by filling leaves, then propagating upward. Lazy propagation enables range updates in O(log n) as well. Use for competitive programming range-query problems.
An ordered set (e.g., SortedSet<T> in C#) maintains elements in sorted order with O(log n) insert/delete/lookup. Use it when you need both fast membership testing and order-based queries (floor, ceiling, predecessor, successor).
// Approach: Sorted interval map keyed by x-range tracks current heights;
// when a square drops, find all overlapping intervals and compute the new height.
// Time: O(n²) Space: O(n)
public class Solution
{
public IList<int> FallingSquares(IList<IList<int>> positions)
{
List<int> ans = new List<int>();
SortedDictionary<(int, int), int> xsToHeight = new SortedDictionary<(int, int), int>(); // {(xStart, xEnd), height}
int maxHeight = int.MinValue;
foreach (var p in positions)
{
int left = p[0];
int sideLength = p[1];
int right = left + sideLength;
// Find the first range that intersects with [left, right).
var it = xsToHeight.Keys.ToList().FindLast(k => k.Item1 < right);
if (it != default && it.Item2 <= left)
it = default;
int maxHeightInRange = 0;
List<(int, int, int)> ranges = new List<(int, int, int)>();
while (it != default && it.Item1 < right)
{
int l = it.Item1;
int r = it.Item2;
int h = xsToHeight[it];
if (l < left)
ranges.Add((l, left, h));
if (right < r)
ranges.Add((right, r, h));
maxHeightInRange = Math.Max(maxHeightInRange, h);
xsToHeight.Remove(it);
it = xsToHeight.Keys.ToList().FindLast(k => k.Item1 < right);
}
int newHeight = maxHeightInRange + sideLength;
xsToHeight[(left, right)] = newHeight;
foreach (var (l, r, h) in ranges)
xsToHeight[(l, r)] = h;
maxHeight = Math.Max(maxHeight, newHeight);
ans.Add(maxHeight);
}
return ans;
}
}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;
}
};