Sort Colors

Sort Colors 

Problem Statement

You’re given:

  • An array nums[] of integers, where each value is either:

    • 0 = Red 🟥

    • 1 = White ⚪

    • 2 = Blue 🔵

You need to sort the array in-place such that the final order is all 0s, followed by 1s, then 2s.

No using .sort() 

Example

Input:
nums = [2, 0, 2, 1, 1, 0]

Output:
[0, 0, 1, 1, 2, 2]

Best Data Structure for the Job

Simple arrays do the trick!

No need to pull out HashMaps or fancy data structures — all you need are:

  • Some pointer magic

  • A while loop

  • A sprinkle of swaps 

Different Approaches

1) Brute Force (Don't do this in interviews )

Just count how many 0s, 1s, and 2s exist, then rewrite the array.

class Solution {
    public void sortColors(int[] nums) {
        int count0 = 0, count1 = 0, count2 = 0;

        for (int num : nums) {
            if (num == 0) count0++;
            else if (num == 1) count1++;
            else count2++;
        }

        for (int i = 0; i < nums.length; i++) {
            if (i < count0) nums[i] = 0;
            else if (i < count0 + count1) nums[i] = 1;
            else nums[i] = 2;
        }
    }
}

2) Dutch National Flag Algorithm 🇳🇱 (Optimal)

We use three pointers:

  • low: points to where the next 0 should go

  • mid: current element

  • high: where the next 2 should go

We loop through the array once and do swaps on the fly.

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

        while (mid <= high) {
            switch (nums[mid]) {
                case 0:
                    int temp0 = nums[low];
                    nums[low] = nums[mid];
                    nums[mid] = temp0;
                    low++;
                    mid++;
                    break;
                case 1:
                    mid++;
                    break;
                case 2:
                    int temp2 = nums[mid];
                    nums[mid] = nums[high];
                    nums[high] = temp2;
                    high--;
                    break;
            }
        }
    }
}

⚠️ Common Pitfalls

  • Forgetting that 2s go to the end and we don’t increment mid after swapping with high

  • Trying to use a sort function 

  • Using extra space , we sort it in-place

📊 Complexity Summary

Approach        Time Complexity         Space Complexity
Brute Force (count + fill)        O(n)        O(1)
Dutch National Flag        O(n)        O(1) 

🌍 Real-World Use Cases

  • Sorting categorized tickets (e.g., priority levels: high, medium, low)

  • Token-based traffic management (based on 3 priority levels)

  • Color-coded medical alert systems


I hope you found this article insightful! Keep exploring, keep learning, and don’t forget to check back daily for more exciting problem breakdowns. If you know someone who would benefit from this, share it with them and help them grow too! That’s it for today—see you in the next post!

                                                                                                                                         Signing off!! 

                                                                                                Master DSA One Problem at a Time :)

Comments

Post a Comment

Popular posts from this blog

Deep Copy, Deep Dive – Clone That Graph!

Clone Graph – Making a Perfect Copy Today’s problem is a classic graph challenge: deep copying a graph given the reference to one of its nodes. At first glance, it may seem like a straightforward copy-paste job—but in a connected undirected graph, cycles and shared references make it trickier than it looks! Let’s break it down! Best Data Structure for Solving It To tackle this, we use a HashMap (or Dictionary) to keep track of already cloned nodes. Why? Graphs can have cycles. Nodes can be shared across paths. Without tracking, we’d create duplicate nodes or go into infinite recursion. Different Approaches – Brute Force to Optimized 1. DFS Approach (Recursive) We use Depth-First Search to traverse and clone nodes recursively. class Solution { private Map<Node, Node> visited = new HashMap <>(); public Node cloneGraph (Node node) { if (node == null ) return null ; if (visited.containsKey(node)) return visited.get(node); ...
Read more

Subarray Scores: Less Than K Challenge

Subarray Score Problem – Number of Subarrays With Score Less Than k Problem Statement: You are given a positive integer array nums[] and an integer k . A subarray's score is defined as: score = sum(subarray) * length(subarray) Your task is to count the number of non-empty subarrays whose score is strictly less than k . Example 1: Input : nums = [2, 1, 4, 3, 5], k = 10 Output : 6 Explanation : Subarrays with scores less than 10 : [2] → 2 * 1 = 2 [1] → 1 * 1 = 1 [4] → 4 * 1 = 4 [3] → 3 * 1 = 3 [5] → 5 * 1 = 5 [2,1] → (2+1) * 2 = 6 Best Technique – Two Pointers (Sliding Window) This problem is best solved using the Two Pointers (or Sliding Window ) approach, which efficiently tracks the sum of a subarray and its length while iterating through the array. We use two pointers start and end to denote the current window. Expand the window with end , and shrink from start as soon as the score becomes ≥ k . Different Approaches: Approach 1: Bru...
Read more

Pascal's Triangle

 Pascal Vibes — Building Triangles Like a Pro Problem Statement Given an integer numRows , return the first numRows of Pascal's Triangle . Each number in the triangle is the sum of the two numbers directly above it . Example: Input: numRows = 5 Output: [ [ 1 ], [ 1,1 ], [ 1,2,1 ], [ 1,3,3,1 ], [ 1,4,6,4,1 ] ] Best Data Structure for Solving the Problem This is a CLASSIC example of Tabulation-based Dynamic Programming   We're filling a triangle row-by-row where: triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j] So we’ll use: A 2D List<List<Integer>> (or array of arrays) No need for fancy trees, heaps, or graphs here. Just pure math and memory  Different Approaches (from Brute Force to Optimized) Approach 1: Build Row by Row Using Previous Row This is the “OG” method — intuitive and easy to visualize. Start with [1] For each new row: Add 1 at the start and end In-between values are sum of two values above it class ...
Read more