Two Sum Problem

Objective: Given an array of integers, and k. Write a program to find indexes of two elements in an array which sum is equal to K.


Given array: [5, 4, 7, 3, 9, 2], Sum = 13
Output: Found indexes are: 4 and 1

Given array: [1, 2, 3, 4, 5], Sum = 9
Found indexes are: 4 and 3

Given array: [1, 2, 3, 4, 5], Sum = 10
No indexes are found


Brute Force: Use nested loops and all possible pairs in the array and check if pair sum is equal to K if found then print the indexes of the pair.

Time Complexity: O(N2)

Better Solution: Use Map

  • Construct a map that stores the array element as key and its index as value. 
  • Iterate the array and for every element x-
    • Calculate  y = K-x.
    • Check if y is present in the map, 
      1. If yes then we have found the pair which sum to K. Get the index of y from the map and print it along with the index of x.
      2. If not then add x and its index into the map.

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

Complete Code:


Given array: [5, 4, 7, 3, 9, 2], Sum = 13
Found indexes are: 4 and 1

Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.

You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: