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

Problem

Given an unsorted array of integers. The task is to find any two non-overlapping pairs whose sum is equal. Two pairs are said to be non-overlapping if all the elements of the pairs are at different indices.

Sample Input

[1, 7, 9, 3]

Sample Output

1 9
7 3

Explanation

They both have sum as 10

Approach

The idea is to traverse the array and generate all possible pairs. This step takes O(N2) time. If a sum is found that is not already present, insert it into the map. Otherwise, check if any of the previously occurring pairs with that sum does not overlap with the current pair.

C++ Programming

#include<bits/stdc++.h>
using namespace std;

typedef pair<int, int> pp;

void solve(int arr[], int n)
{

   unordered_map<int, vector<pp> > map;

   for (int i = 0; i < n - 1; i++) {
       for (int j = i + 1; j < n; j++) {

           int sum = arr[i] + arr[j];

           if (map.find(sum) != map.end()) {

               for (auto pair : map.find(sum)->second) {
                   int m = pair.first, n = pair.second;

                   if ((m != i && m != j) && (n != i && n != j)) {
                       cout << "Pair 1 (" << arr[i] << ", "
                           << arr[j] << ")\nPair 2 ("
                           << arr[m] << ", " << arr[n] << ")";
                       return;
                   }
               }
           }

           map[sum].push_back({ i, j });
       }
   }

   cout << "No pairs present";
}

int main()
{
   int arr[] = { 1, 9, 7, 3};
   int size = sizeof(arr) / sizeof(arr[0]);

   solve(arr, size);

   return 0;
}

Output

Pair 1 (7, 3)
Pair 2 (1, 9)

Python Programming

def solve(arr, nn):
  
   Map = {}

   for i in range(0, nn - 1):
       for j in range(i + 1, nn):
          
           Sum = arr[i] + arr[j]

           if Sum in Map:

               for pair in Map[Sum]:
                   m, n = pair


                   if ((m != i and m != j) and
                       (n != i and n != j)):
                      
                       print("Pair 1 ({}, {})".
                           format(arr[i], arr[j]))
                       print("Pair 2 ({}, {})".
                           format(arr[m], arr[n]))
                       return
                  
           if Sum not in Map:
               Map[Sum] = []
           Map[Sum].append((i, j))
  
   print("No pairs found")

arr = [1, 9, 7, 3]
nn = len(arr)

solve(arr, nn)  

Output

Pair 1 (7, 3)
Pair 2 (1, 9)

Java Programming

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Pair {
   public int x, y;

   Pair(int x, int y)
   {
       this.x = x;
       this.y = y;
   }
}

class Solution {

   public static void solve(int[] arr)
   {

       Map<Integer, List<Pair> > map = new HashMap<>();

       for (int i = 0; i < arr.length - 1; i++) {
           for (int j = i + 1; j < arr.length; j++) {

               int sum = arr[i] + arr[j];

               if (map.containsKey(sum)) {

                   for (Pair pair : map.get(sum)) {
                       int x = pair.x;
                       int y = pair.y;
                       if ((x != i && x != j) && (y != i && y != j)) {
                           System.out.println("Pair 1 (" + arr[i] + ", "
                                           + arr[j] + ")");

                           System.out.println("Pair 2 (" + arr[x] + ", "
                                           + arr[y] + ")");

                           return;
                       }
                   }
               }

               map.putIfAbsent(sum, new ArrayList<>());
               map.get(sum).add(new Pair(i, j));
           }
       }

       System.out.print("No pairs present");
   }

   public static void main(String[] args)
   {
       int[] arr = {1, 9, 7, 3 };

       solve(arr);
   }
}

Output

Pair 1 (7, 3)
Pair 2 (1, 9)

People are also reading:

• Rearrange an array such that arr[i] = i
• Check for pairs in an array with a particular sum
• WAP to Print Square Using * Character
• Find ancestors of a given node in a Binary Tree
• Subset Sum Problem
• Clone a Singly Linked List
• Maximum size square sub-matrices with all 1’s
• Find a Pair with the Given Sum in an Array
• Check if a subarray with 0 sum exists or not
• Circular Doubly Linked List