What is the time complexity of Sort Colors?

The optimal solution has a time complexity of O(n).

What data structures are used to solve Sort Colors?

This problem uses Array, Two Pointers, Sorting. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Sort Colors?

Insight 1: The key is to realize that we don't need to use a general-purpose sorting algorithm. Since we know the exact range of values (0, 1, and 2), we can use a more efficient counting or partitioning approach. Insight 2: A two-pointer (or three-pointer) approach allows us to sort the array in-place with constant extra space. This eliminates the need for auxiliary arrays.

Which companies ask LeetCode 75. Sort Colors in interviews?

This problem is frequently asked at Adobe, Amazon, Apple, Arcesium, Autodesk and 26 more companies.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Sort Colors - LeetCode 75 Solution

Q: How to solve Sort Colors?

The provided solution uses the Dutch National Flag algorithm (also known as the three-way partitioning algorithm). This algorithm iterates through the array using a `mid` pointer. It maintains three regions in the array: elements from `0` to `low-1` are all 0s, elements from `low` to `mid-1` are all 1s, and elements from `high+1` to the end of the array are all 2s. The algorithm processes the element at `nums[mid]` based on its value. If it's 0, it swaps it with the element at `nums[low]` and increments both `low` and `mid`. If it's 1, it simply increments `mid`. If it's 2, it swaps it with the element at `nums[high]` and decrements `high`. The algorithm continues until `mid` crosses `high`.

Sort Colors - Complete Solution Guide

Sort Colors is LeetCode problem 75, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue. We will use the integers 0 , 1 , and 2 to represent the color red, white, and blue, respectively. You must solve this problem without using the library's sort function. Example 1: Input: nums = [2,0,2,1,1,0] Output: [0,0,1,1,2,2] Example 2: Input: nums = [2,0,1] Output: [0,1,2] Constraints: n == nums.length 1 <= n <=

Detailed Explanation

The "Sort Colors" problem asks us to sort an array of integers in-place, where each integer represents a color: 0 (red), 1 (white), and 2 (blue). The goal is to rearrange the array so that all the 0s come first, followed by all the 1s, and then all the 2s. We are given that the array contains only 0s, 1s, and 2s, and we must do this without using any built-in sorting functions provided by the programming language.

Solution Approach

The provided solution uses the Dutch National Flag algorithm (also known as the three-way partitioning algorithm). This algorithm iterates through the array using a `mid` pointer. It maintains three regions in the array: elements from `0` to `low-1` are all 0s, elements from `low` to `mid-1` are all 1s, and elements from `high+1` to the end of the array are all 2s. The algorithm processes the element at `nums[mid]` based on its value. If it's 0, it swaps it with the element at `nums[low]` and increments both `low` and `mid`. If it's 1, it simply increments `mid`. If it's 2, it swaps it with the element at `nums[high]` and decrements `high`. The algorithm continues until `mid` crosses `high`.

Step-by-Step Algorithm

Step 1: Initialize three pointers: `low` to 0, `mid` to 0, and `high` to `nums.length - 1`.
Step 2: While `mid` is less than or equal to `high`, repeat steps 3-5.
Step 3: If `nums[mid]` is 0, swap `nums[mid]` with `nums[low]`, increment both `low` and `mid`.
Step 4: If `nums[mid]` is 1, increment `mid`.
Step 5: If `nums[mid]` is 2, swap `nums[mid]` with `nums[high]`, decrement `high`. Note that `mid` is not incremented in this case because the swapped element from `high` could be any of the three values (0, 1, or 2) and needs to be checked.
Step 6: The loop terminates when `mid` becomes greater than `high`, at which point the array is sorted.

Key Insights

Insight 1: The key is to realize that we don't need to use a general-purpose sorting algorithm. Since we know the exact range of values (0, 1, and 2), we can use a more efficient counting or partitioning approach.
Insight 2: A two-pointer (or three-pointer) approach allows us to sort the array in-place with constant extra space. This eliminates the need for auxiliary arrays.
Insight 3: Maintaining three pointers (low, mid, high) and using them to partition the array based on the value at the `mid` pointer allows for a single-pass solution.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(1)

Topics

This problem involves: Array, Two Pointers, Sorting.

Companies

Asked at: Adobe, Amazon, Apple, Arcesium, Autodesk, Bloomberg, DE Shaw, Docusign, Flipkart, Groww, Meta, Microsoft, Morgan Stanley, Optum, Oracle, PayPal, PhonePe, Pocket Gems, Salesforce, Samsung, Sprinklr, Swiggy, Target, TikTok, Uber, Walmart Labs, Yahoo, Zoho, Zopsmart, eBay, tcs.

Sort Colors | LeetCode 75

Medium

Array Two Pointers Sorting

Time: O(n)Space: O(1)

Solution Code

Available in:

