Random Wits

Life is too short for a diary

Projects

$ latest projects
     ├── encrypted-files
├── binary-semaphore
├── AES
└── DES
view all

Random

$ random stuff
├── my bookshelf
    ├── resources
    └── quotes
    └── about me
say Hello

Back to Top


Tue 13 Nov 2018

Three Sum Problem

Tags: programming leetcode code

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.1

Brute force algorithm

It has problems like it doenst account for duplicate elements. Also it has complexity of @L O(n3) @L which is not optimal.

public static List<List<Integer>> threeSumAlgo1(int[] nums) {

        List<List<Integer>> result = new 
                                 ArrayList<List<Integer>>();

        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                for (int k = j + 1; k < nums.length; k++) {
                        if (nums[i] + nums[j] + nums[k] == 0 ){
                        List<Integer> temp = new ArrayList<>();
                        temp.add(nums[i]);
                        temp.add(nums[j]);
                        temp.add(nums[k]);
                        result.add(temp);
                    }
                }
            }
        }

        return result;
}	

More efficient solution

Using two pointer solution, we can acheive @L O(n2) @L time complexity.

public static List<List<Integer>> threeSumAlgo2(int[] nums) {

        List<List<Integer>> result = new 
                                  ArrayList<List<Integer>>();

        Arrays.sort(nums);

        for(int i = 0; i < nums.length - 2; i++) {
            //fix the value
            int a = nums[i];
            int start = i + 1;
            int end = nums.length - 1;

            // maintain unique triplets 
            if (i > 0 
                  && (nums[i] == nums[i - 1])) {
                continue;
            }

            while (start < end ) {

                int b = nums[start];
                int c = nums[end];

                int sum = a + b + c;

                // maintain unique triplets
                if (start > i + 1 
                          && (nums[start] == nums[start - 1])) {
                    start = start + 1;
                    continue;
                }

                if (sum == 0) {

                    List<Integer> tempResult = new ArrayList<>();
                    tempResult.add(a);
                    tempResult.add(b);
                    tempResult.add(c);
                    result.add(tempResult);

                    start = start + 1;
                    end = end - 1;
                } else if (sum > 0 )  {
                    end = end - 1;
                } else {
                    start = start + 1;
                }
            }
        }

        return result;
}

Footnotes


  1. Leetcode


comments powered by Disqus