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

▶

Steps

setup

Initialize result array

Create a new result array of the same size as input, initialized with zeros as placeholders.

💡 This step sets up the empty array where sorted elements will be placed, making the sorting process explicit.

Line:

n = len(arr)
result = [0] * n

💡 We need a separate array to place elements directly at their correct indices.

traverse

Start iteration over input array

Set pointer i to 0 to start processing the first element of the input array.

💡 We begin placing elements one by one from the input array into the result array.

Line:

for num in arr:
    # processing num

💡 The iteration will cover all elements to place them correctly.

insert

Place element 3 at index 2

The current number is 3. Place it at index 3 - 1 = 2 in the result array.

💡 Each number's value determines its correct position in the sorted array.

Line:

if 1 <= num <= n:
    result[num - 1] = num

💡 The number 3 belongs at index 2, so we place it there directly.

traverse

Move to next input element (1)

Increment pointer i to 1 to process the next element in the input array.

💡 We continue placing elements one by one to build the sorted array.

Line:

for num in arr:
    # next iteration

💡 Moving pointer i shows progress through the input array.

insert

Place element 1 at index 0

The current number is 1. Place it at index 1 - 1 = 0 in the result array.

💡 Placing 1 at the start of the array is the correct sorted position.

Line:

if 1 <= num <= n:
    result[num - 1] = num

💡 The number 1 belongs at index 0, so we place it there directly.

traverse

Move to next input element (5)

Increment pointer i to 2 to process the next element in the input array.

💡 Continuing the iteration to place all elements.

Line:

for num in arr:
    # next iteration

💡 Pointer i moves forward to process the next number.

insert

Place element 5 at index 4

The current number is 5. Place it at index 5 - 1 = 4 in the result array.

💡 Placing 5 at the last index is its correct sorted position.

Line:

if 1 <= num <= n:
    result[num - 1] = num

💡 The number 5 belongs at index 4, so we place it there directly.

traverse

Move to next input element (4)

Increment pointer i to 3 to process the next element in the input array.

💡 Continuing the iteration to place all elements.

Line:

for num in arr:
    # next iteration

💡 Pointer i moves forward to process the next number.

insert

Place element 4 at index 3

The current number is 4. Place it at index 4 - 1 = 3 in the result array.

💡 Placing 4 at index 3 is its correct sorted position.

Line:

if 1 <= num <= n:
    result[num - 1] = num

💡 The number 4 belongs at index 3, so we place it there directly.

traverse

Move to next input element (2)

Increment pointer i to 4 to process the last element in the input array.

💡 Final element to place before finishing.

Line:

for num in arr:
    # next iteration

💡 Pointer i moves to the last element.

insert

Place element 2 at index 1

The current number is 2. Place it at index 2 - 1 = 1 in the result array.

💡 Placing 2 at index 1 completes the sorted array.

Line:

if 1 <= num <= n:
    result[num - 1] = num

💡 The number 2 belongs at index 1, so we place it there directly.

reconstruct

Iteration complete, return result

All elements have been placed in their correct positions. Return the fully sorted result array.

💡 The algorithm finishes by returning the new sorted array.

Line:

return result

💡 The result array now contains all elements sorted from 1 to n.

def cyclic_sort_extra_space(arr):
    n = len(arr)  # STEP 1: get length
    result = [0] * n  # STEP 1: initialize result array
    for i, num in enumerate(arr):  # STEP 2: start iteration
        if 1 <= num <= n:  # STEP 3: check valid range
            result[num - 1] = num  # STEP 3: place num at correct index
    return result  # STEP 12: return sorted array

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

📊

Cyclic Sort (Place 1..n in Correct Positions) - Watch the Algorithm Execute, Step by Step

Watching this step-by-step placement helps you understand how the algorithm uses extra space to achieve a sorted array without swapping in place.

setup

0

0

0

1

0

2

0

3

0

4

Result: [0,0,0,0,0]

traverse

i

0

0

0

1

0

2

0

3

0

4

Result: [0,0,0,0,0]

insert

i

0

0

0

1

3

2

0

3

0

4

Result: [0,0,3,0,0]

traverse

0

0

i

0

1

3

2

0

3

0

4

Result: [0,0,3,0,0]

insert

1

0

i

0

1

3

2

0

3

0

4

Result: [1,0,3,0,0]

traverse

1

0

0

1

i

3

2

0

3

0

4

Result: [1,0,3,0,0]

insert

1

0

0

1

i

3

2

0

3

5

4

Result: [1,0,3,0,5]

traverse

1

0

0

1

3

2

i

0

3

5

4

Result: [1,0,3,0,5]

insert

1

0

0

1

3

2

i

4

3

5

4

Result: [1,0,3,4,5]

traverse

1

0

0

1

3

2

4

3

i

5

4

Result: [1,0,3,4,5]

insert

1

0

2

1

3

2

4

3

i

5

4

Result: [1,2,3,4,5]

reconstruct

1

0

2

1

3

2

4

3

5

4

Result: [1,2,3,4,5]

Key Takeaways

✓ Using an extra array allows direct placement of each element at its correct index without swaps.

This insight is hard to see from code alone because the direct mapping from value to index is implicit.

✓ The iteration pointer 'i' shows progress through the input, while the target index is derived from the element's value.

Visualizing both pointers clarifies how the algorithm processes input and builds output simultaneously.

✓ Each placement is unconditional once the element is validated, showing no need for complex swapping or comparisons.

Seeing the direct placement step-by-step reveals the simplicity and efficiency of this approach.

Practice

