268. Missing Number

#cyclic-sort

Problem

Missing Number - LeetCodeLeetCode

Intuition

Cyclic Sort

Time Complexity

Space Complexity

Solution

class Solution {
    public int missingNumber(int[] nums) {
        // n -> Number of elements in nums, i.e. nums.length
        // Time Complexity: O(n), traversing through the array once
        // Space Complexity: O(1), auxillary space. No extra space is used
        
        int i = 0;

        // Iterate through the array to perform cyclic sort
        while (i < nums.length) {
            // Check if the current element is within the valid range
            // AND not in its correct position
            if (nums[i] < nums.length && nums[i] != i) {
                // Swap the current element with the element at its correct position
                swap(nums, i, nums[i]);
            } else {
                // Move to the next element
                // if the current element is already in its correct position or out of range
                i++;
            }
        }

        // Iterate through the sorted array to find the missing number
        for (int j = 0; j < nums.length; j++) {
            // If an element is not equal to its index, it means the missing number is found
            if (nums[j] != j) {
                return j;
            }
        }

        // If all numbers are in their correct positions, 
        // the missing number is the maximum value (nums.length)
        return nums.length;
    }

    // Helper method to swap two elements in the array
    private void swap(int[] nums, int idx, int num) {
        int temp = nums[idx];
        nums[idx] = nums[num];
        nums[num] = temp;
    }
}