Using Cyclic Sort Pattern

1. Understanding Cyclic Sort Technique

The Cyclic Sort pattern is used to sort arrays containing elements in a specific range (e.g., 1 to N). It's particularly useful when the array elements are in the range [1, N] and you need to place each element at its correct index (i.e., element 1 should be at index 0, element 2 at index 1, etc.).

Property	Description	Example
Time Complexity	O(n) - Each element is visited at most twice	`for (let i = 0; i < arr.length; i++) { ... }`
Space Complexity	O(1) - Constant extra space	Only uses a few variables for swapping
Use Case	Sorting arrays with elements in range [1, N]	Array of integers from 1 to n

Example: Basic Cyclic Sort Implementation

function cyclicSort(arr) {
  let i = 0;
  while (i < arr.length) {
    const correctIndex = arr[i] - 1;
    if (arr[i] !== arr[correctIndex]) {
      [arr[i], arr[correctIndex]] = [arr[correctIndex], arr[i]];
    } else {
      i++;
    }
  }
  return arr;
}

// Example usage:
const nums = [3, 1, 5, 4, 2];
console.log(cyclicSort(nums)); // [1, 2, 3, 4, 5]

Note: The algorithm works by placing each element at its correct index. If an element is not in the right place, it swaps it with the element at its correct index. This continues until all elements are in their correct positions.

2. Finding Missing Number in Range

Property	Description	Example
Algorithm	Cyclic sort pattern to find missing number in range [0, n]	`nums = [3, 0, 1]`
Time Complexity	O(n)	Single pass through array
Space Complexity	O(1)	Constant extra space used

Example: Finding Missing Number

function findMissingNumber(nums) {
  let i = 0;
  while (i < nums.length) {
    const j = nums[i];
    if (nums[i] < nums.length && nums[i] !== nums[j]) {
      [nums[i], nums[j]] = [nums[j], nums[i]];
    } else {
      i++;
    }
  }

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

  return nums.length;
}

const nums = [3, 0, 1];
console.log(findMissingNumber(nums)); // Output: 2

Note: The missing number in the range [0, n] is determined by checking which index does not match its value after sorting.

3. Finding All Missing Numbers

Property	Description	Example
Algorithm	Cyclic sort pattern used to find missing numbers in a range [1, n]	`Input: [3, 0, 1] → Output: 2`
Time Complexity	O(n) - Linear time due to single pass through array	`for (let i = 0; i < nums.length; i++) { ... }`
Space Complexity	O(1) - Constant space, in-place sorting	`nums[i] = nums[nums[i] - 1]`

Example: Finding Missing Number in Array

function findMissingNumber(nums) {
  let i = 0;
  while (i < nums.length) {
    const j = nums[i] - 1;
    if (nums[i] !== nums[j]) {
      [nums[i], nums[j]] = [nums[j], nums[i]];
    } else {
      i++;
    }
  }

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

  return nums.length + 1;
}

// Example usage:
const input = [3, 0, 1];
console.log(findMissingNumber(input)); // Output: 2

Note: The array is expected to contain numbers in the range [1, n] where one number is missing.

4. Finding Duplicate Number in Range

Property	Description	Usage
Algorithm	Cyclic sort pattern	Used to find duplicates in a range of numbers from 1 to n
Time Complexity	O(n)	Linear time complexity due to single pass through array
Space Complexity	O(1)	Constant space usage, no extra data structures required

Example: Finding Duplicate Number in Range

function findDuplicate(nums) {
  let i = 0;
  while (i < nums.length) {
    const j = nums[i] - 1;
    if (nums[i] !== nums[j]) {
      [nums[i], nums[j]] = [nums[j], nums[i]];
    } else {
      i++;
    }
  }
  return nums[nums.length - 1];
}

const nums = [1, 3, 4, 2, 2];
console.log(findDuplicate(nums)); // Output: 2

Note: This algorithm assumes that the array contains numbers in the range 1 to n, where n is the length of the array minus 1.

5. Finding All Duplicates in Array

Property	Description	Example
Algorithm	Cyclic sort pattern used to find duplicates in an array	`int[] arr = {3, 4, 4, 5, 5};`
Time Complexity	O(n) where n is the number of elements in the array	Traverses the array once
Space Complexity	O(1) if not counting the output array	Only uses a constant amount of extra space

Example: Finding All Duplicates in Array

import java.util.*;

public class FindAllDuplicates {
    public static List<Integer> findDuplicates(int[] arr) {
        int i = 0;
        List<Integer> duplicates = new ArrayList<>();

        while (i < arr.length) {
            int correctIndex = arr[i] - 1;
            if (arr[i] != arr[correctIndex]) {
                swap(arr, i, correctIndex);
            } else {
                i++;
            }
        }

        for (int j = 0; j < arr.length; j++) {
            if (arr[j] != j + 1) {
                duplicates.add(arr[j]);
            }
        }

        return duplicates;
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {3, 4, 4, 5, 5};
        System.out.println(findDuplicates(arr)); // Output: [4, 5]
    }
}

Note: The array must be in the range [1, n] where n is the size of the array for this algorithm to work correctly.

6. Finding Corrupt Pair

Given an array of numbers containing n elements where each number is in the range [1, n], one number appears twice and another is missing. The task is to find the duplicate and the missing number.

Property	Description	Example
Input	An array of integers of size `n` where one number is duplicated and one is missing	`[3, 1, 2, 3]`
Output	Array containing the duplicate and missing numbers	`[3, 4]`

Example: Finding Corrupt Pair

