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

Posted in

Vinay Khatri
Last updated on August 10, 2024

## 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<>());
}
}

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)
```