LeetCode Entry
2657. Find the Prefix Common Array of Two Arrays
Duplicates in prefixes
2657. Find the Prefix Common Array of Two Arrays medium substack youtube
https://dmitrysamoylenko.com/leetcode/
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/1365
Problem TLDR
Duplicates in prefixes
Intuition
Only 50 elements, brute-force works. We can use HashSets or bitmasks
Approach
- shortest version in Kotlin is O(n^2)
- in Rust we can use zip+scan, or a simple map
Complexity
-
Time complexity: \(O(n^2|n)\)
-
Space complexity: \(O(n)\)
Code
fun findThePrefixCommonArray(a: IntArray, b: IntArray) =
(1..a.size).map {a.take(it).intersect(b.take(it)).size}
pub fn find_the_prefix_common_array(a: Vec<i32>, b: Vec<i32>) -> Vec<i32> {
let (mut c, mut d) = (0, 0i64);
(0..a.len()).map(|i|{c|=1<<a[i];d|=1<<b[i];(c&d).count_ones() as _}).collect()
}