https://leetcode.com/problems/two-sum

Probably the first problem you solved when you started leetcoding.

This is a classic problem – I haven’t been asked this problem ever in an interview – but this one brings back a lot of memories and yes there was a time I struggled to solve this problem as well 🙂

Using 2 loops would be the most straightforward but slow way to solve this problem – in an interview, the interviewer will expect a better solution that O(N^2) though.

The optimal solution uses a hashmap to keep the index of previously seen numbers – this increases the space complexity to O(n), but improves the time complexity to O(n).

Variant: Although this problem asks for the index of the two numbers that add up to target – there is a variant of this problem that asks for the actual numbers itself (i.e. find the two numbers that add to target). That variant can be solved in O(n logn) time, if we cannot/do-not want to allocated O(n) space – that solution first sorts the input array and then iterates over the sorted array with two pointers – increasing the left pointer if the sum is smaller and reducing the right pointer if the sum is larger than the target.

If you just solved this problem on your own – welcome to leetcoding, you have an exciting journey ahead of you.