C++ Code with comments


#1
vector<int> Solution::solve(vector<int> &A) {
    int N=A.size();
    vector<int> ans;
    // mp is (A[i] : set of all occurences of A[i] in ans)
    unordered_map<int,set<int>> mp;
    for(int i=0; i<N; i++){
        if(mp.find(A[i])!=mp.end()){
            // get the position of first occurence of the element
            int pos=*(mp[A[i]].begin());
            ans[pos]++;
            // the new number at this position can be the first occurence of that number now
            // insert pos into the set of that number
            mp[ans[pos]].insert(pos);
            // delete the position from the set of previous number
            mp[A[i]].erase(mp[A[i]].begin());
        }
        mp[A[i]].insert(i);
        ans.push_back(A[i]);
    }
    return ans;
}

Time Complexity : O(NlogN)
Space Complexity: O(N)