Code Interview Pattern 3–2 pointer loop in the same array

Problem: Pair Sums

Given a list of n integers arr[0..(n-1)], determine the number of different pairs of elements within it which sum to k.

If an integer appears in the list multiple times, each copy is considered to be different; that is, two pairs are considered different if one pair includes at least one array index which the other doesn’t, even if they include the same values.

Example 1

n = 5 k = 6 arr = [1, 2, 3, 4, 3] output = 2

Get Lake22’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

The valid pairs are 2+4 and 3+3.

Example 2

n = 5 k = 6 arr = [1, 5, 3, 3, 3] output = 4

There’s one valid pair 1+5, and three different valid pairs 3+3 (the 3rd and 4th elements, 3rd and 5th elements, and 4th and 5th elements).

Pattern:

It is a single array, but two loops. One loop as seed, one loop to do calculation. The pattern is no difference than 2 pointer loop, the only thing different here is the 2 pointers are within the same array.

def numberOfWays(arr, k):
   # Write your code here
    my_set = set ()
    for i in range (len(arr)):
       for j in range (i+1, len(arr)):
          if (arr[i] + arr[j]) == k:
            my_set.add ((arr[i], arr[j], i, j))
    print (my_set)
    return len(my_set)