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: 4using 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;
}
};

--

--

--

Developer & Husband

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

CSS Scroll Effects

A Complete PROC SQL SAS Guide

RC1 Testnet — Build from Source Linux (Intermediate Level)

GPS Logging App using TcpListener

Why You Need an Effective Cloud Management Platform

IOrchestrationDurableClient doesn’t have SignalEntityAsync

TASK-4:AWS VPC with public, private subnets, internet gateway and NAT gateway

How to use Google as IdP with IDCS Step-by-Step

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
HeavyRiver

HeavyRiver

Developer & Husband

More from Medium

Styling Tips for Wearing Holiday Jewelry | LuxyWish

Mahler — chamber vs. symphonic

All Of The Uses Of Whipped Cream!

Managing Emotions While Receiving Tough Feedback

Managing Emotions While Receiving Tough Feedback