Arrays coding Question from Sapient OT

general
,
1

We are given a vector and integer as follows:

vector<int> numbers
int k

find the count of pairs in numbers that have the diference k.
For example,

numbers = [1,1,2,2,3,3] and
k = 1
thus the ordered pairs will be (1,2) and (2,3) and the count will be 2.

numbers = [1,2,3,4,5,6]
k = 2
thus the ordered pairs will be (1,3), (2,4), (3,5), (4,6) and the count will be 4.

In case no such pair is possible the count needs to be zero and the function will return the count in all cases.

  • No negative values are allowed.
  • In the pair (x,y), x < y.

For the above question, I have successfully written a O(n^2) solution:

int numberofPairs(vector<int>numbers, int k)
{
    int count = 0;
    set<int> s1;
    vector<int>::iterator i;
    set<int>::iterator j;
    set<int>::iterator z;

    for(i = numbers.begin(); i!-numbers.end(); i++)
         s1.insert(*i);

    for(j = s1.begin(); j!=s1.end(); j++)
    {   for(z = s1.begin(); z!=s1.end(); z++)
        {   if((*j + k) == z)
            {
                 count++;
                 break;
            }
        }
    }
    return count;
}

Is there any way possible to solve it with more efficient solution?

2

Yes, I think this problem can be solved in Linear Time and Constant Space using Window Sliding Technique.
Edit: The array needs to be sorted first for this to work.

1 Like
3

can you please help me further ?

4

Yeah, see method 5 of this post. Note- The array need to be sorted for The Window Sliding Technique to work.

5

i have used a set so it is sorted by default with all duplicates removed. thank you!!

1 Like
6

Yup, I see that. I would still prefer the Window Sliding Technique though, for two reasons-

  1. First ofcourse is that it takes constant space unlike set.
  2. In cases when the array is already sorted, this technique performs better beacause it will then take only Linear Time where as set would still take O(N*Log(N)) time and If it is an unoredered_set the Time Complexity will still be Amortized O(N) rather than simply O(N).
1 Like
7

understood, thank you!

8

I think we can make the search time O(1) using an array where each index gives either 0 if that element is absent or 1 if it is present. Then I guess it can be solved in O(N) very simply.

Caution: segmentation fault might happen if range is very large.

9

Maybe this works :-

  1. Sort the vector
  2. Use an unordered_map to map each value to its frequency (unordered_map <int,int> freq)
  3. For each V[i] in V
    a. if V[i]-k is present in map , count+=freq[V[i]-k);
    b. if V[i]+k is present in map , count+=freq[V[i]+k);
  4. print count;