LeetCode Entry
350. Intersection of Two Arrays II
Array intersection with duplicates
350. Intersection of Two Arrays II easy
blog post
substack
youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/657
Problem TLDR
Array intersection with duplicates #easy
Intuition
We can do sorting and two pointers. If nums2 on a hard disk, let’s not touch it, just iterate once. For nums1 we can use a counting sort for O(n) solution. For code golf, we can modify nums1 in-place with O(n^2) solution.
Approach
Golf in Kotlin, can you make it shorter? Counting sort in Rust.
Complexity
-
Time complexity: \(O(n)\) for counting sort, O(nlogn) for both sort & two pointers
-
Space complexity: \(O(n)\) for counting sort (n = 1000), O(1) for sort & two pointers
Code
fun intersect(nums1: IntArray, nums2: IntArray) = nums2.filter {
val i = nums1.indexOf(it); if (i >= 0) nums1[i] = -1; i >= 0
}
pub fn intersect(nums1: Vec<i32>, nums2: Vec<i32>) -> Vec<i32> {
let mut f = vec![0; 1001]; for n in nums1 { f[n as usize] += 1 }
nums2.into_iter().filter(|&n| {
let b = f[n as usize] > 0; f[n as usize] -= 1; b
}).collect()
}