Three Sum Problem

 Given an array and a target. You need to find the triplet such that a[i] + a[j] + a[k] = target and 

a[i] != a[j] != a[k].
Note: Solution must contain unique triplets.

eg: Number of element in array is 7

array = [7, -6, 3, 8, -1, 8, -11]
target = 0

Solution: [-11, 3, 8] [-6, -1, 7] 

Time complexity of brut force solution is O(n^3). 

Optimisation 1: Using Hashmap

We can have some optimisation with hashmap. such that

a[k] = target - (a[i] + a[j]) we need to find all the pairs of a[i] and a[j] and time complexity is O(n^2) and

space complexity is O(m) + O(n)

Optimisation: Two Pointer Approach

a = [-1, -1, 1, 2, 2, 2, 2, 3, 3, 4, 4, 6] and target = 6. 

Here array is sorted.

a[i] = -1

a[j] = -1

a[k] = 6

when j is less than k and calculate new target  (tempTarget) 

int tempTarget = target - a[i];

target - a[i] = a[j] + a[k]

case 1: 6 - (-1)  = -1 + 6

            7 not equal 5

case 2: a[j] = 1

6 - (-1)  = 1 + 6

7 equal 7

sol1: [-1, 1, 6 ]

case 3 : a[j]=2 a[k] = 4 

6 - (-1)  = 2 + 4

7 not equal 6

case 4: a[j] = 2 same for next two values of a[j] if duplicates are present that needs to be ignored.

7 not equal 6

case 5: a[j] = 3

6 - (-1)  = 3 + 4

7 equal 7

sol2: [-1, 3, 4 ]

completed all pairs of a[j] and a[k] when a[i] = -1

if a[i] and a[k] duplicate elements are present that needs to be ignored.

case 6: a[i] = 1, a[j] = 2, a[j] = 6

Process continues

import java.util.Arrays;

/**
 *
 *
 * Brut force complexity is O(n^3)
 *
 * To optimize a[i] + a[j] + a[k] = target
 * a[k] = target - (a[i] + a[j])
 *
 * consider two pointer approach
 * Time complexity is O(n^2)  and space complexity is O(1)
 *
 */

public class ThreeSum {

    public static void main(String[] args) {
        int[] a = {7, -6, 3, 8, -1, 8, -11};
        int target = 0;

        twoPointer(a, target);

    }

    public static void twoPointer(int[] a, int target) {
        Arrays.sort(a);
        int n = a.length;
        for (int i = 0; i < n; i++) {
            if (i == 0 || (a[i] != a[i-1])) {
                int j = i+1;
                int k = n-1;
                int tempTarget = target - a[i];
                while(j < k) {
                    if (a[j] + a[k] == tempTarget) {
                        System.out.println("[ "+ a[i] + ", "+ a[j] + ", " + a[k] + "]");
                        // ignore duplicate
                        while(j < k && a[j] == a[j+1]) j++;
                        while(j < k && a[k] == a[k-1]) k--;
                        j++;
                        k--;
                    } else if (a[j] + a[k] < tempTarget) {
                        j++;
                    } else {
                        k--;
                    }
                }
            }
        }
    }
}