Cyclic Sort (Place 1..n in Correct Positions)

🎯

Cyclic Sort (Place 1..n in Correct Positions)

easyCYCLIC_SORTAmazonGoogle

Imagine you have a row of numbered lockers, but they're all jumbled up. Your task is to quickly rearrange them so that locker number 1 is in the first spot, locker number 2 in the second, and so on.

💡 This problem is about placing numbers in their correct positions in an array. Beginners often struggle because they try sorting with traditional methods instead of leveraging the fact that numbers are from 1 to n, which allows a more efficient approach.

📋

Problem Statement

Given an array containing n integers where each integer is in the range [1, n], rearrange the array so that the integer i is placed at index i-1. Return the sorted array.

1 ≤ n ≤ 10^5Each integer in the array is in the range [1, n]The array may contain duplicates or missing numbers

💡

Example

Input"[3, 1, 5, 4, 2]"

Output[1, 2, 3, 4, 5]

Each number is placed at its correct index: 1 at index 0, 2 at index 1, etc.

• Array with all elements already sorted → output same array
• Array with duplicates → duplicates remain but placed at correct indices if possible
• Array with missing numbers → missing positions remain with incorrect values
• Array of size 1 → output same single element array

⚠️

Common Mistakes

Not swapping elements when they are out of place

Algorithm gets stuck in infinite loop or incorrect output

✅ Always swap arr[i] with arr[arr[i]-1] when they differ

Incrementing index i even when a swap is needed

Some elements remain misplaced, final array is incorrect

✅ Only increment i when current element is at correct position

Not handling duplicates properly

Swapping cycles endlessly or overwrites correct elements

✅ Check if arr[i] != arr[arr[i]-1] before swapping to avoid infinite loops

Assuming input always contains all numbers from 1 to n

Algorithm may access invalid indices or produce wrong output

✅ Validate input or handle missing numbers gracefully

🧠

Brute Force (Sorting with Built-in Sort)

💡 This approach exists because sorting is the most straightforward way to arrange numbers. It helps beginners understand the problem's goal before optimizing.

Intuition

Sort the array using a built-in sorting algorithm, which places all numbers in ascending order, thus placing each number i at index i-1.

Algorithm

1. Use a built-in sort function to sort the array in ascending order.
2. Return the sorted array.

💡 This algorithm is easy to understand but doesn't use the problem's constraints to optimize.

</>

Code

def cyclic_sort_brute(arr):
    arr.sort()
    return arr

# Driver code
if __name__ == '__main__':
    arr = [3, 1, 5, 4, 2]
    print(cyclic_sort_brute(arr))

Line Notes

arr.sort()Sorts the array in ascending order using Python's built-in Timsort, which is efficient and stable.

return arrReturns the sorted array as the final output, fulfilling the problem requirement.

if __name__ == '__main__':Ensures the driver code runs only when this script is executed directly, not when imported.

print(cyclic_sort_brute(arr))Prints the sorted array to verify correctness and demonstrate output.

import java.util.Arrays;
public class CyclicSortBrute {
    public static int[] cyclicSortBrute(int[] arr) {
        Arrays.sort(arr);
        return arr;
    }
    public static void main(String[] args) {
        int[] arr = {3, 1, 5, 4, 2};
        int[] sorted = cyclicSortBrute(arr);
        System.out.println(Arrays.toString(sorted));
    }
}

Line Notes

Arrays.sort(arr);Uses Java's built-in dual-pivot Quicksort to sort the array efficiently.

return arr;Returns the sorted array to the caller.

public static void main(String[] args)Main method to run the example and demonstrate the approach.

System.out.println(Arrays.toString(sorted));Prints the sorted array for verification of correctness.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> cyclicSortBrute(vector<int>& arr) {
    sort(arr.begin(), arr.end());
    return arr;
}

int main() {
    vector<int> arr = {3, 1, 5, 4, 2};
    vector<int> sorted = cyclicSortBrute(arr);
    for (int num : sorted) cout << num << ' ';
    cout << endl;
    return 0;
}

Line Notes

sort(arr.begin(), arr.end());Uses STL sort to arrange elements in ascending order efficiently.

return arr;Returns the sorted vector to the caller.

