We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Two Sum III - Data structure design

Number: 170

Difficulty: Easy

Paid? Yes

Companies: Amazon, LinkedIn

Problem Description

Design a data structure that supports adding integers from a data stream and checking if any two numbers sum up to a given value. The data structure should efficiently support the following operations:

  • add(number): Add the integer to the internal data structure.
  • find(value): Return true if there exists any pair of integers in the internal data structure whose sum equals the given value; otherwise, return false.

Key Insights

  • Maintain a hash table (or map/dictionary) to store each number along with its frequency.
  • The add operation can simply update/increment the count for each number, which is O(1).
  • For the find operation, iterate over the keys in the hash table and for each key, check if (target - key) exists.
  • Special care is needed when (target - key) is the same as key; in that case, ensure that the count of that number is at least 2.

Space and Time Complexity

Time Complexity:

  • add(number): O(1) on average.
  • find(value): O(n) where n is the number of unique entries. Space Complexity: O(n) for storing the numbers and their counts.

Solution

The solution uses a hash table to keep track of the frequencies of the numbers added. For the add operation, update the hash table by increasing the count of the number. For the find operation, iterate over the unique keys in the hash table, and for each key, compute the complement (value - key). If the complement exists in the table and:

  • Either the complement is different from the key, or
  • The complement is the same as the key and its frequency is at least 2, then return true. This design efficiently supports both operations while conforming to the problem constraints.

Code Solutions

# Python implementation of TwoSum class

class TwoSum:
    def __init__(self):
        # Initialize an empty dictionary to store number counts
        self.num_counts = {}
    
    def add(self, number):
        # If number exists, increment its count; otherwise, set its count to 1
        if number in self.num_counts:
            self.num_counts[number] += 1
        else:
            self.num_counts[number] = 1
    
    def find(self, value):
        # Iterate over each unique number in the dictionary
        for num in self.num_counts:
            complement = value - num  # compute the complement
            # Check if the complement exists in the dictionary
            if complement in self.num_counts:
                # if complement is same as num, need at least two occurrences
                if complement == num and self.num_counts[num] > 1:
                    return True
                # if complement is different than num, valid pair exists
                elif complement != num:
                    return True
        return False
← Back to All Questions