It’s that time again where

## The Problem

This problem was asked by Stripe.

Daily Coding Problem

Given an array of integers, find the first missing positive integer in linear time and constant space. In other words, find the lowest positive integer that does not exist in the array. The array can contain duplicates and negative numbers as well.

For example, theinput `[3, 4, -1, 1]`

should give `2`

. Theinput `[1, 2, 0]`

should give `3`

.

You can modify the input array in-place.

## Our Approach

My solution to this is going to go through a few stages, lets list these out.

- We will create a function/method that takes in a single argument and returns an integer, I’ll call this
`lowestInt`

. I thought about that name for a while… - The desired return value is going to be a positive integer, so we will remove the values that are less or equal than 0, and sort the remaining values in ascending order.
- Starting with the value 1, we will iterate through the array/list until we find a missing value, and return that value.

We will just be tackling this challenge in javaScript, but will explain the steps we are taking in a bit more depth than previous challenges

## The Solution

#### Step 1

Our first step was a nice easy one to get us started, create the function. We will also assign the given test cases to variables for testing later.

// Supplied test arrays // Format: array, answer const testCases = [ [[3, 4, -1, 1],2], [[1, 2, 0],3] ] //The alogrithm function lowestInt(array) { }

#### step 2

Next we will remove the negative and zero integers from the list. We are using the filter() function to remove the values that are less than 1.

// The alogrithm function lowestInt(array) { let positives = array.filter(int => int>0); }

Our next task, according to our plan is to sort the array into ascending order.

// The alogrithm function lowestInt(array) { let positives = array.filter(int => int>0); let sorted = positives.sort() }

Nothing too complicated so far.

#### Step 3

The next step is to iterate through the sorted array until there is a missing integer. We will do this with an `if statement`

within a `for loop.`

// The alogrithm function lowestInt(array) { let positives = array.filter(int => int>0); let sorted = positives.sort() for (let i =0;i<=sorted.length; i++ ) { if(sorted[i] != i+1){ return i+1 } } }

And that should be that. I have written a quick test function so that we can load a list of tests and expected answers.

// Test function function runTest(array) { if(lowestInt(array[0]) == array[1]){ return `expected ${array[1]}, received ${lowestInt(array[0])}: Test Passed` } else { return `expected ${array[1]}, received ${lowestInt(array[0])}: Test Failed` } } // Run tests for (let test = 0; test < testCases.length; test++) { console.log(`Test ${test}: ${runTest(testCases[test])}`) }

Just to be sure, let’s add some other tests into the `testCases `

array.

// Supplied test arrays // Format: array, answer const testCases = [ [[3, 4, -1, 1],2], [[1, 2, 0],3], [[3,-88,100,2,6],1], [[1],2], [[],1] ] // Logged: Test 0: expected 2, received 2: Test Passed Test 1: expected 3, received 3: Test Passed Test 2: expected 1, received 1: Test Passed Test 3: expected 2, received 2: Test Passed Test 4: expected 1, received 1: Test Passed

And on that note we are done, I am sure there are more elegant solutions but this seems to work.

Complete code below:

// Supplied test arrays // Format: array, answer const testCases = [ [[3, 4, -1, 1],2], [[1, 2, 0],3], [[3,-88,100,2,6],1], [[1],2], [[],1] ] //The alogrithm function lowestInt(array) { let positives = array.filter(int => int>0); let sorted = positives.sort() for (let i =0;i<=sorted.length; i++ ) { if(sorted[i] != i+1){ return i+1 } } } // Test function function runTest(array) { if(lowestInt(array[0]) == array[1]){ return `expected ${array[1]}, received ${lowestInt(array[0])}: Test Passed` } else { return `expected ${array[1]}, received ${lowestInt(array[0])}: Test Failed` } } // Run tests for (let test = 0; test < testCases.length; test++) { console.log(`Test ${test}: ${runTest(testCases[test])}`) }

## Conclusion

This algorithm could probably be refactored with some form of function chaining, but other than that I am happy with the efficiency of our solution.

For tomorrows challenge we use either PHP or Python