First Missing Positive LeetCode solution in Java

1
class Solution {
2
  public int firstMissingPositive(int[] nums) {
3
    // cyclic sort
4
    int i = 0;
5
    while (i < nums.length) {
6
      int correct = nums[i] - 1;
7
      if (nums[i] > 0 && nums[i] <= nums.length && nums[i] != nums[correct]) {
8
        swap(nums, i, correct);
9
      } else {
10
        i++;
11
      }
12
    }
13
    // linear search to find the missing number
14
    for (int index = 0; index < nums.length; index++) {
15
      if (nums[index] != index + 1) {
16
        return index + 1;
17
      }
18
    }
19
    // if array has all the elements match to its index then 1st missing num will be
20
    // nums.length+1
21
    return nums.length + 1;
22
  }
23

24
  static void swap(int[] arr, int a, int b) {
25
    int temp = arr[a];
26
    arr[a] = arr[b];
27
    arr[b] = temp;
28
  }
29
}