Facebook - Split into monotonic sequences, C++ (gcc)

Facebook - Split into monotonic sequences

#include <bits/stdc++.h>

using namespace std;

struct Node {
    int ind;
    int last_element;
    
    Node (int _ind, int _last_element) {
        ind = _ind;
        last_element = _last_element;
    }
    
    bool operator < (const Node& rhs) const {
        if (last_element != rhs.last_element) 
            return (last_element < rhs.last_element);
        
        return ind < rhs.ind;
    }
};

vector<vector<int>> BreakIntoMonotonicSequences (vector<int>& arr) {
    vector<vector<int>> result;
    set<Node> all;
    
    for (auto i : arr) {
        auto it = all.lower_bound (Node(-1, i));
        if (it == all.begin()) {
            // All of the existing sequence have last-element greater than 'i'
            result.push_back({i});
            Node new_node (result.size()-1, i);
            all.insert(new_node);
        }
        else {
            // There is an node before 'it' whose last-element is smaller than 'i'
            -- it;
            Node cur = *it;
            all.erase(it);
            
            result[cur.ind].push_back(i);
            cur.last_element = i;
            all.insert(cur);
        }
    }
    
    return result;
}

int main() {
    vector<int> arr = {1, 3, 2, 2, 2, 3};
    // vector<int> arr = {1, 2, 5, 48, 74, 4, 5, 5, 8, 12, 0, 56, 2, 2, 3};
    
    vector<vector<int>> result = BreakIntoMonotonicSequences (arr);
    for (auto row : result) {
        for (auto i : row) cout << i << " ";
        cout << endl;
    }
    
    return 0;
}


run \| edit \| history \| help	0