Hasuer's Studio.

5. Pattern Cyclic Sort

Grokking Interview Pattern Interview
Word count: 4.6kReading time: 27 min
2024/05/05

Introduction

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.

Let’s jump on to our first problem to understand the Cyclic Sort pattern in action.

*Cyclic Sort (easy)

Design Gurus Educative.io

Problem Statement

We are given an array containing ‘n’ objects. Each object, when created, was assigned a unique number from 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 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:

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

Example 2:

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

Example 3:

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

Constraints:

  • n == nums.length
  • 1 <= n <= 10^4
  • 0 <= nums[i] <= n

Solution

As we know, the input array contains numbers from the range 1 to n. We can use this fact to devise an efficient way to sort the numbers. Since all numbers are unique, 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.

To place a number (or an object in general) at its correct index, we first need to find that number. If we first find a number and then place it at its correct place, it will take us O(N^2), which is not acceptable as mentioned in the problem statement.

Instead, 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 go through all numbers and place them at their correct indices, hence, sorting the whole array.

Let’s see this visually with the above-mentioned Example-2:

Code

Here is what our algorithm will look like:

这道题使用的算法有几个约束条件，一定要是连续的自然数，而且没有重复，虽然这里是从1开始的自然数，但是不从一开始也可以，只要加上一个偏置就好了 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def sort(self, nums):
        i = 0
        while i < len(nums):
            # 数字从[1,n],所以数字1应该在index=0上
            j = nums[i] - 1  # Calculate the index where the current element should be placed.
            # 这里需要注意的是需要把j = nums[i] - 1单独写出来
            # 不然要是nums[i], nums[nums[i] - 1] = nums[nums[i] - 1], nums[i]会有问题
            if nums[i] != nums[j]:  # Check if the current element is not in its correct position.
                nums[i], nums[j] = nums[j], nums[i]  # Swap the current element with the one at its correct position.
            else:
                i += 1  # If the current element is already in its correct position, move to the next element.
        return nums


def main():
    sol = Solution()
    print(sol.sort([3, 1, 5, 4, 2]))
    print(sol.sort([2, 6, 4, 3, 1, 5]))
    print(sol.sort([1, 5, 6, 4, 3, 2]))


main()

Time complexity

The time complexity of the above algorithm is O(n). Although we are not incrementing the index i when swapping the numbers, this will result in more than ‘n’ iterations of the loop, but in the worst-case scenario, the while loop will swap a total of ‘n-1’ numbers and once a number is at its correct index, we will move on to the next number by incrementing i. So overall, our algorithm will take O(n) + O(n-1) which is asymptotically equivalent to O(n)。

Space complexity

The algorithm runs in constant space O(1).

*Find the Missing Number (easy)

268. Missing Number Design Gurus Educative.io

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:

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

Example 2:

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

Constraints:

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

Solution

This problem follows the Cyclic Sort pattern. Since the input array contains unique numbers from the range 0 to ‘n’, we can use a similar strategy as discussed in Cyclic Sort to place the numbers on their correct index. Once we have every number in its correct place, we can iterate the array to find the index which does not have the correct number, and that index will be our missing number.

However, there are two differences with Cyclic Sort:

  1. In this problem, the numbers are ranged from ‘0’ to ‘n’, compared to ‘1’ to ‘n’ in the Cyclic Sort. This will make two changes in our algorithm:
    • In this problem, each number should be equal to its index, compared to index + 1 in the Cyclic Sort. Therefore => nums[i] == nums[nums[i]]
    • Since the array will have ‘n’ numbers, which means array indices will range from 0 to ‘n-1’. Therefore, we will ignore the number ‘n’ as we can’t place it in the array, so => nums[i] < nums.length
  2. Say we are at index i. If we swap the number at index i to place it at the correct index, we can still have the wrong number at index i. This was true in Cyclic Sort too. It didn’t cause any problems in Cyclic Sort as over there, we made sure to place one number at its correct place in each step, but that wouldn’t be enough in this problem as we have one extra number due to the larger range. Therefore, we will not move to the next number after the swap until we have a correct number at the index i.

Code

Here is what our algorithm will look like:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
    def findMissingNumber(self, nums):
        i, n = 0, len(nums)
        while i < n:
            j = nums[i] #  范围是 [0,n), 所以数字1应该在index=1上
            # 所以当nums[i]在[0,n)时，并且不在自己的位置上（nums[i] != nums[j]），那就要换位置
            if nums[i] < n and nums[i] != nums[j]:
                nums[i], nums[j] = nums[j], nums[i]  # swap
            else:
                i += 1

        # find the first number missing from its index, that will be our required number
        for i in range(n):
            if nums[i] != i:
                return i
		# 这个忘记了，需要加上
        return n # 比如这个例子[0,1]


