Register for our webinar

How to Nail your next Technical Interview

1 hour
Loading...
1
Enter details
2
Select webinar slot
*Invalid Name
*Invalid Name
By sharing your contact details, you agree to our privacy policy.
Step 1
Step 2
Congratulations!
You have registered for our webinar
check-mark
Oops! Something went wrong while submitting the form.
1
Enter details
2
Select webinar slot
*All webinar slots are in the Asia/Kolkata timezone
Step 1
Step 2
check-mark
Confirmed
You are scheduled with Interview Kickstart.
Redirecting...
Oops! Something went wrong while submitting the form.
close-icon
Iks white logo

You may be missing out on a 66.5% salary hike*

Nick Camilleri

Head of Career Skills Development & Coaching
*Based on past data of successful IK students
Iks white logo
Help us know you better!

How many years of coding experience do you have?

Thank you! Your submission has been received!
Oops! Something went wrong while submitting the form.
Iks white logo

FREE course on 'Sorting Algorithms' by Omkar Deshpande (Stanford PhD, Head of Curriculum, IK)

Thank you! Please check your inbox for the course details.
Oops! Something went wrong while submitting the form.
closeAbout usWhy usInstructorsReviewsCostFAQContactBlogRegister for Webinar
Our June 2021 cohorts are filling up quickly. Join our free webinar to Uplevel your career
close

Sort Colors Problem

Given some balls of three colors arranged in a line, rearrange them such that all the red balls go first, then green and then blue ones.

Do rearrange the balls in place. A solution that simply counts colors and overwrites the array is not the one we are looking for.

This is an important problem in search algorithms theory proposed by Dutch computer scientist Edsger Dijkstra. Dutch national flag has three colors (albeit different from ones used in this problem).

Example

Input: [G, B, G, G, R, B, R, G]

Output: [R, R, G, G, G, G, B, B]

There are a total of 2 red, 4 green and 2 blue balls. In this order they appear in the correct output.

Notes

Input Parameters: An array of characters named balls, consisting of letters from {‘R’, ‘G’, ‘B’}.

Output: Return type is void. Modify the input character array by rearranging the characters in-place.

Constraints:

• 1

• Do this in ONE pass over the array - NOT TWO passes, just one pass.

• Solution is only allowed to use constant extra memory.

Solution

As mentioned in the notes: A naive solution to this problem, is to simply count how many balls of each color, and then overwrite the array with that many balls in the expected order of colors. This is not the solution we (and an interviewer would) look for here.

To solve the problem, taking one example will help. Try to play with:

[R, G, G, R, G, B, G, B, R, R, R, G]

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

Suppose our initial array is: [array to process]

----

Now "suppose" after processing some part of the given array, we are able to maintain its structure like:

[R, R, ..., R, R][G, G, ..., G, G][remaining array to process][B, B, ..., B, B]

Just assume that we are able to maintain this structure somehow, currently do not worry about how!

----

If we can maintain the same structure after processing the first ball of "remaining array to process" in O(1) time, then it means now we have to solve the same problem with the reduced size of "remaining array to process".

After we have processed the first ball, we repeat the process for the next ball; that also takes O(1) time and maintains the same structure! So at the end we will be able to maintain the same structure and that will be the sorted array! We are taking O(1) time to process each character hence the time complexity will also be n * O(1) that is O(n)! Let's think how can we maintain the same structure when first letter in the "remaining array to process" is:

----

'R', which means array is:

[R, R, ..., R, R]['G', G, ..., G, G]['R' + other remaining array to process][B, B, ..., B, B]

What should we do with 'R' to maintain the same structure? Swapping it with the leftmost 'G'?

Yes, that is possible and that will maintain the structure with only one swap, "assuming that we have the index of the leftmost G".

So now our array will look like:

[R, R, ..., R, R, 'R'][G, ..., G, G, 'G'][other remaining array to process][B, B, ..., B, B]

----

'G' which means array is:

[R, R, ..., R, R][G, G, ..., G, G]['G' + other remaining array to process][B, B, ..., B, B]

What should we do with 'G' to maintain the same structure?

Nothing to do, just go to the next character!

So now our array will look like:

[R, R, ..., R, R][G, G, ..., G, G, 'G'][other remaining array to process][B, B, ..., B, B]

----

'B' which means array is:

[R, R, ..., R, R][G, G, ..., G, G]['B' + other remaining array to process + 'last character'][B, B, ..., B, B]

What should we do with 'B' to maintain the same structure?

Swap 'B' with the 'last character' of the "remaining array to process"!  Yes that is possible and that will maintain the structure with only one swap "assuming that we have the index of last character". So now our array will look like:

[R, R, ..., R, R][G, G, ..., G, G]['last character' + other remaining array to process]['B', B, B, ..., B, B]

----

We Made Some Assumptions:

1) When the first character is 'R', we assumed that "we have the index of the leftmost G".

2) When the first character is 'B', we assumed that "we have the index of the last character".

