Data Structures and Algorithms — Arrays #1 — Count pairs with the given sum

A step-by-step guide to acing the coding interviews

Problem Statement:

Given an array of N integers, and an integer K, find the number of pairs of elements in the array whose sum is equal to K.

Example 1:

Input:
N = 4, K = 6
arr[] = {1, 5, 7, 1}
Output: 2
Explanation: 
arr[0] + arr[1] = 1 + 5 = 6 
and arr[1] + arr[3] = 5 + 1 = 6.

Example 2:

Input:
N = 4, K = 2
arr[] = {1, 1, 1, 1}
Output: 6
Explanation: 
Each 1 will produce sum 2 with any 1.

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

Asked by the following companies:

Accolite, Adobe, Amazon, FactSet, Flipkart, Goldman Sachs, Hike, MakeMyTrip, Salesforce

Brute Force Approach:

1. Consider each possible pair of numbers in the array.
2. Find the sum for each pair.
3. If the required sum is found, increment the pair count by 1.
4. Return count.

Complexity Analysis:

Time Complexity: O(N²)
Auxiliary Space: O(1)

Optimal Solution — Using Hashing:

• We use a hashmap to store the key-value pairs.
• Key denotes each element in the array. Value stores the number of eligible pairs that can be formed with the key and the other elements.

What are hashmaps?

Hashmap is a Java interface, which stores each entry in key-value pairs. It is found under the java.util package and is very similar to dictionaries in python. It is denoted by Hashmap<Key,Value>.

• Initialize the existing pair count as zero and traverse the array.
• If sum-arr[i] exists in the hashmap, then update the count to count + Value(element). Why?

If sum-arr[i] exists and let’s say that is arr[j], then it means

sum — arr[i] = arr[j]

or, arr[i] + arr[j] = sum

Thus, arr[i] & arr[j] form the required pair that we need.

• Hence, we update the count element by adding the existing pair count.
• Next, add arr[i] to the hashmap. Increment the count by one. If the element already exists in the hashmap, then increment its value by one.
• Return count.

Code:

Complexity Analysis:

Time Complexity: O(N)
Auxiliary Space: O(N) — since we used additional Hashmap.
’N’ is the number of elements in the array.

If you liked this article, please click the “clap” button 👏 a few times.

Gives me enough motivation to put out more content like this. Please share it with a friend who you think this article might help.

Follow me Varsha Das to receive my weekly articles.

Connect with me — Varsha Das | LinkedIn

Follow my Youtube channel where we discuss Data Structures & Algorithms.

Thanks for reading.

Happy learning! 😁