Pattern:Cyclic Sort

Cyclic Sort: Instead of comparing elements like normal sorting, you place each number directly at its correct index.

Example: Find all the numbers disappeared in an array

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {

        int  i =0;
        int n = nums.length;
        while(i<n){
            int correctIndex = nums[i]-1;
            //ignore all the out of bound indexes
            if(correctIndex < nums.length && correctIndex >=0 && nums[i] != nums[correctIndex]){
                swap(i,correctIndex,nums);
            }
            else i++;
        }
        List<Integer> list = new ArrayList<>();
        for(i =0;i<nums.length;i++){
            if((i+1)!=nums[i]) list.add(i+1);
        }
        return list;
    }
    public void swap(int i, int j, int arr[]){
        int temp = arr[i];
        arr[i]= arr[j];
        arr[j] = temp;
    }
}