K-pairs with smallest sum in two arrays in Java

May 2, 2023

K-pairs with smallest sum in two arrays

In this page we will look into a coding question where we will learn how to find the K-pairs with smallest sum in two arrays in Java such that one element of a pair belongs to arr1[ ] and another element belongs to arr2[ ] . There might be different approach to solve this question, one you will find here. If your approach is bit different post it onto the comment section.
K-pairs with smallest sum in two arrays

K-pairs with smallest sum in two arrays in Java

The problem of finding k pairs with the smallest sum in two arrays, A and B, involves selecting k pairs of numbers, one from each array, such that the sum of each pair (ai, bi) is minimized. The constraint is that each pair must consist of one element from A and one element from B.
 
For instance, given arrays A = [1, 3, 11] and B = [2, 4, 8], with k = 4, the smallest sum pairs would be (1, 2), (3, 2), (1, 4), and (3, 4), with sums of 3, 5, 5, and 7, respectively.

On this page we will discuss two different methods for this-

  1. Brute Force Approach
  2. Min Heap Approach
K-pairs with smallest sum in two arrays in Java
  1. Brute Force approach: The brute force method for finding k pairs with the smallest sum in two arrays involves iterating over all possible pairs of indices from both arrays and calculating the sum of each pair. The steps for the brute force method are as follows:

Algorithm:

  1. Initialize a result vector to hold k pairs with the smallest sum.
  2. Iterate over all pairs of indices (i, j) such that i is between 0 and the size of the first array minus 1, and j is between 0 and the size of the second array minus 1.
  3. Calculate the sum of the ith element in the first array (A[i]) and the jth element in the second array (B[j]).
  4. If the result vector is not yet full (i.e., its size is less than k), add the current pair (i, j) and its sum to the result vector.
  5. If the result vector is full (i.e., its size is equal to k), and the current sum is smaller than the sum of the largest pair in the result vector:
    i. Remove the largest pair from the result vector.
    ii. Add the current pair (i, j) and its sum to the result vector.
  6. Repeat steps 3-5 for all pairs of indices.
  7. After processing all pairs, the result vector will contain the k pairs with the smallest sum.
  8. Return the result vector.
DSA desktop gif
DSA mobile gif

Introduction  to Arrays

Introduction to 2-D Arrays

Array Rotation

Reverse an Array or String

Sort the array in Waveform

Java Code for Brute Force approach

Run 
import java.util.*;

class Pair< U, V > {
    public final U first;
    public final V second;

    public Pair(U first, V second) {
        this.first = first;
        this.second = second;
    }
}


public class Main {

    public static List< Pair< Integer, Integer>> kSmallestPairs(List< Integer> A, List< Integer> B, int k) {
        List< Pair< Integer, Integer>> result = new ArrayList<>(); // to store k pairs with smallest sum
        int n1 = A.size();
        int n2 = B.size();

        // Nested loop to iterate over all pairs of indices
        for (int i = 0; i < n1; ++i) {
            for (int j = 0; j < n2; ++j) {
                int sum = A.get(i) + B.get(j); // calculate the sum

                if (result.size() < k) {
                    result.add(new Pair<>(A.get(i), B.get(j)));
                } else if (sum < result.get(result.size() - 1).first + result.get(result.size() - 1).second) {
                    result.remove(result.size() - 1); // remove the largest pair
                    result.add(new Pair<>(A.get(i), B.get(j)));
                }

                // Sort the result list in ascending order based on the sum
                Collections.sort(result, new Comparator< Pair< Integer, Integer>>() {
                    @Override
                    public int compare(Pair< Integer, Integer> a, Pair< Integer, Integer> b) {
                        return a.first + a.second - b.first - b.second;
                    }
                });
            }
        }

        return result;
    }

    public static void main(String[] args) {
        List< Integer> A = Arrays.asList(1, 3, 11);
        List< Integer> B = Arrays.asList(2, 4, 8);
        int k = 4;

        List< Pair< Integer, Integer>> result = kSmallestPairs(A, B, k);

        System.out.println("K pairs with smallest sum: ");
        for (Pair< Integer, Integer> pair : result) {
            System.out.print("(" + pair.first + ", " + pair.second + ") ");
        }
    }
}

Output

K pairs with smallest sum: 
(1, 2) (1, 4) (3, 2) (3, 4)
  1. Min Heap Method:This algorithm outlines a more optimized approach using a min heap to find k pairs with the smallest sum in two arrays. The steps for this
    approach are as follows:

