Triplets With A Given Sum In Java 8

Finding three numbers in an array that sum to a specific target value is a common problem in computer science, frequently encountered in coding challenges and real-world data processing. In this article, you will learn various approaches to efficiently find such triplets in Java 8.

Problem Statement

Given an array of integers, the task is to find all unique triplets in the array whose elements sum up to a specified target value. This problem tests algorithmic thinking, particularly in optimizing search operations within data structures. It's crucial to identify not just if such a triplet exists, but to list all unique combinations.

Example

Consider the array [12, 3, 1, 2, -6, 5, -8, 6] and a target sum of 0. A valid triplet is [-8, 2, 6], as -8 + 2 + 6 = 0. Another valid triplet is [-8, 3, 5], as -8 + 3 + 5 = 0. And [-6, 1, 5], as -6 + 1 + 5 = 0.

Background & Knowledge Prerequisites

To understand the solutions presented, a basic grasp of the following Java concepts is helpful:

• Arrays: Understanding how to declare, initialize, and iterate through arrays.
• Loops: for loops for iteration.
• Sorting Algorithms: Knowledge of how sorting affects array traversal and potential optimizations.
• Conditional Statements: if-else constructs for logic control.
• Lists/Collections: Using ArrayList to store results.

Use Cases or Case Studies

This problem has applications in various domains:

• Financial Analysis: Identifying three transactions or stock prices that sum to a target profit or loss.
• Game Development: In puzzle games, finding three items or resources that combine to meet a specific requirement.
• Data Mining: Searching for patterns in datasets where the sum of three attributes indicates a specific event or condition.
• Cryptography: Certain cryptographic algorithms or key generation processes might involve finding number combinations with specific sums.
• Optimization Problems: As a sub-problem in larger optimization tasks where a specific combination of three variables needs to meet a constraint.

Solution Approaches

We will explore two primary approaches: a straightforward brute-force method and a more optimized method using sorting and the two-pointer technique.

Approach 1: Brute Force

This method involves checking every possible combination of three distinct numbers in the array.

• Summary: Uses three nested loops to iterate through all unique combinations of three elements and checks if their sum equals the target.
• Complexity:
• Time Complexity: O(n^3) due to three nested loops.
• Space Complexity: O(1) (excluding space for storing results).

// Triplets with Given Sum - Brute Force
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

// Main class containing the entry point of the program
public class Main {
    public static void main(String[] args) {
        int[] arr = {12, 3, 1, 2, -6, 5, -8, 6};
        int targetSum = 0;
        List<List<Integer>> result = findTripletsBruteForce(arr, targetSum);

        System.out.println("Triplets (Brute Force) for sum " + targetSum + ":");
        result.forEach(System.out::println);

        int[] arr2 = {1, 2, 3, 4, 5, 6};
        targetSum = 9;
        List<List<Integer>> result2 = findTripletsBruteForce(arr2, targetSum);
        System.out.println("\\nTriplets (Brute Force) for sum " + targetSum + ":");
        result2.forEach(System.out::println);
    }

    public static List<List<Integer>> findTripletsBruteForce(int[] arr, int targetSum) {
        List<List<Integer>> triplets = new ArrayList<>();
        int n = arr.length;

        // Sort the array to handle duplicates later (optional for correctness but good for unique triplets)
        // Although sorting itself is O(N log N), the O(N^3) dominates.
        Arrays.sort(arr); 

        // Step 1: Iterate through the first element
        for (int i = 0; i < n - 2; i++) {
            // Skip duplicate elements for the first number
            if (i > 0 && arr[i] == arr[i - 1]) {
                continue;
            }

            // Step 2: Iterate through the second element
            for (int j = i + 1; j < n - 1; j++) {
                // Skip duplicate elements for the second number
                if (j > i + 1 && arr[j] == arr[j - 1]) {
                    continue;
                }

                // Step 3: Iterate through the third element
                for (int k = j + 1; k < n; k++) {
                    // Skip duplicate elements for the third number
                    if (k > j + 1 && arr[k] == arr[k - 1]) {
                        continue;
                    }

                    // Step 4: Check if the sum equals the target
                    if (arr[i] + arr[j] + arr[k] == targetSum) {
                        triplets.add(Arrays.asList(arr[i], arr[j], arr[k]));
                    }
                }
            }
        }
        return triplets;
    }
}

Run

• Sample Output:

  Triplets (Brute Force) for sum 0:
  [-8, 2, 6]
  [-8, 3, 5]
  [-6, 1, 5]
  
  Triplets (Brute Force) for sum 9:
  [1, 2, 6]
  [1, 3, 5]
  [2, 3, 4]

• Stepwise Explanation:

1. The findTripletsBruteForce method takes an integer array arr and a targetSum.
2. An ArrayList named triplets is initialized to store the results.
3. The array arr is sorted. This is not strictly necessary for correctness in brute force but helps in ensuring uniqueness of triplets in the output and simplifying duplicate handling logic.
4. The outer loop (i) iterates from the first element up to n - 2 (to ensure there are at least two elements remaining after arr[i]).
5. The first if condition (i > 0 && arr[i] == arr[i - 1]) skips duplicate arr[i] values to avoid generating duplicate triplets.
6. The second loop (j) iterates from i + 1 up to n - 1.
7. The second if condition (j > i + 1 && arr[j] == arr[j - 1]) skips duplicate arr[j] values.
8. The innermost loop (k) iterates from j + 1 up to n.
9. The third if condition (k > j + 1 && arr[k] == arr[k - 1]) skips duplicate arr[k] values.
10. Inside the innermost loop, the sum of arr[i], arr[j], and arr[k] is checked against targetSum.
11. If the sum matches, a new List containing these three elements is added to the triplets list.
12. Finally, the triplets list is returned.