So somehow we need to maintain these two indices and we will be able to solve the problem by following the steps above.

Also when we are starting we can take,

[R, R, ..., R, R], [G, G, ..., G, G] and [B, B, ..., B, B] parts = "". And then start our solution!

The idea sounds complex but the code can be very simple!

Time Complexity:

O(n).

Auxiliary Space Used:

O(1) as we are using only constant extra space.

Space Complexity:

O(n).

Try yourself in the Editor

Note: Input and Output will already be taken care of.

Sort Colors Problem

Given some balls of three colors arranged in a line, rearrange them such that all the red balls go first, then green and then blue ones.

Do rearrange the balls in place. A solution that simply counts colors and overwrites the array is not the one we are looking for.

This is an important problem in search algorithms theory proposed by Dutch computer scientist Edsger Dijkstra. Dutch national flag has three colors (albeit different from ones used in this problem).

Example

Input: [G, B, G, G, R, B, R, G]

Output: [R, R, G, G, G, G, B, B]

There are a total of 2 red, 4 green and 2 blue balls. In this order they appear in the correct output.

Notes

Input Parameters: An array of characters named balls, consisting of letters from {‘R’, ‘G’, ‘B’}.

Output: Return type is void. Modify the input character array by rearranging the characters in-place.

Constraints:

• 1

• Do this in ONE pass over the array - NOT TWO passes, just one pass.

• Solution is only allowed to use constant extra memory.

Solution

As mentioned in the notes: A naive solution to this problem, is to simply count how many balls of each color, and then overwrite the array with that many balls in the expected order of colors. This is not the solution we (and an interviewer would) look for here.

To solve the problem, taking one example will help. Try to play with:

[R, G, G, R, G, B, G, B, R, R, R, G]

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

Suppose our initial array is: [array to process]

----

Now "suppose" after processing some part of the given array, we are able to maintain its structure like:

[R, R, ..., R, R][G, G, ..., G, G][remaining array to process][B, B, ..., B, B]

Just assume that we are able to maintain this structure somehow, currently do not worry about how!

----

If we can maintain the same structure after processing the first ball of "remaining array to process" in O(1) time, then it means now we have to solve the same problem with the reduced size of "remaining array to process".

After we have processed the first ball, we repeat the process for the next ball; that also takes O(1) time and maintains the same structure! So at the end we will be able to maintain the same structure and that will be the sorted array! We are taking O(1) time to process each character hence the time complexity will also be n * O(1) that is O(n)! Let's think how can we maintain the same structure when first letter in the "remaining array to process" is:

----

'R', which means array is:

[R, R, ..., R, R]['G', G, ..., G, G]['R' + other remaining array to process][B, B, ..., B, B]

What should we do with 'R' to maintain the same structure? Swapping it with the leftmost 'G'?

Yes, that is possible and that will maintain the structure with only one swap, "assuming that we have the index of the leftmost G".

So now our array will look like:

[R, R, ..., R, R, 'R'][G, ..., G, G, 'G'][other remaining array to process][B, B, ..., B, B]

----

'G' which means array is:

[R, R, ..., R, R][G, G, ..., G, G]['G' + other remaining array to process][B, B, ..., B, B]

What should we do with 'G' to maintain the same structure?

Nothing to do, just go to the next character!

So now our array will look like:

[R, R, ..., R, R][G, G, ..., G, G, 'G'][other remaining array to process][B, B, ..., B, B]

----

'B' which means array is:

[R, R, ..., R, R][G, G, ..., G, G]['B' + other remaining array to process + 'last character'][B, B, ..., B, B]

What should we do with 'B' to maintain the same structure?

Swap 'B' with the 'last character' of the "remaining array to process"!  Yes that is possible and that will maintain the structure with only one swap "assuming that we have the index of last character". So now our array will look like:

[R, R, ..., R, R][G, G, ..., G, G]['last character' + other remaining array to process]['B', B, B, ..., B, B]

----

We Made Some Assumptions:

1) When the first character is 'R', we assumed that "we have the index of the leftmost G".

2) When the first character is 'B', we assumed that "we have the index of the last character".

So somehow we need to maintain these two indices and we will be able to solve the problem by following the steps above.

Also when we are starting we can take,

[R, R, ..., R, R], [G, G, ..., G, G] and [B, B, ..., B, B] parts = "". And then start our solution!

The idea sounds complex but the code can be very simple!

Time Complexity:

O(n).

Auxiliary Space Used:

O(1) as we are using only constant extra space.

Space Complexity:

O(n).

Worried About Failing Tech Interviews?

Attend our free webinar to amp up your career and get the salary you deserve.

Ryan-image
Hosted By
Ryan Valles
Founder, Interview Kickstart
blue tick
Accelerate your Interview prep with Tier-1 tech instructors
blue tick
360° courses that have helped 14,000+ tech professionals
blue tick
100% money-back guarantee*
Register for Webinar
All Blog Posts