Problem Statement

Given an array of integers nums and an integer target, return 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.

Example

Input: nums = [2,7,11,15], target = 9
Output: [0,1]

Explanation

The goal of this problem is to find any two unique elements from this list that sums up to the target value and return the indices as list.

In our example 2+7 = 9 which fulfills the above condition. So, we can return index of 2 and index of 7 as list [0,1].

It is ensured that the target can be found by adding any two unique element of this list.

Intuitions

Case 1: We can iterate through each elements and try to find the two elements that sums up to our target. In this solution we will need nested loop where the first loop will take one element from the array and the second loop will add other elements one by one and returns the indices once we sum up to the target.

Even though this solution is accepted. this is an O(n²) solution since we are iterating through each elements in nested loop.

Case 2: Searching elements in an array takes O(n) time. What if instead of iterating through the array twice in nested loop we can find the next number on O(1) time.

To tackle this problem we can use Hash Map. Searching in Hash Map takes O(1) time but will add O(n) space to our solution.

Solution

Step 1

Loop through each elements of the array and find the next integer required diff = target — num to sum up to the target from our Hash MapnumSet = {}.

Step 2

If the required value does not exist in our numSet then we will add our current element with the corresponding index to the Hash Map numSet[num] = idx.

Step 3

If the required value exists in our numSet then we simply return the indices as return [idx, numSet[diff] where idx refers to the index of current element and the difference required to fulfill our target repectively.

Final Code

Complexity

Time Complexity

As we are iterating over all the items in the list once, the time complexity will be O(n).

Space Complexity

And as we are using Hash Map to cache our target differences we can say the space complexity will be O(n).

Happy Coding.

More content at PlainEnglish.io.

Sign up for our free weekly newsletter. Follow us on Twitter, LinkedIn, YouTube, and Discord.

Learn how to create better content for developers with Circuit.