Given an integer array, return all the triplets that will sum up to the target number.

• Result should be a set and should not contain duplicate triplets.

Overview

1. Set the first number and consider it as the start number.
2. Set left pointer next to the start number and right pointer to the end.
3. Move left and right pointer accordingly until left index goes over the right index.
4. Add triplet if sum is equal to target.
5. Move start number to the left and repeat.

Flow Diagram

Time Complexity

Time complexity is O(n^2). Because we are iterating through the array once with a for loop. For each of the numbers we then iterate again with a while loop. Usually, if not always, a loop within a loop leads to O(n^2) time complexity.

Space Complexity

We are not using any extra space for this algorithm, which is great. Although, all numbers might end up being part of a triplet result, giving us a space complexity of O(n)

Java Source Code

public List<Integer[]> calculate(int[] array,int target) {
        Arrays.sort(array);
        final List<Integer[]> triplets = new ArrayList<>();

        for (var i=0;i<array.length-2;i++) {
            var leftIndex = i+1;
            var rightIndex = array.length-1;

            while(leftIndex < rightIndex) {
                var currentSum = array[i] + array[leftIndex] + array[rightIndex];

                if(currentSum==target) {
                    triplets.add(new Integer[]{array[i],array[leftIndex],array[rightIndex]});
                    leftIndex++;
                    rightIndex--;
                } else if(currentSum < target) {
                    leftIndex++;
                } else {
                    rightIndex--;
                }
            }
        }

Conclusion

All truth passes through three stages. First, it is ridiculed. Second, it is violently opposed. Third, it is accepted as being self-evident.

Arthur Schopenhauer