int main() {Entry point for the program execution to demonstrate the approach.

for (int num : sorted) cout << num << ' ';Prints each element of the sorted array to verify correctness.

function cyclicSortBrute(arr) {
    arr.sort((a, b) => a - b);
    return arr;
}

// Driver code
const arr = [3, 1, 5, 4, 2];
console.log(cyclicSortBrute(arr));

Line Notes

arr.sort((a, b) => a - b);Sorts the array numerically in ascending order using a comparator.

return arr;Returns the sorted array as the final output.

const arr = [3, 1, 5, 4, 2];Initializes the example input array for demonstration.

console.log(cyclicSortBrute(arr));Outputs the sorted array to the console for verification.

⏱

Complexity

TimeO(n log n)

SpaceO(1) or O(n) depending on sort implementation

Sorting takes O(n log n) time; space depends on the sorting algorithm used (Timsort uses O(n) auxiliary space).

💡 For n=10^5, sorting might take about 10^6 operations, which is acceptable but not optimal compared to linear time.

Interview Verdict: Accepted but not optimal

This approach works but doesn't leverage the problem's constraints for better performance.

🧠

Better Approach (Index-based Swapping Using Cyclic Sort)

💡 This approach uses the problem's constraint that numbers are from 1 to n to place each number directly at its correct index, avoiding full sorting.

Intuition

Iterate through the array and swap elements to their correct positions until all elements are placed correctly.

Algorithm

1. Initialize index i = 0.
2. While i < n, check if element at i is at correct position (arr[i] == i+1).
3. If not, swap arr[i] with arr[arr[i] - 1] to place it correctly.
4. If yes, increment i.
5. Repeat until all elements are placed correctly.

💡 The key is to keep swapping until the current element is at its correct index, then move forward.

</>

Code

def cyclic_sort(arr):
    i = 0
    n = len(arr)
    while i < n:
        correct_index = arr[i] - 1
        if arr[i] != arr[correct_index]:
            arr[i], arr[correct_index] = arr[correct_index], arr[i]
        else:
            i += 1
    return arr

# Driver code
if __name__ == '__main__':
    arr = [3, 1, 5, 4, 2]
    print(cyclic_sort(arr))

Line Notes

i = 0Start from the first index to check placement, ensuring we scan the entire array.

correct_index = arr[i] - 1Calculate the correct index for the current element based on its value.

if arr[i] != arr[correct_index]:Check if current element is not at its correct position to decide if swap is needed.

arr[i], arr[correct_index] = arr[correct_index], arr[i]Swap to place the element at its correct index, moving closer to sorted array.

public class CyclicSort {
    public static int[] cyclicSort(int[] arr) {
        int i = 0;
        int n = arr.length;
        while (i < n) {
            int correctIndex = arr[i] - 1;
            if (arr[i] != arr[correctIndex]) {
                int temp = arr[i];
                arr[i] = arr[correctIndex];
                arr[correctIndex] = temp;
            } else {
                i++;
            }
        }
        return arr;
    }
    public static void main(String[] args) {
        int[] arr = {3, 1, 5, 4, 2};
        int[] sorted = cyclicSort(arr);
        System.out.println(java.util.Arrays.toString(sorted));
    }
}

Line Notes

int i = 0;Initialize index to start scanning the array from the beginning.

int correctIndex = arr[i] - 1;Find the correct position for the current element based on its value.

if (arr[i] != arr[correctIndex]) {Check if the element is misplaced and needs swapping.

int temp = arr[i]; arr[i] = arr[correctIndex]; arr[correctIndex] = temp;Swap elements to correct positions, moving closer to sorted array.

#include <iostream>
#include <vector>
using namespace std;

vector<int> cyclicSort(vector<int>& arr) {
    int i = 0;
    int n = arr.size();
    while (i < n) {
        int correctIndex = arr[i] - 1;
        if (arr[i] != arr[correctIndex]) {
            swap(arr[i], arr[correctIndex]);
        } else {
            i++;
        }
    }
    return arr;
}

int main() {
    vector<int> arr = {3, 1, 5, 4, 2};
    vector<int> sorted = cyclicSort(arr);
    for (int num : sorted) cout << num << ' ';
    cout << endl;
    return 0;
}

Line Notes

int i = 0;Start scanning from the first element to ensure all elements are checked.

int correctIndex = arr[i] - 1;Calculate the target index for the current element based on its value.

if (arr[i] != arr[correctIndex]) {Check if the element is not in the correct position and needs swapping.

swap(arr[i], arr[correctIndex]);Swap to place the element correctly, moving towards sorted array.

function cyclicSort(arr) {
    let i = 0;
    const n = arr.length;
    while (i < n) {
        const correctIndex = arr[i] - 1;
        if (arr[i] !== arr[correctIndex]) {
            [arr[i], arr[correctIndex]] = [arr[correctIndex], arr[i]];
        } else {
            i++;
        }
    }
    return arr;
}

// Driver code
const arr = [3, 1, 5, 4, 2];
console.log(cyclicSort(arr));

Line Notes

let i = 0;Initialize pointer to start of array to scan all elements.

const correctIndex = arr[i] - 1;Determine the correct index for the current element based on its value.

if (arr[i] !== arr[correctIndex]) {Check if the element is misplaced and requires swapping.

[arr[i], arr[correctIndex]] = [arr[correctIndex], arr[i]];Swap elements to their correct positions, progressing towards sorted array.

⏱

Complexity

TimeO(n)

SpaceO(1)

Each element is swapped at most once to its correct position, resulting in linear time complexity.

💡 For n=10^5, this means about 10^5 operations, which is very efficient and suitable for large inputs.

Interview Verdict: Accepted and optimal

This approach is the best for this problem as it uses the problem constraints to achieve linear time and constant space.

🧠

Alternative Approach (Using Extra Array for Placement)

💡 This approach uses extra space to place elements at their correct indices, which is easier to understand but less space efficient.

Intuition

Create a new array of size n, place each element from the input array at index element-1, then return the new array.

Algorithm

1. Create a new array of size n initialized with zeros or placeholders.
2. Iterate over the input array and place each element at index element-1 in the new array.
3. Return the new array.

💡 This approach is straightforward but uses extra memory, trading space for simplicity.

</>

Code

def cyclic_sort_extra_space(arr):
    n = len(arr)
    result = [0] * n
    for num in arr:
        if 1 <= num <= n:
            result[num - 1] = num
    return result

# Driver code
if __name__ == '__main__':
    arr = [3, 1, 5, 4, 2]
    print(cyclic_sort_extra_space(arr))

Line Notes

result = [0] * nInitialize a new array to hold sorted elements, filled with zeros as placeholders.

for num in arr:Iterate over each element in the input array to place them correctly.

if 1 <= num <= n:Check if the number is within valid range before placing to avoid index errors.

result[num - 1] = numPlace the number at its correct index in the new array, ensuring sorted order.

public class CyclicSortExtraSpace {
    public static int[] cyclicSortExtraSpace(int[] arr) {
        int n = arr.length;
        int[] result = new int[n];
        for (int num : arr) {
            if (num >= 1 && num <= n) {
                result[num - 1] = num;
            }
        }
        return result;
    }
    public static void main(String[] args) {
        int[] arr = {3, 1, 5, 4, 2};
        int[] sorted = cyclicSortExtraSpace(arr);
        System.out.println(java.util.Arrays.toString(sorted));
    }
}

Line Notes

int[] result = new int[n];Create a new array to store sorted elements, initialized with zeros.

for (int num : arr) {Iterate over each element in the input array to place them correctly.

if (num >= 1 && num <= n) {Validate the number is within the expected range to avoid errors.

result[num - 1] = num;Place the number at its correct index in the new array.

#include <iostream>
#include <vector>
using namespace std;

vector<int> cyclicSortExtraSpace(const vector<int>& arr) {
    int n = arr.size();
    vector<int> result(n, 0);
    for (int num : arr) {
        if (num >= 1 && num <= n) {
            result[num - 1] = num;
        }
    }
    return result;
}

int main() {
    vector<int> arr = {3, 1, 5, 4, 2};
    vector<int> sorted = cyclicSortExtraSpace(arr);
    for (int num : sorted) cout << num << ' ';
    cout << endl;
    return 0;
}

Line Notes

vector<int> result(n, 0);Initialize a new vector with zeros to hold sorted elements as placeholders.

for (int num : arr) {Loop through each element in the input array to place them correctly.

if (num >= 1 && num <= n) {Check if the number is valid before placing to avoid invalid indices.

result[num - 1] = num;Place the number at its correct position in the new array.

function cyclicSortExtraSpace(arr) {
    const n = arr.length;
    const result = new Array(n).fill(0);
    for (const num of arr) {
        if (num >= 1 && num <= n) {
            result[num - 1] = num;
        }
    }
    return result;
}

// Driver code
const arr = [3, 1, 5, 4, 2];
console.log(cyclicSortExtraSpace(arr));

Line Notes

const result = new Array(n).fill(0);Create a new array filled with zeros to hold sorted elements as placeholders.

for (const num of arr) {Iterate over each element in the input array to place them correctly.

if (num >= 1 && num <= n) {Validate the number before placing it to avoid invalid indices.

result[num - 1] = num;Place the number at its correct index in the new array.

⏱

Complexity

TimeO(n)

SpaceO(n)

We iterate once over the array and use extra space proportional to n for the new array.

💡 For n=10^5, this means 10^5 operations and 10^5 extra space units, trading space for simplicity.

Interview Verdict: Accepted but uses extra space

This approach is simple but not space efficient compared to the in-place cyclic sort.

📊

All Approaches - One-Glance Tradeoffs

💡 Use the cyclic sort (Approach 2) in 95% of interviews because it is optimal and uses constant space.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Sorting)	O(n log n)	O(1) or O(n)	No	N/A	Mention only - never code
2. Cyclic Sort (In-place Swapping)	O(n)	O(1)	No	N/A	Code this approach
3. Extra Space Placement	O(n)	O(n)	No	N/A	Mention if interviewer allows extra space

💼

Interview Strategy

💡 Use this guide to understand the problem deeply and practice explaining each approach clearly before your interview.

How to Present

Step 1: Clarify the problem constraints and input range.Step 2: State the brute force approach using sorting and its complexity.Step 3: Introduce the cyclic sort approach leveraging the 1 to n range for O(n) time.Step 4: Discuss edge cases and test your code with examples.Step 5: Mention alternative approaches if time permits.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 8min → Test: 5min. Total ~20min

What the Interviewer Tests

The interviewer tests your understanding of array indexing, in-place swapping, and ability to optimize from naive sorting to linear time.

Common Follow-ups

• What if numbers are not in range 1 to n? → Need different approach or validation.
• How to find missing or duplicate numbers using cyclic sort? → Modify algorithm to detect mismatches.

💡 These follow-ups test your ability to adapt the cyclic sort pattern to related problems.

🔍

Pattern Recognition

When to Use

1) Array contains numbers from 1 to n (or similar range), 2) Need to place elements at correct indices, 3) Want O(n) time, 4) Can swap elements in-place.

Signature Phrases

place 1..n in correct positionsnumbers in range 1 to nswap elements to correct index

NOT This Pattern When

Sorting problems without fixed range or problems requiring complex DP or greedy strategies

Similar Problems

Find Missing Number - uses cyclic sort to detect missing elementsFind All Duplicates in an Array - uses cyclic sort to find duplicates

Practice

1. Given the following code snippet, what is the output when calling findDisappearedNumbers([2,3,2,1])?

easy

A. [4,2]

B. [4]

C. [3,4]

D. [1,4]

Solution

1. Step 1: Trace swaps in the while loop

   Initial array: [2,3,2,1] - i=0: nums[0]=2, correct=1; swap nums[0] and nums[1] -> [3,2,2,1] - i=0: nums[0]=3, correct=2; swap nums[0] and nums[2] -> [2,2,3,1] - i=0: nums[0]=2, correct=1; nums[0]==nums[1], so i=1 - i=1: nums[1]=2, correct=1; nums[1]==nums[1], i=2 - i=2: nums[2]=3, correct=2; nums[2]==nums[2], i=3 - i=3: nums[3]=1, correct=0; swap nums[3] and nums[0] -> [1,2,3,2] - i=3: nums[3]=2, correct=1; nums[3]==nums[1], i=4 (end)

2. Step 2: Identify missing numbers

   Final array: [1,2,3,2] Check indices: - i=0: 1 == 1 - i=1: 2 == 2 - i=2: 3 == 3 - i=3: 2 != 4 -> missing number is 4

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Only 4 is missing from 1 to 4 [OK]

Hint: Trace swaps carefully to find final array [OK]

Common Mistakes:

• Off-by-one in missing number
• Confusing duplicates with missing
• Stopping swaps too early

2. Given the following code snippet implementing the optimal cyclic sort approach, what is the returned output when the input is [3, 4, -1, 1]?

def find_smallest_missing_range(nums):
    n = len(nums)
    i = 0
    while i < n:
        correct_pos = nums[i] - 1
        if 1 <= nums[i] <= n and nums[i] != nums[correct_pos]:
            nums[i], nums[correct_pos] = nums[correct_pos], nums[i]
        else:
            i += 1
    start = 1
    for i in range(n):
        if nums[i] != i + 1:
            start = i + 1
            break
    else:
        return [n + 1, n + 1]
    end = start
    while end <= n and nums[end - 1] != end:
        end += 1
    return [start, end - 1]

print(find_smallest_missing_range([3, 4, -1, 1]))

easy

A. [4, 4]

B. [1, 1]

C. [2, 2]

D. [2, 3]

Solution

1. Step 1: Trace cyclic sort swaps

   Initial array: [3,4,-1,1] - i=0: nums[0]=3, correct_pos=2; swap nums[0] and nums[2] -> [-1,4,3,1] - i=0: nums[0]=-1 (not in 1..n), i++ -> i=1 - i=1: nums[1]=4, correct_pos=3; swap nums[1] and nums[3] -> [-1,1,3,4] - i=1: nums[1]=1, correct_pos=0; swap nums[1] and nums[0] -> [1,-1,3,4] - i=1: nums[1]=-1 (not in 1..n), i++ -> i=2 - i=2: nums[2]=3, correct_pos=2; already correct, i++ -> i=3 - i=3: nums[3]=4, correct_pos=3; already correct, i++ -> i=4 (end)

2. Step 2: Find smallest missing positive range

   Array after sorting: [1, -1, 3, 4] Check indices: - i=0: nums[0]=1 correct - i=1: nums[1]=-1 != 2 -> start=2 Find end: - end=2: nums[1]=-1 != 2 -> end=3 - end=3: nums[2]=3 == 3 -> stop Return [2, 2]

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Output matches expected missing smallest positive range [2, 2] [OK]

Hint: Trace swaps carefully to find final array state [OK]

Common Mistakes:

• Off-by-one in start or end calculation
• Ignoring negative numbers during swaps

3. What is the time complexity of the optimal cyclic sort approach for finding all missing numbers in an array of size n, and why?

medium

A. O(n log n) because of the sorting-like swaps

B. O(n^2) because nested swaps can occur repeatedly for duplicates

C. O(n) because each element is swapped at most once to its correct position

D. O(n) but with O(n) auxiliary space for tracking swaps

Solution

1. Step 1: Analyze the while loop behavior

   Each number is swapped at most once to its correct index, so total swaps ≤ n.

2. Step 2: Confirm no nested repeated swaps

   Duplicates cause skipping increments but do not cause repeated swaps for the same element, so total operations remain linear.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Linear time due to single pass and limited swaps [OK]

Hint: Each element swaps at most once [OK]

Common Mistakes:

• Assuming sorting cost O(n log n)
• Thinking duplicates cause quadratic swaps
• Confusing auxiliary space with time

4. Identify the bug in the following cyclic sort implementation for finding the corrupt pair:

medium

A. Line 6: Missing increment of i after else condition

B. Line 3: Incorrect initialization of n

C. Line 7: Swap logic is incorrect

D. Line 10: Return statement does not handle all cases

Solution

1. Step 1: Analyze the while loop behavior

   Without incrementing i in the else branch, the loop can get stuck when nums[i] == nums[correct_index], causing infinite loop.

2. Step 2: Identify fix

   Adding i += 1 in the else branch ensures progress and termination.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Infinite loop caused by missing index increment [OK]

Hint: Always increment index if no swap to avoid infinite loops [OK]

Common Mistakes:

• Forgetting to increment index after no swap
• Swapping incorrectly
• Misplaced return statements

5. What is the time complexity of the optimal binary search approach to find the kth missing positive number in a sorted array of length n?

medium

A. O(n)

B. O(log n)

C. O(k log n)

D. O(n log k)

Solution

1. Step 1: Analyze the binary search loop

   The algorithm performs a binary search on the array indices, halving the search space each iteration, resulting in O(log n) iterations.

2. Step 2: Confirm constant work per iteration

   Each iteration computes missing count in O(1) time, so total time is O(log n).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Binary search on array length n -> O(log n) [OK]

Hint: Binary search halves search space each iteration [OK]

Common Mistakes:

• Confusing k with n in complexity
• Assuming linear scan dominates