Approach 2: Using Sorting and Two Pointers

This approach significantly improves performance by first sorting the array and then using a two-pointer technique.

• Summary: Sort the array. Iterate through each element. For each element, use two pointers (one at the start and one at the end of the remaining sub-array) to find two numbers that sum to the required remaining value.
• Complexity:
• Time Complexity: O(n^2) (O(n log n) for sorting + O(n^2) for two-pointer traversals).
• Space Complexity: O(1) (excluding space for storing results).

// Triplets with Given Sum - Sorted Two Pointers
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

// Main class containing the entry point of the program
public class Main {
    public static void main(String[] args) {
        int[] arr = {12, 3, 1, 2, -6, 5, -8, 6};
        int targetSum = 0;
        List<List<Integer>> result = findTripletsTwoPointers(arr, targetSum);

        System.out.println("Triplets (Two Pointers) for sum " + targetSum + ":");
        result.forEach(System.out::println);

        int[] arr2 = {1, 2, 3, 4, 5, 6};
        targetSum = 9;
        List<List<Integer>> result2 = findTripletsTwoPointers(arr2, targetSum);
        System.out.println("\\nTriplets (Two Pointers) for sum " + targetSum + ":");
        result2.forEach(System.out::println);
    }

    public static List<List<Integer>> findTripletsTwoPointers(int[] arr, int targetSum) {
        List<List<Integer>> triplets = new ArrayList<>();
        Arrays.sort(arr); // Step 1: Sort the array
        int n = arr.length;

        // Step 2: Iterate through the array, fixing the first element
        for (int i = 0; i < n - 2; i++) {
            // Skip duplicate elements for the first number
            if (i > 0 && arr[i] == arr[i - 1]) {
                continue;
            }

            // Step 3: Initialize two pointers for the remaining sub-array
            int left = i + 1;
            int right = n - 1;

            // Step 4: Use two pointers to find the remaining two numbers
            while (left < right) {
                int currentSum = arr[i] + arr[left] + arr[right];

                if (currentSum == targetSum) {
                    triplets.add(Arrays.asList(arr[i], arr[left], arr[right]));
                    left++; // Move left pointer
                    right--; // Move right pointer

                    // Skip duplicate elements for the second number
                    while (left < right && arr[left] == arr[left - 1]) {
                        left++;
                    }
                    // Skip duplicate elements for the third number
                    while (left < right && arr[right] == arr[right + 1]) {
                        right--;
                    }
                } else if (currentSum < targetSum) {
                    left++; // Sum is too small, increment left pointer
                } else { // currentSum > targetSum
                    right--; // Sum is too large, decrement right pointer
                }
            }
        }
        return triplets;
    }
}

Run

• Sample Output:

  Triplets (Two Pointers) for sum 0:
  [-8, 2, 6]
  [-8, 3, 5]
  [-6, 1, 5]
  
  Triplets (Two Pointers) for sum 9:
  [1, 2, 6]
  [1, 3, 5]
  [2, 3, 4]

• Stepwise Explanation:

1. The findTripletsTwoPointers method starts by sorting the input array arr using Arrays.sort(). This is crucial for the two-pointer technique to work.
2. It then iterates with a for loop, fixing arr[i] as the first element of a potential triplet. The loop runs from 0 to n - 2.
3. A condition if (i > 0 && arr[i] == arr[i - 1]) ensures that duplicate arr[i] values are skipped, preventing duplicate triplets in the output.
4. Inside the for loop, two pointers, left and right, are initialized. left points to i + 1 (the element immediately after arr[i]), and right points to n - 1 (the last element of the array).
5. A while loop continues as long as left is less than right.
6. currentSum is calculated using arr[i], arr[left], and arr[right].
7. If currentSum == targetSum:

• The triplet (arr[i], arr[left], arr[right]) is a valid solution and is added to the triplets list.
• Both left and right pointers are moved inward (left++, right--).
• Additional while loops are used to skip any duplicate elements at left and right to ensure only unique triplets are collected.

1. If currentSum < targetSum: The sum is too small. To increase the sum, the left pointer is incremented (left++) to consider a larger number.
2. If currentSum > targetSum: The sum is too large. To decrease the sum, the right pointer is decremented (right--) to consider a smaller number.
3. The while loop continues until left crosses right, at which point all possible combinations for the current arr[i] have been explored.
4. After the outer for loop completes, the triplets list containing all unique triplets is returned.

Conclusion

Finding triplets with a given sum is a foundational problem in algorithms, demonstrating how different approaches can lead to vastly different performance characteristics. While the brute-force method is easy to understand, its O(n^3) time complexity makes it impractical for large datasets. The optimized approach using sorting and the two-pointer technique reduces the complexity to O(n^2), offering a much more efficient solution suitable for most practical scenarios. Understanding the trade-offs between these methods is key to selecting the right algorithm for a given problem constraint.

Summary

• Problem: Find all unique sets of three numbers in an array that sum to a target value.
• Brute Force (O(n^3)): Involves three nested loops, checking every combination. Simple to implement but inefficient for large inputs. Requires careful handling of duplicates if unique triplets are needed.
• Sorting + Two Pointers (O(n^2)):
• First, sort the array (O(n log n)).
• Iterate through each element arr[i] as the first number.
• Use two pointers (left and right) in the remaining part of the array to find the other two numbers (O(n) for each arr[i]).
• Efficiently handles duplicate elements to ensure unique triplet results.
• Key Insight: Sorting the array enables the efficient two-pointer technique to quickly converge on the target sum or adjust pointers based on whether the current sum is too high or too low.