Code Challenge: Day 3

It’s that time again where i try and solve a problem posed by Daily Coding Problem. This problem has been identified as hard, so lets see what I can do.

The Problem

This problem was asked by Stripe.
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, the input [3, 4, -1, 1] should give 2. The input [1, 2, 0] should give 3.
You can modify the input array in-place.

Daily Coding Problem

Our Approach

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

  1. 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…
  2. 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.
  3. 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

Leave a Reply