Finding pairs of complementary numbers

Question

This is the "Pairs with Positive Negative values" problem from geeksforgeeks.org.

Given an array of distinct integers, print all the pairs having positive value and negative value of a number that exists in the array.

NOTE: If there is no such pair in the array , print "0".

Input:
The first line consists of an integer T i.e number of test cases. The first line of each test case consists of an integer n. The next line of each test case consists of n spaced integers.

Output:
Print all the required pairs in the increasing order of their absolute numbers.

Here is my code:

def findPairs(l):
 listLen=len(l)
 nums=set()
 for i in range(listLen):
 if (-1*l[i]) in l[i+1:]:
 nums.add(abs(l[i]))
 continue 
 nums=sorted(nums)
 #print (nums)
 pairs=[]
 for num in nums:
 pairs.extend([-1*num,num])
 return pairs 
T=int(input())
pair=[]
for i in range(T):
 input()
 pair=findPairs(list(map(int,input().split())))
 if len(pair):
 print(" ".join(str(x) for x in pair))
 else:
 print("0")

Answer 1

You definitely incorporated the response to your previous questions, such as:

• Extract code into functions.
• Always indent with 4 spaces.
• Process input immediately instead of storing all input data and results in lists.

There is still too little (horizontal) whitespace, I suggest to check your code against the PEP8 coding style, for example at PEP8 online.

Also function and variable names should be snake_case according to PEP8.

More suggestions:

• Variable names: T is too short and non-descriptive, num_tests would be better. pair is better named pairs.
• There is no need to pre-assign pair=[].

• The value of the iterator variable i in the main loop is not needed, a common convention is use _ instead:

  for _ in range(T):
  

• Negation as in -1*l[i] can be simplified to -l[i]

• When printing the result list

  print(" ".join(str(x) for x in pair))
  

  you can use map instead, as you already do when reading the input:

  print(" ".join(map(str, pair)))
  

Improving the performance:

Your algorithm has two nested loops traversing through the list, i.e. the time complexity is \$ O(n^2) \$ as a function of the list length.

This can be improved by sorting the list first. One option would be to sort the numbers in increasing order, e.g.

-3 -1 1 2 3 6

for the first test case, and then traverse the list from both ends to find pairs. The time complexity is \$ O(n \log n) \$ for the sorting, and \$ O(n) \$ for the traversal, so this would be faster for large input.

Another option is to sort the number in increasing absolute value, e.g.

 -3 3 -1 1 2 6

Again a linear sweep of the sorted list is now sufficient to find matching pairs, which are now consecutive entries.

Here is a possible implementation of the second approach:

def find_pairs(numbers):
 numbers.sort(key=lambda x: x + 0.5 if x >= 0 else -x)
 pairs = []
 for pair in [(x, y) for x, y in zip(numbers, numbers[1:]) if x == -y]:
 pairs.extend(pair)
 return pairs

using

• sort() with a custom key. This relies on the given fact that the numbers are distinct integers.
• zip and list comprehension to enumerate pairs of consecutive list entries.