🌀 Cycle Sort: Asked in Amazon, Google, and Microsoft

Hello folks 👋,

Recently, I came across Cycle Sort, and it instantly caught my attention due to its simplicity and power, especially in solving some tricky array problems. It's also been asked in interviews at Amazon, Google, and Microsoft — so it's definitely worth knowing!

In this post, I'll explain Cycle Sort, when to use it, and show you some popular problems that can be solved using it.

📘 What is Cycle Sort?
Cycle Sort is a sorting algorithm that works by placing each element at its correct index in the minimum number of writes.
It's mainly useful when you’re dealing with arrays where:

All numbers are in a range (like 0 to N or 1 to N)
The array may contain missing or duplicate values
It is an in-place sorting algorithm with O(n) time complexity in the best case and also uses O(1) space.

⏰ When to Use Cycle Sort?
Use Cycle Sort when:

You're given an array with elements from 1 to N or 0 to N
You're solving problems related to:
Missing numbers
Duplicate numbers
Correct positioning based on value
It’s not a general-purpose sorting algorithm, but it’s perfect for certain types of interview problems.

✅ Problems Solved Using Cycle Sort
Here are some important problems you can easily solve using Cycle Sort technique:

please find the problems with solutions on my GitHub :
https://github.com/br-lovanshi/Python_basic_to_advance

• Solved Problems:
  • ✅ Missing Number (LeetCode)
  • ✅ Find All Numbers Disappeared in an Array
  • ✅ Find the Duplicate Number
  • ✅ First Missing Positive
  • ✅ Set Mismatch

public class CycleSort {

    public static void cycleSort(int[] arr) {
        int i = 0;
        while (i < arr.length) {
            int correctIndex = arr[i] - 1;
            if (arr[i] != arr[correctIndex]) {
                // swap arr[i] with arr[correctIndex]
                int temp = arr[i];
                arr[i] = arr[correctIndex];
                arr[correctIndex] = temp;
            } else {
                i++;
            }
        }
    }

    public static void main(String[] args) {
        int[] nums = {3, 5, 2, 1, 4};
        cycleSort(nums);
        System.out.print("Sorted array: ");
        for (int num : nums) {
            System.out.print(num + " ");
        }
    }
}

I’ve solved all of these using Cycle Sort, and the logic becomes very clean and easy once you understand the concept.

Cycle Sort is one of those hidden gems in DSA — not commonly used in real-world sorting tasks, but incredibly powerful for specific interview questions.

If you're preparing for top tech interviews, I highly recommend learning it and practicing the problems above!

Let me know what you think — and feel free to share more problems where this helped you!

Happy coding! 🚀