Problem Description

The Two Sum III - Data structure design problem asks you to design a data structure that supports two operations:

• add(number): Add the number to an internal data structure.
• find(value): Find if there exists any pair of numbers which sum is equal to the specified value.

Key constraints:

• You may add the same number multiple times.
• For find(value), you need to check for any pair (including the same number twice if it was added at least twice) that sums to value.
• Do not reuse the same instance of a number unless it has been added more than once.

Thought Process

At first glance, it seems like every time we call find(value), we could check all possible pairs in the data structure to see if any sum to value. This brute-force approach works, but is inefficient, especially if there are many elements or many find queries.

To optimize, we need a way to quickly check if a complement (i.e., value - number) exists for any number we've seen so far. This is similar to the classic Two Sum problem, which is commonly solved using a hash map for constant-time lookups.

However, since numbers can be repeated and we need to support multiple add and find calls, we must also track the count of each number. This ensures that if we want to use the same number twice (e.g., number + number == value), we have added it at least twice.

Solution Approach

Let's break down the solution step by step:

1. Data Structure Choice:
   • We use a hash map (dictionary) to store each number as a key and its count as the value.
   • This allows us to check if a number exists in O(1) time and to track how many times it has been added.
2. add(number):
   • When a number is added, increment its count in the hash map.
3. find(value):
   • Iterate through each unique number in the hash map.
   • For each number, compute its complement: complement = value - number.
   • Two cases:
     • If complement == number, check if its count is at least 2 (since we need two instances).
     • If complement != number, check if complement exists in the hash map.
   • If any such pair is found, return true. If no such pair exists after checking all, return false.

This approach ensures that add is O(1), and find is O(n), where n is the number of unique numbers added.

Example Walkthrough

Let's walk through an example:
Operations:

• add(1)
• add(3)
• add(5)
• find(4) (should return true: 1+3=4)
• find(7) (should return false: no two numbers sum to 7)

1. After add(1): hashmap = {1:1}
2. After add(3): hashmap = {1:1, 3:1}
3. After add(5): hashmap = {1:1, 3:1, 5:1}
4. find(4):
   • Check number 1: complement = 3. 3 exists in map. Return true.
5. find(7):
   • Check 1: complement = 6 (not in map)
   • Check 3: complement = 4 (not in map)
   • Check 5: complement = 2 (not in map)
   • No pair found. Return false.

Time and Space Complexity

Brute-force approach:

• add(number): O(1) per addition (if using a list)
• find(value): O(n²) per query (check all pairs in the list)
• Space: O(n), where n is the number of numbers added

• add(number): O(1) per addition (hash map update)
• find(value): O(k), where k is the number of unique numbers (iterate through keys)
• Space: O(k), where k is the number of unique numbers

The optimized approach is much faster for repeated find queries, especially when the number of unique numbers is small compared to the total number of add calls.

Summary

The Two Sum III problem is elegantly solved by using a hash map to track the count of each number added. This allows for constant-time additions and efficient lookups for pairs that sum to a target value. By carefully handling the case where the same number is used twice, and leveraging the hash map's O(1) access, we achieve an efficient and flexible data structure. The key insight is to use counting to handle duplicates and to iterate over unique numbers for the find operation, making the solution both simple and performant.

Code Implementation

class TwoSum:

    def __init__(self):
        self.counts = {}

    def add(self, number: int) -> None:
        if number in self.counts:
            self.counts[number] += 1
        else:
            self.counts[number] = 1

    def find(self, value: int) -> bool:
        for num in self.counts:
            complement = value - num
            if complement == num:
                if self.counts[num] > 1:
                    return True
            else:
                if complement in self.counts:
                    return True
        return False
      

class TwoSum {
    unordered_map<int, int> counts;
public:
    TwoSum() {}

    void add(int number) {
        counts[number]++;
    }

    bool find(int value) {
        for (auto &p : counts) {
            int num = p.first;
            int complement = value - num;
            if (complement == num) {
                if (p.second > 1) return true;
            } else {
                if (counts.count(complement)) return true;
            }
        }
        return false;
    }
};
      

import java.util.*;

class TwoSum {
    private Map<Integer, Integer> counts;

    public TwoSum() {
        counts = new HashMap<>();
    }

    public void add(int number) {
        counts.put(number, counts.getOrDefault(number, 0) + 1);
    }

    public boolean find(int value) {
        for (int num : counts.keySet()) {
            int complement = value - num;
            if (complement == num) {
                if (counts.get(num) > 1) return true;
            } else {
                if (counts.containsKey(complement)) return true;
            }
        }
        return false;
    }
}
      

class TwoSum {
    constructor() {
        this.counts = new Map();
    }
    add(number) {
        this.counts.set(number, (this.counts.get(number) || 0) + 1);
    }
    find(value) {
        for (let num of this.counts.keys()) {
            let complement = value - num;
            if (complement === num) {
                if (this.counts.get(num) > 1) return true;
            } else {
                if (this.counts.has(complement)) return true;
            }
        }
        return false;
    }
}