1. You are given an unsorted array of integers that may contain duplicates, negatives, and zeros. Your task is to find the smallest continuous range of positive integers that are missing from the array. Which algorithmic approach guarantees an optimal O(n) time and O(1) space solution for this problem?

easy

A. Using a hash set to store all positive numbers and then checking for the missing range

B. Sorting the array and then scanning linearly to find the missing range

C. Using a dynamic programming approach to track presence of numbers

D. Using cyclic sort to place each positive integer at its correct index and then scanning for the missing range

Solution

1. Step 1: Understand problem constraints

   The problem requires finding the smallest missing positive range in O(n) time and O(1) space, which excludes sorting (O(n log n)) and hash sets (O(n) space).

2. Step 2: Identify the algorithm that achieves in-place linear time

   Cyclic sort places each positive integer at its correct index in the array, enabling a single pass to find the missing range efficiently.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Cyclic sort is known for in-place linear time sorting of numbers in range 1 to n [OK]

Hint: Cyclic sort achieves O(n) time and O(1) space for this problem [OK]

Common Mistakes:

• Assuming sorting is optimal
• Confusing hash set space with time complexity

2. You are given a sorted array of unique positive integers and a positive integer k. You need to find the kth positive integer that is missing from this array. Which algorithmic approach guarantees the most efficient solution in terms of time complexity?

easy

A. Use binary search on the array to find the position where the count of missing numbers reaches k.

B. Use a brute force linear scan counting missing numbers until the kth missing is found.

C. Use dynamic programming to store missing counts and find the kth missing number.

D. Use a greedy approach to iteratively guess missing numbers and verify their presence.

Solution

1. Step 1: Understand the problem constraints

   The array is sorted and contains unique positive integers. We want the kth missing positive number not in the array.

2. Step 2: Identify the optimal approach

   Binary search can be used to find the smallest index where the count of missing numbers is at least k, leveraging the formula missing = arr[mid] - (mid + 1). This yields O(log n) time complexity.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Binary search exploits sorted order and missing count formula [OK]

Hint: Binary search on missing count is optimal [OK]

Common Mistakes:

• Thinking brute force is efficient enough
• Confusing DP with missing count calculation

3. Suppose the input array can contain duplicate numbers and numbers outside the range 0 to n, or the array is immutable. Which modification to the cyclic sort approach correctly finds the missing number under these constraints?

hard

A. Use the sum formula approach since cyclic sort requires unique numbers and mutable array

B. Modify cyclic sort to skip numbers outside 0 to n and duplicates, swapping only valid numbers

C. Use a hash set to track all numbers and then find the missing one in O(n) time and O(n) space

D. Sort the array using built-in sort and scan for missing number, ignoring duplicates

Solution

1. Step 1: Understand constraints

   Duplicates and out-of-range numbers break cyclic sort assumptions; immutability prevents in-place swaps.

2. Step 2: Choose approach handling duplicates and immutability

   Hash set tracks presence without modifying input, handling duplicates and invalid numbers safely.

3. Step 3: Analyze tradeoffs

   Hash set uses O(n) space but guarantees correctness under constraints where cyclic sort fails.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Hash set approach works with duplicates and immutable inputs [OK]

Hint: Cyclic sort requires unique, mutable arrays [OK]

Common Mistakes:

• Trying to adapt cyclic sort without handling duplicates
• Assuming sum formula always works with duplicates
• Ignoring immutability constraints

4. Suppose the array can contain duplicate positive integers and you want to find the kth missing positive number. Which modification to the optimal binary search approach is necessary to handle duplicates correctly?

hard

A. No modification needed; binary search works the same with duplicates.

B. Modify the missing count calculation to account for duplicates by counting unique elements only.

C. Preprocess the array to remove duplicates before applying binary search.

D. Use a hash set to track missing numbers instead of binary search.

Solution

1. Step 1: Understand impact of duplicates

   Duplicates break the assumption that arr[i] - (i + 1) equals missing count because indices no longer correspond to unique elements.

2. Step 2: Identify correct fix

   Removing duplicates restores the strictly increasing property needed for binary search and correct missing count calculation.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Preprocessing to unique elements preserves binary search correctness [OK]

Hint: Binary search requires strictly increasing array [OK]

Common Mistakes:

• Assuming duplicates don't affect missing count
• Trying to fix missing count formula without removing duplicates

5. If the input array can contain numbers reused multiple times (duplicates can appear more than once), which modification to the cyclic sort approach correctly finds one duplicate and one missing number?

hard

A. Use a frequency array to count occurrences instead of cyclic sort

B. Modify cyclic sort to skip swapping when nums[i] == nums[correct] to avoid infinite loops

C. Run cyclic sort multiple times until no swaps occur

D. Sort the array and scan for duplicates and missing numbers

Solution

1. Step 1: Understand the problem extension

   Multiple duplicates break naive cyclic sort because repeated swaps cause infinite loops.

2. Step 2: Modify cyclic sort to skip swapping when duplicate detected

   Adding a check to skip swapping if nums[i] == nums[correct] prevents infinite loops and still finds mismatch.

3. Step 3: Contrast other options

   Frequency array uses extra space, multiple runs are inefficient, sorting is O(n log n).

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Skipping swaps on duplicates fixes infinite loop in cyclic sort [OK]

Hint: Skip swaps when duplicate detected to avoid infinite loops [OK]

Common Mistakes:

• Assuming cyclic sort works unchanged with multiple duplicates
• Relying on multiple passes instead of fixing swap condition
• Ignoring space constraints by using frequency arrays