mardi 20 novembre 2018

good pairs in an array

For array A a good pair is defined as a pair where A[i] + A[j] = i + j where i < j and i and j are the indices of the array.

Example A = [1, 0, 3, 2]

The answer is 4. The pairs (0,1), (1, 2), (0, 3), (2, 3) are good pairs.

This was my approach A[i] + A[j] = i + j

so A[i] - i = j - A[j]

and the code was something like this

int answer = 0;
map<int, int> map;
map.insert(A[0], 1)
for(int i = 1; i < A.size(); ++i){
    int right = i - A[i];
    if(map.find(right) != map.end()){
        answer += map[right];
    }
    int left = A[i] - i;
    if(map.find(left) != map.end()){
        map[left] += 1;
    }
    else{
        map.insert({left, 1});
    }
}

This solution passed only half the test cases. Can someone tell me the corner cases i missed.

Aucun commentaire:

Enregistrer un commentaire