CODEWITHSUNDEEP
algorithm
Harly Chen
Harly Chen

Reputation: 63

My solution only use one for loop but why performance is low?

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.

Upvotes: 1

Views: 128

Answers (3)

chux
chux

Reputation: 153640

OP's performance is "low" certainly because it is producing the wrong answers.

return maxInt % 2 == 0 ? maxInt - 1 : maxInt + 1; makes little sense.

Simplify algorithm.

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

Recognize that between values [1...N+1], there must be at least 1 value not in A[]. A[] has, at most, N different values. Pigeonhole principle

Cost O(N) time, O(N) more space solution, no hash table, no BST:

  1. Form an array B[N+1] of T/F values - set all to false. Index this array [1...N+1]. Cost O(N) time, O(N) more space.

  2. Walk array A. For each A[i], test if A[i] <= N (and A[i] >= 1). If A[i] in range, set B[A[i]] = true. Cost O(N) time.

  3. Walk array B. Find the first B[i] that is false, i is the answer. Cost O(N) time.

Sample C code:

size_t LowestMissingPositive(size_t N, const int A[N]) {
  unsigned char Used[N + 1];
  memset(Used, 0, sizeof Used);
  for (size_t i = 0; i < N; i++) {
    if (A[i] >= 1 && (unsigned) A[i] <= N) {
      Used[A[i] - 1] = 1;
    }
  }
  for (size_t i = 0; i <= N; i++) {
    if (!Used[i]) {
      return i + 1;
    }
  }
  // Code never expected to get here.
  return N + 1;
}

Note: "each element of array A is an integer within the range [−1,000,000..1,000,000]" is not really an important stipulation other than the type of A[] needs to handle the range. E.g. at least a 21-bit wide integer type.

Upvotes: 1

Dmitrii Bychenko
Dmitrii Bychenko

Reputation: 186748

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

Upvotes: 1

Daniel
Daniel

Reputation: 7714

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

Upvotes: 0

Related Questions