Two Sum III - Data structure design - Practice Coding Problems

Two Sum III - Data structure design - Problem

Array Hash Table Two Pointers Design Data Stream Easy

Design a data structure that accepts a stream of integers and checks if it has a pair of integers that sum up to a particular value.

Implement the TwoSum class:

TwoSum() - Initializes the TwoSum object, with an empty array initially.
void add(int number) - Adds number to the data structure.
boolean find(int value) - Returns true if there exists any pair of numbers whose sum is equal to value, otherwise returns false.

Input & Output

Example 1 — Basic Operations

$ Input: operations = ["TwoSum", "add", "add", "add", "find", "find"], values = [null, 1, 3, 2, 4, 7]

› Output: [null, null, null, null, true, false]

💡 Note: Initialize TwoSum, add numbers 1, 3, 2. find(4) returns true because 1+3=4. find(7) returns false because no pair sums to 7.

Example 2 — Duplicate Numbers

$ Input: operations = ["TwoSum", "add", "add", "find"], values = [null, 2, 2, 4]

› Output: [null, null, null, true]

💡 Note: Add 2 twice, then find(4) returns true because 2+2=4. Need to handle duplicate numbers correctly.

Example 3 — No Valid Pair

$ Input: operations = ["TwoSum", "add", "add", "find"], values = [null, 1, 5, 3]

› Output: [null, null, null, false]

💡 Note: Add 1 and 5, then find(3) returns false because no combination of 1 and 5 equals 3.

Constraints

-10⁵ ≤ number ≤ 10⁵
-2×10⁵ ≤ value ≤ 2×10⁵
At most 10⁴ calls to add and find

Visualization

Tap to expand

Understanding the Visualization

Stream Input

Numbers arrive one by one via add() calls

Store Efficiently

Hash map tracks numbers and frequencies

Fast Lookup

find() checks complements in O(1) time

Key Takeaway

🎯 Key Insight: Use hash map to store frequencies and enable O(1) complement lookups for efficient pair detection

Asked in

Li LinkedIn 15 A Amazon 12 G Google 8 M Microsoft 6

The key insight is to use a hash map to store numbers with their frequencies, enabling O(1) complement lookups during find operations. The optimal hash map approach achieves O(1) add and O(n) find operations. Time: O(n) for find, Space: O(n) for storage.

Common Approaches

Approach	Time	Space	Notes
✓ Hash Map Optimization	O(n)	O(n)	Use hash map to store numbers and check complements in O(1) time
Brute Force with Array	O(n²)	O(n)	Store numbers in array, check all pairs for each find operation

Hash Map Optimization — Algorithm Steps

Store numbers in hash map with frequency count
For find, check each number's complement in the map
Handle duplicates carefully (num + num = target case)

Visualization

Tap to expand

Step-by-Step Walkthrough

Store with Frequency

Hash map tracks number frequencies

Check Complement

For each number, lookup target - number

Handle Duplicates

Special case when number pairs with itself

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define HASH_SIZE 10007

typedef struct HashNode {
    int key;
    int value;
    struct HashNode* next;
} HashNode;

typedef struct {
    HashNode* table[HASH_SIZE];
} TwoSum;

int hash(int key) {
    return abs(key) % HASH_SIZE;
}

TwoSum* twoSumCreate() {
    TwoSum* obj = (TwoSum*)malloc(sizeof(TwoSum));
    for (int i = 0; i < HASH_SIZE; i++) {
        obj->table[i] = NULL;
    }
    return obj;
}

void twoSumAdd(TwoSum* obj, int number) {
    int idx = hash(number);
    HashNode* node = obj->table[idx];
    
    while (node) {
        if (node->key == number) {
            node->value++;
            return;
        }
        node = node->next;
    }
    
    node = (HashNode*)malloc(sizeof(HashNode));
    node->key = number;
    node->value = 1;
    node->next = obj->table[idx];
    obj->table[idx] = node;
}

int getCount(TwoSum* obj, int key) {
    int idx = hash(key);
    HashNode* node = obj->table[idx];
    
    while (node) {
        if (node->key == key) {
            return node->value;
        }
        node = node->next;
    }
    return 0;
}

bool twoSumFind(TwoSum* obj, int value) {
    for (int i = 0; i < HASH_SIZE; i++) {
        HashNode* node = obj->table[i];
        while (node) {
            int num = node->key;
            int complement = value - num;
            
            if (complement != num) {
                if (getCount(obj, complement) > 0) {
                    return true;
                }
            } else {
                if (node->value > 1) {
                    return true;
                }
            }
            node = node->next;
        }
    }
    return false;
}

int main() {
    char line1[1000], line2[1000];
    fgets(line1, sizeof(line1), stdin);
    fgets(line2, sizeof(line2), stdin);
    
    TwoSum* obj = twoSumCreate();
    printf("[null");
    
    // Simple demo
    twoSumAdd(obj, 1);
    printf(",null");
    twoSumAdd(obj, 3);
    printf(",null");
    bool result = twoSumFind(obj, 4);
    printf(",%s", result ? "true" : "false");
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Find operation iterates through unique numbers once, hash lookups are O(1)

✓ Linear Growth

Space Complexity

O(n)

Hash map stores up to n unique numbers with their frequencies

⚡ Linearithmic Space

35.0K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Hash Map Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler