Cyclic Sort Problems

This pattern describes an interesting approach to deal with problems involving arrays containing numbers in a given range. For example, take the following problem:

You are given an unsorted array containing `n` numbers taken from the range `1` to `n`. The array can have duplicates, which means that some numbers will be missing. Find all the missing numbers.

To efficiently solve this problem, we can use the fact that the input array contains numbers in the range of 1 to n. For example, to efficiently sort the array, we can try placing each number at its correct place, i.e., placing 1 at index 0, placing 2 at index 1, and so on. Once we are done with the sorting, we can iterate the array to find all indices missing the correct numbers. These will be our required numbers.

Cyclic Sort (easy)

Problem Statement

We are given an array containing n objects. Each object, when created, was assigned a unique number from the range 1 to n based on their creation sequence. This means that the object with sequence number 3 was created just before the object with sequence number 4.

Write a function to ::sort the objects in-place on their creation sequence number in O(n) and without using any extra space::. For simplicity, let’s assume we are passed an integer array containing only the sequence numbers, though each number is actually an object.

Example 1:

Input: [3, 1, 5, 4, 2]
Output: [1, 2, 3, 4, 5]

Example 2:

Input: [2, 6, 4, 3, 1, 5]
Output: [1, 2, 3, 4, 5, 6]

Example 3:

Input: [1, 5, 6, 4, 3, 2]
Output: [1, 2, 3, 4, 5, 6]
using namespace std;

#include <iostream>
#include <vector>

class CyclicSort {
 public:
  static void sort(vector<int> &nums) {
    int i = 0;
    while (i < nums.size()) {
      int j = nums[i] - 1;
      if (nums[i] != nums[j]) {
        swap(nums, i, j);
      } else {
        i++;
      }
    }
  }

 private:
  static void swap(vector<int> &arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }
};

int main(int argc, char *argv[]) {
  vector<int> arr = {3, 1, 5, 4, 2};
  CyclicSort::sort(arr);
  for (auto num : arr) {
    cout << num << " ";
  }
  cout << endl;

  arr = vector<int>{2, 6, 4, 3, 1, 5};
  CyclicSort::sort(arr);
  for (auto num : arr) {
    cout << num << " ";
  }
  cout << endl;

  arr = vector<int>{1, 5, 6, 4, 3, 2};
  CyclicSort::sort(arr);
  for (auto num : arr) {
    cout << num << " ";
  }
  cout << endl;
}

Find the Missing Number (easy)

Problem Statement

We are given an array containing ’n’ distinct numbers taken from the range 0 to ’n’. Since the array has only ’n’ numbers out of the total ‘n+1’ numbers, find the missing number.

Example 1:

Input: [4, 0, 3, 1] 
Output: 2

Example 2:

Input: [8, 3, 5, 2, 4, 6, 0, 1]
Output: 7
using namespace std;

#include <iostream>
#include <vector>

class MissingNumber {
 public:
  static int findMissingNumber(vector<int> &nums) {
    // TODO: Write your code here
    int N = nums.size();
    for (int i = 0; i < N; i++) {
      while(nums[i] < N && nums[i] != i) {
        swap(nums[i], nums[nums[i]]);
      }
    }
    for (int i = 0; i < N; i++) {
      if (nums[i] != i) {
        return i;
      }
    }
    return N;
  }
};

Find all Missing Numbers (easy)

Problem Statement

We are given an unsorted array containing numbers taken from the range 1 to ’n’. The array can have duplicates, which means some numbers will be missing. Find all those missing numbers.

Example 1:

Input: [2, 3, 1, 8, 2, 3, 5, 1]
Output: 4, 6, 7

Explanation: The array should have all numbers from 1 to 8, due to duplicates 4, 6, and 7 are missing.

Example 2:

Input: [2, 4, 1, 2]
Output: 3

Example 3:

Input: [2, 3, 2, 1]
Output: 4
using namespace std;

#include <iostream>
#include <vector>

