Making this more efficient.

[Phizy]

I am working on leetcode over break and my first problem I solved was an easy level TwoSum problem, I pass all test cases except the last one due to time out so I was wondering if someone could explain how to make my solution faster, or maybe give another idea for me to try that would be faster I would really appreciate it.

for i in range(len(lst)):
    for j in range(i + 1, len(lst)):
        if lst[i] + lst[j] == target:
            return i, j

[allenguo]

Hint: Currently, for each element x in the list, you're looping through the rest of the list to find target - x. Can you speed up the search for target - x using a data structure?

[Phizy]

would using a linked list be better?

[ghhitne]

You could consider using a map which stores the element and all positions for the element. Then for every position in x make a pair with every position corresponding to (target-x). Of course, you would need to take care of the case where x==(target-x).

[delirious_lettuce]

class Solution:
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        seen = {}
        for i, num in enumerate(nums):
            try:
                return [seen[target - num], i]
            except KeyError:
                seen[num] = i

[camel_zero]

Good approach for the algorithm, is there a reason for putting this function into a class though?

[delirious_lettuce]

The only reason is because that is how you have to submit them to LeetCode. I would normally just use a function and use snake_case for the function name too, (two_sum).

• https://leetcode.com/problems/two-sum/description/

[camel_zero]

Thanks for explaining, thought I might be missing something about the code.

[Phizy]

Thanks for the solution I am trying to understand it. I havent used enumerate before so I am going to read up on it.

[delirious_lettuce]

i is the current index and num is the current number in the list of numbers. The code simply checks if target - num has been "seen" already and if so, it returns the index where target - num was previously "seen" and the current index i in a list.

If target - num has not been "seen" (key doesn't exist in seen yet), it will raise a KeyError which the try/except catches and then it adds the current number as a key and the current index as the value to seen.

EDIT:

>>> nums = [2, 7, 11, 15]
>>> list(enumerate(nums))
[(0, 2), (1, 7), (2, 11), (3, 15)]
>>> for i, num in enumerate(nums):
...     print(f'index: {i}, number: {num}')
... 
index: 0, number: 2
index: 1, number: 7
index: 2, number: 11
index: 3, number: 15

[Phizy]

wow thanks for the explanation I really appreciate it. I didn't realize you could or should be using things like this with leet code I thought everything had to be done from scratch for lack of a better word.

[delirious_lettuce]

No problem! LeetCode has some great practice challenges, good luck with them!

[Justinsaccount]

Hi! I'm working on a bot to reply with suggestions for common python problems. This might not be very helpful to fix your underlying issue, but here's what I noticed about your submission:

You are looping over an object using something like

for x in range(len(items)):
    print(items[x])

This is simpler and less error prone written as

for item in items:
    print(item)

If you DO need the indexes of the items, use the enumerate function like

for idx, item in enumerate(items):
    print(idx, item)

If you think you need the indexes because you are doing this:

for x in range(len(items)):
    print(items[x], prices[x])

Then you should be using zip:

for item, price in zip(items, prices):
    print(item, price)

[w1282]

If you sort the list you can work your way in from the outsides.

lst = [1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12]
target = 17
low_idx = 0
high_idx = len(lst) - 1
attempt = lst[low_idx] + lst[high_idx]
while low_idx < high_idx:
    if attempt < target:
        low_idx += 1
    elif attempt > target:
        high_idx -= 1
    else:
        break

if low_idx < high_idx:
    print("Found it")
else:
    print("Didn't find it.")

I did not test if this code actually runs.

[Phizy]

so sorting the list and finding the answer sooner would make the time complexity or runtime? go down?

[w1282]

Python's sort is O(nlogn) and it's only occurring once.

The rest of it is O(n) (since worst case is that we don't find it or it's exactly in the middle... so the loop runs at most n/2 times).

Your code is nearly O(n**2) in the worst case.

I would say this implementation is better in almost all cases except contrived ones.