Good morning! Here's our prompt for today.

We have an unsorted array of integers such as the following:

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

In the above example, the minimum number is -2 and the maximum is 3. If it were sorted, it would look like:

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

This means there is an expected range (defined as the collection of values between the minimum and maximum values) of [-2, -1, 0, 1, 2, 3] for the array.

But look at the example again:

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

We're missing a number: 2. The smallest missing positive integer for our input array is 2.

Can you write a method that takes such an array and returns the first missing positive integer?

1leastMissingPositive([1, 2, 3, 0])
2// 4

In the above example, it is 4 since we already have 0 through 3. Have your code run in O(n) time with constant space (hence, we can easily determine if it was sorted, but most sorts will take O(n * log n) time).

Constraints

• Length of the array <= 100000
• The array can be empty
• The array will contain values between -100000 and 100000
• The final answer will always fit in the integer range
• Expected time complexity : O(n)
• Expected space complexity : O(1)

Try to solve this here or in Interactive Mode.

How do I practice this challenge?

xxxxxxxxxx

​

def least_missing_pos(nums):

    # fill in

    return nums

​

​

import unittest

​

​

class Test(unittest.TestCase):

    def test_1(self):

        assert least_missing_pos([3, 5, -1, 1]) == 2

        print("PASSED: Expect least_missing_pos([3,5,-1,1]) to return 2")

​

    def test_2(self):

        assert least_missing_pos([5, 6, 7, 8, 9]) == 1

        print("PASSED: Expect least_missing_pos([5,6,7,8,9]) to return 1")

​

    def test_3(self):

        assert least_missing_pos([]) == 1

        print("PASSED: Expect least_missing_pos([]) to return 1")

​

    def test_4(self):

        assert callable(least_missing_pos) == True

        print("PASSED: Expect least_missing_pos to be a function")

​

​

if __name__ == "__main__":

    unittest.main(verbosity=2)

    print("Nice job, 4/4 tests passed!")

Here's a video of us explaining the solution.

To change the speed of the video or see it in full screen, click the icons to the right of the progress bar.

Here's our guided, illustrated walk-through.

How do I use this guide?