Mark As Completed Discussion

The hash above represents a record of elements we've seen so far that can be looked up via their difference from the goal. We can then use that information in subsequent iterations to find a matching pair, since we can try to look up arr[i] in the hash.

In the above example of [1, 3, 4], we only need two iterations!

  1. At index 0, we encounter 1.
  2. Calculate the difference between goal - arr[i]. 4 - 1 = 3
  3. Take the difference of 3 and store it in our table. hash[3] = 0 (we store the index)

As soon as we get to index 1 and see 3, we can:

  1. Look up 3 in the hash map
  2. Retrieve index 0

So we know that 1 (index 0) and 3 (index 1) pair sum to 4. We return [0, 1].

The time complexity of this solution is O(n) because we iterate through all the elements exactly once. Space complexity is similarly O(n) as the hash map will grow proportionate to the input.