The Question:

Write a function:

class Solution { 
 public int solution(int[] A) {...} 
}

that, given an array A of N integers, returns the smallest positive integer (greater than 0) that does not occur in A.

For example:

Given A = [1, 3, 6, 4, 1, 2], the function should return 5.
Given A = [1, 2, 3], the function should return 4.
Given A = [−1, −3], the function should return 1.

Assume that:

N is an integer within the range [1..100,000]; each element of array A is an integer within the range [−1,000,000..1,000,000].

Complexity:

expected worst-case time complexity is O(N); expected worst-case space complexity is O(N) (not counting the storage required for input arguments).

May I know why I get so low score to answer the question? My solution below:

public static int solution(int[] A) {
    int returnInt = 1;
    int maxInt = 0;

    if (A.length == 0) 
        return returnInt;

    for (int i = 0; i < A.length; i  ) 
    {
        if (A[i] > maxInt) 
            maxInt = A[i];
    }
    
    if (maxInt < returnInt) 
        return returnInt;

    return maxInt % 2 == 0 
        ? maxInt - 1 
        : maxInt   1;
}

The solution has only one for loop, I do not understand why I get a very low score.

CodePudding user response：

You can use HashSet<int> exists to store all positive items of A; then you can check if number 1..exists.Count is in exists.

C# code:

public static int solution(int[] A) {
  if (A is null || A.Length <= 0)
    return 1;

  var exists = new HashSet<int>();

  foreach (int item in A)
    if (item > 0)
      exists.Add(item);

  for (int i = 1; i <= exists.Count;   i)
    if (!exists.Contains(i))
      return i;

  return exists.Count   1;
}

In the worst case we have

Time complexity: O(n), providing that we have good hash function: foreach loop is O(n) - adding to hash set is O(1), for (int i = 1; i <= exists.Count; i) is O(n) as well - Contains is O(1) in case of hash set

Space complexity: O(n) (hash set)

If we can allow ourselves to get slightly worse time complexity - O(n * log(n)) we can have O(1) space complexity only:

C# code:

public static int solution(int[] A) {
  if (A is null || A.Length <= 0)
    return 1;

  Array.Sort(A);

  for (int i = 0, prior = 0; i < A.Length; prior = Math.Clamp(A[i  ], 0, A.Length)) 
    if (A[i] > 0 && A[i] != prior   1)
      return prior   1;

  return Math.Clamp(A[A.Length - 1]   1, 1, A.Length);
}

CodePudding user response：

1. Create a list L with all integers from A which are bigger than 0. O(n)

2. Sort L. O(n lg(n))

3. If L is empty, return 1. If L[0] is not 1, return 1.

4. Iterate through L. If L[i] != i, return i. O(n)

Total complexity = O(n n lg(n)) = O(n lg(n)).