Computer Science
Updated 6 days ago | GitHub

Find Sum Pair

TIP101 Unit 10 Session 2 (Click for link to problem statements)

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 25 mins
  • 🛠️ Topics: Hash Map, Pair Sum

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

  • Established a set (2-3) of test cases to verify their own solution later.
  • Established a set (1-2) of edge cases to verify their solution handles complexities.
  • Have fully understood the problem and have no clarifying questions.
  • Have you verified any Time/Space Constraints for this problem?
  • What should be returned if no such pair of integers exist?
    • An empty list [].
  • Can the two pairs share an element?
    • No. The two pairs must use four different positions (indices) in the list. Equal values at different positions are fine, so [1, 2, 2, 1] has the answer 1 + 2 = 2 + 1. A single position cannot be used in both pairs, so [1, 2, 2] has no answer: 1 + 2 = 1 + 2 would use the 1 at index 0 twice. This page uses that rule because the TIP101 problem statement is behind the course login. It matches the classic version of this problem, which uses the same example list.
HAPPY CASE
Input: numbers = [3, 4, 7, 1, 2, 9, 8]
Output: [3, 8, 4, 7]
Explanation: 3 + 8 = 4 + 7

HAPPY CASE
Input: numbers = [1, 2, 3, 4, 5]
Output: [1, 4, 2, 3]
Explanation: 1 + 4 = 2 + 3

EDGE CASE
Input: numbers = [1, 2, 3]
Output: []
Explanation: No such integers exist.

EDGE CASE
Input: numbers = []
Output: []
Explanation: The list is empty, so no such integers exist.

EDGE CASE
Input: numbers = [1, 2, 2]
Output: []
Explanation: The pairs at indices (0, 1) and (0, 2) both sum to 3, but they share index 0. A three-element list cannot supply four distinct positions.

EDGE CASE
Input: numbers = [1, 2, 2, 1]
Output: [1, 2, 2, 1]
Explanation: 1 + 2 = 2 + 1 using indices (0, 1) and (2, 3). Duplicate values are allowed as long as the indices differ.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Pair Sum problems, we want to consider the following approaches:

  • Using a hash map to track sums and corresponding pairs of numbers.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use a hash map to store the indices of the first pair seen for each sum. If the same sum appears again with a pair that shares no index with the stored pair, return the numbers from both pairs. If the new pair shares an index, skip it and keep the stored pair.

Keeping only the first pair for each sum does not miss any answer. Say two pairs with sum s exist that share no index, and (a, b) is the first pair with sum s. If either of the two pairs shares no index with (a, b), the loop reaches it after (a, b) and returns. Otherwise each of them shares exactly one index with (a, b), and they share different ones because they share no index with each other. So one has the form (a, c) with numbers[c] == numbers[b], and the other has the form (b, d) with numbers[d] == numbers[a]. Then (c, d) also sums to s and shares no index with (a, b), so the loop returns when it reaches (c, d).

1) Initialize a hash map `map` to store each sum and the indices of the first pair that produced it.
2) Iterate through each index `i` of the list `numbers`:
    a) Iterate through each index `j` from `i+1` to the end of the list:
        i) Calculate the sum of `numbers[i]` and `numbers[j]`.
        ii) If the sum is already in `map` with stored indices `(a, b)`:
            - If `(a, b)` shares an index with `(i, j)`, skip this pair.
            - Otherwise, return `[numbers[a], numbers[b], numbers[i], numbers[j]]`.
        iii) If the sum is not in `map`, store the sum with the indices `(i, j)`.
3) If no such pair is found, return an empty list.

⚠️ Common Mistakes

  • Not correctly handling cases where no such pairs exist.
  • Storing only the values of a pair in the hash map. Without the indices, the code cannot tell when two pairs reuse the same position. With duplicate values, [1, 2, 2] would then return [1, 2, 1, 2], using the 1 at index 0 twice.
  • Overwriting the stored pair with a pair that shares an index. Keep the first pair stored for each sum, because a later pair that shares no index with it will still be found.

4: I-mplement

Implement the code to solve the algorithm.

def find_sum_pair(numbers):
    length = len(numbers)
    map = {}

    for i in range(length):
        for j in range(i + 1, length):
            sum = numbers[i] + numbers[j]
            if sum in map:
                a, b = map[sum]
                # Skip a pair that reuses an index from the stored pair
                if a in (i, j) or b in (i, j):
                    continue
                return [numbers[a], numbers[b], numbers[i], numbers[j]]
            else:
                map[sum] = (i, j)
    return []

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code’s variables along the way.

  • Trace through your code with an input to check for the expected output.
  • Example: Trace with numbers = [3, 4, 7, 1, 2, 9, 8]
    • Sum = 3 + 4 = 7, store indices (0, 1) in map
    • Sum = 3 + 7 = 10, store indices (0, 2) in map
    • Sum = 3 + 1 = 4, store indices (0, 3) in map
    • Sum = 3 + 2 = 5, store indices (0, 4) in map
    • Sum = 3 + 9 = 12, store indices (0, 5) in map
    • Sum = 3 + 8 = 11, store indices (0, 6) in map
    • Sum = 4 + 7 = 11, found stored indices (0, 6), which share no index with (1, 2), so return [3, 8, 4, 7]
  • Example: Trace with numbers = [1, 2, 2]
    • Sum = 1 + 2 = 3, store indices (0, 1) in map
    • Sum = 1 + 2 = 3, found stored indices (0, 1), which share index 0 with (0, 2), so skip
    • Sum = 2 + 2 = 4, store indices (1, 2) in map
    • No more pairs, return []

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N represents the length of the list numbers.

  • Time Complexity: O(N^2) because we need to check all pairs of elements.
  • Space Complexity: O(N^2) in the worst case for storing sums and their corresponding pairs in the hash map.