Reduce big-O complexity in sorting algorithm

Question

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?

Off the top of my head: You can sort the array descending (which can be O(n log n)) and then iterate until array[i + 1] < array[i] - 1. — Marvin
– Marvin, Commented Sep 4, 2019 at 13:49
@Marvin Not quite, this would return 7 for [6, 8], when it should return 1. I'd discard any value <=0, then sort in ascending order, and then iterate to return the first index i where sorted_array[i] 1= i. Still O(n log n) for sorting. — joanis
– joanis, Commented Sep 4, 2019 at 14:19
If you let k be the max int allowed (1000000 in the question), you can also solve it in O(max(k,n)) by creating a array flag[] of k+1 bits initialized to all false except flag[0]. Iterate through the array and set flag[array[i]] if array[i]>0. Then find the first i such that flag[i] is not set. For fastest results, use the sorted array algorithm if k < n log n else the flag algorithm. — joanis
– joanis, Commented Sep 4, 2019 at 14:22
Note that since the numbers are integers, sorting can be done in order n using some form of radix sort. Once you have them ordered, then compute the minimum of the complement (on the positive numbers), which can be done in order n too. — aligur
– aligur, Commented Sep 4, 2019 at 14:23
@aligur good point, and with the max being known, radix sort will have a known number of iterations. — joanis
– joanis, Commented Sep 4, 2019 at 14:27

Prune · Accepted Answer · 2019-09-04 17:47:46Z

1

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

answered Sep 4, 2019 at 17:47

Prune

78k14 gold badges63 silver badges83 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Reduce big-O complexity in sorting algorithm

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related