LeetCode Entry

349. Intersection of Two Arrays

10.03.2024 easy 2024 kotlin rust

Intersection of two nums arrays

349. Intersection of Two Arrays easy blog post substack youtube image.png

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/534

Problem TLDR

Intersection of two nums arrays #easy

Intuition

Built-in Set has an intersect method, that will do the trick. However, as a follow up, there is a O(1) memory solution using sorting (can be done with O(1) memory https://stackoverflow.com/questions/55008384/can-quicksort-be-implemented-in-c-without-stack-and-recursion), then just use two-pointers pattern, move the lowest:

...
      if nums1[i] < nums2[j] { i += 1 } else
      if nums1[i] > nums2[j] { j += 1 } else {
        let x = nums1[i]; res.push(x);
        while (i < nums1.len() && nums1[i] == x) { i += 1 }
        while (j < nums2.len() && nums2[j] == x) { j += 1 }
      }
...

Approach

Let’s write shorter code, to save our own space and time by using built-in implementations.

  • Rust wants into_iter instead of iter, as iter makes vec<&&i32>
  • Rust didn’t compile without cloned

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(n)\)

Code


  fun intersection(nums1: IntArray, nums2: IntArray) =
    nums1.toSet().intersect(nums2.toSet()).toIntArray()



  pub fn intersection(mut nums1: Vec<i32>, mut nums2: Vec<i32>) -> Vec<i32> {
    nums1.into_iter().collect::<HashSet<_>>()
    .intersection(&nums2.into_iter().collect()).cloned().collect()
  }