Introduction

This pattern describes an interesting approach to deal with problems involving arrays containing numbers in a given range. For example, take the following problem:

You are given an unsorted array containing numbers taken from the range 1 to ‘n’. 
The array can have duplicates, which means that some numbers will be missing. 
Find all the missing numbers.

To efficiently solve this problem, we can use the fact that the input array contains numbers in the range of 1 to ‘n’. For example, to efficiently sort the array, we can try placing each number in its correct place, i.e., placing ‘1’ at index ‘0’, placing ‘2’ at index ‘1’, and so on. Once we are done with the sorting, we can iterate the array to find all indices that are missing the correct numbers. These will be our required numbers.

Patterns

1. i + 1 based

//cyclic sort when numbers are i + 1 based
//[1, 2, 3, 4, 5]
for (int i = 0; i < nums.length;) {
    int j = nums[i] - 1; // position it should be
    if (nums[j] != nums[i]) {
        swap(nums, i, j);
    } else {
        i++;
    }
}

2. when we have zero and looking for a missing number

int i = 0;
while (i < nums.length) {
    if (nums[i] < nums.length && nums[i] != nums[nums[i]])
        swap(nums, i, nums[i]);
    else
        i++;
}

for (i = 0; i < nums.length; i++)
    if (nums[i] != i)
        return i;

return nums.length;

3. first missing positive

for (int i = 0; i < nums.length; ) {
    int j = nums[i] - 1;
    if (j < nums.length && j >= 0 && nums[j] != nums[i]) {
        swap(nums, i, j);
    } else {
        i++;
    }
}

Untitled

Complexities

Most of the cases we're looking for O(n) time and O(1) space.