function findCorruptPair(nums) {
  let i = 0;
  while (i < nums.length) {
    const j = nums[i] - 1;
    if (nums[i] !== nums[j]) {
      [nums[i], nums[j]] = [nums[j], nums[i]];
    } else {
      i++;
    }
  }

  for (let i = 0; i < nums.length; i++) {
    if (nums[i] !== i + 1) {
      return [nums[i], i + 1];
    }
  }

  return [-1, -1];
}

console.log(findCorruptPair([3, 1, 2, 3])); // [3, 4]

Note: This approach uses cyclic sort to place each number in its correct index, then identifies the mismatch.

7. Finding First K Missing Positive Numbers

Given an unsorted array of positive integers, find the first K missing positive numbers.

Property	Description	Example
Input	Array of positive integers, size `n`	`[3, -1, 4, 5, 2]`
Output	First `K` missing positive integers	`[1, 6]`
Time Complexity	O(n + K)
Space Complexity	O(K)

Example: Finding First K Missing Positive Numbers

function findMissingPositive(arr, k) {
  const n = arr.length;
  // Place each number in its correct position
  for (let i = 0; i < n; i++) {
    while (arr[i] > 0 && arr[i] <= n && arr[arr[i] - 1] !== arr[i]) {
      [arr[arr[i] - 1], arr[i]] = [arr[i], arr[arr[i] - 1]];
    }
  }

  const missing = [];
  const extra = new Set();

  // Collect missing numbers
  for (let i = 0; i < n && missing.length < k; i++) {
    if (arr[i] !== i + 1) {
      missing.push(i + 1);
    }
  }

  // Add extra numbers beyond array size
  let num = n + 1;
  while (missing.length < k) {
    if (!extra.has(num)) {
      missing.push(num);
    }
    num++;
  }

  return missing;
}

// Example usage:
const arr = [3, -1, 4, 5, 2];
console.log(findMissingPositive(arr, 2)); // [1, 6]

Note: This algorithm uses cyclic sort to place numbers in their correct positions, then identifies missing positive integers.

8. Finding First Missing Positive Number

Property	Description	Example
Problem	Finds the smallest positive integer (starting from 1) that is missing from an unsorted array of integers.	Array: [3, 4, -1, 1] → Missing: 2
Approach	Use cyclic sort to place each positive integer at its correct index (value 1 at index 0, value 2 at index 1, etc.).	After sorting: [1, -1, 3, 4]
Time Complexity	O(n)	Single pass through the array.
Space Complexity	O(1)	Sorts in-place, no extra space needed.

Example: Finding First Missing Positive

function firstMissingPositive(nums) {
  let i = 0;
  const n = nums.length;

  // Cyclic sort to place each positive number at its correct index
  while (i < n) {
    const j = nums[i] - 1;
    if (nums[i] > 0 && nums[i] <= n && nums[i] !== nums[j]) {
      [nums[i], nums[j]] = [nums[j], nums[i]];
    } else {
      i++;
    }
  }

  // Find the first index where value is not correct
  for (i = 0; i < n; i++) {
    if (nums[i] !== i + 1) {
      return i + 1;
    }
  }

  // If all positions are correct, return n + 1
  return n + 1;
}

// Example usage:
console.log(firstMissingPositive([3, 4, -1, 1])); // Output: 2
console.log(firstMissingPositive([1, 2, 0]));    // Output: 3
console.log(firstMissingPositive([7, 8, 9, 11, 12])); // Output: 1

Note: This pattern is useful for problems where you need to find missing elements in a sequence or validate array properties.

9. Sorting Array In-Place with Cyclic Sort

The Cyclic Sort pattern is used to sort arrays containing elements in a specific range (e.g., 1 to N). It's particularly useful when the array elements are in the range [1, N] and we want to sort them in-place.

Property	Description	Example
Time Complexity	O(n) - Each element is visited at most twice	`for (let i = 0; i < arr.length; i++) { ... }`
Space Complexity	O(1) - No extra space used	`const sorted = cyclicSort(arr);`

Example: Sorting Array with Cyclic Sort

function cyclicSort(arr) {
  let i = 0;
  while (i < arr.length) {
    const j = arr[i] - 1;
    if (arr[i] !== arr[j]) {
      [arr[i], arr[j]] = [arr[j], arr[i]];
    } else {
      i++;
    }
  }
  return arr;
}

const nums = [3, 1, 5, 4, 2];
console.log(cyclicSort(nums)); // [1, 2, 3, 4, 5]

Note: The array must contain elements in the range [1, N] for this algorithm to work correctly.

10. Finding Disappeared Numbers in Range

Property	Description	Example
Problem	Finds all numbers in the range [1, n] that are missing from an array of size n	`[4, 3, 2, 7, 8, 2, 3, 1]` → `[5, 6]`
Approach	Use cyclic sort to place each number in its correct position, then find mismatches	Sort array so `nums[i] = i + 1`
Time Complexity	O(n)	Single pass for sorting, single pass for finding missing
Space Complexity	O(1)	No extra space used beyond input array

Example: Finding Disappeared Numbers

function findDisappearedNumbers(nums) {
  let i = 0;
  while (i < nums.length) {
    const j = nums[i] - 1;
    if (nums[i] !== nums[j]) {
      [nums[i], nums[j]] = [nums[j], nums[i]];
    } else {
      i++;
    }
  }

  const result = [];
  for (let j = 0; j < nums.length; j++) {
    if (nums[j] !== j + 1) {
      result.push(j + 1);
    }
  }

  return result;
}

// Example usage:
const input = [4, 3, 2, 7, 8, 2, 3, 1];
console.log(findDisappearedNumbers(input)); // [5, 6]

Note: This pattern works because each number in the range [1, n] should be at index (number - 1) after sorting.