3Sum problem - Leet code - Time limit exceeded

Question

I am trying to solve the 3Sum problem on Leetcode (https://leetcode.com/problems/3sum/). the logic I am using is:

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        k = list()
        l = len(nums)
        s= set()
        for idx,val in enumerate(nums):
            for j in range(idx+1,l):
                val2 = nums[j]
                temp = 0 - (val + val2)
                if temp in nums[j+1:]:
                    print(s)
                    if val not in k or val2 not in k or temp not in k:
                        k.append([val,val2,temp])
                        s.update([val,val2,temp])
        return k

In order to not add duplicate lists (lists with same elements) in the result, I am pushing all unique values to a set. Then checking if the set doesn't contain at least one of the three elements before adding to the list. I think this should prevent me from adding duplicate lists. Please correct me if I am wrong.

But the output result I see is :

Your input
    [-1,0,1,2,-1,-4]
stdout
    set()
    {0, 1, -1}
    {0, 1, 2, -1}
Output
    [[-1,0,1],[-1,2,-1],[0,1,-1]]
Expected
    [[-1,-1,2],[-1,0,1]]

I don't understand why [0,1,-1] is getting added to my result even though the set s contains all three elements 0,1,-1. Where am I going wrong?

EDIT

Using the answers posted below, the final logic I built is:

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        k = list()
        l = len(nums)
        for idx,val in enumerate(nums):
            for j in range(idx+1,l):
                val2 = nums[j]
                temp = 0 - (val + val2)
                if temp in nums[j+1:]:
                    item = sorted([val,val2,temp])
                    if item not in k:
                        k.append(item)
        return k

However, when I run this, time limit is exceeding for a large input. I get the error message Time Limit Exceeded. 311/313 testcases passed and 2 of them failed.

Is there a way to improvise the runtime for this logic?

Answer 1

Sort your list, so that all solution lists will be in order. Then add only when the new list is not in the solution set -- your current test is useless, as it checks scalars against lists, which will always result in "I need this solution".

nums = [-1,0,1,2,-1,-4]
nums.sort()
print(nums)
k = list()
l = len(nums)
s= set()
old_val2 = None
for idx, val in enumerate(nums):
    for j in range(idx+1,l):
        val2 = nums[j] 
        temp = 0 - (val + val2)
        if temp in nums[j+1:]:
            print(s)
            # if val not in k or val2 not in k or temp not in k:
            if [val, val2, temp] not in k:
                k.append([val,val2,temp])
                s.update([val,val2,temp])
print(k)

Output:

[-4, -1, -1, 0, 1, 2]
set()
{2, -1}
{0, 1, 2, -1}
[[-1, -1, 2], [-1, 0, 1]]

Answer 2

Take a look at this line of your code

if val not in k or val2 not in k or temp not in k:

Here k is lists of lists and val,val2,temp are int. So this is definitely evaluate to True and you always append to the list.

Also you must first sort the lists before adding to the k, so that [-1,0,1] and [0,1,-1] are identified as same.

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        k = list()
        l = len(nums)
        s= set()
        for idx,val in enumerate(nums):
            for j in range(idx+1,l):
                val2 = nums[j]
                temp = 0 - (val + val2)
                if temp in nums[j+1:]:
                    print(s)
                    res = sorted([val,val2,temp])
                    if res not in k:
                        k.append(res)
                        s.update(res)
        return k

Result is:

set()
{0, 1, -1}
{0, 1, 2, -1}
[[-1, 0, 1], [-1, 2, -1]]