Daily Coding Problem: Problem #4

1

For reference see original thread: Here

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.

Here is my solution. Feel free to break and let me know. :grinning:

<script>
    //Test Input
    const arr = [3, 4, -1, 1];

    const findFirstMissingPositiveValue = (arr) => {
      let tempArr = arr.filter(findPositiveValue); //Strip out non positive numbers
      
      tempArr.sort(function(a, b){return a - b}); //Sort lowest to highest.
      if (tempArr.length == 0) {
        return 1;  //Empty array, lowest non-existing positive value possible is 1.
      }
      

      let minPos = 1;
      for (let i = 0; i < tempArr.length; i++) {
        if (tempArr[i] == minPos) {
          minPos = tempArr[i] + 1;
        } else {
          break; //End loop, lowest non-existing positive value has been determined.
        }
      }

      return minPos;
    }

    //Filter - find positive values
    function findPositiveValue(value) {
        return value > 0;
    }
    
    
    console.log(findFirstMissingPositiveValue(arr));
  
  </script>
2

I have refactored your code:

const arr = [3, 4, -1, 1];

const findFirstMissingPositiveValue = (arr) => {
  let tempArr = arr.filter(findPositiveValue); //Strip out non positive numbers
  
  tempArr.sort(function(a, b){return a - b}); //Sort lowest to highest.

// if any positive values, return the 1st value plus 1 else return 1
  return tempArr.length ? tempArr[0] + 1: 1;
}

//Filter - find positive values
function findPositiveValue(value) {
    return value > 0;
}

console.log(findFirstMissingPositiveValue(arr));

There is probably a quicker way to do it though! :smiley:

3

Remember, the problem states: find the lowest positive integer that does not exist in the array. When I used [6, -6, 4, 5] it fails.

So my approach is to get an array with only the existing positive values and sorted from lowest to highest. Then loop through and determine the lowest possible value that does not already exist starting at 1.

True, there probably is a more quicker way. I’m not up on algorithms yet and I didn’t want to just copy one from Google. I just worked through the problem logically in my head until I came up with this solution.

4

Isn’t that sort algorithm nlog(n) so that it violates the linear time constraint?

5

To be completely honest I didn’t know what that meant and focused more on -

“In other words, find the lowest positive integer that does not exist in the array.”
and
“You can modify the input array in-place.”

So I felt my solution was valid, but I could definitely be wrong in my interpretation.

6

Linear time means you can pass through the array as much as you want, right? This is the solution I came up with, not sure about it.

function findSmallestMissingInt(arr) {
  let min = 1;
  let prevLoopMin;
  while (min !== prevLoopMin) { // Exit once no increment has occurred in the previous loop
    prevLoopMin = min;
    for (const num of arr) { 
      if (num === min) min++; // Increment min if its current value is found in the array
    }
  }
  return min;
}

It’ll just continuously loop through the array, incrementing min when it runs into the same number, and then return when it completes a loop without incrementing.

7

As fun as this is, codewars has loads of algorithms to practice and you are not restricted to JS. The algos come with explanations and usually a batch of tests (not just one).

8

I think that the worst-case performance of your algorithm is that it traverses the array n * n times (n for the outer loop, and n for the inner loop) so it looks like O(n**2) rather than O(n) (linear). I think the rule-of-thumb is that any nesting of loops will put you out of the linear range.

1 Like
9

It’s always tricky when you try to estimate real time complexity, as Big-O notation is the worst case… For example on array of 300,000 random numbers between -50 and 50, my solution below, as well as findSmallestMissingInt(arr) from @colinthornton run in 0.9ms in avarage, while “linear for-loop” iteration over all items takes about 2.35ms on my computer, which is quite good, even though they both look like O(n**2)

const findFirstMissingPos = arr => [...Array(Math.max(...arr) + 1).keys()].filter(int => !arr.includes(int + 1))[0] + 1;
10

That’s true! Big O is a crude “consumer-index” for algorithms. It only indicates asymptotic behavior as the data-set grows. For a given data-set an O(n**2) algorithm could be way faster than O(n) or even O(1). At least in principle.

Edit: I guess not even asymptotic, just a functional upper bound. But anyway it sounded like in the original problem statement Stripe wasn’t looking for just any old answer, they wanted O(n) or better.

11

Here’s my solution:

function findFirstMissingPositiveValue(arr){
  const max = arr.reduce((acc, curr) => curr > acc ? curr : acc) + 1;
  for(let i = 1; i <= max; i++){
    if(!arr.includes(i)) return i;
  }
}
2 Likes
12

My first thought. Is there any reason not to do it like below? Not too sure if it’s constant space & linear time but I think it is(?)

using System;
using System.Linq;
using System.Collections.Generic;

public class DCP_04
{
    public static void Main()
    {
    String input = Console.ReadLine();
    int[] numbers = input.Split(' ').Select(int.Parse).ToArray();

    Console.WriteLine(FirstMissingPositiveInt(numbers));
    }

    public static int FirstMissingPositiveInt(int[] intArray)
    {
    HashSet<int> positiveNumbers = new HashSet<int>();

    for (int i = 0; i < intArray.Length; i++) if (intArray[i] > 0) positiveNumbers.Add(intArray[i]);
    int missingPositveInt = 1;
    while (true)
    {
    if (positiveNumbers.Contains(missingPositveInt)) missingPositveInt++;
    else break;
    }
    return missingPositveInt;
    }
}
1 Like
13

My C# experience is still less than a year, but it looks like a fine solution to me and it works! Welcome to the community and your first post.

14

@davisg67 I would request you to please delete this post as soon as possible. Also, please don’t continue this practice. This is not in compliance with the community’s code of conduct.

Thank you.

15

What are you talking about?

16

@gebulmer Actually, freeCodeCamp moderators have informed me that the habit I started of posting interview question from a outside resource is not in compliance with the community’s guidelines. It’s a kind of advertisement of the product. So, this post should be deleted.

That’s all mate :slight_smile: I hope it cleared things up a bit.

17

You’re right that those kinds of questions don’t belong here, but this thread wasn’t about that as far as I can tell?

If I recall correctly, back in December a group of campers organised doing some daily challenges together, not as part of interview questions, but just as a fun set of puzzles to learn about algorithms and programming together

This thread comes across like that too

18

Yes its in line of those.

19

Either way, it’s for the moderators to decide, not us

We don’t have the authority to decide whether posts should live or die, so we shouldn’t really be telling other people what to do

20

Yes. Since, I was the one who started this. So, it’s my responsibility to stop it if it breaks any of the guidelines.