Two Sum — Asked in Facebook, Google, and Amazon Interviews

Problem Statement :

You are given an array of integers of length ’n’ and an integer ‘x’. Your task is to return a pair of elements such that they add up to ‘Target’.

The first line contains two integers, integer ’n’, denoting the number of elements, and integer ‘x’, denoting the ‘Target’.

The next line contains the array of numbers from where we have to consider the numbers.

Given:

4 9
2 7 11 13

Output :

7 2

Explanation of given Test Cases :

For the given test case, we can see that the sum of  2 and 7 is equal to 9 and it is the only valid pair.

Approach:

Hashing Solution:

This problem can be solved efficiently by using the technique of hashing. Use a hash_map to check for the current array value x(let). If there exists a value target_sum - x, which on adding to the former gives, target_sum, print out that value pair.

This can be done in constant time.

Code:

Time Complexity : O(N)
Space Complexity : O(N)

Thanks for Reading

Placewit grows the best engineers by providing an interactive classroom experience and by helping them develop their skills and get placed in amazing companies.

Learn more at Placewit. Follow us on Instagram and Facebook for daily learning.