Find Pairs

JCSU Unit 2 Problem Set 2 (Click for link to problem statements)

Problem Highlights

• 💡 Difficulty: Medium
• ⏰ Time to complete: 20 mins
• 🛠️ Topics: Nested Lists, Pairs, Two-Pointer Pattern

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 is the goal of the problem?
  • The goal is to find all pairs of numbers in a nested list whose sum equals the given target.
• Are there constraints on input?
  • The input may contain nested lists of integers or integers directly in the main list.

HAPPY CASE Input: nums = [1, 2, [3, 4], [5], 6] target = 7 Output: [(1, 6), (2, 5), (3, 4)] Explanation: The pairs of numbers that add up to 7 are (1, 6), (2, 5), and (3, 4).

EDGE CASE Input: nums = [] target = 10 Output: [] Explanation: An empty list results in no pairs.

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 finding problems, we want to consider the following approaches:

• Flattening and Hashing: Flatten the nested list into a single list, then use a set to track complements for efficient lookup.
• Two-Pointer Technique (Alternative): If the list is sorted, use two pointers to find pairs.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea:
Flatten the nested list into a single list, then use a set to track seen numbers. For each number in the flattened list, calculate its complement with respect to the target sum. If the complement exists in the set, add the pair to the result.

Steps:

1. Initialize an empty list flattened.
   • Iterate through the input nums:
     • If the item is a sublist, extend flattened with its elements.
     • If the item is an integer, append it to flattened.
2. Initialize an empty list pairs and an empty set seen.
3. For each number in flattened:
   • Calculate the complement as target - num.
   • If the complement exists in seen, add the pair (complement, num) to pairs.
   • Add the current number to seen.
4. Return the list of pairs.

4: I-mplement

Implement the code to solve the algorithm.

def find_pairs(nums, target):
    # Flatten the nested list into a single list of integers
    flattened = []
    for item in nums:
        if isinstance(item, list):  # Check if the item is a sublist
            flattened.extend(item)  # Extend the flattened list with elements from the sublist
        else:
            flattened.append(item)  # Append the item directly if it's not a sublist

    pairs = []  # Initialize a list to store the pairs
    seen = set()  # Use a set to track visited numbers for efficiency

    for num in flattened:
        complement = target - num  # Calculate the complement for the current number
        if complement in seen:  # Check if the complement is in the set of seen numbers
            pairs.append((complement, num))  # Add the pair to the result list
        seen.add(num)  # Add the current number to the set of seen numbers

    return pairs  # Return the list of pairs

5: R-eview

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

Example 1:

• Input: nums = [1, 2, [3, 4], [5], 6] target = 7
• Expected Output: [(1, 6), (2, 5), (3, 4)]
• Observed Output: [(1, 6), (2, 5), (3, 4)]

Example 2:

• Input: nums = [] target = 10
• Expected Output: []
• Observed Output: []

6: E-valuate

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

Assume n is the total number of elements in the nested lists.

• Time Complexity: O(n) because we iterate through the list to flatten it and then iterate again to find pairs.
• Space Complexity: O(n) because we create a new list for the flattened elements and use a set for seen numbers.