I dont quite get the order i which the pair of arr is getting positioned, need help regarding that.
Problem of the day
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.
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.
1 <= N <= 10^3
-10^5 <= ARR[i] <= 10^5
-2 * 10^5 <= S <= 2 * 10^5
Time Limit: 1 sec
5 5
1 2 3 4 5
1 4
2 3
Here, 1 + 4 = 5
2 + 3 = 5
Hence the output will be, (1,4) , (2,3).
5 0
2 -3 3 3 -2
-3 3
-3 3
-2 2
As N is relatively small, an O(N^2) solution may pass.
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).
O(1).
Constant extra space is required.
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.
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;
}
}
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;
}
}
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;
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;
}
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;
}
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;
}
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
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;
}
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;
}
}