easyArraysPattern: Cyclic Sort / Index Hashing
Find Missing Indices Solution
Problem Statement
Given a positive integer n and an array of distinct integers arr, find all indices from 1 to n that are not present in arr.
Examples
Example 1:
Input:[10, [1, 2, 3, 5, 6, 7, 8, 9, 10]]
Output:[4]
Explanation: The student number 4 is missing from the attendance sheet
Example 2:
Input:[5, [1, 3, 5]]
Output:[2, 4]
Explanation: The student numbers 2 and 4 are missing from the attendance sheet
Constraints
- 1 <= n <= 10^5
- 1 <= arr[i] <= n
Time: O(N) Space: O(1)
Iterate array, use absolute value as index and negate the value at that index. In second pass, any positive value's index + 1 is a missing number. Time O(N), Space O(1).
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
No solution code is currently loaded.
Complete this code in the workspace editor.