Need help optimizing this O(n^2) solution, getting partially correct answer


#1

int Solution::solve(vector &A) {
vector<pair<int,int>> vec;
int i,j;
i=0;

//store all intervals ending with same element
while(i<A.size()){
    vec.push_back({i,i});
    j=i+1;
    
    while(j<A.size()){
        if(A[j]==A[i]){
            vec[i].second = j;
        }
        j++;
    }
    
    i++;
}

int start,end;
//need to merge overlapping intervals and store in new vector
for(i=0;i<vec.size();i++){
    start = vec[i].first;
    end = vec[i].second;
    j=i+1;
    
    while(j<vec.size()){
            //check for overlap and merge intervals
            if(vec[j].second > end && vec[j].first <= end){
                end =  vec[j].second;
                vec.erase(vec.begin()+j);
                continue;
            }
            //if subset just remove
            else if(vec[j].second<=end){
                vec.erase(vec.begin()+j);
                continue;
            }
            j++;

    }
    //if not already 'nice' then push to new vector
    if(start!=end)
        vec[i].second = end;
}

int ans=0;
//iterate over vec and count maximum occuring element using hash
unordered_map<int,int> hash;
for(i=0;i<vec.size();i++){
    hash.clear();
    
    for(j=vec[i].first;j<=vec[i].second;j++){
        hash[A[j]]++;
    }
    int max = 0;
    for(auto k:hash){
        if(max<k.second)
            max = k.second;
    }
    //subtract it from length of segment to get 'difficulty'
    ans+= vec[i].second + 1 - vec[i].first - max;
    
}
return ans;

}