def main():
    sol = Solution()
    print(sol.findMissingNumber([4, 0, 3, 1]))
    print(sol.findMissingNumber([8, 3, 5, 2, 4, 6, 0, 1]))


main()

Time complexity

The time complexity of the above algorithm is O(n). In the while loop, although we are not incrementing the index i when swapping the numbers, this will result in more than ‘n’ iterations of the loop, but in the worst-case scenario, the while loop will swap a total of ‘n-1’ numbers and once a number is at its correct index, we will move on to the next number by incrementing i. In the end, we iterate the input array again to find the first number missing from its index, so overall, our algorithm will take O(n) + O(n-1) + O(n) which is asymptotically equivalent to O(n).

Space complexity

The algorithm runs in constant space O(1).

Find all Missing Numbers (easy)

448. Find All Numbers Disappeared in an Array Design Gurus Educative.io

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:

1
2
3
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:

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

Example 3:

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

Constraints:

  • n == nums.length
  • 1 <= n <= 10^5
  • 1 <= nums[i] <= n

Solution

This problem follows the Cyclic Sort pattern and shares similarities with Find the Missing Number with one difference. In this problem, there can be many duplicates whereas in ‘Find the Missing Number’ there were no duplicates and the range was greater than the length of the array.

However, we will follow a similar approach though as discussed in Find the Missing Number to place the numbers on their correct indices. Once we are done with the cyclic sort we will iterate the array to find all indices that are missing the correct numbers.

Code

Here is what our algorithm will look like:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
    def findNumbers(self, nums):
        i = 0  # Initialize a pointer for iterating through the list.
        while i < len(nums):
            #  范围是 [1,n], 所以数字1应该在index=0上
            j = nums[i] - 1  # Calculate the target index for the current element.
            if nums[i] != nums[j]:  # Check if the current element is not in its correct position.
                nums[i], nums[j] = nums[j], nums[i]  # Swap the elements to their correct positions.
            else:
                i += 1  # If the current element is in the correct position, move to the next element.

        missingNumbers = []

        for i in range(len(nums)):
            if nums[i] != i + 1:  # Check if the element at index 'i' is not in the correct position.
                missingNumbers.append(i + 1)  # Add the missing number to the list.

        return missingNumbers


def main():
    sol = Solution()
    print(sol.findNumbers([2, 3, 1, 8, 2, 3, 5, 1]))
    print(sol.findNumbers([2, 4, 1, 2]))
    print(sol.findNumbers([2, 3, 2, 1]))


main()

Time complexity

The time complexity of the above algorithm is O(n)

Space complexity

Ignoring the space required for the output array, the algorithm runs in constant space O(1).

*Find the Duplicate Number (easy)

287. Find the Duplicate Number Design Gurus Educative.io

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:

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

Example 2:

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

Example 3:

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

Constraints:

  • nums.length == n + 1
  • 1 <= n <= 10^5
  • 1 <= nums[i] <= n
  • All the integers in nums appear only once except for precisely one integer which appears two or more times.

Solution

This problem follows the Cyclic Sort pattern and shares similarities with Find the Missing Number. Following a similar approach, we will try to place each number on its correct index. Since there is only one duplicate, if while swapping the number with its index both the numbers being swapped are same, we have found our duplicate!

Code

Here is what our algorithm will look like:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
# 按照之前几道题的思路写的如下：
def find_number(nums):
    i = 0
    while i < len(nums):
        j = nums[i] - 1 
        
        if nums[i] != nums[j]:
            nums[i], nums[j] = nums[j], nums[i]
        else:
            i += 1
    for i in range(len(nums)):
        if nums[i] != i + 1:
            return nums[i]

# 以下是官方的，更加简洁一些
class Solution:
    def find_duplicate(self, nums):
        i = 0
        while i < len(nums):
            if nums[i] != i + 1:  # Check if the current element is in its correct position
                # 范围是 [1,n], 所以数字1应该在index=0上
                # 当不在自己的位置上（nums[i] != nums[j]），那就要换位置
                j = nums[i] - 1  # Calculate the correct index for the current element
                if nums[i] != nums[j]:  # Check if the current element is not equal to the element at its correct index
                    nums[i], nums[j] = nums[j], nums[i]  # Swap the elements to their correct positions
                else:  # We have found the duplicate
                    return nums[i]
            else:
                i += 1  # Move to the next element

        return -1  # No duplicate found


def main():
    sol = Solution()
    print(sol.find_duplicate([1, 4, 4, 3, 2]))
    print(sol.find_duplicate([2, 1, 3, 3, 5, 4]))
    print(sol.find_duplicate([2, 4, 1, 4, 4]))


main()

Time complexity

The time complexity of the above algorithm is O(n).

Space complexity

The algorithm runs in constant space O(1) but modifies the input array.

Similar Problems

Problem 1: Can we solve the above problem in O(1) space and without modifying the input array?

Solution: While doing the cyclic sort, we realized that the array will have a cycle due to the duplicate number and that the start of the cycle will always point to the duplicate number. This means that we can use the fast & the slow pointer method to find the duplicate number or the start of the cycle similar to Start of LinkedList Cycle(Pattern 4 problem 3)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution:
    def findDuplicate(self, arr):
        slow, fast = arr[0], arr[arr[0]]
        while slow != fast:
            slow = arr[slow]
            fast = arr[arr[fast]]

        # find cycle length
        current = arr[arr[slow]]
        cycleLength = 1
        while current != arr[slow]:
            current = arr[current]
            cycleLength += 1

        return self.find_start(arr, cycleLength)

    def find_start(self, arr, cycleLength):
        pointer1, pointer2 = arr[0], arr[0]
        # move pointer2 ahead 'cycleLength' steps
        while cycleLength > 0:
            pointer2 = arr[pointer2]
            cycleLength -= 1

        # increment both pointers until they meet at the start of the cycle
        while pointer1 != pointer2:
            pointer1 = arr[pointer1]
            pointer2 = arr[pointer2]

        return pointer1


def main():
    sol = Solution()
    print(sol.findDuplicate([1, 4, 4, 3, 2]))
    print(sol.findDuplicate([2, 1, 3, 3, 5, 4]))
    print(sol.findDuplicate([2, 4, 1, 4, 4]))


main()

The time complexity of the above algorithm is O(n) and the space complexity is O(1).

Find all Duplicate Numbers (easy)

442. Find All Duplicates in an Array Design Gurus Educative.io

Problem Statement

We are given an unsorted array containing ‘n’ numbers taken from the range 1 to ‘n’. The array has some duplicates, find all the duplicate numbers without using any extra space.

Example 1:

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

Example 2:

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

Constraints:

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

Solution

This problem follows the Cyclic Sort pattern and shares similarities with Find the Duplicate Number. Following a similar approach, we will place each number at its correct index. After that, we will iterate through the array to find all numbers that are not at the correct indices. All these numbers are duplicates.

Code

Here is what our algorithm will look like:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution:
    def findNumbers(self, nums):
        i = 0
        while i < len(nums):
            # 范围是 [1,n], 所以数字1应该在index=0上
            j = nums[i] - 1  # Calculate the index where the current element should be if it's not a duplicate.
            # 当不在自己的位置上（nums[i] != nums[j]），那就要换位置
            if nums[i] != nums[j]:  # Check if the current element is not in its correct position.
                nums[i], nums[j] = nums[j], nums[
                    i]  # Swap the current element with the element at its correct position.
            else:
                i += 1  # Move to the next element if the current element is already in its correct position.
		# 个人认为这里有问题，比如[3, 4, 4, 5, 5, 5, 5]就会返回[4,5,5,5]而不是[4,5]
        # 但是leetcode 442中说明了“each integer appears once or twice”那就不用考虑这个情况
        # solution的解答也是对的
        duplicateNumbers = []
        for i in range(len(nums)):
            if nums[i] != i + 1:  # Identify elements that are not in their correct positions, which are duplicates.
                duplicateNumbers.append(nums[i])  # Add the duplicates to the list.

        return duplicateNumbers


def main():
    sol = Solution()
    print(sol.findNumbers([3, 4, 4, 5, 5]))
    print(sol.findNumbers([5, 4, 7, 2, 3, 5, 3]))


main()

Time complexity

The time complexity of the above algorithm is O(n).

Space complexity

Ignoring the space required for storing the duplicates, the algorithm runs in constant space O(1).

Problem Challenge 1

Design Gurus Educative.io

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:

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

Example 2:

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

Constraints:

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

Solution

This problem follows the Cyclic Sort pattern and shares similarities with Find all Duplicate Numbers. Following a similar approach, we will place each number at its correct index. Once we are done with the cyclic sort, we will iterate through the array to find the number that is not at the correct index. Since only one number got corrupted, the number at the wrong index is the duplicated number and the index itself represents the missing number.

Code

Here is what our algorithm will look like:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
    def findNumbers(self, nums):
        i = 0  # Initialize a pointer for iteration through the array.
        while i < len(nums):
            # 范围是 [1,n], 所以数字1应该在index=0上
            j = nums[i] - 1  # Calculate the expected index for the current number.
            # 当不在自己的位置上（nums[i] != nums[j]），那就要换位置
            if nums[i] != nums[j]:  # Check if the current number is not at its expected index.
                nums[i], nums[j] = nums[j], nums[i]  # Swap the current number with the one at its expected index.
            else:
                i += 1  # Move to the next element when no swap is needed.

        for i in range(len(nums)):
            if nums[i] != i + 1:  # Find the first number that is not in its correct position.
                return [nums[i], i + 1]  # Return the corrupted number and the number it should be.

        return [-1, -1]  # Return [-1, -1] if no corruption is found.


def main():
    sol = Solution()
    print(sol.findNumbers([3, 1, 2, 5, 2]))
    print(sol.findNumbers([3, 1, 2, 3, 6, 4]))


main()

Time complexity

The time complexity of the above algorithm is O(n).

Space complexity

The algorithm runs in constant space O(1).

# Problem Challenge 2

41. First Missing Positive Design Gurus Educative.io

Find the Smallest Missing Positive Number (medium)

Given an unsorted array containing numbers, find the smallest missing positive number in it.

Note: Positive numbers start from ‘1’.

Example 1:

1
2
3
Input: [-3, 1, 5, 4, 2]
Output: 3
Explanation: The smallest missing positive number is '3'

Example 2:

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

Example 3:

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

Example 4:

1
2
Input: [33, 37, 5]
Output: 1

Constraints:

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

Solution

This problem follows the Cyclic Sort pattern and shares similarities with Find the Missing Number with one big difference. In this problem, the numbers are not bound by any range so we can have any number in the input array.

However, we will follow a similar approach though as discussed in Find the Missing Number to place the numbers on their correct indices and ignore all numbers that are out of the range of the array (i.e., all negative numbers and all numbers greater than or equal to the length of the array). Once we are done with the cyclic sort we will iterate the array and the first index that does not have the correct number will be the smallest missing positive number!

Code

Here is what our algorithm will look like:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution:
    def findNumber(self, nums):
        i, n = 0, len(nums)
        # Rearrange the elements to place each positive integer at its correct index.
        # Negative numbers and numbers greater than the array size are ignored.
        while i < n:
            j = nums[i] - 1 # j表示nums[i]应该在的index， 所以数字1应该在index=0上
            # len(nums) >= nums[i] > 0的话，nums[i]就应该在nums中有一个正确的位置
        	# 所以如果不在（nums[i] != nums[j]），就要调换
            if nums[i] > 0 and nums[i] <= n and nums[i] != nums[j]:
                nums[i], nums[j] = nums[j], nums[i]  # Swap
            else:
                i += 1

        # Find the first index where the element does not match its expected positive value.
        for i in range(n):
            if nums[i] != i + 1:
                return i + 1

        # If all elements from 1 to n are present, return n + 1.
        # 这个忘记了，比如示例[0]就应该返回1
        return len(nums) + 1


def main():
    sol = Solution()
    print(sol.findNumber([-3, 1, 5, 4, 2]))
    print(sol.findNumber([3, -2, 0, 1, 2]))
    print(sol.findNumber([3, 2, 5, 1]))


main()

Time complexity

The time complexity of the above algorithm is O(n).

Space complexity

The algorithm runs in constant space O(1).

*Problem Challenge 3

Similar | 1539. Kth Missing Positive Number Design Gurus Educative.io

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:

1
2
3
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:

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

Example 3:

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

Constraints:

  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= 1000
  • 1 <= k <= 1000
  • nums[i] < nums[j] for 1 <= i < j <= nums.length

Solution

This problem follows the Cyclic Sort pattern and shares similarities with Find the Smallest Missing Positive Number. The only difference is that, in this problem, we need to find the first ‘k’ missing numbers compared to only the first missing number.

We will follow a similar approach as discussed in Find the Smallest Missing Positive Number to place the numbers on their correct indices and ignore all numbers that are out of the range of the array. Once we are done with the cyclic sort we will iterate through the array to find indices that do not have the correct numbers.

If we are not able to find ‘k’ missing numbers from the array, we need to add additional numbers to the output array. To find these additional numbers we will use the length of the array. For example, if the length of the array is 4, the next missing numbers will be 4, 5, 6 and so on. One tricky aspect is that any of these additional numbers could be part of the array. Remember, while sorting, we ignored all numbers that are greater than or equal to the length of the array. So all indices that have the missing numbers could possibly have these additional numbers. To handle this, we must keep track of all numbers from those indices that have missing numbers. Let’s understand this with an example:

1
nums: [2, 1, 3, 6, 5], k =2

After the cyclic sort our array will look like:

1
nums: [1, 2, 3, 6, 5]

From the sorted array we can see that the first missing number is ‘4’ (as we have ‘6’ on the fourth index) but to find the second missing number we need to remember that the array does contain ‘6’. Hence, the next missing number is ‘7’.

Code

Here is what our algorithm will look like:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution:
    def findNumbers(self, nums, k):
        n = len(nums)
        i = 0
        while i < len(nums):
            j = nums[i] - 1 # j表示nums[i]应该在的index， 所以数字1应该在index=0上
        	# 当不在自己的位置上（nums[i] != nums[j]），那就要换位置
            if nums[i] > 0 and nums[i] <= n and nums[i] != nums[j]:
                nums[i], nums[j] = nums[j], nums[i]  # Swap the current element with its correct position.
            else:
                i += 1

        missingNumbers = []
        extraNumbers = set()
        for i in range(n):
            if len(missingNumbers) < k:
                if nums[i] != i + 1:
                    missingNumbers.append(i + 1)  # Add the missing number to the result list.
                    extraNumbers.add(nums[i])  # Keep track of extra numbers encountered.

        # Add the remaining missing numbers
        candidateNumber = n + 1
        while len(missingNumbers) < k:
            # Ignore if the array contains the candidate number
            if candidateNumber not in extraNumbers:
                missingNumbers.append(candidateNumber)  # Add remaining missing numbers to the result list.
            candidateNumber += 1

        return missingNumbers


def main():
    sol = Solution()
    print(sol.findNumbers([3, -1, 4, 5, 5], 3))
    print(sol.findNumbers([2, 3, 4], 3))
    print(sol.findNumbers([-2, -3, 4], 2))


main()

Time complexity

The time complexity of the above algorithm is O(n + k), as the last two for loops will run for O(n) and O(k) times respectively.

Space complexity

The algorithm needs O(k) space to store the extraNumbers(the set).

Author：Hasuer

Link：https://hasuer.github.io/5-pattern-cyclic-sort/index.html

Publish date：May 5th 2024, 2:41:54 pm

Update date：May 28th 2024, 11:27:42 am

License：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. Introduction
  2. 2. *Cyclic Sort (easy)
    1. 2.1. Problem Statement
    2. 2.2. Solution
    3. 2.3. Code
      1. 2.3.1. Time complexity
      2. 2.3.2. Space complexity
  3. 3. *Find the Missing Number (easy)
    1. 3.1. Problem Statement
    2. 3.2. Solution
    3. 3.3. Code
      1. 3.3.1. Time complexity
      2. 3.3.2. Space complexity
  4. 4. Find all Missing Numbers (easy)
    1. 4.1. Problem Statement
    2. 4.2. Solution
    3. 4.3. Code
      1. 4.3.1. Time complexity
      2. 4.3.2. Space complexity
  5. 5. *Find the Duplicate Number (easy)
    1. 5.1. Problem Statement
    2. 5.2. Solution
    3. 5.3. Code
      1. 5.3.1. Time complexity
      2. 5.3.2. Space complexity
    4. 5.4. Similar Problems
  6. 6. Find all Duplicate Numbers (easy)
    1. 6.1. Problem Statement
    2. 6.2. Solution
    3. 6.3. Code
      1. 6.3.1. Time complexity
      2. 6.3.2. Space complexity
  7. 7. Problem Challenge 1
    1. 7.1. Find the Corrupt Pair (easy)
    2. 7.2. Solution
    3. 7.3. Code
      1. 7.3.1. Time complexity
      2. 7.3.2. Space complexity
  8. 8. # Problem Challenge 2
    1. 8.1. Find the Smallest Missing Positive Number (medium)
    2. 8.2. Solution
    3. 8.3. Code
      1. 8.3.1. Time complexity
      2. 8.3.2. Space complexity
  9. 9. *Problem Challenge 3
    1. 9.1. Find the First K Missing Positive Numbers (hard)
    2. 9.2. Solution
    3. 9.3. Code
      1. 9.3.1. Time complexity
      2. 9.3.2. Space complexity
Total : 41
2024
2022
2021
Interview
技术笔记 Grokking-Interview-Pattern