Find two non-overlapping pairs having same sum in an array

Given an unsorted array of integers, find two non-overlapping pairs in it having same sum.

 

For example,


Input: { 3, 4, 7, 3, 4 }
Output: (4, 3) and (3, 4)
 

Input:  { 3, 4, 7, 4 }
Output: No non-overlapping pairs is present in the array
Note (3, 4) and (3, 4) forms overlapping pair as index of 3 is same in both pairs

 

The idea is to consider every pair of elements in the array one by one and insert it into a map. For each pair, we check if their sum exists in the map or not. If we have encountered the sum before, and elements involved in previous occurrence (m, n) don’t overlap with the current pair (i, j), we print the both pairs and return.

 
Below is C++/Java implementation of the program –

C++

Download   Run Code

Output:

First Pair  (4, 3)
Second Pair (3, 4)

Java

Download   Run Code

Output:

First Pair  (4, 3)
Second Pair (3, 4)

 
Thanks for reading.

Please use our online compiler to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 



Leave a Reply

avatar
  Subscribe  
Notify of