LeetCode Entry
442. Find All Duplicates in an Array
All duplicate numbers of 1..n using O(1) memory
442. Find All Duplicates in an Array medium
blog post
substack
youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/549
Problem TLDR
All duplicate numbers of 1..n using O(1) memory #medium
Intuition
There are no restrictions not to modify the input array, so let’s flat all visited numbers with a negative sign:
// 1 2 3 4 5 6 7 8
// 4 3 2 7 8 2 3 1
// * -
// * -
// - *
// * -
// * -
// - * --2
// - * --3
// - *
Inputs are all positive, the corner cases of negatives and zeros are handled.
Approach
- don’t forget to
abs - Rust didn’t permit to iterate and modify at the same time, use pointers
Complexity
-
Time complexity: \(O(n)\)
-
Space complexity: \(O(1)\)
Code
fun findDuplicates(nums: IntArray) = buildList {
for (x in nums) {
if (nums[abs(x) - 1] < 0) add(abs(x))
nums[abs(x) - 1] *= -1
}
}
pub fn find_duplicates(mut nums: Vec<i32>) -> Vec<i32> {
let mut res = vec![];
for j in 0..nums.len() {
let i = (nums[j].abs() - 1) as usize;
if nums[i] < 0 { res.push(nums[j].abs()) }
nums[i] *= -1
}
res
}