Find the Missing Number in an Array Using Cycle Sort Algorithm

In this post, we will go over the sorting technique known as cycle sort and solve the missing number problem by applying cycle sort algorithm.

Problem Statement

You are given an array containing n distinct numbers from 0 to n, but one number from this range is missing. Your objective is to find that missing number.

For example, given the array [3, 0, 1], the missing number is 2.

Solution

Before trying to solve this problem, let’s understand Cycle Sort technique.

What is Cycle Sort?

Cycle sort is a comparison-based sorting algorithm that is in-place and not stable.

The algorithm works by identifying cycles among elements that need to be rotated into their correct positions.

The algorithm works by considering each element in the array one at a time and placing it in its correct position by rotating the cycle of elements that includes the target position.

Here’s a high-level overview of how cycle sort operates:

1. Start with the first element in the array. For each element, starting from the beginning, determine its correct position in the sorted array by counting the number of elements that are smaller than it. This gives you the position where the current element must go.
2. Check if the element is already in the correct position. If the element is already where it belongs, move on to the next element. If not, you have identified a cycle that needs to be rotated.
3. Rotate the cycle. Move the element to its correct position, and move the element that was in that position to its own correct position. Continue this process until you have moved every element in the cycle to its correct position. This forms a “cycle” of moves, which is why the algorithm is called “cycle sort.”
4. Continue with the next element. Once a cycle is complete, move on to the next element that has not been correctly positioned yet and repeat the process.
5. End when the end of the array is reached. Once every element has been considered and placed in its correct position, the sorting is complete.

The main advantage of cycle sort is its minimal number of writes. This is particularly useful in applications where writes are significantly more expensive than reads, such as with flash memory. It is optimal in the sense that it reduces the number of writes to the theoretical minimum necessary to sort the array. However, its time complexity for comparison operations is still O(n²) in the worst case, similar to other quadratic sorting algorithms like bubble sort, insertion sort, and selection sort.

Applying Cycle Sort to Solve the “Missing Number” Problem

Given the array’s nature [containing n distinct numbers from 0 to n], each element ideally matches its index, except for the missing number. By applying the cycle sort technique, we can place each element in its proper position based on its value, essentially sorting the array.

Once sorted, the position where the element doesn’t match the index indicates the missing number.

Cycle sort is apt for this problem because it efficiently rearranges the elements with minimal memory writes. Since each number should be positioned at its corresponding index, cycle sort’s methodology of cyclically moving elements to their rightful place ensures that any deviation from this order directly points to the missing number.

Java Code Solution

public class Solution {
    public int missingNumber(int[] nums) {
        int i = 0;
        while (i < nums.length) {
            if (nums[i] < nums.length && nums[i] != nums[nums[i]]) {
                // Swap the elements to the correct position
                int temp = nums[nums[i]];
                nums[nums[i]] = nums[i];
                nums[i] = temp;
            } else {
                i++;
            }
        }

        // Find the missing number
        for (i = 0; i < nums.length; i++) {
            if (nums[i] != i) {
                return i;
            }
        }

        // If all numbers are correctly placed, the missing number is 'n'
        return nums.length;
    }
}

Solution Approach

1. Cycle through the array: Iteratively place each number in its correct position unless it’s already there or the number is n.
2. Identify the anomaly: Post-sorting, scan the array to find the index where the value doesn’t match, revealing the missing number.
3. Consider edge cases: If all positions match, the missing number is n, as the array contains all numbers from 0 to n-1.

Time and Space Complexity

• Time Complexity: O(n²) in the worst case due to the nested nature of cycle sort, though, for this specific problem, it behaves closer to O(n) because each element is moved at most once.
• Space Complexity: O(1), as the sorting and search are performed in place, requiring no additional storage proportional to the input size.

Follow me on Medium for more such insightful explorations into coding challenges.