# PermCheck Codility with time complexity of O(N)

I have this solution for Codility's PermCheck problem. In summary, the task is to check whether array A contains each number in $1 \ldots N$ exactly once.

I got 100% for it but I got a time complexity of $O(N * log(N))$ or $O(N)$. How could I make this code $O(N)$? Could you also give a brief description of what makes code $O(N)$?

Array.Sort(A);
if(A[0] == 1 && A.Length == 1) return 1;
if(A[0] != 1) return 0;

int n = 0;
for(int i = 0; i < A.Length; i++)
{
if(i < A.Length - 1)
{
if(A[i+1] == A[i] + 1)
{
n += 1;
}
else
{
return 0;
}
}
}
return 1;
• Taken from the site you linked: "Copyright 2009–2014 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited." I am not sure whether you are even allowed to ask this question... – Vogel612 Nov 9 '14 at 17:51
• Well i'm just asking to review my code from a question which they have public. Besides i'm not exactly the first person in the queue to ask for a review of their code from this site. So if you could help and just let me know at the very least how this code doesn't truly represent an O(N) time complexity :) Cheers – HusCode Nov 9 '14 at 17:56

This code involves sorting an array of $N$ elements, so it has $O(N * log N)$ time complexity. To achieve $O(N)$ time complexity, you need to avoid sorting input data. Instead, you can create an array of $N$ bools to check that each number from $1$ to $N$ is present in the input array.

• Thankyou. I managed to solve it using a boolean array that you suggested and you gave a clear answer. Cool! – HusCode Nov 9 '14 at 18:04

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

So, who said that you will have a disordered sequence of 1, 2, 3, 4... You might get N = 6, and array A[1, 4, 5, 7, 1000, 6].

So, your solutions are wrong. I suggest you to use HashTable to store a value and check if it has one or not.

Although I don't know C#, I can make some observations based on other C-family languages.

Firstly, the code appears incomplete. I'll have to assume that this is the body of a function declared to accept an array A and return a boolean.

Array.Sort(A);

Obviously, sorting is O(n log n) in the general case, so the method can't scale better than that.

if(A[0] == 1 && A.Length == 1) return 1;
if(A[0] != 1) return 0;

There's no need to test A[0] twice, if we swap the order of these tests. But we do need to check that A is not empty before accessing A[0].

int n = 0;

What's n for? It's assigned but never used.

for(int i = 0; i < A.Length; i++)
{
if(i < A.Length - 1)
{
/// code
}
}

That simplifies to

for(int i = 0;  i < A.Length - 1;  i++)
{
/// code
}

The whole loop and the prior tests (for the A.Length <= 1 cases) simplifies to just

for (int i = 0;  i < A.Length;  i++)
if (A[i] != i+1)
return 0;
return 1;

No need for those A[0] checks at all.

# My version:

Array.Sort(A);
for (int i = 0;  i < A.Length;  ++i)
if (A[i] != i+1)
return 0;
return 1;

# Algorithm improvements

As other answers hint, to get O(n) speed (at a cost of O(n) memory use), we'll want to allocate a bitmap of size A.Length, and populate the entries as we go. We can exit early whenever we see an out-of-range value or a repeated value (i.e. an already set bit). If no value causes early exit, then we must have seen every integer in the range exactly once.

That would look something like:

// UNTESTED!
int N = A.Length;
bool[] b = new bool[N];
for (int i = 0;  i < N;  ++i) {
int x = A[i];
if (x < 0 || x >= N || b[x])
return 0;
b[x] = true;
}
return 1;
int l = A.Length;
int [] B = A.Distinct().ToArray();
Array.Sort(B);
int lB = B.Length;

if ( l <=0) return 0;
if (l == 1 && A[0] == 1) return 1;

return (B[lB-1] == lB && lB == l)? 1 : 0;

I've got 100% too and $O(N)$ or $O(N * log(N))$ in time complexity

• You have presented an alternative solution, but haven't reviewed the code. Please edit it to explain your reasoning (how your solution works and how it improves upon the original) so that everyone can learn from your thought process. – Toby Speight Jan 31 '18 at 14:53

An alternative algorithm is possible, with time complexity $O(N)$ or $O(N * log(N))$, passing all test cases. See the code below, with inline comments explaining the alternative logic:

// declare at the top
using System.Collections.Generic;

// ...

Dictionary<int, int> dict = new Dictionary<int, int>();

// loop through array to get dict
for (int i = 0; i < A.Length; i++)
{
if (A[i] <= 0) // Remove minus
{
continue;
}
if (dict.ContainsKey(A[i])) // Remove duplicates
{
continue;
}
}
// loop through dict for first missing number or return next number
for (int i = 1; i <= dict.Count + 1; i++)
{
if (!dict.ContainsKey(i))
{
return i; // return first item not in dic
}
else
{
continue;
}
return i; // return value higher then dict i.e. [1,2,3] = 4

}

return 0; // you don't ever get here