 # Find number of subarrays containing pairs with sum K

I need help with a problem that appeared in one of the coding tests for a company. The problem was something like this -

Given an unsorted array of integers and an integer k, find the number of subarrays where there exists a pair of integers ai and aj (i != j) in the subarray such that ai + aj = k

I was not able to find this problem online. Is this solvable using the sliding window technique? Can anyone help me with this?

There is obviously a naive brute force in O(n^3). For every subarray, check if it is `valid` or not ?
We can speed it up to O(n^2) by counting in clever way.

Both technique uses an O(n) space for HashSet/unorderd_map.

We can further optimise it to O(nlogn) time.
Imagine a pair satisfying the condition at i, j. This allows you to take i*(n-j + 1) subarrays.
We can use this observation.
Let’s iterate `i` from `1..n`
for `i` , we want to find closes `j` s.t. `j>i` and `a[i] + a[j] =k`. (Easily doable in logn time ).
For this pair, let’s add `i*(n-j+1)` to our answer.
To avoid overcounting subarrays, we should keep track of previous `i` and previous `j`

How to avoid overcounting?

Lets start with an observation consider two pairs `{i1,j1}` and `{i2,j2}`
If `{i2,j2}` is completely inside `{i1,j1}` then we can get rid of `i1,j1` as `i2,j2` will count every subarray.
Let’s maintain a stack to achieve this.
(we will push the pair `{i,j}` in stack)
In the loop for `i = 1..n`
Let’s find closest `j` as described above.
Pop all the elements from stack which are `completely larger than curr pair`. Since i is always increasing, we can only check for j’s .
This will also maintain out stack in `increasing j`.
After that we need to count subarray from every element in stack.

int pi = 0;
For (i,j) in stack(bottom of stack to top):
ans+=(i-pi)*(n-j+1);
pi = i;

This should avoid overcounting.
Since, every element is popped and pushed atmost once . Time is O(n)

do you mean something like for each pair count how many subarrays that pair contributes ?

Nope ,it is quite the opposite.
For every subarray i…j , check if it contains a pair s.t. sum is k.