Cyclic Sort

void cyclicSort(int[] nums) {
    int i = 0;
    while (i < nums.length) {
        int correctIdx = nums[i] - 1; // where nums[i] should be
        if (nums[i] != nums[correctIdx]) {
            // Swap nums[i] to its correct position
            int tmp = nums[i];
            nums[i] = nums[correctIdx];
            nums[correctIdx] = tmp;
        } else {
            i++; // nums[i] is at its correct position
        }
    }
}
// [3,1,5,4,2] → sort → [1,2,3,4,5]

public int missingNumber(int[] nums) {
    int i = 0;
    while (i < nums.length) {
        int j = nums[i];
        if (j < nums.length && nums[i] != nums[j]) {
            int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp;
        } else {
            i++;
        }
    }
    // Find the first position where nums[i] != i
    for (int k = 0; k < nums.length; k++)
        if (nums[k] != k) return k;
    return nums.length; // missing number is n
}
// [3,0,1] → sort → [0,1,3] → position 2 is wrong → missing = 2

public List<Integer> findDisappearedNumbers(int[] nums) {
    int i = 0;
    while (i < nums.length) {
        int j = nums[i] - 1;
        if (nums[i] != nums[j]) {
            int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp;
        } else {
            i++;
        }
    }
    List<Integer> missing = new ArrayList<>();
    for (int k = 0; k < nums.length; k++)
        if (nums[k] != k + 1) missing.add(k + 1);
    return missing;
}

public int findDuplicate(int[] nums) {
    int i = 0;
    while (i < nums.length) {
        if (nums[i] != i + 1) {
            int j = nums[i] - 1;
            if (nums[i] != nums[j]) {
                int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp;
            } else {
                return nums[i]; // duplicate found!
            }
        } else {
            i++;
        }
    }
    return -1;
}

public List<Integer> findAllDuplicates(int[] nums) {
    int i = 0;
    while (i < nums.length) {
        int j = nums[i] - 1;
        if (nums[i] != nums[j]) {
            int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp;
        } else {
            i++;
        }
    }
    List<Integer> duplicates = new ArrayList<>();
    for (int k = 0; k < nums.length; k++)
        if (nums[k] != k + 1) duplicates.add(nums[k]);
    return duplicates;
}