This post is completed by 2 users

  • 0
 Add to List
Beginner

471. 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.

Example:

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

Approach:

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)

Output:

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

Related Problems: