Hacker News Reader

Comment by ghshephard | Hacker News Reader

While it may require an extra set, the following is a lot more pythonic, and also finds the first missing positive in the same two passes that your code did (which is actually O(2n), and honestly made my eyes bleed trying to follow.)

  def missPos(a):
      b={x for x in a}
      for x in range(1,len(b)+2):
          if not x in b:
              return x

View on HN

Just wanted to add a more functional solution:

    def miss_pos(a):
        b = range(1, len(a)+2)
        return min(set(b).difference(a))

It's probably not as efficient, but remember the first rule of optimization: http://c2.com/cgi/wiki?FirstRuleOfOptimization

I wonder why so much discussion about arbitrary rules of assignment when the solution to the problem can be written (and is more readable) without ever mentioning this complicated "assignment" feature.

Set creation takes O(N) space and O(N log(N)) time, and the inner loop condition (if not x in b) is also log(N). So it's slower in time and it requires more space. People usually don't distinguish between O(N) and O(2N), because actual performance is dependent on implementation choices and CPU cache locality and all that stuff isn't really part of algorithmic complexity analysis.

I do like your solution better though, but mostly because it doesn't mutate the array passed to the function. A function called "firstMissingPositive" shouldn't modify state.

Why would set creation (and the not x in b inner loop) take O(Nlog(N)) time? I would have thought it would have just required a hash-lookup for each element (O(1)?) being added (and then, a decision to either add the element or not.

Actual times definitely more than O(N) growth.

  a10k = []
  for x in range(10000):
    a10k.append(randint(1,20000))
  %timeit b10k = set(a10k)


   10k elements  = 364 microseconds/loop
  100k elements  = 5 milliseconds/loop
   1mm elements  = 170 milliseconds/loop
  10mm elements  = 2.4 seconds/loop.
 100mm elements  = 34.5 seconds/loop

Presumably the jump from 100k elements to 1mm elements hit that "cache locality" boundary you were referring to.

I'm assuming a set is internally a balanced tree of some sort. So lookup and insertions are O(log N). So N insertions should be O(N log N).

Edit - nevermind. It's a hash table of course. So I'm wrong.

Run this on Python 3 or use xrange instead of range on Python 2 and you get N space instead of 2N anyway :)

Also, the average case for set membership testing is O(1), so the average case runtime would actually be O(N).

https://wiki.python.org/moin/TimeComplexity#set

The context for these coding-challenges is they are the type for algorithm competition or white-board coding interview.

Back then when I was still looking for job, I was asked this question by a startup. I gave out this hashset solution and was quickly asked if O(1) space solution was available and then asked to implemented it.

If the space restriction is not an issue, I would definitely go with the method you suggested. Way more succinct and easier to follow.

O(n) = O(2n)

Nice!

Is there an advantage in using a set comprehension over set(a) or is it just a stylistic choice?

None that I know of - As a novice python programmer, I just try and use comprehensions for everything so my eyes get used to the pattern.

The set function is somewhat faster.

  a=[]
  for x in range(10000):
      a.append(randint(1,2000))

  %timeit b=set(a)
  1000 loops, best of 3: 373 µs per loop

  %timeit b={x for x in a}
  1000 loops, best of 3: 542 µs per loop

style

While comprehensions are definitely standard Python, I would argue that if you're not actually changing any value (as is the case here, then just `set(a)`, being much simpler, is more Pythonic.

Reply on news.ycombinator.com