Given an array, count the number of pairs with a given sum.

Objective: Given an array of integers, write a program to count all the pairs with the given sum.


Given array: [1, 5, 7, 1, -1], Sum= 6
Total Pairs: 3
Note: pairs are (1, 5), (5, 1) and (7, -1)

Given array: [4, 5, 1, 2, 9, -2, -4], Sum= 5
Total Pairs: 2
Note: pairs are (4, 1) and (9, -4)

Given array: [3, 3, 3, 3], Sum= 6
Total Pairs: 6


Naive approach to run the nested loops and add each pair to check it with the given sum.

Time Complexity: O(N2)

Better approach is to use the Map. 

  1. Traverse the array and construct a map with elements in the array as key and their count as value. 
  2. Initialize pairCount = 0.
  3. Now traverse the map and for each key X in map with count>0
    • Do Y = sum –  X, check if Y is present in map and count>0 , if yes then get the X and Y counts from map.
    •  Let’s say X_COUNT is count of X and Y_COUNT is count of Y.
    • If X and Y are same means both elements are same then do pairCount + X_COUNT*(X_COUNT-1)/2. (Number of ways to pick 2 elements out of n = nC2) 
    • If X and Y are not same then Do pairCount = pairCount + X_COUNT*Y_COUNT.
    • Put X and Y count 0 in the map.
  4. Return pairCount.   

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

Complete Code


Given array: [1, 5, 7, 1, -1], Sum= 6
Total Pairs: 3

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: