05. Cyclic Sort

core algorithm

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.

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

Code

def sort_objects(arr):
    i = 0
    while i < len(arr):
        correct_index = arr[i] - 1  # Find the correct index for the current element
        if arr[i] != arr[correct_index]:
            # Swap the current element with the one at its correct index
            arr[i], arr[correct_index] = arr[correct_index], arr[i]
        else:
            i += 1  # Move to the next index if already in correct place

# Example usage
arr = [2, 6, 4, 3, 1, 5]
sort_objects(arr)
print(arr)  # Output: [1, 2, 3, 4, 5, 6]

Explanation

As we know, the input array contains numbers from the range 1 to n.
We can use this fact to create an efficient way to sort the numbers.
Since all numbers are unique, we can try placing each number at its correct place,
placing 1 at index “0”,
placing 2 at index “1”, and so on.
To place a number at its correct index, we first need to find that number.
What if we iterate the array one number at a time, and if the current number we are iterating is not at the correct index, we swap it with the number at its correct index.
This way, we will iterate all numbers and place them at their correct indices.

Problem 1: Missing Number(Leetcode:268)

Problem Statement

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.

Example 1:

Input: nums = [3,0,1]
Output: 2
Explanation:
n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.

Example 2:

Input: nums = [0,1]
Output: 2
Explanation:
n = 2 since there are 2 numbers, so all numbers are in the range [0,2]. 2 is the missing number in the range since it does not appear in nums.

Example 3:

Input: nums = [9,6,4,2,3,5,7,0,1]
Output: 8
Explanation:
n = 9 since there are 9 numbers, so all numbers are in the range [0,9]. 8 is the missing number in the range since it > does not appear in nums.

Constraints:

n == nums.length
1 <= n <= 10^4
0 <= nums[i] <= n
All the numbers ofnums` are unique.

Code and Explaination

Approach 1Approach 2

Explaination:
This is first approach

Explaination:
This is second approach

Problem 2: Find All Duplicates in an Array (Leetcode:442)

Problem Statement

Given an integer array nums of length n where all the integers of nums are in the range [1, n] and each integer appears at most 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 auxiliary space, excluding the space needed to store the output

Example 1:

Input: nums = [4,3,2,7,8,2,3,1]
Output: [2,3]

Example 2:

Input: nums = [1,1,2]
Output: [1]

Example 3:

Input: nums = [1]
Output: []

Constraints:

n == nums.length
1 <= n <= 10^5
1 <= nums[i] <= n
Each element in nums appears once or twice.

Code and Explaination

Approach 1Approach 2

Explaination:
This is first approach

Explaination:
This is second approach

Problem 3: Find All Numbers Disappeared in an Array (Leetcode:448)

Problem Statement

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.

Example 1:

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

Example 2:

Input: nums = [1,1]
Output: [2]

Constraints:

n == nums.length
1 <= n <= 105
1 <= nums[i] <= n

Follow up:

Could you do it without extra space and in O(n) runtime?
You may assume the returned list does not count as extra space.

Code and Explaination

Approach 1Approach 2

Explaination:
This is first approach

Explaination:
This is second approach

Problem 4: Set Mismatch (Leetcode:645)

Problem Statement

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.

Example 1:

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

Example 2:

Input: nums = [1,1] Output: [1,2]

Constraints:

2 <= nums.length <= 10^4 1 <= nums[i] <= 10^4

Code and Explaination

Approach 1Approach 2

Explaination:
This is first approach

Explaination:
This is second approach

Problem 5: First Missing Positive (Leetcode:41)

Problem Statement

Given an unsorted integer array nums. Return the smallest positive integer that is not present in nums.
You must implement an algorithm that runs in O(n) time and uses O(1) auxiliary space.

Example 1:

Input: nums = [1,2,0]
Output: 3
Explanation: The numbers in the range [1,2] are all in the array.

Example 2:

Input: nums = [3,4,-1,1]
Output: 2
Explanation: 1 is in the array but 2 is missing.

Example 3:

Input: nums = [7,8,9,11,12]
Output: 1
Explanation: The smallest positive integer 1 is missing.

Constraints:

1 <= nums.length <= 10^5
-2^31 <= nums[i] <= 2^31 - 1

Code and Explaination

Approach 1Approach 2

Explaination:
This is first approach

Explaination:
This is second approach