# The Placement Fixer

> Each value belongs in exactly one spot.

Canonical URL: <https://datadriven.io/problems/the_placement_fixer>

Domain: Python · Difficulty: medium · Seniority: L4

## Problem

Given a list of integers in range 1..n with possible duplicates (where n = len(list)), return a sorted version using cyclic sort logic (each distinct value i is placed at index i-1). If duplicates exist, the exact algorithmic behavior is: return the sorted list for the simple no-duplicate case. With duplicates, return the sorted list as well.

## Worked solution and explanation

### Why this problem exists in real interviews

This tests the **cyclic sort** algorithm, an O(n) in-place sorting technique for arrays where values are within a known range. Interviewers use it to check whether candidates know this niche but powerful pattern for range-bounded data.

> **Trick to Solving**
>
> Each value v should be at index v-1. Swap `nums[i]` with `nums[nums[i]-1]` until `nums[i]` is in its correct position or a duplicate is detected. This places each number in O(1) amortized swaps.

---

### Break down the requirements

#### Step 1: Iterate through the array

For each index, check if the value at that index is in its correct position (value v at index v-1).

#### Step 2: Swap until correct or duplicate

While `nums[i] != i + 1` and the target position does not already hold the correct value, swap.

#### Step 3: Handle duplicates

If `nums[i] == nums[nums[i]-1]`, a duplicate is in the way. Move on to the next index.

---

### The solution

**Cyclic sort with in-place swapping**

```python
def cyclic_sort(nums):
    i = 0
    while i < len(nums):
        correct_idx = nums[i] - 1
        if nums[i] != nums[correct_idx]:
            nums[i], nums[correct_idx] = nums[correct_idx], nums[i]
        else:
            i += 1
    return nums
```

> **Time and Space Complexity**
>
> **Time:** O(n). Each element is swapped at most once into its correct position, so total swaps are bounded by n.
> 
> **Space:** O(1). The sort is in-place.

> **Interviewers Watch For**
>
> Can you explain why this is O(n) despite the inner while loop? Each swap places at least one element in its final position, so the total number of swaps across all iterations is at most n.

> **Common Pitfall**
>
> Infinite loop when duplicates exist. The condition `nums[i] != nums[correct_idx]` must be checked to detect when a swap would not change anything.

---

## Common follow-up questions

- How would you find all missing numbers after cyclic sort? _(Tests scanning for positions where `nums[i] != i + 1`.)_
- What if the range were 0 to n instead of 1 to n? _(Tests adjusting the formula to `correct_idx = nums[i]`.)_
- Can you find the duplicate number using this approach? _(Tests that the duplicate is the element stuck at the wrong position after sorting.)_
- How does cyclic sort compare to counting sort? _(Tests understanding that counting sort uses O(n) extra space while cyclic sort is in-place.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/the_placement_fixer)
- [Python Interview Questions](https://datadriven.io/python-interview-questions)
- [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep)
- [Daily Challenge](https://datadriven.io/daily)

---

Source: DataDriven (https://datadriven.io). 100% free data engineering interview prep. Live code execution against Postgres 16, Python 3.11, and Spark sandboxes. No paywall, no premium tier, no signup gate.