SORTING 0S,1S,2S

 

Sorting 0s, 1s, and 2s – Dutch National Flag Algorithm

Introduction

This problem involves sorting an array containing only 0s, 1s, and 2s in ascending order. The challenge is to solve it without using built-in sorting functions and ideally in a single pass with constant space.

Problem Statement

Given an array arr[] containing only:

  • 0s

  • 1s

  • 2s

Sort the array in ascending order.

Example

Input:

arr = [0, 1, 2, 0, 1, 2]

Output:

[0, 0, 1, 1, 2, 2]

Solution Code

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

        while (mid <= high) {
            if (arr[mid] == 0) {
                int temp = arr[low];
                arr[low] = arr[mid];
                arr[mid] = temp;

                low++;
                mid++;
            } 
            else if (arr[mid] == 1) {
                mid++;
            } 
            else { // arr[mid] == 2
                int temp = arr[mid];
                arr[mid] = arr[high];
                arr[high] = temp;

                high--;
            }
        }
    }
}

Approach Used: Dutch National Flag Algorithm

Idea

We divide the array into three parts:

  • 0s region = beginning

  • 1s region = middle

  • 2s region = end

We use three pointers:

  • low = for placing 0s

  • mid = current element

  • high = for placing 2s

How It Works

  1. Initialize:

    • low = 0, mid = 0, high = n - 1

  2. Traverse while mid <= high:

    • If arr[mid] == 0
      Swap with arr[low], increment both low and mid

    • If arr[mid] == 1
       Just move mid

    • If arr[mid] == 2
      Swap with arr[high], decrement high

Why This Approach Was Chosen

  • Solves the problem in one pass (O(n))

  • Uses constant extra space (O(1))

  • Much more efficient than sorting (O(n log n))

  • Specifically designed for arrays with limited values (0,1,2)

Alternative Approaches

  • Counting approach
    Count number of 0s, 1s, 2s and overwrite array
     Simple
     Requires two passes

  • Built-in sort()
     Not allowed in this problem

Why Dutch Flag?
Because it satisfies both:

  • One-pass requirement

  • Constant space constraint

Time and Space Complexity

  • Time Complexity: O(n)

  • Space Complexity: O(1)

Important Observation

  • When swapping with high, we do not increment mid
     Because the swapped element needs to be checked again

Conclusion

The Dutch National Flag algorithm is an efficient and elegant solution for sorting arrays containing only 0s, 1s, and 2s. It meets all constraints of the problem by performing the task in a single traversal with constant space, making it the optimal approach.

Comments

Post a Comment

Popular posts from this blog

THE DELIVERY MAN

  The Delivery Man – Python List Operations  Introduction Lists in Python are used to store multiple items in a single variable. They are flexible, allowing us to add, remove, update, and manipulate elements easily. In this task, different list operations are performed to simulate a delivery man's workflow. 1. Creating a list and accessing an item items = ["Notebook", "Pencil", "Eraser", "Ruler", "Marker"] print(items[2]) Approach: Indexing Why: Lists use zero-based indexing, so the third item is accessed using index 2. 2. Adding a new item items.append("Glue Stick") print(items) Approach: append() method Why: It adds an item at the end of the list, which is ideal for adding new deliveries. 3. Inserting an item items.insert(2, "Highlighter") print(items) Approach: insert() method Why: Used when we need to add an item at a specific position instead of the end. 4. Removing an item items.remove("Ruler...
Read more

EC2 LAUNCHING

  EC2 Step 1: Launch EC2 Instance Go to: AWS Console --> EC2 --> Launch Instance Configure: Name : my-web-server AMI : Amazon Linux 2 (easy for beginners) Instance Type : t2.micro (free tier) Step 2: Key Pair Create or select a key pair. Step 3: Network Settings  Allow these: SSH (port 22) --> for login  HTTP (port 80) --> for web access Step 4: Launch Instance Click Launch Instance Step 5: Connect to Instance Use: EC2 --> Connect --> EC2 Instance Connect (easiest) OR via terminal: with this command. for this you have to download the pem files while selecting the key pair.  ssh -i your-key.pem ec2-user@<public-ip> Step 6: Install Web Server For Amazon Linux: sudo yum update -y sudo yum install httpd -y Step 7: Start Web Server sudo systemctl start httpd sudo systemctl enable httpd Step 8: Add a Web Page echo "Hello from EC2" | sudo tee /var/www/html/index.html Step 9: Get Public IP Go to EC2 d...
Read more

SORT A LINKED LIST USING MERGE SORT

  Sort a Linked List using Merge Sort Introduction Sorting a linked list efficiently is a common problem in data structures. Unlike arrays, linked lists do not allow direct access to elements, so algorithms like quicksort are not ideal. Merge Sort is the best choice for linked lists because: It does not require random access It works efficiently with node-based structures Problem Statement Given the head of a linked list: Sort the list in ascending order Return the sorted linked list Example Input: 10 -> 30 -> 20 -> 40 -> 60 -> 50 Output: 10 -> 20 -> 30 -> 40 -> 50 -> 60 Solution Code class Solution: def mergeSort(self, head): if not head or not head.next: return head mid = self.getMiddle(head) next_to_mid = mid.next mid.next = None left = self.mergeSort(head) right = self.mergeSort(next_to_mid) return self.merge(left, right) def getMiddle(self,...
Read more