CODEWITHSUNDEEP
algorithmloopsiterationbig-o
half of a glazier
half of a glazier

Reputation: 2076

Reduce big-O complexity in sorting algorithm

I made the acquaintance of big-O a couple of weeks ago and am trying to get to grips with it, but although there's a lot of material out there about calculating time complexity, I can't seem to find out how to make algorithms more efficient.

I've been practicing with the the demo challenge in Codility:

Write a function 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.
The given array can have integers between -1 million and 1 million.

I started with a brute-force algorithm: 

public int solution(int[] A)
        {
            for ( int number = 1; number < 1000000; number ++)
            {
                if (doesContain(A, number)){}
                else return i;
            }
            return 0;
        }

This passed all tests for correctness but scored low on performance because the running time was way past the limit, time complexity being O(N**2).

I then tried putting the array into an arraylist, which reduces big-O since each object is "touched" only once, and I can use .Contains which is more efficient than iteration (not sure if that's true; I just sort of remember reading it somewhere).

public int solution(int[] A)
    {
        ArrayList myArr = new ArrayList();
        for (int i=0; i<A.Length; i++)
        {
            myArr.Add(A[i]);
        }
        for ( int i = 1; i < 1000000; i++)
        {
            if (myArr.Contains(i)){}
            else return i;
        }
        return 0;
    }

Alas, the time complexity is still at O(N**2) and I can't find explanations of how to cut down time.

I know I shouldn't be using brute force, but can't seem to think of any other ways... Anyone have an explanation of how to make this algorithm more efficient?

Upvotes: 0

Views: 369

Answers (1)

Prune
Prune

Reputation: 77837

This is a typical interview question. Forget the sort; this is a detection problem, O(n + m) on n elements and a max value of m (which is given as a constant).

boolean found[1000000] = False  /// set all elements to false

for i in A    // check all items in the input array
    if i > 0
        found[i] = True

for i in (0, 1000000)
    if not found[i]
        print "Smallest missing number is", i

Upvotes: 1

Related Questions