CODEWITHSUNDEEP
pythonalgorithmnested-loops
Darkhan
Darkhan

Reputation: 3225

How to speed up nested for loop in python?

My leetcode algorithm for 3sum problem can't make through the 311th test case - the time limit exceeded (the list length is 3000)

The nested loop seems to be the most inefficient part of my algorithm. Is there a way to make it more efficient by using different approach?

def threeSum(self, nums: List[int]) -> List[List[int]]:
    result = []

    for i, e in enumerate(nums):
        for i2, e2 in enumerate(nums[i+1:]):
            e3 = -1 * (e + e2)
            l = [e,e2,e3]
            l.sort()
            if l in result:
                continue

            nums[i] = ''
            nums[i2+i+1] = ''
            if e3 in nums:
                result.append(l)
            nums[i] = e
            nums[i2+i+1] = e2

    return result

I also tried removing l.sort(), but time limit is still exceeded:

nums.sort()
    for i, e in enumerate(nums):
        for i2, e2 in enumerate(nums[i+1:]):
            e3 = -1 * (e + e2)
            l = []
            if e3 > e2:
                l = [e,e2,e3]
            elif e3 < e:
                l = [e3,e,e2]
            else:
                l = [e,e3,e2]
            if l in result:
                continue

            nums[i] = ''
            nums[i2+i+1] = ''
            if e3 in nums:
                result.append(l)
            nums[i] = e
            nums[i2+i+1] = e2

    return result

Upvotes: 1

Views: 229

Answers (1)

Meny Issakov
Meny Issakov

Reputation: 1421

First of all, one ground rule is to never change the list you are iterating over.

Second thing, you need to change the way you think about it. Think how you can reduce the existing problem into a multiple 2sum problems, and solve each and every one of the individually.

Upvotes: 1

Related Questions