Two Sum III - Data structure design

easy hash map design data structure

Problem

Design a structure with add(number) and find(value): find returns true iff two stored numbers sum to value.

Inputadd(1); add(3); add(5); find(4); find(7)

Outputtrue, false

1+3=4 exists; no pair sums to 7.

ops (add:x or find:x, semicolon-separated)

class TwoSum:
    def __init__(self):
        self.cnt = {}

    def add(self, number):
        self.cnt[number] = self.cnt.get(number, 0) + 1

    def find(self, value):
        for x, c in self.cnt.items():
            need = value - x
            if need == x:
                if c >= 2:
                    return True
            elif need in self.cnt:
                return True
        return False

class TwoSum {
  constructor() { this.cnt = new Map(); }
  add(number) {
    this.cnt.set(number, (this.cnt.get(number) || 0) + 1);
  }
  find(value) {
    for (const [x, c] of this.cnt) {
      const need = value - x;
      if (need === x) {
        if (c >= 2) return true;
      } else if (this.cnt.has(need)) {
        return true;
      }
    }
    return false;
  }
}

class TwoSum {
    Map<Integer, Integer> cnt = new HashMap<>();
    public void add(int number) {
        cnt.merge(number, 1, Integer::sum);
    }
    public boolean find(int value) {
        for (Map.Entry<Integer, Integer> e : cnt.entrySet()) {
            int x = e.getKey(), c = e.getValue();
            int need = value - x;
            if (need == x) {
                if (c >= 2) return true;
            } else if (cnt.containsKey(need)) {
                return true;
            }
        }
        return false;
    }
}

class TwoSum {
    unordered_map<int, int> cnt;
public:
    void add(int number) { cnt[number]++; }
    bool find(int value) {
        for (auto& [x, c] : cnt) {
            int need = value - x;
            if (need == x) {
                if (c >= 2) return true;
            } else if (cnt.count(need)) {
                return true;
            }
        }
        return false;
    }
};

Explanation

We don't store the numbers in a list — instead we keep a count map cnt that remembers how many times each value was added. This makes add instant and find a quick scan.

add(number) just bumps cnt[number] by one. Counting (not a plain set) matters for the case where a pair is two copies of the same value.

find(value) walks over each stored number x and computes its partner need = value - x. If need is a different number that exists in the map, we have a pair. If need equals x itself, we need two copies of x, so we require c >= 2.

Example: after adding 1, 3, 5, calling find(4) tries x = 1, needs 3, which is present → true. find(7) finds no partner for any stored number → false.

Time: add O(1), find O(n) Space: O(n)