Solution: Find Two Pairs in an Array Such That a+b = c+d

Let’s solve the Find Two Pairs in an Array Such That a+b = c+d problem.

We'll cover the following

Statement

Given an array of distinct integers, nums, determine whether there exist two pairs, (a,b)(a, b) and (c,d)(c, d), such that a+b=c+da + b = c + d, where aa, bb, cc, and dd are unique elements within the array. If there are multiple solutions, return any one of them.

Constraints:

  • 44 \leq nums.length 103\leq 10^3

  • 103-10^3 \leq nums[i] 103\leq 10^3

Solution

In this solution, we identify pairs of numbers with matching sums by utilizing a map to remember the sums and its associated pairs. By storing each unique sum as a key and the corresponding pair as its value, the algorithm can quickly check if a previously encountered sum matches the sum of a current pair. This enables the identification of two distinct pairs that add up to the same sum.

Let’s walk through the following steps of the solution:

  • Initializes an empty map to store the sum of pairs.

  • Iterate over each pair of numbers in nums and calculate their sum. Check whether this sum has already been encountered and stored in the map:

    • If yes, return the two pairs that add up to this sum: the one previously stored and the current one.

    • Otherwise, add the sum as key and its pair as the corresponding value in the map for future reference.

  • Return NULL, if no such pairs are found by the end of the iteration.

Let’s look at the illustration below to better understand the solution:

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.