Ufdjrw

I have the following task:

Given an unsorted integer array, find the first missing positive integer. Your algorithm should run in O(n) time and use constant space.

After thinking and getting a hint, I decided to change the input list A. The following is the code:

def firstMissingPositive(A):
 m=max(A)
 ln=len(A)
 i=0
 while i<ln:
 if A[i]>=1 and A[i]<=ln:
 if A[A[i]-1]!=m+1:

 A[A[i]-1], A[i] = m+1, A[A[i]-1]
 else:
 i+=1

 else:
 i+=1
 for i in range(ln):
 if A[i]!=m+1:
 return i+1

When I run it, it takes a long time. What shall I do to make it a bit faster?

EDIT: here is the list A.

A=[ 417, 929, 845, 462, 675, 175, 73, 867, 14, 201, 777, 407, 80, 882, 785, 563, 209, 261, 776, 362, 730, 74, 649, 465, 353, 801, 503, 154, 998, 286, 520, 692, 68, 805, 835, 210, 819, 341, 564, 215, 984, 643, 381, 793, 726, 213, 866, 706, 97, 538, 308, 797, 883, 59, 328, 743, 694, 607, 729, 821, 32, 672, 130, 13, 76, 724, 384, 444, 884, 192, 917, 75, 551, 96, 418, 840, 235, 433, 290, 954, 549, 950, 21, 711, 781, 132, 296, 44, 439, 164, 401, 505, 923, 136, 317, 548, 787, 224, 23, 185, 6, 350, 822, 457, 489, 133, 31, 830, 386, 671, 999, 255, 222, 944, 952, 637, 523, 494, 916, 95, 734, 908, 90, 541, 470, 941, 876, 264, 880, 761, 535, 738, 128, 772, 39, 553, 656, 603, 868, 292, 117, 966, 259, 619, 836, 818, 493, 592, 380, 500, 599, 839, 268, 67, 591, 126, 773, 635, 800, 842, 536, 668, 896, 260, 664, 506, 280, 435, 618, 398, 533, 647, 373, 713, 745, 478, 129, 844, 640, 886, 972, 62, 636, 79, 600, 263, 52, 719, 665, 376, 351, 623, 276, 66, 316, 813, 663, 831, 160, 237, 567, 928, 543, 508, 638, 487, 234, 997, 307, 480, 620, 890, 216, 147, 271, 989, 872, 994, 488, 291, 331, 8, 769, 481, 924, 166, 89, 824, -4, 590, 416, 17, 814, 728, 18, 673, 662, 410, 727, 667, 631, 660, 625, 683, 33, 436, 930, 91, 141, 948, 138, 113, 253, 56, 432, 744, 302, 211, 262, 968, 945, 396, 240, 594, 684, 958, 343, 879, 155, 395, 288, 550, 482, 557, 826, 598, 795, 914, 892, 690, 964, 981, 150, 179, 515, 205, 265, 823, 799, 190, 236, 24, 498, 229, 420, 753, 936, 191, 366, 935, 434, 311, 920, 167, 817, 220, 219, 741, -2, 674, 330, 909, 162, 443, 412, 974, 294, 864, 971, 760, 225, 681, 689, 608, 931, 427, 687, 466, 894, 303, 390, 242, 339, 252, 20, 218, 499, 232, 184, 490, 4, 957, 597, 477, 354, 677, 691, 25, 580, 897, 542, 186, 359, 346, 409, 655, 979, 853, 411, 344, 358, 559, 765, 383, 484, 181, 82, 514, 582, 593, 77, 228, 921, 348, 453, 274, 449, 106, 657, 783, 782, 811, 333, 305, 784, 581, 746, 858, 249, 479, 652, 270, 429, 614, 903, 102, 378, 575, 119, 196, 12, 990, 356, 277, 169, 70, 518, 282, 676, 137, 622, 616, 357, 913, 161, 3, 589, 327 ]

look to me that doing it in both O(n) and constant space is kind of impossible. (I stand corrected, the link of Rockybilly give such solution)

To do it in constant space one is kind of forced to sort the list and that is O(n log n) for most sorting algorithms, and the ones here looks like insertion sort which is in average O(n²)

So FWIW I choose to discard the constant space in order to do it as close to O(n) as I can think of which give me a 2n solution (in the worse case scenario, in average is n+k) (which in big O notation is still O(n) )

def firstMissingSince(sequence, start=1):
 uniques = set()
 maxitem = start-1
 for e in sequence:
 if e >= start:
 uniques.add(e)
 if e > maxitem:
 maxitem = e
 return next( x for x in range(start, maxitem+2) if x not in uniques )

(version 2 bellow )

I could have used set(sequence), and max(sequence) but both are O(n), so I combined them in the same loop, and I use set for two reason: first is a potential reduction in space by ignoring duplicates and in the same way I only care for number greater or equal to my lower bound (which I also make generic) and second is for the O(1) membership testing.

The last line is a simple linear search for the missing element with the property that default to start if the maximum element is lower to start or is the maximum+1 if the array have no missing element between start and its maximum.

here are some tests borrow from the others answers...

