Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Pair Sum

Easy
0/40
Average time to solve is 15m
profile
Contributed by
3060 upvotes
Asked in companies
OpenTextPhone PeGoogle

Problem statement

You are given an integer array 'ARR' of size 'N' and an integer 'S'. Your task is to return the list of all pairs of elements such that each sum of elements of each pair equals 'S'.

Note:

Each pair should be sorted i.e the first value should be less than or equals to the second value. 

Return the list of pairs sorted in non-decreasing order of their first value. In case if two pairs have the same first value, the pair with a smaller second value should come first.
Detailed explanation ( Input/output format, Notes, Images )
Input Format:
The first line of input contains two space-separated integers 'N' and 'S', denoting the size of the input array and the value of 'S'.

The second and last line of input contains 'N' space-separated integers, denoting the elements of the input array: ARR[i] where 0 <= i < 'N'.
Output Format:
Print 'C' lines, each line contains one pair i.e two space-separated integers, where 'C' denotes the count of pairs having sum equals to given value 'S'.
Note:
You are not required to print the output, it has already been taken care of. Just implement the function.
Constraints:
1 <= N <= 10^3
-10^5 <= ARR[i] <= 10^5
-2 * 10^5 <= S <= 2 * 10^5

Time Limit: 1 sec
Sample Input 1:
5 5
1 2 3 4 5
Sample Output 1:
1 4
2 3
Explaination For Sample Output 1:
Here, 1 + 4 = 5
      2 + 3 = 5
Hence the output will be, (1,4) , (2,3).
Sample Input 2:
5 0
2 -3 3 3 -2
Sample Output 2:
-3 3
-3 3
-2 2
Hint

As N is relatively small, an O(N^2) solution may pass.

Approaches (3)
Brute Force
  • Initialize a list to store our results.
  • For each element in the array 'ARR[i]', check if ('ARR[i]' + ‘ARR[j]’), equals to given sum or not, where ‘i’ < ‘j’ < ‘N’.
  • If the condition matches, add the pair('ARR[i]', ‘ARR[j]’) to the list. Sort the list of pairs as per the given output format and return this list.
Time Complexity

O(N ^ 2), where ‘N’ is the number of elements in the array.

 

In the worst case, for each element, we will be checking all other elements in the array. Hence the overall time complexity will be O(N ^ 2).

Space Complexity

O(1).

 

Constant extra space is required.

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Pair Sum
All tags
Sort by
Search icon

Interview problems

Order of the pair of small arr

I dont quite get the order i which the pair of arr is getting positioned, need help regarding that.

19 views
0 replies
0 upvotes

Interview problems

Cleaner (probably better?) solution than the editorial

While asymptomatically the space complexity will remain O(n), my solution does not take any extra space. The space complexity is O(n) due to the sorting algorithm. In the editorial solutions, even after you disregard the space complexity due to the sorting section, the hashmap accounts for O(n) space. But in my solution, if you disregard the sorting, space complexity becomes O(1)

 

Anyway, here's my solution:

 

/**
Author: Abhinav Parag Mishra

Time Complexity: O(n²)

Space Complexity: O(n)

**/

import java.io.*;
import java.util.* ;

public class Solution{
    public static List<int[]> pairSum(int[] arr, int s) {
        // Write your code here.
        List<int[]> result = new ArrayList<int[]>();
        Arrays.sort(arr);
        int i = 0, j = arr.length - 1, num1, num2, sum;
        while( i < j ){
            num1 = arr[i];
            num2 = arr[j];
            sum = num1 + num2;
            if(sum > s){
                j--;
            }else if(sum < s){
                i++;
            }else {
                if(num1 == num2){ // For example [5,5,5,5] when s = 10
                    int totalElements = j - i + 1;
                    int totalCombinations = (totalElements - 1) * totalElements / 2; // n * (n + 1) / 2
                    while(totalCombinations-- > 0){
                        result.add(new int[]{num1, num2}); // Add all possible combinations of [5,5]
                    }
                    break;
                }else {
                    int totalNum1s = 1, totalNum2s = 1; // For example [2,2,2,3,3] when s = 10
                    while(arr[++i] == num1) totalNum1s++; // Total num1s (2s) = 3
                    while(arr[--j] == num2) totalNum2s++; // Total num2s (3s) = 2
                    int totalIterations = totalNum1s * totalNum2s; // Total iterations = 3*2 = 6
                    while(totalIterations-- > 0) {
                        result.add(new int[]{num1, num2}); // Push [2,3] 6 times
                    }
                }
            }
        }
        return result;
    }
}

 

 

29 views
0 replies
0 upvotes

Interview problems

JAVA || ALL Test Cases Passed || Easy Code

import java.io.*;

import java.util.* ;

 

public class Solution{