Algorithm:

  1. Create a min heap of pairs where each pair consists of an element from the first array and an element from the second array, along with their sum.
  2. Initialize heap size to 0.
  3. For each element in the second array: a. Create a pair with the first element from the first array and the current element from the second array. b. Add this pair to the min heap and increment heap size.
  4. While k is greater than 0: a. Extract the minimum element from the heap. b. Print it as one of the k pairs. c. Decrement k. d. If the extracted pair was from the first array: i. Create a new pair with the next element from the first array and the same element from the second array. ii. Add this new pair to the heap.
  5. Repeat steps 4a-4d until k pairs have been extracted or the heap becomes empty.

Java Code for Min Heap approach

Run 
import java.util.*;

class Main {
    static class Pair< T, U> {
        private T first;
        private U second;

        public Pair(T first, U second) {
            this.first = first;
            this.second = second;
        }

        public T getKey() {
            return first;
        }

        public U getValue() {
            return second;
        }
    }

    static class PairComparator implements Comparator< Pair< Integer, Integer>> {
        public int compare(Pair< Integer, Integer> p1, Pair< Integer, Integer> p2) {
            return (p1.getKey() + p1.getValue()) - (p2.getKey() + p2.getValue());
        }
    }

    public static List< Pair< Integer, Integer>> kSmallestPairs(List< Integer> nums1, List< Integer> nums2, int k) {
        int n1 = nums1.size();
        int n2 = nums2.size();
        List< Pair< Integer, Integer>> result = new ArrayList<>();

        // Create a min heap with custom comparator
        PriorityQueue< Pair< Integer, Integer>> minHeap = new PriorityQueue<>(new PairComparator());

        for (int i = 0; i < n1 && i < k; i++) {
            minHeap.offer(new Pair<>(nums1.get(i), nums2.get(0)));
        }
        while (k > 0 && !minHeap.isEmpty()) {
            Pair< Integer, Integer> currPair = minHeap.poll();
            result.add(currPair);
            k--;

            if (currPair.getValue() < n2 - 1) {
                minHeap.offer(new Pair<>(currPair.getKey(), nums2.get(currPair.getValue() + 1)));
            }
        }

        return result;
    }

    public static void main(String[] args) {
        List< Integer> nums1 = Arrays.asList(1, 3, 11);
        List< Integer> nums2 = Arrays.asList(2, 4, 8);
        int k = 4;

        List< Pair< Integer, Integer>> result = kSmallestPairs(nums1, nums2, k);

        System.out.print("K pairs with smallest sum: ");
        for (Pair< Integer, Integer> pair : result) {
            System.out.print("(" + pair.getKey() + ", " + pair.getValue() + ") ");
        }
    }
}

Output

K pairs with smallest sum: (1, 2) (3, 2) (11, 2)

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get Prime

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

Get Prime
Course List
Course List

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout
Checkout

Introduction to Trees

Binary Trees

Binary Search Trees

Traversals

  • Traversal in Trees
  • Tree Traversals: Breadth-First Search (BFS) : C | C++ | Java
  • Tree Traversals: Depth First Search (DFS) : C | C++ | Java
  • Construct a Binary Tree from Postorder and Inorder

B – Trees

AVL Trees

  • AVL Trees
    • AVL Trees: Introduction
    • AVL Tree Insertion : C | C++ | Java
    • AVL Tree Deletion : C | C++ | Java
    • Insertion in a Binary Tree (Level Order) – C | C++ | Java
    • Searching in Binary Tree – C | C++ | Java
    • Searching in a Binary Search Tree – C | C++ | Java

Complete Programs for Trees

  • Depth First Traversals – C | C++ | Java
  • Level Order Traversal – C | C++ | Java
  • Construct Tree from given Inorder and Preorder traversals – C | C++ | Java
  • Construct Tree from given Postorder and Inorder traversals – C | C++ | Java
  • Construct Tree from given Postorder and Preorder traversal – C | C++ | Java
  • Find size of the Binary tree – C | C++ | Java
  • Find the height of binary tree – C | C++ | Java
  • Find maximum in binary tree – C | C++ | Java
  • Check whether two tree are identical- C| C++| Java
  • Spiral Order traversal of Tree- C | C++| Java
  • Level Order Traversal Line by Line – C | C++| Java
  • Hand shaking lemma and some Impotant Tree Properties.
  • Check If binary tree if Foldable or not.- C| C++| Java
  • check whether tree is Symmetric – C| C++| Java.
  • Check for Children-Sum in Binary Tree- C|C++| Java
  • Sum of all nodes in Binary Tree- C | C++ | Java
  • Lowest Common Ancestor in Binary Tree- C | C++ | Java