class Solution {
    public void sortColors(int[] nums) {
        int low = 0, mid = 0, high = nums.length - 1;

        while (mid <= high) {
            if (nums[mid] == 0) {
                int temp = nums[low];
                nums[low] = nums[mid];
                nums[mid] = temp;
                low++;
                mid++;
            } else if (nums[mid] == 1) {
                mid++;
            } else { // nums[mid] == 2
                int temp = nums[high];
                nums[high] = nums[mid];
                nums[mid] = temp;
                high--;
            }
        }
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 75: Sort Colors - Detailed explanation and solution approaches.

Topics

Array Two Pointers Sorting

Companies

AdobeAmazonAppleArcesiumAutodeskBloombergDE ShawDocusign

Stats

Difficulty:Medium

Languages:4

Companies:31

Problem #:75

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

6 steps

1
Step 1: Initialize three pointers: `low` to 0, `mid` to 0, and `high` to `nums.length - 1`.
2
Step 2: While `mid` is less than or equal to `high`, repeat steps 3-5.
3
Step 3: If `nums[mid]` is 0, swap `nums[mid]` with `nums[low]`, increment both `low` and `mid`.
4
Step 4: If `nums[mid]` is 1, increment `mid`.
5
Step 5: If `nums[mid]` is 2, swap `nums[mid]` with `nums[high]`, decrement `high`. Note that `mid` is not incremented in this case because the swapped element from `high` could be any of the three values (0, 1, or 2) and needs to be checked.
6
Step 6: The loop terminates when `mid` becomes greater than `high`, at which point the array is sorted.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(1)

💪 Constant space - Uses same memory regardless of input!

📝

Why?

The time complexity is linear because the `while` loop iterates through the array once. The space complexity is constant because the algorithm does not use any additional data structures that scale with the input size.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Counting Sort

Count the occurrences of 0, 1, and 2, and then rewrite the array based on these counts.

Time: O(n)Space: O(1) since the counts are limited to three possible values, it uses constant extra space.

Trade-offs: While this approach is conceptually simple, it involves two passes over the array (one for counting and one for rewriting). The Dutch National Flag algorithm achieves the same result in a single pass.

✨

Key Insights

1Insight 1: The key is to realize that we don't need to use a general-purpose sorting algorithm. Since we know the exact range of values (0, 1, and 2), we can use a more efficient counting or partitioning approach.
2Insight 2: A two-pointer (or three-pointer) approach allows us to sort the array in-place with constant extra space. This eliminates the need for auxiliary arrays.
3Insight 3: Maintaining three pointers (low, mid, high) and using them to partition the array based on the value at the `mid` pointer allows for a single-pass solution.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Two Pointers

Using two indices to traverse data from different positions simultaneously.

Sorting

Arranging elements in a specific order (ascending/descending).

Edge Cases

Edge case 1: Empty array (`nums` is empty). The algorithm handles this case correctly because the while loop condition `mid <= high` will be false from the beginning, and no operations will be performed. The array remains unchanged (which is already sorted as an empty array).
Edge case 2: Array with all elements being the same (e.g., all 0s, all 1s, or all 2s). The algorithm correctly handles these cases, resulting in the array remaining unchanged or requiring a single pass to put the elements in their correct positions.
Edge case 3: Array with only two distinct colors (e.g., only 0s and 1s). The algorithm still works correctly to sort the array.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Incorrectly incrementing `mid` after swapping `nums[mid]` with `nums[high]`. Since the value at the new `nums[mid]` is unknown (it was swapped from `nums[high]`), it needs to be re-examined. So only `high` is decremented.

✗Common mistake 2: Using a general-purpose sorting algorithm like bubble sort or quicksort. While these algorithms would work, they are less efficient (O(n log n) on average) and unnecessary given the specific constraints of the problem.

✗Common mistake 3: Forgetting the boundary condition for the `while` loop (`mid <= high`). If the loop condition is incorrect, the algorithm may not sort the array correctly or may access the array out of bounds.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Data categorization or classification where data points can belong to a limited number of categories. For example, classifying customer segments into low, medium, and high value.

🏦Real-world scenario 2: Prioritizing tasks in a system with different urgency levels (e.g., high, medium, low). The algorithm can efficiently arrange tasks based on their urgency.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

Medium problems are the bread and butter of technical interviews. Practice explaining your approach before coding.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

👨‍💻 From Experience

This problem pattern appears frequently in real codebases. I've used similar logic when building production systems.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: August 15, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jul 13

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJul 6

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJun 29

❓

Frequently Asked Questions

When should I use in-place modification vs creating a new array?

Use in-place modification when space complexity matters (O(1) space requirement) and the original array can be modified. Create a new array when you need to preserve the original data or when the problem involves significant restructuring that would complicate in-place logic.

How do I avoid infinite loops with two pointers?

Always ensure your loop condition guarantees termination (typically left < right or slow != fast). Move at least one pointer in each iteration, and handle edge cases where pointers might not move (like skipping duplicates). Draw out pointer movement on paper first.

How much time should I spend on a medium problem in interviews?

In a 45-minute interview, aim for: 5-10 minutes understanding and clarifying, 5-10 minutes discussing approach, 20-25 minutes coding, and 5-10 minutes testing. If stuck after 15 minutes of thinking, verbalize your thought process and ask for hints.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Sort Colors"?

For this medium-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether two pointers techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?