class AllMissingNumbers {
 public:
  static vector<int> findNumbers(vector<int> &nums) {
    vector<int> missingNumbers;
    // TODO: Write your code here
    int N = nums.size();
    for (int i = 0; i < N; i++) {
      // current val is not at their approriate position
      // and also the value on the position has not the same val
      while (nums[i] != i + 1 && nums[nums[i] - 1] != nums[i]) {
        swap(nums[i], nums[nums[i] - 1]);
      }
    }

    for (int i = 0; i < N; i++) {
      if (nums[i] != i + 1) {
        missingNumbers.push_back(i + 1);
      }
    }
    return missingNumbers;
  }
};

Find the Duplicate Number (easy)

Problem Statement

We are given an unsorted array containing ‘n+1’ numbers taken from the range 1 to ’n’. The array has only one duplicate but it can be repeated multiple times. Find that duplicate number without using any extra space. You are, however, allowed to modify the input array.

Example 1:

Input: [1, 4, 4, 3, 2]Output: 4

Example 2:

Input: [2, 1, 3, 3, 5, 4]Output: 3

Example 3:

Input: [2, 4, 1, 4, 4]Output: 4
using namespace std;

#include <iostream>
#include <vector>

class FindDuplicate {
 public:
  static int findNumber(vector<int> &nums) {
    // TODO: Write your code here
    int N = nums.size();
    int i = 0;
    while (i < N) {
      if (nums[i] != i + 1) {
        // we need swap it to nums[i] - 1
        if (nums[nums[i] - 1] == nums[i]) {
          return nums[i];
        }
        swap(nums[i], nums[nums[i] - 1]);
      } else {
        i++;
      }
    }
    // here, input is invalid actually.
    return -1;
  }
};

Find the Corrupt Pair (easy)

We are given an unsorted array containing ’n’ numbers taken from the range 1 to ’n’. The array originally contained all the numbers from 1 to ’n’, but due to a data error, one of the numbers got duplicated which also resulted in one number going missing. Find both these numbers.

Example 1:

Input: [3, 1, 2, 5, 2]Output: [2, 4]Explanation: '2' is duplicated and '4' is missing.

Example 2:

Input: [3, 1, 2, 3, 6, 4]Output: [3, 5]Explanation: '3' is duplicated and '5' is missing.
using namespace std;

#include <iostream>
#include <string>
#include <vector>

class FindCorruptNums {
 public:
  static vector<int> findNumbers(vector<int> &nums) {
    // TODO: Write your code here
    int N = nums.size();
    int i = 0;
    while(i < N) {
      if (nums[i] != i + 1 && nums[nums[i] - 1] != nums[i]) {
        swap(nums[i], nums[nums[i] - 1]);
      } else {
        i++;
      }
    }

    for (int i = 0; i < N; i++) {
      if (nums[i] != i + 1) {
        return {nums[i], i + 1};
      }
    }
    return { -1, -1 };
  }
};

Find the First K Missing Positive Numbers (hard)

Given an unsorted array containing numbers and a number ‘k’, find the first ‘k’ missing positive numbers in the array.

Example 1:

Input: [3, -1, 4, 5, 5], k=3
Output: [1, 2, 6]
Explanation: The smallest missing positive numbers are 1, 2 and 6.

Example 2:

Input: [2, 3, 4], k=3
Output: [1, 5, 6]
Explanation: The smallest missing positive numbers are 1, 5 and 6.

Example 3:

Input: [-2, -3, 4], k=2
Output: [1, 2]
Explanation: The smallest missing positive numbers are 1 and 2.
#include <iostream>
#include <vector>
#include <unordered_set>

using namespace std;

class FirstKMissingPositive {
 public:
  static vector<int> findNumbers(vector<int> &nums, int k) {
    vector<int> missingNumbers;
    int N = nums.size();
    int i = 0;
    while(i < N) {
      if (nums[i] > 0 && nums[i] <= N && nums[nums[i] - 1] != nums[i]) {
        swap(nums[i], nums[nums[i] - 1]);
      } else {
        i++;
      }
    }

    // record numbers shown in numbers but without approriate positions.
    // to avoid adding them later
    unordered_set<int> s;
    for (i = 0; i < N; i++) {      
      if (nums[i] != i + 1 && missingNumbers.size() < k) {
        missingNumbers.push_back(i + 1);
        s.insert(nums[i]);
      }
    }

    int v = N + 1;
    while(missingNumbers.size() < k) {
      if (!s.count(v)) {
        missingNumbers.push_back(v);
      }
      v++;
    }
    return missingNumbers;
  }
};