Understanding Big-O with a specific example

Question

I am working on a rather simple question, to make sure that I understand these concepts.

The question is: there exists an array A of n elements, either being RED, WHITE, or BLUE. Rearrange the array such that all WHITE elements come before all BLUE elements, and all BLUE elements come before all RED elements. Construct an algorithm in O(n) time and O(1) space.

From my understanding, the pseudocode for the solution would be:

numW = numB = 0
for i = 0 to n:
    if ARRAY[i] == WHITE:
        numW++
    else if ARRAY[i] == BLUE:
        numB++

for i = 0 to n:
    if numW > 0:
        ARRAY[i] = WHITE
        numW--
    else if numB > 0:
        ARRAY[i] = BLUE
        numB--
    else:
        ARRAY[i] = RED

I believe it is O(n) because it runs through the loop twice and O(2n) is in O(n). I believe the space is O(1) because it is not dependent on the overall number of elements i.e. there will always be a count for each

Is my understanding correct?

I'm not sure your approach is correct. You're not actually moving elements; rather, you're calculating the number of each element, and then filling the array from start to end for each color. That may work for simple types, but what happens when you have references to objects? This same logic won't work. — Kenneth K., May 15 '18 at 00:01
O(2n) is O(n) so going through the array twice doesn't break that rule. O(1) means that memory is fixed cost. You are adding 3 vars independent on N. This should also be fine. It gets trickier if you want to do it in 1 pass though, which is possible. — Michael Dorgan, May 15 '18 at 00:07
@KennethK - He's basically doing what a counting sort does by recreate the data from counts. That is O(n) and should be fine. Because he knows there are only 3 types, he is also in O(1) for vars. I think it is a fine solution. — Michael Dorgan, May 15 '18 at 00:10
@MichaelDorgan "sorting" part there is easy to conceptualize, I can't think of a way to do it in O(1) right off the bat though — basil, May 15 '18 at 00:11
@basil your understanding is correct. Time Complexity is O(n) and space is O(1). — nice_dev, May 15 '18 at 06:20
@basil - O(1) - Can't think of a way without having to read all the data at least once either. Doing it with just 1 iteration can be done with a huge lookup table using the RWB data as an index or with a method where you keep pointers to both ends of the data and swap as you go without building up counts. — Michael Dorgan, May 15 '18 at 16:59

score 1 · Answer 1 · answered May 15 '18 at 00:08

1

If it's linear time, and your algorithm appears to be, then it's O(n) as you suspect. There's a great summary here: Big-O for Eight Year Olds?

answered May 15 '18 at 00:08

David Gaertner

386
2
7

Hmm, I feel conflicted about posting a link and not explaining the gist of why it is applicable to this answer. Following the link, there are also many answers, most of which do not mention O(n) complexity, because the question did not mention it either. How would you reassure the OP that the answer is indeed O(n) time and O(1) space? – tucuxi May 15 '18 at 17:58
The OP needs to know that any positive coefficient of n is irrelevant when classifying the run time as O(n). A line is a line, and after a million iterations, the slope isn't as important relative to different algorithms that are better (e.g., O(log n)) or worse (O(n^2)). – David Gaertner May 16 '18 at 19:10

score 1 · Answer 2 · answered May 15 '18 at 09:08

Yes, your solution runs in O(n) time in O(1) space.

Below is my solution which also runs in O(n) time and O(1) space, but also works when we have references to objects, as @kenneth suggested in the comments.

import java.util.Arrays;
import java.util.Random;
import static java.lang.System.out;

class Color{
    char c;
    Color(char c){
        this.c = c;
    }
}

public class Solution {

    private static void rearrangeColors(Color[] collection){
        int ptr = 0;   

        // move all whites to the left

        for(int i=0;i<collection.length;++i){
            if(collection[i].c == 'W'){
                swap(collection,ptr,i);
                ptr++;
            }
        }

        // move all blacks to the left after white       

        for(int i=ptr;i<collection.length;++i){
            if(collection[i].c == 'B'){
                swap(collection,ptr,i);
                ptr++;
            }
        }
    }

    private static void swap(Color[] collection,int ptr1,int ptr2){
        Color temp = collection[ptr1];
        collection[ptr1] = collection[ptr2];
        collection[ptr2] = temp;
    }

    private static void printColors(Color[] collection){
        for(int i=0;i<collection.length;++i){
            out.print(collection[i].c + ( i != collection.length - 1 ? "," : ""));
        }
        out.println();
    }

    public static void main(String[] args) {
        // generate a random collection of 'Color' objects
        Random r = new Random();
        int array_length = r.nextInt(20) + 1;// to add 1 if in case 0 gets generated 
        Color[] collection = new Color[array_length];
        char[] colors_domain = {'B','W','R'};

        for(int i=0;i<collection.length;++i){
            collection[i] = new Color(colors_domain[r.nextInt(3)]);
        }

        // print initial state
        printColors(collection);
        // rearrange them according to the criteria
        rearrangeColors(collection);
        // print final state
        printColors(collection);        
    }

}

Except that the colors are red white and blue, not just black and white. Still this would sort 3 colors fine :) — Michael Dorgan, May 15 '18 at 16:45
Thanks @MichaelDorgan. If there are more colors to rearrange, we will have to make the method `rerrangeColors()` recursive with a queue of ordering of colors as an extra parameter to the method, polling each at a time and applying the same logic to it. — nice_dev, May 15 '18 at 17:00
Not quite. You can sort to either end of the collection at the same time, not just to the front (assuming the collection supports this). That means we can get away with just one loop with 2 compares. That's the beauty of his problem. It is just simple enough to be done in 1 loop with care. Honestly, it sounds like an interview question. — Michael Dorgan, May 15 '18 at 17:05

score 0 · Answer 3 · answered May 15 '18 at 21:49

I won't say this is 100% correct, but a quick test case here did work. If anything, it shows the idea of being able to do it in one pass. Is it faster? Probably not. OP's answer I believe is still the best for this case.

#include <stdio.h>

char temp;
#define SWAP(a,b) { temp = a; a = b; b = temp;}

int main()
{
    int n = 10;
    char arr[] = "RWBRWBRWBR";
    printf("%s\n", arr);

    int white = 0;

    for(int i=0; i<n; i++)
    {
        if(arr[i] == 'B')
        { 
            SWAP(arr[i], arr[n-1]);
            i--; n--;
        }
        else if(arr[i] == 'R')
        {
            SWAP(arr[i], arr[white]);
            white++;
        }
    }

    printf("%s\n", arr);
}

Understanding Big-O with a specific example

3 Answers3