Valid Pair Sum

This article describes the question from Day 7 of the 30 Days of Code competition hosted by Geeks for Geeks.

Question

Given an array of size N, find the number of distinct pairs {a[i], a[j]} (i != j) in the array with their sum greater than 0.

Example 1:

Input: N = 3, a[] = {3, -2, 1} Output: 2 Explanation: {3, -2}, {3, 1} are two possible pairs.

Example 2:

Input: N = 4, a[] = {-1, -1, -1, 0} Output: 0 Explanation: There are no possible pairs.

Your Task: You don't need to read input or print anything. Complete the function ValidPair() which takes the array a[ ] and size of array N as input parameters and returns the count of such pairs.

Expected Time Complexity: O(N * Log(N)) Expected Auxiliary Space: O(1)

Constraints: 1 ≤ N ≤ 105 -104 ≤ a[i] ≤ 104

Simple Solution

A naive approach to this question would be to generate all the possible pairs, then filter it for those whose sums are greater than zero. For simplicity, we can employ the combinations method from the itertools library. This generates all possible combinations from a list, in our case pairs (n=2).

from itertools import combinations 
class Solution:
    def ValidPair(self, a, n): 
        pairs = combinations(a,2)
        sums = map(sum, pairs)
        valid = list(filter(lambda x: sum(x) > 0, sums))
        return len(valid)

However, this solution does not meet the time constraints for the competition. Our answer must have a complexity of O(N * Log(N)). This simple approach we have devised may be easy on the eyes, but it is not efficient computationally. We must optimize our code.

Optimized Solution

Here we have an approach that completes its execution within the time constraints.

class Solution:
    def ValidPair(self, a, n): 
        p = 0 
        q = len(a) - 1
        s = 0
        a.sort()
        while p<q:
            if (a[p]+a[q]>0):
                s += q-p
                q -= 1
            else:
                p += 1
        return s

This solution starts by sorting the array. This is so the smallest numbers come first. This is an important step so that we can evaluate our solution in one pass, without having to backtrack.

When working out the number of valid pairs, we consider the two indexes p and q. p represents the index of the lowest number.q is the index of the highest number. Computers start counting at 0, so this is the length of the array minus one len(a) - 1, to avoid index out of bounds errors.

We check if the first p and last q numbers of the sorted array make a pair whose sum p+q is greater than zero.

If they do, then all the proceeding pairs, i.e., (a+1,q), (a+2,q), etc ..., must also be valid, since they are larger than a. In this scenario, we add q-p to our sum and decrease q by one. The new value of q is not as large as the previous, so it is possible that not all the same pairs sum to greater than zero.

In the scenario that p+q is not greater than zero, we increase p by one. The previous value for p was too low to make any valid pairs. No valid pairs were made, so we do not increase the counter. The next value of p is higher, so it likely it could make more pairs than its predecessor.

The value s is increased by the number of valid pairs each iteration. After the loop has completed, it represents the number of valid pairs. This operation is performed in 0(n) time complexity, as each iteration the range being considered is made closer (i.e., either the q is decreased, or the p is increased).