jw2013 on Python Multiple Assignment Is a Puzzle

Comment on Python Multiple Assignment Is a Puzzle parent

jw2013OP12y

The function you wrote:

    a) takes O(n*lgn) time; the method in post uses O(n) time
    b) use extra memory; the method in post uses O(1) extra memory
    c) have logical error: the problem asks to find the first missing positive (in range [1, infinity)).

So firstMissingPositive([4,100]) should return 1, instead of 5. But the problem is not stated in the post, so let's assume you are implementing the first missing positive in range(A[0], A[-1] + 1) for sorted(A), your code does not handle corner case well.

For example:

    a) your firstMissingPositive([100]) gives ValueError: min() arg is an empty sequence
    b) your firstMissingPositive([]) gives IndexError: list index out of range

It is attempting to write three-liners that seems to solve the problem, but it is far more important to solve the problem in time and space efficient way. At least, it is important to handle the corner cases well.

zebulanmcranahn 12y

  def firstMissingPositive(A):
      try:
          for x in range(1, max(A)+1):
              if x not in A: return x
      except: return A

  def firstMissingPositive(A):
      try: return next(x for x in range(1, max(A)+1) if x not in A)
      except: return A

Two above return:

  print(firstMissingPositive([4,2,5,7,1])) # 3
  print(firstMissingPositive([4,100]))     # 1
  print(firstMissingPositive([]))          # []
  print(firstMissingPositive([5]))         # 1

I wasn't sure what [5] or [] were supposed to return so maybe I'm still wrong? Had never heard of this question before, thought I'd try it out.

Thanks for the reply, very informative.

TheLoneWolfling 12y

You really should change "except" to "except ValueError" there.

Also, I suggest first converting A to a set. Just "A = set(A)" would work.

yeukhon 12y

HN is not really for code review, but why are you using try and except here??

TheLoneWolfling 12y

Python is designed for it, and it makes it cleaner, so why not?

EAFP: Easier to ask for forgiveness than permission

That being said, just a blanket except is a bad idea.

zebulanmcranahn 12y

Thanks for the ValueError tip. I added it as well as a TypeError just in case the input comes in as a string. My skills are beginner level at best, tips like yours help a lot!

Comments