Two Sum - Solution to LeetCode Problem #1

While this is an extremely simple problem, it has been asked in Apple, Amazon, Adobe, Google, Microsoft, Meta and tons of other companies.

Problem Statement

Given an array of integers nums and an integer target, return the indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order.

Examples

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Input: nums = [3,2,4], target = 6
Output: [1,2]

Input: nums = [3,3], target = 6
Output: [0,1]

Approach 1

The simplest, and the most straightforward approach is to have nested loops, the outer loop having an iterative variable i starting from 0 to n-2, and the inner loop with j from i+1 to n-1  where n is the length of the array nums. Check if nums[i] + nums[j] == target and if true, return (i, j).

Since we know that we would always have a solution, we do not need to explicitly handle a case where this would not have a solution. But, it would be recommended to return something like (-1, -1) or null just to impress your recruiters (obviously after asking them about what you're expected to return if there is no solution).

This approach has a Time Complexity of O(N2) and a Space Complexity of O(1). So, let's look at a few other solutions that are a bit more efficient.

Approach 2

When in doubt, throw in a HashMap 😁😁

HashMap provides access to its contents in O(1) time. So, we can have an HashMap called hmap where the key would be the element and the value would be its index in the nums array.

We then iterate through the nums array with i from 0 to n-1 where n is the length of the array. For each nums[i], check if target - nums[i] is present in hmap. If it is present, return (i, hmap[target - nums[i]]), else add nums[i], i to the HashMap and continue.

This approach has a time complexity of O(N) and space complexity of O(N), which is miles ahead when compared to our previous approach.

A Similar Question

Suppose the interviewer asks you for the integers in the array instead of their indices, then this is another way you can solve the problem ⬇.  

We can start by sorting our array and then have two pointers, one at the beginning start, another at the end called end and then add the values at these positions and compare the value with target.

If it's greater than target, we could move the pointer end, one step to the left. If it's lesser than target, we could move the pointer start, one step to the right.

We repeat this process till nums[start] + nums[end] = target. Assuming we use a decent sorting algorithm, we would get a time complexity of O(N log N) for the sorting part, and complexity of O(N) for moving the pointers. By the rules of Big O notation, the time complexity would be O(N log N + N) = O(N log N).  

Hope you enjoyed this article. If this helped you, please do subscribe for more.

We're always looking for feedback, and would be happy if you could share the same over here.