LeetCode #494: Target Sum (Python)

Question

Below is my solution to LC #494: Target Sum (given a list of numbers and a target integer, find out how many different ways the numbers can be subtracted from the total sum to result in the target sum).

There's one very common pattern in Python here that I question, and it's the use of for num in nums[1:]:. Iterating over nums[1:] is very explicit and readable, but it results in the creation of a whole new array when that really isn't our intention. That also means additional wasted time and wasted memory.

I used to always do for i in range(1, len(nums)): in these situations, but I see most other people using nums[1:]. Would love to hear thoughts on that.

And if there's a cleaner way to write this without having to initialize the counts hash from nums[0] separately from the body of the loop, that'd be great too. I couldn't think of a cleaner way.

class Solution:
 def findTargetSumWays(self, nums: List[int], S: int) -> int:
 counts = {nums[0]: 1, -nums[0]: 1}
 if nums[0] == 0:
 counts[0] += 1
 for num in nums[1:]:
 keys = list(counts)
 new = {}
 for key in keys:
 if key + num not in new:
 new[key + num] = 0
 if key - num not in new:
 new[key - num] = 0
 new[key + num] += counts[key]
 new[key - num] += counts[key]
 counts = new
 return counts[S] if S in counts else 0
```

Answer 1

for num in nums[1:] is the prefered way to iterate over a partition of an array; if you are worried about performance, it actually is faster, because accessing by index is more expensive in python than copying then iterating values (you can play with snippets of timeit to verify that claim, but I'm fairly sure of that - accessing by index in python involves way more checks and operations than it does in a language like C).

The performance issue with your program, if there is one, isn't there. The copy is just done once in the outter loop, and since it is repeated by num your inner loop is way more costy. Mind this: since every iteration can in the worst case double the number of items in keys, your program is actually of complexity O(2^n) where n is the array length.

In a matter of using more efficient structures you can also use Counter from collections that saves a bit of verbosity (it has zero as default value) and computation time (it is optimized C structure).

Without optimizing the algorithm, which I believe is part of the challenge :

from collections import Counter
class Solution:
 def findTargetSumWays(self, nums: List[int], S: int) -> int:
 counts = Counter()
 counts[-nums[0]] += 1
 counts[nums[0]] += 1
 for num in nums[1:]:
 new = Counter()
 for key in counts.keys():
 new[key + num] += counts[key]
 new[key - num] += counts[key]
 counts = new
 return counts[S]

• Diane M: Your base solution is not bad, adding a small optimization I was able to best 87.82% of submitted solutions in run time.
• NightDriveDrones: Can I ask what your optimization was? Also, what do you think about using collections.defaultdict(int) instead of collections.Counter (since we're only using the default value feature)?
• Diane M: @user107870 I believe Counter is more optimized because it's less generic but I have no idea if it really is. The optimization was 1- sort nums in descending order and 2- remove keys in counts if they are distant of S of more than the sum of remaining nums.

Answer 2

List objects are iterables. A for loop implicitly calls iter() on the list, but you can do it yourself, too.

nums_iter = iter(nums)
num0 = next(nums_iter)
for num in nums_iter:
 # ...

The list is not copied, and the for loop will begin with the second item, as required.

However, this is far less clear than for num in nums[1:]:

---

Much clearer is to leverage itertools, specifically itertools.islice():

for num in islice(nums, 1, None):
 # ...

However, islice() also allows a step greater than one, which means you probably lose performance to the code that supports this unneeded capability.

Copying the array might be a smaller performance penalty. You’ll want to profile each approach, and evaluate the trade off between readability and performance.

---

Speaking of unnecessary copies:

keys = list(counts)

counts is not changed in the loop below, so memorizing the list of keys is an unnecessary copy. You could simply use:

for key in counts:
 # ...

---

counts[key] is an unnecessary lookup. And you are doing it twice. Better is to retrieve the value with the key during the iteration process.

for key, val in counts.items():
 # ...

---

And, as mentioned in @ArthurHavlicek’s answer, use collections.Counter.

• NightDriveDrones: After reading docs, I can see islice might be useful if we were using a single iterator in multiple contexts, but is it adding anything over range / xrange when we're just doing a single loop through?
• AJNeufeld: The documentation says "Roughly equivalent to", and then a blob of Python code. Don’t get fooled; it is not implemented in Python. It will be implemented directly in C, (assuming CPython), and may approach the performance of looping over the list directly, but without the penalty of copying the list.