Falling Squares Solutions in C++

/// Source : https://leetcode.com/contest/leetcode-weekly-contest-54/problems/falling-squares/
/// Author : liuyubobobo
/// Time   : 2017-10-21

#include <iostream>
#include <vector>
using namespace std;

/// Using heights to record all the falling squares
/// Time Complexity: O(len(position)^2)
/// Space Complexity: O(len(position))
class Solution {

public:
    vector<int> fallingSquares(vector<pair<int, int>>& positions) {

        int n = positions.size();
        vector<int> heights(n, 0);
        for(int i = 0 ; i < positions.size() ; i ++){

            heights[i] = positions[i].second;
            for(int j = 0 ; j < i ; j ++)
                if(intersection(positions[j], positions[i]))
                    heights[i] = max(heights[i], heights[j] + positions[i].second);
        }

        vector<int> res(n, 0);
        res[0] = heights[0];
        for(int i = 1 ; i < n ; i ++)
            res[i] = max(heights[i], res[i-1]);

        return res;
    }

private:
    bool intersection(const pair<int, int>& a, const pair<int, int>& b){
        int l1 = a.first;
        int r1 = a.first + a.second - 1;
        int l2 = b.first;
        int r2 = b.first + b.second - 1;

        if(l1 > r2 || l2 > r1)
            return false;

        return true;
    }
};


void printVec(const vector<int>& vec){

    for(int i = 0 ; i < vec.size() ; i ++)
        cout << vec[i] << ((i == vec.size() - 1) ? '\n' : ' ');
}


int main() {

    vector<pair<int, int>> va;
    va.push_back(make_pair(1, 2));
    va.push_back(make_pair(2, 3));
    va.push_back(make_pair(6, 1));
    vector<int> res1 = Solution().fallingSquares(va);
    printVec(res1);


    vector<pair<int, int>> vb;
    vb.push_back(make_pair(100, 100));
    vb.push_back(make_pair(200, 100));
    vector<int> res2 = Solution().fallingSquares(vb);
    printVec(res2);

    return 0;
}

/// Source : https://leetcode.com/contest/leetcode-weekly-contest-54/problems/falling-squares/
/// Author : liuyubobobo
/// Time   : 2017-10-28

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <cassert>

using namespace std;

/// Coordinates compression and simulation
/// Time Complexity: O(len(position)^2)
/// Space Complexity: O(len(position))
class Solution {

public:
    vector<int> fallingSquares(vector<pair<int, int>>& positions) {

        int n = positions.size();
        set<int> unique_pos;
        for(pair<int, int> position: positions){
            unique_pos.insert(position.first);
            unique_pos.insert(position.first + position.second - 1);
        }

        map<int, int> indexes;  // pos -> index
        vector<int> pos;        // index -> pos
        for(int p: unique_pos){
            indexes[p] = pos.size();
            pos.push_back(p);
        }

        assert(indexes.size() == pos.size());
        vector<int> heights(indexes.size(), 0);
        vector<int> res;
        for(pair<int, int> position: positions){

            int startIndex = indexes[position.first];
            int rightBound = position.first + position.second - 1;

            int best = 0;
            for(int i = startIndex ; i < pos.size() && pos[i] <= rightBound ; i ++)
                best = max(best, heights[i]);

            for(int i = startIndex ; i < pos.size() && pos[i] <= rightBound ; i ++)
                heights[i] = best + position.second;

            best = 0;
            for(int i = 0 ; i < heights.size() ; i ++)
                best = max(best, heights[i]);

            res.push_back(best);
        }

        return res;
    }

};


void printVec(const vector<int>& vec){

    for(int i = 0 ; i < vec.size() ; i ++)
        cout << vec[i] << ((i == vec.size() - 1) ? '\n' : ' ');
}


int main() {

    vector<pair<int, int>> va;
    va.push_back(make_pair(1, 2));
    va.push_back(make_pair(2, 3));
    va.push_back(make_pair(6, 1));
    vector<int> res1 = Solution().fallingSquares(va);
    printVec(res1);


    vector<pair<int, int>> vb;
    vb.push_back(make_pair(100, 100));
    vb.push_back(make_pair(200, 100));
    vector<int> res2 = Solution().fallingSquares(vb);
    printVec(res2);

    return 0;
}