Number of Pairs with Given Sum — Asked in Amazon, Samsung and Nagarro Interview

Problem Statement :

You have been given an integer array/list(arr) and a number ‘Sum’. Find and return the total number of pairs in the array/list which when added, results equal to the ‘Sum’.

The first line contains 2 space-separated integers N and Sum.

Next line contains N space-separated integers representing array elements.

Sample Input:

6 10
2 8 10 5 -2 5

Sample Output:


Explanation of Sample Test Case:

We have 2 pairs that sum up to 10. They are, (2, 8) and (5, 5). Note that we are not counting (8,2), as (2,8) and (8,2) is considered same.

Approach :

Map/Dictionary Approach

  1. Create a hashmap/dictionary which will store the count of occurrences of each elements and initially it will be empty.
  2. Run a loop from i=0 to N-1 and for each i’th element its value is arr[i] and we need to find the number which is equal to Sum — arr[i]. So check if sum-arr[i] is present in the hashmap/dictionary. If it is present, the answer will be increased by the count of occurrence of sum-arr[i] present in the hashmap/dictionary as arr[i] can be paired with all those sum-arr[i] elements present in its left side.
  3. Now increase the count of arr[i] in the hashmap/dictionary by 1.

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

Code :

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.




Upskilling students for tech placements!

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Preoptimization, and Death by a Thousand Comforts

Setting Up Unit Testing For Java In VS Code (with Maven)

Recursive Function and the Yo Yo

Understanding Core Concepts of Cloud Infrastructure

Unity ads, monetization with benefits to the player.

Cosmos Tip App @cosmostipbot (alpha) now live on Telegram.

Stack Quiz

Monitoring vs. Observability

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store


Upskilling students for tech placements!

More from Medium

Google Interview Question — LeetCode 690

14 Days Study Plan to Crack Algo I

Understanding Huffman Coding

Minimum Moves to Reach Target Score