Hashing — Two Sum III (Data Structure Design)

↗ LeetCode: Two Sum III - Data Structure Design · Easy · pattern chapter →

Asked atLinkedInMetaGoogle

Design TwoSum supporting add(x) and find(t).

Example 1 —

TwoSum ts = new TwoSum();
ts.add(1); ts.add(3); ts.add(5);
ts.find(4);  // true  (1 + 3)
ts.find(7);  // false

Example 2 — Duplicate handling: add(3); add(3); find(6) → true (uses both 3s).

Example 3 — Empty: find(10) on a fresh TwoSum → false.

Constraints — up to 10⁴ ops total. Naive O(n²) per-find would give 10⁸ ops; wisely chosen design gives ~10⁴.

Progressive Hints

Try to solve it yourself first. Reveal hints only when stuck — each hint is progressively more specific.

---

⏱️Interview timer00:00

Practice under interview pressure. Start when you begin reading; stop when you finish. Save best only when you had a full working solution.

Target for interview: Medium = 20-25 min · Hard = 30-40 min · Best time persists on this device only.

Approach 1 — Fast add, slow find (canonical if adds dominate)

Insight. Store counts in a HashMap. On add, increment count in O(1). On find, iterate over each stored value k and check whether t - k also exists (with duplicate handling for k == t/2).

class TwoSum {
    Map<Integer, Integer> cnt = new HashMap<>();
    void add(int x) { cnt.merge(x, 1, Integer::sum); }
    boolean find(int t) {
        for (int k : cnt.keySet()) {
            int need = t - k;
            if (k == need) { if (cnt.get(k) >= 2) return true; }
            else if (cnt.containsKey(need)) return true;
        }
        return false;
    }
}

Complexity — add O(1); find O(n). In an interview say "ask the interviewer about the ratio of adds to finds — pick a design accordingly."

Approach 2 — Fast find, slow add

Precompute all pairwise sums into a HashSet on add. find = O(1), add = O(n).

class TwoSumFastFind {
    List<Integer> nums = new ArrayList<>();
    Set<Integer> sums = new HashSet<>();
    void add(int x) {
        for (int y : nums) sums.add(x + y);
        nums.add(x);
    }
    boolean find(int t) { return sums.contains(t); }
}

Complexity — add O(n); find O(1). Say aloud in an interview: "trade-space-for-time: sums grows to O(n²), fine at 10⁴ ops but explodes at 10⁶."

---

Try it yourself

Complexity summary

Approach	add	find	Grade
Fast add	O(1)	O(n)	Canonical when adds dominate
Fast find	O(n)	O(1)	When finds dominate

When to use which

• Ask the interviewer about ratio — pick the matching design.
• Balanced → hybrid or ordered TreeSet.
• "Stream infinite" → fast add.

✨AI Study CompanionBeta

Related problems

• Two Sum

Was this page helpful?