    public static List<int[]> pairSum(int[] arr, int s) {

        // Write your code here.

        List<int[]> list= new ArrayList<>();

       // Map<Integer,Integer> map = new HashMap<>();

        for(int i=0;i<arr.length;i++){

            for(int j =i+1;j<arr.length;j++){

                if(arr[i]+arr[j]==s){

                    int[] d =new int[]{arr[i],arr[j]};

                    Arrays.sort(d);

                    list.add(d);

                }

            }

        }

        Collections.sort(list,(a,b)->a[0]==b[0]?a[1]-b[1]:a[0]-b[0]);

        return list;

    }

}

 

java

Easy

122 views
0 replies
0 upvotes

Interview problems

Most easy C++

vector<vector<int>> ans;

 

   for(int i=0;i<n;i++){

      for(int j=i+1;j<n;j++){

         if(arr[i]+arr[j] == s){

            vector<int> temp;

            temp.push_back(min(arr[i] , arr[j]));

            temp.push_back(max(arr[i] , arr[j]));

            ans.push_back(temp);

         }

      }

   }

   sort(ans.begin() , ans.end());

   return ans;

146 views
0 replies
0 upvotes

Interview problems

Pair Sum, C++ || A little optimization with for loop approach, giving result better than 98.8%.

#include <bits/stdc++.h>

 

vector<vector<int>> pairSum(vector<int> &arr, int s){

   // Write your code here.

 

   vector<vector<int>> result;

    sort(arr.begin(), arr.end()); // sorting the input array in the beginning.

    

    for(int i = 0 ; i < arr.size(); i++)

    {

        for(int j = i+1; j < arr.size(); j++)

        {

            if(arr[i] + arr[j] == s)

            {

                result.push_back({arr[i], arr[j]});

            }

            

            else if(arr[i] + arr[j] > s)

            break;

            

            else

            continue;

        }

    }

    return result;

}

185 views
1 reply
0 upvotes

Interview problems

Pair sum

#include <bits/stdc++.h>

 

vector<vector<int>> pairSum(vector<int> &arr, int s){

   // Write your code here.

 

   vector<vector<int>> ans;

 

   for(int i = 0; i<arr.size();i++){

      for(int j = i+1; j<arr.size();j++){

         if(arr[i]+arr[j] == s){

            vector<int>temp;

            temp.push_back(min(arr[i],arr[j]));

            temp.push_back(max(arr[i],arr[j]));

            ans.push_back(temp);

         }

      }

   }

 

   sort(ans.begin(),ans.end());

   return ans;

}

147 views
0 replies
0 upvotes

Interview problems

Pair Sum || Easy to Uderstand || Better than 70.26%

#include <bits/stdc++.h>

 

vector<vector<int>> pairSum(vector<int> &arr, int s){

   // Write your code here.

 

   vector<vector<int>>ans;

 

   for(int i=0; i<arr.size(); i++){

 

      for(int j=i+1; j<arr.size(); j++){

 

         if(arr[i] + arr[j] == s){

 

            vector<int>temp;

            temp.push_back(min(arr[i],arr[j]));

            temp.push_back(max(arr[i],arr[j]));

            ans.push_back(temp);

         }

      }

   }

   sort(ans.begin(),ans.end());

   return ans;

}

214 views
0 replies
0 upvotes

Interview problems

can we do this pair sum question

import java.util.Arrays;

import java.util.Scanner;

class A

{

    public static void main(String args[])

    {

        Scanner sc=new Scanner(System.in);

     

        int N=sc.nextInt();

        int S=sc.nextInt();//target

         int ARR[]=new int[N];

         int i;

         for(i=0;i<N;i++)

         {

             ARR[i]=sc.nextInt();

         }

         for( i=0;i<N;i++)

         {

             for(int j=i+1;j<N;j++)

             {

                 if(ARR[i]+ARR[j]==S)

                 {

                     System.out.println("Pairs"+ARR[i]+" "+ARR[j]);

                 }

             }

         }

         sc.close();

        

    }

} like this but it is not accepting 

213 views
1 reply
0 upvotes
profile

Interview problems

C++ easiest soln PAIR SUM

vector<vector<int>> pairSum(vector<int> &arr, int s){

// Write your code here.

vector<vector<int> >ans;

 

for(int i=0;i<arr.size();i++){

for(int j=i+1;j<arr.size();j++){

if(arr[i]+arr[j]== s){

vector<int>temp;

temp.push_back(min(arr[i],arr[j]));

temp.push_back(max(arr[i],arr[j]));

ans.push_back(temp);

}

}

}

sort(ans.begin(),ans.end());

return ans;

}

 

258 views
0 replies
1 upvote

Interview problems

Pair Sum

import java.io.*;

import java.util.* ;

 

public class Solution{

public static List<int[]> pairSum(int[] arr, int s) {

// Write your code here.

Arrays.sort(arr);

List<int[]> result = new ArrayList<>();

for(int i=0; i<arr.length; i++){

for(int j= i+1; j<arr.length; j++){

if(arr[i]+arr[j]== s){

int[] foundPair = new int[2];

foundPair[0]= arr[i];

foundPair[1] = arr[j];

result.add(foundPair);

}

}

}

return result;

}

}

 

362 views
0 replies
0 upvotes
Full screen
Console