Find Pairs in Array with Given Sum in Java

April 27, 2023

Pairs in Array with Given Sum in Java

On this page, we will look into a coding question where we will learn how to Find Pairs in Array with Given Sum in Java Programing Language. There might be different approaches to solve this question, one you will find here. If your approach is a bit different post it in the comment section.

Find Pairs in Array with given Sum in Java

To find pairs in an array with a given sum in Java, we can use two methods

Brute Force (Time complexity: O(n^2) )
Using Sorting (Time complexity: O(n log n) )

Both methods have their own pros and cons. The brute force method can be slow for large arrays but it is very simple and easy to implement . The sorting method is faster for large arrays, but requires extra space for sorting and modifying the original array.

Method 1 : Brute Force Method

In this approach, we check every pair of elements in the array to see if their sum is equal to the given target sum.
This method has a time complexity of O(n^2) as we have to compare each element with every other element

Java code for brute force

Run

// Java implementation to
// print pairs with given sum.

public class Main
{
    static void pairssum(int a[], int size, int sum)
    {
        System.out.print("The pairs present are : ");
        //traverse through the array to find pairs
        for (int i = 0; i < size; i++)
            for (int j = i + 1; j < size; j++)
                if (a[i] + a[j] == sum)
                    System.out.print("(" + a[i] + ", " + a[j]+ ") ");
    }

    // Driver Code
    public static void main(String[] arg)
    {
        int a[] = { 5, 2, 3, 4, 1, 6, 7 };
        int size = a.length;
        int sum = 7;
        pairssum(a, size, sum);
    }
}

OUTPUT:
The pairs present are : (5, 2) (3, 4) (1, 6)

Introduction to Arrays

Introduction to 2-D Arrays

Array Rotation

Reverse an Array or String

Sort the array in Waveform

Method 2 : Sorting Method

The array is first sorted in ascending order in the sorting technique.
Then, we employ two pointers, one of which points to the first element and the other to the last element.
These two pointers values are added, and we then check to see if the result equals the specified sum.
The left pointer is increased if the value is less than the total, and the right pointer is decreased if the value is higher.
This method has a time complexity of O(n log n) due to the sorting algorithm used.

Java code for sorting method

Run

import java.util.*;

public class Main
{
    public static void findPairs(int arr[], int n, int targetSum)
    {
        Arrays.sort(arr);
        int left = 0, right = n - 1;
        System.out.print("The pairs present are : ");
        while (left < right)
        {
            int currSum = arr[left] + arr[right];
            if(currSum == targetSum)
	        {
	            System.out.print("(" + arr[left] + ", "+ arr[right] + ") ");
	            left++;
	            right--;
	        }
            else if (currSum < targetSum)
	        {
	            left++;
	        }
            else
	        {
	            right--;
	        }
        }
    }
    
    public static void main(String args[])
    {
        int arr[] = { 5, 8, 1, 4, 6, 3, 2, 7 };
        int n = arr.length;
        int targetSum = 10;
        findPairs (arr, n, targetSum);
    }
}

OUTPUT:
The pairs present are : (2, 8) (3, 7) (4, 6)

Prime Course Trailer

Related Banners

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Checkout list of all the video courses in PrepInsta Prime Subscription

Arrays

Introduction to Arrays – C | C++ | Java
Introduction to 2-D Arrays – C | C++ | Java
Sorting of Array – C | C++ | Java
Array Rotation – C | C++ | Java
Reverse an array or string- C | C++ | Java
Find pairs in array with given sum – C | C++ | Java
Sort the array in Waveform – C | C++ | Java
Majority Element in Array – C | C++ | Java
Boyer-Moore’s Voting Algorithm – C | C++ | Java
K-pairs with smallest sum in 2 arrays – C | C++ | Java
Largest Sum Contigous SubArray – C | C++ | Java
Maximum Average Sub-array of K length – C | C++ | Java
Size of sub-array with max sum – C | C++ | Java
Sub-array with given sum – C | C++ | Java
Triplet that sum to a given value – C | C++ | Java
Segregate 0’s and 1’s in array – C | C++ | Java
Segregate 0’s 1’s and 2’s in array – C | C++ | Java
Sort elements in array by frequency – C | C++ | Java
Finding pythagorean triplets in an array – C | C++ | Java
Reorder array using given indexes – C | C++ | Java
Merging two sorted arrays – C | C++ | Java
Minimum number of Merge Operations to make an Array Palindrome – C | C++ | Java
Find Zeros to be Flipped so that number of Consecutive 1’s is maximized – C | C++ | Java