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.

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.

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).

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.

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)

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.

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;
}
}

@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.

@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 I hope it cleared things up a bit.

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