SimuVedaAlgorithms Lab Open in the lab

Hashing / Beginner

Two Sum with a Hash Map Visualizer

Walk once. For each value, ask the hash map whether its partner (target − value) was already seen. If not, remember this value and its index.

Start the Two Sum with a Hash Map simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(1)
Average timeO(n)
Worst timeO(n)
Extra spaceO(n)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. Target is 9. The map starts empty. [2, 7, 11, 15, 1, 8]
  2. At 2: its partner would be 9 − 2 = 7.
  3. 7 hasn’t been seen. Remember 2 at index 0.
  4. At 7: its partner would be 9 − 7 = 2.
  5. 2 is in the map at index 0. Answer: [0, 1].

Try it with your own input →

Two Sum with a hash map in Java, Python, C++, C and JavaScript

int[] twoSum(int[] a, int target) {
  Map<Integer, Integer> seen = new HashMap<>();
  for (int i = 0; i < a.length; i++) {
    int need = target - a[i];
    if (seen.containsKey(need))
      return new int[]{seen.get(need), i};
    seen.put(a[i], i);
  }
  return new int[]{-1, -1};
}
def two_sum(a, target):
    seen = {}
    for i in range(len(a)):
        need = target - a[i]
        if need in seen:
            return [seen[need], i]
        seen[a[i]] = i
    return [-1, -1]
vector<int> twoSum(const vector<int>& a, int target) {
  unordered_map<int, int> seen;
  for (int i = 0; i < (int)a.size(); i++) {
    int need = target - a[i];
    if (seen.count(need))
      return {seen[need], i};
    seen[a[i]] = i;
  }
  return {-1, -1};
}
/* Values are small here (0..99), so an array stands in for the hash map. */
#define MAXV 100

void twoSum(int a[], int n, int target, int out[2]) {
  int seen[MAXV];
  for (int v = 0; v < MAXV; v++) seen[v] = -1;
  for (int i = 0; i < n; i++) {
    int need = target - a[i];
    if (need >= 0 && need < MAXV && seen[need] >= 0) {
      out[0] = seen[need]; out[1] = i; return;
    }
    seen[a[i]] = i;
  }
  out[0] = out[1] = -1;
}
function twoSum(a, target) {
  const seen = new Map();
  for (let i = 0; i < a.length; i++) {
    const need = target - a[i];
    if (seen.has(need))
      return [seen.get(need), i];
    seen.set(a[i], i);
  }
  return [-1, -1];
}

In an interview

LeetCode 1, Two Sum: the indexes of two values that add up to the target. The most-asked interview question there is.

Brute force checks every pair, O(n²). Sorting plus two pointers is O(n log n) but loses the original indexes. The hash map is O(n) and keeps them.

More hashing