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.

Problem statement taken from: https://leetcode.com/problems/two-sum

Example 1:

Example 2:

Example 3:

Explanation

Brute force

A brute force solution is to use two nested loops.

We use an outer loop with iterator i to visit each element of the array and inner loop with iterator j to check if there is any other element that adds up to the target.

A small code block in C++ will look like this.

The time complexity for the above code is O(N²) and hence the solution is not efficient.

Hash Map

The problem can be solved in O(N) time, using extra space.

We can use a Hash table / HashMap. The HashMap will store the array element as a key and the value will be the index at which the element is stored.

Algorithm

C++ solution

Golang solution

Originally published at https://alkeshghorpade.me.

Software Engineer. Working Saeloun. My portfolio https://alkeshghorpade.me