Cyclic sort:
A useful and fun to apply algorithm but talked about very less as per my observation.
Given that the elements in a given sequence are in a range, say [1, n], we can apply Cyclic sort and sort our array in linear time.
The very essence of the algorithm is that, we put the elements at the index where they are supposed to be.
Say we are given an array [5, 3, 1, 2, 4], the array after sorting will be [1, 2, 3, 4, 5].
But here is the thing, if we observe we'll see that 1 is at index 0, 2 is at index 1, 3 is at index 2 and so on. So if the index is i, the value in it would be i + 1.
There still might be variations, but the essence would be same. We would still be able to apply this algorithm with ease.
Here is the code for the algorithm in JAVA:
import java.util.*;
class CycleSort {
public static void main(String[] args) {
int[] arr = {5, 4, 1, 3, 2};
cyclicSort(arr);
System.out.println(Arrays.toString(arr));
}
static void cyclicSort(int[] arr) {
int i = 0;
while (i < arr.length) {
// the correct index is supposed to be the (element - 1)th index
int correctIdx = arr[i] - 1;
if (arr[i] != arr[correctIdx]) {
// if the current element is not equal to the element present at the current index
// put the element in the correct index by swapping
int temp = arr[i];
arr[i] = arr[correctIdx];
arr[correctIdx] = temp;
} else {
i++; // otherwise move forward
}
}
}
}
// TC: O(n) + O(n - 1) => O(n)
// SC: O(1)Watch this video for a detailed explanation of this algorithm
If you like the video, don't forget to thank him in the comments. He's an OG educator!
There are a few problems which we can solve using this technique.
NOTE:
In many of these problems, it has been asked to solve them without moifying the original array or by using any extra space. But the thing is, as a candidate you can't directly jump to the optimization of the solution. You have to solve it with a naive approach. Time or space optimization comes later, until the interviewer asks you to do so. So for that you have to learn as many approaches as possible.
If you check my posts in the solutions section of these problems, you'll find that I have solved them in numerous approaches. Next time someone says your solution is wrong because you have used extra space or modified the array, don't listen. Solve it with a brute force/naive approach and gradually optimize until you fulfil the constraints.
268. Missing Number 🟩
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.
Solution in JAVA:
class Solution {
public int missingNumber(int[] nums) {
int n = nums.length, i = 0;
while (i < n) {
int correctIdx = nums[i];
if (nums[i] < n && nums[i] != nums[correctIdx]) {
int temp = nums[i];
nums[i] = nums[correctIdx];
nums[correctIdx] = temp;
} else {
i++;
}
}
for (int j = 0; j < n; j++) {
if (j != nums[j]) {
return j;
}
}
return n;
}
}
// TC: O(n), SC: O(1)448. Find All Numbers Disappeared in an Array 🟩
Given an array nums of n integers where nums[i] is in the range [1, n], return an array of all the integers in the range [1, n] that do not appear in nums.
Solution in JAVA:
class Solution {
public List<Integer> findDisappearedNumbers(int[] nums) {
int n = nums.length, i = 0;
while (i < n) {
int correctIdx = nums[i] - 1;
if (nums[i] != nums[correctIdx]) {
int temp = nums[i];
nums[i] = nums[correctIdx];
nums[correctIdx] = temp;
} else {
i++;
}
}
List<Integer> ans = new ArrayList();
for (i = 0; i < n; i++) {
if (nums[i] != i + 1) {
ans.add(i + 1);
}
}
return ans;
}
}
// TC: O(n)
// SC: O(1) - ignoring the output list645. Set Mismatch 🟩
You have a set of integers s, which originally contains all the numbers from 1 to n. Unfortunately, due to some error, one of the numbers in s got duplicated to another number in the set, which results in repetition of one number and loss of another number.
You are given an integer array nums representing the data status of this set after the error.
Find the number that occurs twice and the number that is missing and return them in the form of an array.
Solution in JAVA:
class Solution {
public int[] findErrorNums(int[] nums) {
int i = 0;
while (i < nums.length) {
int correctIdx = nums[i] - 1;
if (nums[i] != nums[correctIdx]) {
swap(nums, i, correctIdx);
} else {
i++;
}
}
for (i = 0; i < nums.length; i++) {
if (nums[i] != i + 1) {
return new int[] {nums[i], i + 1};
}
}
return new int[0];
}
void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
// TC: O(n) + O(n) => O(n)
// SC: O(1)287. Find the Duplicate Number 🟨
Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.
There is only one repeated number in nums, return this repeated number.
You must solve the problem without modifying the array nums and uses only constant extra space.
Solution in JAVA:
class Solution {
public int findDuplicate(int[] nums) {
int i = 0;
while (i < nums.length) {
int correctIdx = nums[i] - 1;
if (nums[i] != nums[correctIdx]) {
int temp = nums[i];
nums[i] = nums[correctIdx];
nums[correctIdx] = temp;
} else {
i++;
}
}
for (i = 0; i < nums.length; i++) {
if (nums[i] != i + 1) {
return nums[i];
}
}
return 0;
}
}
// TC: O(n) + O(n) ~ O(n)
// SC: O(1)OR
class Solution {
public int findDuplicate(int[] nums) {
int i = 0;
while (i < nums.length) {
if (nums[i] != i + 1) {
int correctIdx = nums[i] - 1;
if (nums[i] != nums[correctIdx]) {
int temp = nums[i];
nums[i] = nums[correctIdx];
nums[correctIdx] = temp;
} else {
return nums[i];
}
} else {
i++;
}
}
return 0;
}
}
// TC: O(n), SC: O(1)442. Find All Duplicates in an Array 🟨
Given an integer array nums of length n where all the integers of nums are in the range [1, n] and each integer appears once or twice, return an array of all the integers that appears twice.
You must write an algorithm that runs in O(n) time and uses only constant extra space.
Solution in JAVA:
class Solution {
public List<Integer> findDuplicates(int[] nums) {
int i = 0;
while (i < nums.length) {
int correctIdx = nums[i] - 1;
if (nums[i] != nums[correctIdx]) {
swap(nums, i, correctIdx);
} else {
i++;
}
}
List<Integer> ans = new ArrayList<>();
for (i = 0; i < nums.length; i++) {
if (nums[i] != i + 1) {
ans.add(nums[i]);
}
}
return ans;
}
void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
// TC: O(n) + O(n) ~ O(n)
// SC: O(1)41. First Missing Positive 🟥
Given an unsorted integer array nums, return the smallest missing positive integer.
You must implement an algorithm that runs in O(n) time and uses constant extra space.
Solution in JAVA:
class Solution {
public int firstMissingPositive(int[] nums) {
int n = nums.length, i = 0;
while (i < n) {
int correctIdx = nums[i] - 1;
if (nums[i] > 0 && nums[i] < n && nums[i] != nums[correctIdx]) {
swap(nums, i, correctIdx);
} else {
i++;
}
}
for (i = 0; i < n; i++) {
if (nums[i] != i + 1) {
return i + 1;
}
}
return n + 1;
}
public void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
// TC: O(n), SC: O(1)Explanations to all these problems are available in that video.
If there are more problems, would be glad if they're suggested in the comments of this post. Would be happy to add them!
Do upvote if you like, Thanks :D