268. Missing Number

Missing Number

Problem Description

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

Example 1:

Input: nums = [3,0,1]

Output: 2

Explanation:

n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.

Example 2:

Input: nums = [0,1]

Output: 2

Explanation:

n = 2 since there are 2 numbers, so all numbers are in the range [0,2]. 2 is the missing number in the range since it does not appear in nums.

Example 3:

Input: nums = [9,6,4,2,3,5,7,0,1]

Output: 8

Explanation:

n = 9 since there are 9 numbers, so all numbers are in the range [0,9]. 8 is the missing number in the range since it does not appear in nums.

Constrains:

n == nums.length

1 <= n <= 104

0 <= nums[i] <= n

All the numbers of nums are unique.

 

Follow up: Could you implement a solution using only O(1) extra space complexity and O(n) runtime complexity?

Understanding the Mechanics: The Cycle Sort Algorithm

The essence of Cycle Sort lies in identifying and processing cycles within the array. A cycle occurs when an element at a particular index is not in its correct sorted position, and placing it in its correct position displaces another element that also isn't in its correct position, and so on, until we return to the original index.

Let's break down the algorithm step by step with a technical lens:

1. Iteration through the Array: The algorithm iterates through the array, considering each element as a potential starting point of a cycle.

2. Finding the Correct Position: For each element arr[i], we determine its correct sorted position. If the array contains numbers from 0 to N-1, the correct position for the number x is simply index x. If the range is 1 to N, the correct position for x is x - 1.

3. Identifying and Processing Cycles:

- If the element arr[i] is already in its correct position (arr[i] == i for 0-N-1 range), we move to the next element.

- If arr[i] is not in its correct position, we've encountered the start of a cycle. We then do the following:
- Store the current element (item = arr[i]).

- Find the correct position (pos) for item.

- While the item is not yet at its starting position i:

    - If item is already at pos, it means there are duplicate values (which violates the initial assumption of unique numbers for optimal Cycle Sort performance). In a strict Cycle Sort for unique elements, this scenario ideally shouldn't occur if the input adheres to the range. However, in a practical implementation, you might need to handle such cases (though it would deviate from the core efficiency of Cycle Sort for unique ranges).

    - Swap arr[pos] with item. Now, the element that was at pos is now in item's original position, and item moves closer to its correct place.

Update pos to the correct position of the newly placed element (item).

4. Continuing the Process: This process of identifying and rotating elements within cycles continues until the entire array has been traversed. At this point, all elements will be in their correct sorted positions.

Here's the Cycle Sort algorithm implemented in JavaScript:

function cycleSort(arr) {
  const n = arr.length;
  let writes = 0; // To track the number of writes (for demonstration)

  for (let cycleStart = 0; cycleStart < n - 1; cycleStart++) {
    let item = arr[cycleStart];
    let pos = cycleStart;

    // Find the correct position for the current item
    for (let i = cycleStart + 1; i < n; i++) {
      if (arr[i] < item) {
        pos++;
      }
    }

    // If the item is already in the correct position, continue
    if (pos === cycleStart) {
      continue;
    }

    // Skip duplicate elements (though ideally not present in the assumed unique range)
    while (item === arr[pos]) {
      pos++;
    }

    // Place the item in its correct position
    [arr[pos], item] = [item, arr[pos]];
    writes++;

    // Rotate the rest of the cycle
    while (pos !== cycleStart) {
      pos = cycleStart;
      for (let i = cycleStart + 1; i < n; i++) {
        if (arr[i] < item) {
          pos++;
        }
      }

      while (item === arr[pos]) {
        pos++;
      }

      [arr[pos], item] = [item, arr[pos]];
      writes++;
    }
  }
  return arr;
}

// Example usage:
const unsortedArray = [4, 3, 2, 1, 0];
const sortedArray = cycleSort(unsortedArray);
console.log("Sorted array:", sortedArray); // Output: Sorted array: [ 0, 1, 2, 3, 4 ]

const anotherUnsortedArray = [2, 0, 1, 4, 3];
const anotherSortedArray = cycleSort(anotherUnsortedArray);
console.log("Another sorted array:", anotherSortedArray); // Output: Another sorted array: [ 0, 1, 2, 3, 4 ]
Adapting for Finding the Missing Number (JavaScript)
Here's the JavaScript adaptation of your Python code to find the missing number:

Adapting for Finding the Missing Number (JavaScript):

Code:

/**
 * @param {number[]} nums
 * @return {number}
 */
var missingNumber = function(nums) {
    let i = 0;
    const n = nums.length;
    while (i < n) {
        const num = nums[i];
        if (num < n && num !== i) {
            [nums[i], nums[num]] = [nums[num], nums[i]];
        } else {
            i++;
        }
    }

    for (let i = 0; i < n; i++) {
        if (nums[i] !== i) {
            return i;
        }
    }
    return n;
};

Time and Space Complexity Revisited

Time Complexity: In the best and average case, where cycles are short, the time complexity is indeed O(N) because each element is visited and placed in its correct position at most once. The nested loops might seem concerning, but each element swap contributes to placing an element correctly, and we process each element a constant number of times within the cycle rotations. In the worst-case scenario (though less typical with the intended input range of unique elements), the time complexity can still be considered O(N) as the number of swaps is bounded by the number of elements.


Space Complexity: Cycle Sort is an in-place algorithm, utilizing a constant amount of extra space for temporary variables during swaps. Therefore, the space complexity is O(1).

Conclusion

That’s all folks! In this post, we solved LeetCode problem 286 Missing Number

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!