699. Falling Squares

699.cs

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;
    }
}

699.cpp

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;
    }
};

Was this solution helpful?