3sum Closest Leetcode Solution – Leetcode Python

LeetCode has a Medium coding Problem in Its’ Algorithm Section “3sum Closest Leetcode Solution”. Today We are going to solve this problem. LeetCode Link of the Problem is HERE

Question

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

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]]

Input: nums = []
Output: []

Input: nums = [0]
Output: []

Constraints:

• 0 <= nums.length <= 3000
• -105 <= nums[i] <= 105

Coding 3sum Closest Leetcode Solution

The Skeleton Code given by leetcode is

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        

Firstly, Sort the given array of integers. Create another variable of the set. Creating a set means that, we don’t allow any duplicates.

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """        
        s = sorted(nums)        
        output = set()
        

Secondly, run a loop starting from 0 to the end of the array. Create a target variable that is equal to the negative of the Value.

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """        
        s = sorted(nums)        
        output = set()
        for k in range(len(s)):
            target = -s[k]

Thirdly, create two variables i and j. where i equals the second element of the list and j equal to the last element of the set. Check for two values that are added and been equal to the target value thus that the total sum will be equal to zero. If the sum of two values is less than the target then increment the i which will go the third element. If the sum is greater than the Target then decrement the j value which will come to the second last element.

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """        
        s = sorted(nums)        
        output = set()
        for k in range(len(s)):
            target = -s[k]
            i,j = k+1, len(s)-1
            while i < j:
                sum_two = s[i] + s[j]
                if sum_two < target:
                    i += 1
                elif sum_two > target:
                    j -= 1

Finally, check for values that are added and give the answer zero. If such values exist then append them into the output set. increment the i and decrement the j. Finally when the loop ends return the output .

Complete Solution:

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """        
        s = sorted(nums)        
        output = set()
        for k in range(len(s)):
            target = -s[k]
            i,j = k+1, len(s)-1
            while i < j:
                sum_two = s[i] + s[j]
                if sum_two < target:
                    i += 1
                elif sum_two > target:
                    j -= 1
                else:
                    output.add((s[k],s[i],s[j]))
                    i += 1
                    j -= 1
        return output