448. Find All Numbers Disappeared in an Array

• python3

Problem

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.

Pseudocode

0. It must run in O(n) time without using extra space.
1. Check the first element. If it is not in the correct position, replace it with the element that should be there.
2. Repeat step 1 until the element is in the correct position.
3. Move on to the second element and repeat the process.
4. Return the list once all elements are in their correct positions.

Code

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        
        for i in range(len(nums)):
            while nums[nums[i]-1] != nums[i]:
                nums[nums[i]-1], nums[i] = nums[i], nums[nums[i]-1]

        return [i for i in range(1, len(nums)+1) if i != nums[i-1]]
            

Result

• Time Complexity :
  - for loop: Visits each element of the array once, so it is O(n).
  - while loop: Performs swap operations until each element is in its correct position. Once an element is in its correct position, it no longer moves. Therefore, there are at most O(n) swaps in total across the entire array.
  - In the worst case, each element can move only once, so it is O(n).
  Therefore, the overall time complexity is O(n) + O(n) = O(2n), which simplifies to O(n).
• Space Complexity :
  - Space usage: Modifies the input array nums in place, so no additional space is used.
  - Therefore, the space complexity is O(1).

Review

• At first, I thought of this approach, but I hit a wall because I didn't think of using a while loop. Still, my efforts to solve the problem within the constraints will keep helping me improve.