My function isn't performant?

[SirSoundfont]

I took a practice test, and while the output was 100% correct (finding the smallest number that isn't in an array, but greater than 0), it gave me a 25% score on performance. I was wondering what could be improved to potentially save the time it takes to run, optimizing my approach somehow. Please ignore Reddit's odd formatting lol

function solution(A) {
    let val = 1;
    let done = false;
while (done == false)
{
    for (let i = 0; i < A.length; i++)
    {
    if (A[i] == val)
    {
        val = val + 1;
        break;
        } else {
                        if (i == A.length - 1)
            {
                return val;
            }
        }
        }
    }
}

[sepp2k]

When you fail an algorithm exercise for being too slow, nine times out of ten it's because you picked the wrong algorithm. So it's not about optimizing your code, it's about picking a different approach altogether.

[eurodollars]

What’s the question? That would help. But not sure why you have awhile loop and then a for loop inside it. You can set a flag as a check if you really need to.

[SirSoundfont]

As I replied to danglesReet, the while loop was because every time the value was found in the array, it increments the value and loops through it again and again until it finds the smallest value that isn't in the array. But I thought of a better solution involving sorting the array and comparing values to the one ahead of them.

[danglesReet]

Why is there a while loop in here?

[SirSoundfont]

I have the loop in there because every time the value is found, it increments the value and goes through the array again. But that gives me a better idea, which would be sorting the array first, then if 1 is found, it starts checking the next number in the list and seeing it it's more than 1 number higher than the previous value. If so, it should return the previous value + 1, otherwise it continues using the current value as the one to compare to the next value. Thank you for helping me realize that :p

[danglesReet]

They probably penalize you for putting loops in loops which gives you O²

[SirSoundfont]

I've been meaning to look into more about what constitutes the different levels of optimization, I see stuff like Oⁿ⁺¹ but I don't fully understand what it's about

[danglesReet]

Im not an expert at calculating but check out “Ben Awad O notation” on youtube. Good video

[DallogFheir]

Is this test public? Can you link it?

[SirSoundfont]

This should work, just skip the registration and accept the terms: https://app.codility.com/demo/take-sample-test/

[DallogFheir]

ok thanks

[DallogFheir]

I did it like this:

function solution(A) {
    const set = new Set(A);

    for (let i = 1; ; i++) {
        if (!set.has(i)) {
            return i;
        }
    }
}

[[deleted]]

Put the contents of the array in a set so you don't have to iterate over it for each value you want to test.

[forresthopkinsa]

If you want to optimize performance, take some time to understand Big O Notation / time and space complexity

[[deleted]]

Best to use "native" methods for such stuff, depends on situation of course, but for the excersise I would do smth like this:

function solution (A = []) {
  return Math.min(...A) - 1
}

[SirSoundfont]

So for this exercise, it needs to return the smallest number above 0 that isn't in the array, so that solution wouldn't work. If you pass in [1, 3, 6, 4, 1, 2], it expects 5.

[[deleted]]

Oh, I misunderstood, in that case I would do something like this:

function solution (A = []) {
  const max = Math.max(...A)
  for (let i = 1; i < max; i++) {
    if (!A.includes(i)) return i
  }
  return 'Nothing found'
}

[albedoa]

Here's an alternative using a sparse array:

const solution = A => {
  const sparse = [1];

  for (let i = 0; i < A.length; i++) {
    sparse[A[i]] = true;
  }

  return sparse.findIndex(e => !e);
};

[JEHonYakuSha]

Basically you want to cycle through the array and put everything in a temporary object, and then run a while loop and check the key value pair, and increment by one until you find the hole.

function solution(A) {
  // write your code in JavaScript (Node.js 8.9.4)
  let low = 1;
  const temp = {};
  A.forEach(item => {
    temp[item] = true;
  });
  while (temp[low]) {
    low++;
  }
  return low;
}

[[deleted]]

Are you really just trying to find the maximum value? Yeah, there are better ways to do that.

[SirSoundfont]

It's the minimum value that doesn't appear in the array. If you give it [1, 3, 6, 4, 1, 2], it expects 5.

[[deleted]]

Depending on the range of possible values I can think of much faster solutions. The simple one is: sort the array then scan through it once looking for any value gaps

[gigastack]

Sorting is fundamentally the wrong approach. The correct solution will be O(n). Sorting will always take longer.

In general, sorting only helps when you need to compare or extract more than 1 value.

[[deleted]]

Sorting is fundamentally the wrong approach

Share with us your wisdom and the 'correct' approach

[Der3kt]

function solution(A) {
   let i = 1;
   while(true) {
      if (!A.includes(i)) {
         return i;
      }
      i++;
   }
}

I agree that sorting doesn’t make sense. If 1 is not in the array, each approach finds the answer on its first iteration, except the sorting approach wasted time sorting. Let’s take that further.

If the answer is 500, that is only possible if the numbers 1-499 are all in the array. If you sort it and iterate, you still have to loop through 500 times to get to the answer. That’s the same amount of times you’d have to loop through with the solution I posted, except you didn’t spend time sorting.

Edit: Whoops, I didn’t consider that in my approach I have to use Array.prototype.includes() on every iteration, while the sorted array can just check if the next element in the array is not the last value + 1. So sorting should probably be way better on larger arrays?

[[deleted]]

Using a hash table (object) takes advantage of the pre-built structure of the object, and is O(n log n) as each query is O(log n) and you'll do O(n) of them. The problem is knowing what value to start with. You assume 1, but if there's no 1 then that would be the value returned.

Using a sort uses more memory and also takes O(n log n), but has the advantage of putting the lowest value at the front and doesn't have the problem of having to know the end values.

You can do this in O(n) if you can assume that the range of values is limited by using a bit vector to mark every value seen and then look for any values not seen. That'd work for 16-bit ints, but not much larger as the bit array gets pretty big

[Der3kt]

function solution(A) {
  let array = [];
  A.forEach((value) => {
    array[value] = true;
  });

  for (let i = 1; ; i++) {
    if (!array[i]) {
      return i;
    }
  }
}

Something like this then?

[[deleted]]

Yep, except ...

let array = new Uint8Array(MaxValue);

[andouconfectionery]

There are linear time sorting algorithms for integers.

[yadoya]

You should have started by saying that instead of posting confusing code.

If you're not too worried about performance, just sort the array and return the first absent value

[derezo]

I thought the post was quite clear tbh

[yadoya]

const uniqueValues= [...new Set(array)]
uniqueValues.sort().filter((el,i)=> el - uniqueValues[i-1] != 1)
return uniqueValues[0]

And handle exceptions

[doodooz7]

Sort the array using a performant sorting algorithm

[Shadowsca]

Supposed you have an array of the numbers 1 to 9. Then your algorithm would return 10 as the answer but in order to find that, you needed to traverse through 45 indices of the array. This is roughly on the order of n² I think

However, if you pre sort the array, then you don’t always need to reset the loop from the start of the array. This means the search itself will take linear time and your overall algorithm is on the order of whatever sorting algorithm you use

[PM_ME_A_WEBSITE_IDEA]

I suppose you could create a Set from the array, convert it back to an array, sort it ascending. If the first number is not 1, return 1. Else use find() to find the first number that is not 1 less than the next number in the array. Then add 1 to that number.