# Grokking the Coding Interview's Cyclic Sort

Cyclic sort, Missing number, Missing numbers, Find duplicate, Find duplicates, Find corrupt pair

### 1. Cyclic sort

Given an array containing n objects where each object, when created, was assigned a unique number from 1 to n based on their creation sequence. This means that the object with sequence number 3 was created just before the object with sequence number 4.

Write a function to sort the objects in-place on their creation sequence number in O(n) and without any extra space.

Example:

```
- Input: []int{6, 3, 5, 2, 4, 1}
Output: []int{1, 2, 3, 4, 5, 6}
```

Approach:

```
- Use the fact that we are given a range of 1-n, can try placing each number at
its correct index in the array, say 1 at 0, 2 at 1, 3 at 2 and so on.
- Iterate through the array and if the current number is not at the correct index,
swap it with the number at its correct index.
```

Cost:

```
- O(n) time, O(1) space.
```

### 2. Given an array containing n numbers taken from the range 1 to n. It can have duplicates. Find all those missing numbers.

Example:

```
- Input: []int{2, 3, 1, 8, 2, 3, 5, 1}
Output: []int{4, 6, 7}
```

Approach:

```
- Similar to missing number problem, can rearrange the array using cyclic
sort.
- Those that do not have the correct indices are the missing ones.
```

Cost:

```
- O(n) time and O(1) space.
```

### 3. Given an array containing n distinct numbers taken from the range 0 to n. Since the array has only n numbers out of the total n+1 numbers, find the missing number.

Example:

```
- Input: []int{4, 0, 3, 1}
Output: 2
```

Approach:

```
- Sort the array using the cyclic sort first.
- The one that does not have the correct index is the missing one.
```

Cost:

```
- O(n) time, O(1) space.
```

### 4. Given an array containing n+1 numbers taken from the range 1 to n. It has only one duplicate number but can be repeated over time. Find that one.

Example:

```
- Input: []int{1, 4, 4, 3, 2}
Output: 4
```

Approach:

```
- Similar to missing number problem, can place each number on its correct
index.
- If while swapping the number with its index both the numbers being swapped
are same, we have found the duplicate.
```

Cost:

```
- O(n) time, O(1) space.
```

### 5. Given an array containing n numbers taken from the range 1 to n. It can have some duplicates. Find all those numbers.

Example:

```
- Input: []int{5, 4, 7, 2, 3, 5, 3}
Output: []int{3, 5}
```

Approach:

```
- Similar to missing number problem, can rearrange the array using cyclic
sort.
- Those that do not have the correct indices are the duplicate ones.
```

Cost:

```
- O(n) time, O(1) space.
```

### 6. Given an array containing n+1 numbers taken from the range 1 to n. One of the numbers got duplicated which also resulted in one number going missing. Find these numbers.

Example:

```
- Input: []int{3, 1, 2, 5, 2}
Output: []int{2, 4}
```

Approach:

```
- Similar to finding duplicates problem, can place each number on its correct
index.
- The one is not at its correct index is the duplicate and its index itself
is the missing number.
```

Cost:

```
- O(n) time, O(1) space.
```

For more coding problems, please visit https://github.com/hoanhan101/algo.

Tagged: #grokking-the-coding-interview, #algorithm