Return the lowest positive integer value not contained in an int[] array, optimized for performance

Question

I was doing an assessment online to return the lowest positive value of an int not in the array.

I used this code:

class Solution
{
    public static int solution(int[] A)
    {
        int hold = 1;

        while (A.Contains(hold))
        {
            hold++;
        }

        return hold;
    }
}

It works and received 100% for correctness however got 25% for efficiency. How can I make this more efficient? The website states that the testing can be of an array up to 100,000 values. My coding skills outside of WinForms are lacking and I would appreciate any help in order to make my code more efficient.

An example test would be [1, 3, 6, 4, 1, 2], and it would return 5.

Well, you could make that O(n) by iterating the array only once. — Fildor, Mar 12 '23 at 10:47
@Charlieface no, an example test would be [1, 3, 6, 4, 1, 2] and it would return 5 — carp200, Mar 12 '23 at 11:47
Related language-agnostic question: [Find the smallest positive integer that does not occur in a given sequence](https://stackoverflow.com/questions/51719848/find-the-smallest-positive-integer-that-does-not-occur-in-a-given-sequence). — Theodor Zoulias, Mar 12 '23 at 14:16
@TheodorZoulias not sure how i didnt see that - exact same website i was using. thanks for sharing! — carp200, Mar 12 '23 at 17:47

shingo · Answer 1 · 2023-03-12T14:24:31.003

2

This code tests whether a continuous positive integer exists, so you can sort the array first, then find out the discontinuous position.

public static int solution(int[] A)
{
    Array.Sort(A);

    var j = Array.IndexOf(A, 1);
    if (j < 0)
        return 1;

    int k = 1;
    for (int i = j + 1; i < A.Length; i++)
    {
        if (A[i] - k > 1)
            break;
        k = A[i];
    }
    return k + 1;
}

edited Mar 12 '23 at 14:24

answered Mar 12 '23 at 11:04

shingo

18,436
5
23
42

using the test data [1, 3, 6, 4, 1, 2], this should return 5, however it returns 1 – carp200 Mar 12 '23 at 11:45
A minor flaw of this solution is that it modifies its argument, which is generally undesirable. – Theodor Zoulias Mar 12 '23 at 12:38
tested this on the website, 60% correctness (failed 3 tests - i wonder if that's related to the negative number/zero bug @TheodorZoulias noticed), and 50% on performance. performance is better than my original attempt but not as fast/efficient as the accepted solution (100% on both) – carp200 Mar 12 '23 at 13:04
1

@TheodorZoulias Thank you for pointing out the bug. Update again, now I will find the first 1 first. – shingo Mar 12 '23 at 14:43

score 1 · Accepted Answer · answered Mar 12 '23 at 10:52

1

The easiest change would be to turn the array into a HashSet<int>. This reduces the lookup time A.Contains(hold) from O(n) to essentially O(1):

    public static int solution(int[] A)
    {
        var hashSet = new HashSet<int>(A);
        int hold = 1;

        while (hashSet.Contains(hold))
        {
            hold++;
        }

        return hold;
    }

answered Mar 12 '23 at 10:52

Klaus Gütter

11,151
6
31
36

Optimization for memory: add only positive numbers in the `hashSet`. Non-positive numbers can be safely ignored. – Theodor Zoulias Mar 12 '23 at 14:25

Theodor Zoulias · Answer 3 · 2023-03-12T14:08:08.400

Here is a LINQ approach. It's unlikely to be as fast as the solutions in the other answers. It might be a bit cuter though:

public static int GetLowestPositiveNumberNotContained(int[] array)
{
    return array
        .Where(n => n > 0)
        .Distinct()
        .Order()
        .Append(-1)
        .Zip(Enumerable.Range(1, Array.MaxLength + 1))
        .First(e => e.First != e.Second)
        .Second;
}

Explanation:

We filter out the non-positive numbers in the array.
We filter out the duplicates.
We sort the filtered query (unique positive numbers in the array).
We append a negative number (sentinel) at the end, so that we don't fall into the Mediterranean sea.
We create pairs by zipping the query (sorted unique positive numbers), with an incremental sequence of numbers that starts from 1.
We find the first pair having non-equal members.
The second member of this pair is the number that we are searching for. It's the lowest positive number not contained in the array.

Online demo.

Return the lowest positive integer value not contained in an int[] array, optimized for performance

3 Answers3