Domain 1EasyCORE

Two Sum III - Data structure design

The problem requires designing a data structure that can efficiently handle two operations: adding an integer to the data structure and checking if there exists any pair of integers in the data structure that sum up to a given value. The inputs are a series of `add` operations with integers and `find` operations with target sums. The outputs for `find` operations are boolean values indicating whether such a pair exists.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Hash Table#Design

170. Two Sum III - Data structure design

Model: qwen2.5-coder:14b
Topics: Hash Table,Design
FAANG asked: 0
Acceptance rate: 35.0%


Problem Breakdown

The problem requires designing a data structure that can efficiently handle two operations: adding an integer to the data structure and checking if there exists any pair of integers in the data structure that sum up to a given value. The inputs are a series of add operations with integers and find operations with target sums. The outputs for find operations are boolean values indicating whether such a pair exists.

Inputs:

  • add(int number): Adds an integer to the data structure.
  • find(int value): Checks if any two numbers in the data structure sum up to the given value.

Outputs:

  • For find, return true if there is at least one pair of integers that sum to the target value, otherwise return false.

Implicit Constraints and Edge Cases:

  • The data structure should handle a large number of operations efficiently.
  • Duplicates are allowed, meaning the same integer can be added multiple times.
  • Negative numbers are possible.
  • Overflow conditions need to be considered for the sum operation.

Intuition

A brute-force approach would involve storing all numbers in an array and checking each pair during the find operation. This approach has a time complexity of O(n^2) for the find operation, which is inefficient given the constraints.

The key insight is to use a hash table (dictionary in Python) to store the frequency of each number added. During the find operation, we can check if there exists another number that complements the current number to reach the target sum. This reduces the time complexity for the find operation to O(n), where n is the number of unique numbers stored.

Approach

  1. Data Structure Choice:

    • Use a dictionary (self.num_counts) to store each unique number as a key and its frequency as the value.
  2. Initialization:

    • Initialize an empty dictionary in the constructor.
  3. Add Operation:

    • When adding a number, increment its count in the dictionary.
    • If the number is not already present, add it with a count of 1.
  4. Find Operation:

    • For each unique number in the dictionary:
      • Calculate the complement needed to reach the target sum (complement = value - number).
      • Check if the complement exists in the dictionary.
      • If the complement is the same as the current number, ensure there are at least two occurrences of this number.
    • Return true if such a pair is found; otherwise, return false.

Complexity Analysis

  • Time Complexity:

    • add(int number): O(1), as dictionary operations (insert and update) are average O(1).
    • find(int value): O(n), where n is the number of unique numbers stored in the dictionary.
  • Space Complexity:

    • O(n), where n is the number of unique numbers added to the data structure.

Solution

class TwoSum:
    def __init__(self):
        # Initialize an empty dictionary to store the frequency of each number
        self.num_counts = {}

    def add(self, number: int) -> None:
        # Add the number to the dictionary or increment its count if it already exists
        if number in self.num_counts:
            self.num_counts[number] += 1
        else:
            self.num_counts[number] = 1

    def find(self, value: int) -> bool:
        # Iterate through each unique number in the dictionary
        for number in self.num_counts:
            complement = value - number
            # Check if the complement exists in the dictionary
            if complement in self.num_counts:
                # If the complement is the same as the current number, ensure there are at least two occurrences
                if complement == number and self.num_counts[number] > 1:
                    return True
                elif complement != number:
                    return True
        # Return false if no valid pair is found
        return False

Edge Cases Handled

  • Empty Input: The data structure starts empty, and find operations will correctly return false.
  • Duplicates: The dictionary stores the frequency of each number, allowing duplicates to be handled.
  • Negative Numbers: The solution works with negative numbers as they are valid inputs.
  • Overflow: The problem constraints ensure that overflow conditions do not occur within the given range.