Introduction to Trees

Binary Trees

Binary Search Trees

Traversals

  • Traversal in Trees
  • Tree Traversals: Breadth-First Search (BFS) : C | C++ | Java
  • Tree Traversals: Depth First Search (DFS) : C | C++ | Java
  • Construct a Binary Tree from Postorder and Inorder

B – Trees

AVL Trees

  • AVL Trees
    • AVL Trees: Introduction
    • AVL Tree Insertion :  C | C++ | Java
    • AVL Tree Deletion : C | C++ | Java
    • Insertion in a Binary Tree (Level Order) – C | C++ | Java
    • Searching in Binary Tree – C | C++ | Java
    • Searching in a Binary Search Tree – C | C++ | Java

Complete Programs for Trees

  • Depth First Traversals – C | C++ | Java
  • Level Order Traversal – C | C++ | Java
  • Construct Tree from given Inorder and Preorder traversals – C | C++ | Java
  • Construct Tree from given Postorder and Inorder traversals – C | C++ | Java
  • Construct Tree from given Postorder and Preorder traversal – C | C++ | Java
  • Find size of the Binary tree – C | C++ | Java
  • Find the height of binary tree – C | C++ | Java
  • Find maximum in binary tree – C | C++ | Java
  • Check whether two tree are identical- C| C++| Java
  • Spiral Order traversal of Tree- C | C++| Java
  • Level Order Traversal LIne by Line – C | C++| Java
  • Hand shaking lemma and some Impotant Tree Properties.
  • Check If binary tree if Foldable or not.- C| C++| Java
  • check whether tree is Symmetric  C| C++| Java.
  • Check for Children-Sum in Binary Tree- C|C++| Java
  • Sum of all nodes in Binary Tree- C | C++ | Java
  • Lowest Common Ancestor in Binary Tree. C | C++ | Java

2 comments on “K-pairs with smallest sum in two arrays in Java”


  • Harshith M P 1SG20IS036

    import java.util.*;

    public class Main {

    public static void kSmallestPair(int[] A, int[] B,
    int K)
    {
    int n = A.length;
    // Min heap which contains tuple of the format
    // (sum, (i, j)) i and j are the indices
    // of the elements from array A
    // and array B which make up the sum.
    PriorityQueue pq
    = new PriorityQueue((a, b) -> a[0] – b[0]);

    // my_set is used to store the indices of
    // the pair(i, j) we use my_set to make sure
    // the indices does not repeat inside min heap.
    Set mySet = new HashSet();

    // initialize the heap with the minimum sum
    // combination i.e. (A[0] + B[0])
    // and also push indices (0,0) along
    // with sum.
    pq.offer(new int[] { A[0] + B[0], 0, 0 });
    mySet.add(“0,0”);

    // iterate upto K
    int count = 0;
    while (count < K && !pq.isEmpty()) {
    // array format (sum, i, j).
    int[] temp = pq.poll();
    int i = temp[1], j = temp[2];
    System.out.println(
    "(" + A[i] + ", " + B[j]
    + ")"); // Extracting pair with least sum
    // such that one element is from
    // arr1 and another is from arr2

    // check if i+1 is in the range of our first
    // array A
    boolean flag = false;
    if (i + 1 < n) {
    int sum = A[i + 1] + B[j];
    // insert (A[i + 1] + B[j], i + 1, j)
    // into min heap.
    String key = (i + 1) + "," + j;

    // insert only if the pair (i + 1, j) is
    // not already present inside the set i.e.
    // no repeating pair should be present
    // inside the heap.
    if (!mySet.contains(key)) {
    pq.offer(new int[] { sum, i + 1, j });
    mySet.add(key);
    flag = true;
    }
    }

    // check if j+1 is in the range of our second
    // array B
    if (j + 1 < B.length) {
    // insert (A[i] + B[j + 1], i, j + 1)
    // into min heap.
    int sum = A[i] + B[j + 1];
    String key = i + "," + (j + 1);

    // insert only if the pair (i, j + 1)
    // is not present inside the heap.
    if (!mySet.contains(key)) {
    pq.offer(new int[] { sum, i, j + 1 });
    mySet.add(key);
    flag = true;
    }
    }
    if (!flag) {
    break;
    }
    count++;
    }
    }

    public static void main(String[] args)
    {
    int[] A = { 1 };
    int[] B = { 2, 4, 5, 9 };
    int K = 8;
    kSmallestPair(A, B, K);
    }
    }