assert 1 == firstMissingSince(A) 
assert 2 == firstMissingSince([1,4,3,6,5])
assert 2 == firstMissingSince([1,44,3,66,55]) 
assert 6 == firstMissingSince([1,2,3,4,5]) 
assert 4 == firstMissingSince([-6, 3, 10, 14, 17, 6, 14, 1, -5, -8, 8, 15, 17, -10, 2, 7, 11, 2, 7, 11])
assert 4 == firstMissingSince([18, 2, 13, 3, 3, 0, 14, 1, 18, 12, 6, -1, -3, 15, 11, 13, -8, 7, -8, -7])
assert 4 == firstMissingSince([-6, 3, 10, 14, 17, 6, 14, 1, -5, -8, 8, 15, 17, -10, 2, 7, 11, 2, 7, 11])
assert 3 == firstMissingSince([7, -7, 19, 6, -3, -6, 1, -8, -1, 19, -8, 2, 4, 19, 5, 6, 6, 18, 8, 17])

the answer of Rockybilly make me realize that I don't need to know the maximum value at all, so here is version 2

from itertools import count

def firstMissingSince(sequence, start=1):
 uniques = set(sequence) # x for x in sequence if x>=start 
 return next( x for x in count(start) if x not in uniques )

def first_missing_positive(nums):

 bit = 0

 for n in nums:
 if n > 0:
 bit |= 1 << (n - 1)

 flag = 0

 while bit != 0:
 if (bit & 1 == 0):
 break
 flag += 1
 bit >>= 1

 return flag + 1

O(1) space complexity and O(n) time complexity solution.

FWIW, here is how I did it:

def firstMissingPositive(A):
 for i in range(len(A)):
 while A[i] != i+1 and 0 < A[i] < len(A):
 value = A[i]-1
 A[i], A[value] = A[value], A[i]
 for i, value in enumerate(A, 1):
 if i != value:
 return i
 return len(A)+1

assert firstMissingPositive([1,4,3,6,5]) == 2
assert firstMissingPositive([1,44,3,66,55]) == 2
assert firstMissingPositive([1,2,3,4,5]) == 6
assert firstMissingPositive(A) == 1

May not be the complete cause for long run times but I did find a bug that will cause an infinite loop. I started by creating random integer arrays of length 20.

a = [random.randint(-10, 20) for _ in range(20)]

Added two print statements to see what was happening.

 while i<ln:
 print(A)
 if A[i]>=1 and A[i]<=ln:
 if A[A[i]-1]!=m+1:
 print("Swapping %d"%i)
 A[A[i]-1], A[i] = m+1, A[A[i]-1]
 else:
 ...

With this array as input you get into an infinite loop:

a = [-6, 3, 10, 14, 17, 6, 14, 1, -5, -8, 8, 15, 17, -10, 2, 7, 11, 2, 7, 11]

>>>
...
[18, 18, -8, -10, -6, 6, 14, 18, -5, 18, 18, 15, 17, 18, 2, 7, 18, 18, 7, 11]
Swapping 5
[18, 18, -8, -10, -6, 6, 14, 18, -5, 18, 18, 15, 17, 18, 2, 7, 18, 18, 7, 11]
Swapping 5
[18, 18, -8, -10, -6, 6, 14, 18, -5, 18, 18, 15, 17, 18, 2, 7, 18, 18, 7, 11]
...

Turns out that if A[A[i]-1] equals A[i] then you end up always putting the same number back into A[i]. In this case i == 5, A[5] == 6 and A[A[i]-1] == 6. In this statement,

A[A[i]-1], A[i] = m+1, A[A[i]-1]

The right hand side is evaluated; m+1 is assigned to A[5]; then 6 is assigned to A[5]. I fixed it for this one case by swapping the assignment order:

A[i], A[A[i]-1] = A[A[i]-1], m+1

With the list you added to the question, it now throws an IndexError with my mod. Even though the right hand side gets evaluated first, it appears that A[A[i]-1] on the left hand side doesn't get evaluated till after the first assignment is made and a large number has been placed in A[i].

Plagiarizing Rob's solution - evaluate [A[i]-1 before any swaps are made:

def firstMissingPositive(A):
 m=max(A)
 ln=len(A)
 print('max:, len:'.format(m, ln))
 i=0
 while i<ln:
## print(A[:20])
 if A[i]>=1 and A[i]<=ln:
 if A[A[i]-1]!=m+1:
## print("Swapping %d"%i)
 v = A[i]-1
 A[i], A[v] = A[v], m+1
 else:
 i+=1
 else:
 i+=1
 for i in range(ln):
 if A[i]!=m+1:
 return i+1

And it still sometimes returns a wrong result so minus one for me. It produces wrong results for the following:

[18, 2, 13, 3, 3, 0, 14, 1, 18, 12, 6, -1, -3, 15, 11, 13, -8, 7, -8, -7]
[-6, 3, 10, 14, 17, 6, 14, 1, -5, -8, 8, 15, 17, -10, 2, 7, 11, 2, 7, 11]
[7, -7, 19, 6, -3, -6, 1, -8, -1, 19, -8, 2, 4, 19, 5, 6, 6, 18, 8, 17]

Here is my solution.

from collections import defaultdict

def firstMissingPositive(A):

 d = defaultdict(int)
 for i in A:
 d[i] = 1

 j = 1
 while True:
 if d[j] == 0:
 return j
 j += 1

Space complexity: O(n)

Time complexity: O(n + k). Which is considered O(n). Also ignored hashing complexity.

By the way: Googling gives the answer you seek, constant space and O(n) time.