Leetcode - 3Sum

Leetcode : 3Sum

Description

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.
Notice that the solution set must not contain duplicate triplets.

Example 1

Input

nums = [-1,0,1,2,-1,-4]

Output

[[-1,-1,2],[-1,0,1]]

Example 2

Input

nums = []

Output

[]

Example 3

Input

nums = [0]

Output

[]

Approach

Brute force might be a solution to get the three sums which equal zero. However, brute force is not an efficient algorithm as size of array increases O(N^2). Hence, two pointer algorithm is implemented here to ensure O(N) time complexity.

Solutions

Solution I (Python)

class Solution(object):
    def threeSum(self, nums):
        nums.sort()

        result = []

        for i in range(len(nums) - 2):

            if i > 0 and nums[i] == nums[i-1]:
                continue

            left = i + 1
            right = len(nums) - 1

            while left < right:
                total = nums[i] + nums[left] + nums[right]

                if total < 0: 
                    left = left + 1
                elif total > 0:
                    right = right - 1
                else:
                    result.append([nums[i], nums[left], nums[right]])

                    while left < right and nums[left] == nums[left+1]:
                        left = left + 1
                    while left < right and nums[right] == nums[right-1]:
                        right = right - 1
                
                    left = left + 1
                    right = right - 1
        
        return result

Result

Runtime: 664 ms
Memory Usage: 16 MB
Runtime Beats 70.73% of Python Submission

Solution II (JavaScript)

var threeSum = function(nums) {
    nums = nums.sort((a, b) => a - b);
    let result = [];
    let target = 0 
    let low, high, sum; 
    
    if(nums.length < 3) return result; 
    
    for(let i = 0; i < nums.length - 2; i++) {
        if(i > 0 && nums[i] === nums[i-1]) continue;
        
        low = i + 1;
        high = nums.length - 1; 
        
        while(low < high) {
            sum = nums[i] + nums[low] + nums[high];
            
            if(sum === target) {
                result.push([nums[i], nums[low], nums[high]]);
                while(low < high && nums[low] === nums[low + 1]) low++;
                while(low < high && nums[high] === nums[high - 1]) high--; 
                low++;
                high--;
            } else if(sum < target) {
                low++;
            } else {
                high--; 
            }
        }
    }
    return result; 
};

Result

Runtime: 160 ms
Memory Usage: 46.9 MB
Runtime Beats 55.27% of JavaScript Submission