Leetcode 15 - 3 sum

Question

This is a Leetcode problem -

Given an array nums of n integers, are there elements \$a, b, c\$ in nums such that \$a + b + c\$ = 0? Find all unique triplets in the array which gives the sum of zero.

Note -

The solution set must not contain duplicate triplets.

Example -

Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is -

[
  [-1, 0, 1],
  [-1, -1, 2]
]

NOTE - [-1, 0, 1] and [1, 0, -1] are considered duplicates.

Here is my solution to this challenge -

def three_sum(nums):
    if nums == None or len(nums) < 3:
        return []    
    res = []
    nums.sort()
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        j = i + 1
        k = len(nums) - 1
        while j < k:   
            if nums[i] + nums[j] + nums[k] > 0:
                k -= 1
                while nums[k] == nums[k + 1] and k > j:
                    k -= 1
            elif nums[i] + nums[j] + nums[k] < 0:
                j += 1
                while nums[j] == nums[j - 1] and j < k:
                    j += 1
            else:
                res.append([nums[i], nums[j], nums[k]])
                j += 1; k -= 1
                while nums[k] == nums[k + 1] and k > j:
                    k -= 1
                while nums[j] == nums[j - 1] and j < k:
                    j += 1
    return res

So I would like to know whether I could make my program shorter and more efficient. Also, I would like to know if I could make my code PEP 8 compliant (if possible) as I'm having trouble (understanding) with the PEP 8 checker (I need explanations for why I'm getting these errors) -

Also, any recommendations for better PEP 8 checkers? I'll be glad to know.

Answer 1

AlexV has covered the formatting stuff.

With regards to the length and efficiency of the code:

You've clearly put a lot of thought into how to calculate the list of tuples requested. And you've found some good efficiencies! But you're approaching this from the wrong direction: Start with the clearest syntactically legal expression of the desired result you can write, and then add complexity/efficiency as needed.

def three_sum(nums: List[int]) -> Set[Tuple[int,int,int]]: # Type-hints are optional.
    return {
        tuple(sorted([a, b, c]))
        for a in nums
        for b in nums
        for c in nums
        if 0 == (a + b + c)
    }

That's pretty concise and pretty clear, but it's just about the least efficient way one could do it.

• We should be sorting first, and our inner loops should only cover values greater-than-or-equal-to (or only less than/equal to) the value grabbed by the outer loop.
• We can ignore duplicate values in nums, since each value will be considered alongside itself anyway.

This will reduce the length of our loops. It may actually increase the time we spend sorting/culling, but that will depend on the input data.

def three_sum(nums: List[int]) -> Set[Tuple[int,int,int]]:
    indexed_culled = enumerate(sorted(set(nums)))
    return {
        (a, b, c)
        for (a, i_a) in indexed_culled
        for (b, i_b) in indexed_culled[i_a:]
        for (c, _) in indexed_culled[i_b:]
        if 0 == (a + b + c)
    }

This is still lacking in the kind of maximal efficiency your code seems to be striving for. It is the version I'd want to see in most production situations, but if runtime optimization is critical then maybe we should try to shorten/avoid the innermost loop. If the c loop has five items to run, in ascending integer value, and the first a + b + c is 1, then we shouldn't have to do the other four.

def three_sum(nums: List[int]) -> Set[Tuple[int,int,int]]:
    culled = set(nums)
    indexed = enumerate(sorted(culled))
    pairs = {
        (a, b)
        for (a, i_a) in indexed
        for (b, _) in indexed[i_a:]
    }
    return {
        (a, b, 0 - (a + b))
        for (a, b) in pairs
        if 0 - (a + b) in culled
    }

Of course if runtime optimization is critical, you'll want someone better versed than me in python's different iterable types to reconsider all my Set/List/Tuple/Generator choices.

Answer 2

Have you actually read or at least skimmed PEP8 regarding the aspects mentioned by the style checking tool?

The first error (E711) basically wants you to write if nums is None or ... instead of ``. You can find this at section Programming Recommendations.

The second one (E702) tells you that you are using a semicolon to cram multiple lines into a single one. Simple searching your code for ; will bring up j += 1; k -= 1. It is not recommended to have multiple instructions per line, so each of them should be on its own line. This can be found in the section titled Other Recommendations.

As you know, Python can be a bit picky when it comes to whitespace. The explanation why trailing whitespace is frowned upon may also be found under Other Recommendations in PEP8 (see previous link).

As for the missing newline at the end of the file: there is no Python specific reason why you have to do this. It's just that most people tend to do this. pylint's help page on that message tells you more about it:

While Python interpreters typically do not require line end character(s) on the last line, other programs processing Python source files may do, and it is simply good practice to have it. This is confirmed in Python docs: Line Structure which states that a physical line is ended by the respective line end character(s) of the platform.

Which brings us to other tools that can be use to check your code style. Python has a lot of them, e.g. pylint (mentioned above - also with a static code checker), flake8, pycodestyle (formerly pep8), and bandit to name a few. There is a Visual Studio Code help page about which linters are supported by that specific IDE with a few more of them. Just pick an code editor (Visual Studio Code, Atom, vim, emacs, ...) or IDE (Eclipse with Python plugin, PyCharm, Spyder, ...) of your choice, type its name into Google search, add "python linter"/"python stylecheck" to your query and you are more than likely to find something that either describes how to use built-in tools or integrations to do just that.