How can I name elements that are duplicates instead of extracting it from a list? (python)

Question

My leetcode solution has been (finally!) accepted but I know it can be improved - in particular line 12 and 13.

How can I make this code simpler and more efficient? How can I name elements that are duplicates instead of extracting it from a list?

Q: LeetCode Two Sum

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
            Y = []
            for i in nums:
                for j in nums:
                    if i + j == target and i != j:
                        return([nums.index(i),nums.index(j)])

                    elif i + j == target and i == j:
                        for n in nums:
                            if nums.count(n) > 1:
                                Y.append(n)
                                indices = [i for i, val in enumerate(nums) if val == Y[0]]
                                return indices

I am pretty new at coding and I am not sure how to improve my skills. I have picked up the basics from an intro course but I find leetcode questions super difficult :( I find some hackerrank & codility questions more doable but I am currently hitting a wall as the questions get harder. I copied and pasted the enumerate fn too tbh.

Thanks so much!

Answer 1

Thank you for the optional type annotation, it is lovely.

---

Rather than twoSum, PEP-8 asks that you name it two_sum. It may sound trivial. But conforming to community norms helps to make your code more readable. When someone picks it up and is paying attention to what you said, rather than how you said it, the code review conversation suddenly kicks into higher gear, where you're getting the more substantive advice you were really looking for.

---

Avoid extraneous ( ) parens in return([a, b]).

---

Prefer to define a public API that returns a tuple rather than a list when the number of elements is part of the API. That is, when number of elements is known apriori, such as "it's always TWO elements". This is a python cultural thing. Think of a tuple as being similar to a C struct (well, an immutable struct).

---

To answer the titular question directly, let me introduce you to the batteries-included Counter data structure.

Also, defaultdict(list) is pretty rocking!

---

Your search for the proper index could be done by fast C code rather than interpreted bytecode:

https://docs.python.org/3/library/stdtypes.html#common-sequence-operations

But y.index(val) is still going to take O(N) linear time, and there's nothing wrong with that.

---

There is much more to be gained from choosing an appropriate algorithm than from sweating tiny details of implementing it this way or that way. Big-oh matters.

We have a pretty explicitly O(N^2) quadratic nested loop situation. Are you sure we need to spend that many cycles?

Hint: Once we have decided on 1st candidate addend, how much flexibility is there in choosing a 2nd winning addend? Does computer science offer a data structure that would support looking up such an addend in O(1) constant time?

---

The for i / for j loops use kind of odd identifiers. That is, we conventionally expect indexes, such as we might get back from enumerate. Consider using a / b instead. Also, consider using for i, a in enumerate(nums):, since that would obviate the later .index() call, and would simplify the "are these two numbers the same?" testing.

The running time of that final elif is honestly pretty terrible, looks like it might be O(N^4) quartic. Imagine I gave you a target of 3, and the input was a million zeros followed by [1, 2]. How much time would we spend down in that last part? Yeah. Lots and lots of time. Choosing appropriate algorithm matters a lot.