Cyclic Sort Pattern

🔄 Cyclic Sort Animation

Locker 1

👇

Index 0

→ goes to #3

Locker 2

Index 1

Locker 3

Index 2

Locker 4

4✓

Index 3

Locker 5

Index 4

Start: Array [3,1,5,4,2]. Place each number at index = value - 1

Step 1 of 7

Current/Swapping

Correct Position ✓

🎯 Explain Like I'm 5...

Imagine you have 5 parking spots 🅿️ numbered 1, 2, 3, 4, 5. Each car has a number on it and MUST park in its matching spot!

🚗 The Parking Game: Cars are parked in wrong spots: [3, 1, 5, 4, 2]

• Look at spot 1: Car #3 is here! 😱
• Move Car #3 to spot 3 (swap them!)
• Now look at spot 1 again: Car #1 is here? YES! ✅ Move to next spot!
• Look at spot 2: Car #1 is here! Swap with spot 1...
• Keep swapping until EVERY car is in the right spot!

Final: [1, 2, 3, 4, 5] - Perfect parking! 🎉

🚀 Why is it clever? You don't move forward until the current spot has the RIGHT car! Each car only moves ONCE to its correct spot. Super efficient - like everyone finding their assigned seat at a concert! 🎪

When Should You Use This Pattern?

✓Array contains numbers in a given range (like 1 to n)
✓Finding missing or duplicate numbers
✓Need to sort with O(n) time and O(1) space
✓Numbers should be at index = value - 1

📝 Example 1: Find Missing Number

Given array [4, 0, 3, 1] containing n numbers from 0 to n, find the missing number.

Step-by-Step Thinking:

Place each number at its correct index (0 at index 0, 1 at index 1...)
After sorting: [0, 1, _, 3, 4]
Find the index where number doesn't match - that's the missing number!

FindMissingNumber.java

java

public class FindMissingNumber {
    public static int findMissing(int[] nums) {
        int i = 0;
        // Cyclic sort: Place each number at correct index
        while (i < nums.length) {
            // If number is valid and not at correct position
            if (nums[i] < nums.length && nums[i] != nums[nums[i]]) {
                // Swap it to correct position
                swap(nums, i, nums[i]);
            } else {
                i++;
            }
        }
        // Find the missing number
        for (i = 0; i < nums.length; i++) {
            if (nums[i] != i) {
                return i;  // This index is missing its number
            }
        }
        return nums.length;  // All numbers present, missing is n
    }
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    public static void main(String[] args) {
        int[] nums = {4, 0, 3, 1};
        System.out.println("Missing number: " + findMissing(nums));
        // Output: Missing number: 2
    }
}

📝 Example 2: Find All Duplicates

Given array [4, 3, 2, 7, 8, 2, 3, 1] with n numbers from 1 to n, find all duplicates.

FindDuplicates.java

java

import java.util.*;
public class FindDuplicates {
    public static List<Integer> findDuplicates(int[] nums) {
        int i = 0;
        // Cyclic sort
        while (i < nums.length) {
            int correctIndex = nums[i] - 1;  // Number should be at index = value - 1
            if (nums[i] != nums[correctIndex]) {
                swap(nums, i, correctIndex);
            } else {
                i++;
            }
        }
        // Find duplicates
        List<Integer> duplicates = new ArrayList<>();
        for (i = 0; i < nums.length; i++) {
            // If number at index i is not i+1, it's a duplicate
            if (nums[i] != i + 1) {
                duplicates.add(nums[i]);
            }
        }
        return duplicates;
    }
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    public static void main(String[] args) {
        int[] nums = {4, 3, 2, 7, 8, 2, 3, 1};
        List<Integer> duplicates = findDuplicates(nums);
        System.out.println("Duplicates: " + duplicates);
        // Output: Duplicates: [2, 3]
    }
}

📝 Example 3: First Missing Positive

Find the smallest missing positive integer in unsorted array [3, 4, -1, 1].

FirstMissingPositive.java

java

public class FirstMissingPositive {
    public static int firstMissingPositive(int[] nums) {
        int i = 0;
        // Cyclic sort (only for positive numbers in range [1, n])
        while (i < nums.length) {
            int correctIndex = nums[i] - 1;
            // Only sort if number is positive and within range
            if (nums[i] > 0 && nums[i] <= nums.length
                && nums[i] != nums[correctIndex]) {
                swap(nums, i, correctIndex);
            } else {
                i++;
            }
        }
        // Find first missing positive
        for (i = 0; i < nums.length; i++) {
            if (nums[i] != i + 1) {
                return i + 1;  // This positive number is missing
            }
        }
        // All numbers [1, n] are present
        return nums.length + 1;
    }
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    public static void main(String[] args) {
        int[] nums1 = {3, 4, -1, 1};
        int[] nums2 = {7, 8, 9, 11, 12};
        System.out.println("First missing: " + firstMissingPositive(nums1));
        // Output: 2
        System.out.println("First missing: " + firstMissingPositive(nums2));
        // Output: 1
    }
}

🔑 Key Points to Remember

1️⃣Works when numbers are in range [1, n] or [0, n]
2️⃣Place number at index = value - 1 (for 1 to n)
3️⃣Time Complexity: O(n) - each number moved at most once!
4️⃣Space Complexity: O(1) - sorting in-place

💪 Practice Problems

• Find All Missing Numbers
• Find Corrupt Pair (missing and duplicate)
• Find K Missing Positive Numbers
• Set Mismatch