How to speed up nested for loop in python?

Question

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

How about sorting one time at the beginning of the algorithm, then running your loops? — ggorlen
– ggorlen, Commented Mar 22, 2020 at 5:57
I would sort the list in advance and not on every step. That way you can also have early stop — Tom Ron
– Tom Ron, Commented Mar 22, 2020 at 5:58
@ggorlen thank you, but the e3 can be smaller or bigger than e and e2 even after sorting in advance, and the len is only 3. And I've just tried sorting in advance and removed the l.sort() - it took more time and the answer is incorrect — Darkhan
– Darkhan, Commented Mar 22, 2020 at 6:21

Meny Issakov · Accepted Answer · 2020-03-22 07:24:54Z

1

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.

edited Mar 22, 2020 at 7:24

answered Mar 22, 2020 at 7:16

Meny Issakov

1,4412 gold badges15 silver badges31 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Darkhan Over a year ago

how am I changing the list? what do you mean by 2sum?

Meny Issakov Over a year ago

You are updating the same list you're iterating by setting nums[i] during the iteration. create a new list and append to it. 2sum is the same problem as 3sum, just when 2 numbers and not 3. if you would exclude for every iteration of the list, the number at your index, then you need to find 2 numbers in the list (excluding your index), that equal to the number at your index

Darkhan Over a year ago

Thank you, I've removed the nums[I] = ... code, but the time limit is still exceeded. And how is 2sum going to simplify the algorithm? I still have to find 2 numbers that sum up to the third

Collectives™ on Stack Overflow

How to speed up nested for loop in python?

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related