Solution 1 - Counter (Hash Map)

Count occurrences in the smaller array, then emit matches from the other.

TimeComplexity: O(n+m)

SpaceComplexity: O(\min(n,m))

""" 0350.1 - Intersection of Two Arrays II - Solution 1 - Counter (Hash Map) """

from collections import Counter
from typing import List

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        if len(nums1) > len(nums2):
            nums1, nums2 = nums2, nums1
        c = Counter(nums1)
        out: List[int] = []
        for x in nums2:
            if c[x] > 0:
                out.append(x)
                c[x] -= 1
        return out

if __name__ == "__main__":
    print(Solution().intersect([1,2,2,1],[2,2]))

function intersect(nums1,nums2){
 if(nums1.length>nums2.length) [nums1,nums2]=[nums2,nums1];
 const m=new Map();
 for(const x of nums1) m.set(x,(m.get(x)||0)+1);
 const out=[];
 for(const x of nums2){
  const v=m.get(x)||0;
  if(v>0){ out.push(x); m.set(x,v-1); }
 }
 return out;
}

function intersect(nums1:number[],nums2:number[]):number[]{
 if(nums1.length>nums2.length) [nums1,nums2]=[nums2,nums1];
 const m:Map<number,number>=new Map();
 for(const x of nums1) m.set(x,(m.get(x)??0)+1);
 const out:number[]=[];
 for(const x of nums2){
  const v=m.get(x)??0;
  if(v>0){ out.push(x); m.set(x,v-1); }
 }
 return out;
}

package main

func intersect(nums1, nums2 []int) []int {
	if len(nums1) > len(nums2) {
		nums1, nums2 = nums2, nums1
	}
	cnt := map[int]int{}
	for _, x := range nums1 {
		cnt[x]++
	}
	out := []int{}
	for _, x := range nums2 {
		if cnt[x] > 0 {
			out = append(out, x)
			cnt[x]--
		}
	}
	return out
}

func main() {}

use std::collections::HashMap;

fn intersect(nums1: &[i32], nums2: &[i32]) -> Vec<i32> {
	let (a, b) = if nums1.len() <= nums2.len() { (nums1, nums2) } else { (nums2, nums1) };
	let mut cnt: HashMap<i32, i32> = HashMap::new();
	for &x in a { *cnt.entry(x).or_insert(0) += 1; }
	let mut out: Vec<i32> = vec![];
	for &x in b {
		if let Some(v) = cnt.get_mut(&x) {
			if *v > 0 {
				out.push(x);
				*v -= 1;
			}
		}
	}
	out
}

fn main() {}

Solution 2 - Sorting + Two Pointers

Sort both arrays; walk them with two pointers and collect matches.

TimeComplexity: O(n \log n + m \log m)

SpaceComplexity: O(1)

from typing import List

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        nums1.sort()
        nums2.sort()
        i = j = 0
        out: List[int] = []

        while i < len(nums1) and j < len(nums2):
            if nums1[i] < nums2[j]:
                i += 1
            elif nums1[i] > nums2[j]:
                j += 1
            else:
                out.append(nums1[i])
                i += 1
                j += 1

        return out

function intersectSorted(a,b){
 a=[...a].sort((x,y)=>x-y);
 b=[...b].sort((x,y)=>x-y);
 let i=0,j=0,out=[];
 while(i<a.length && j<b.length){
  if(a[i]<b[j]) i++;
  else if(a[i]>b[j]) j++;
  else { out.push(a[i]); i++; j++; }
 }
 return out;
}

function intersectSorted(a:number[],b:number[]):number[]{
 a=[...a].sort((x,y)=>x-y);
 b=[...b].sort((x,y)=>x-y);
 let i=0,j=0;
 const out:number[]=[];
 while(i<a.length && j<b.length){
  if(a[i]<b[j]) i++;
  else if(a[i]>b[j]) j++;
  else { out.push(a[i]); i++; j++; }
 }
 return out;
}

package main

import "sort"

func intersectSorted(a, b []int) []int {
	sort.Ints(a)
	sort.Ints(b)

	i, j := 0, 0
	out := []int{}
	for i < len(a) && j < len(b) {
		if a[i] < b[j] {
			i++
		} else if a[i] > b[j] {
			j++
		} else {
			out = append(out, a[i])
			i++
			j++
		}
	}
	return out
}

func main() {}

fn intersect_sorted(mut a: Vec<i32>, mut b: Vec<i32>) -> Vec<i32> {
	a.sort_unstable();
	b.sort_unstable();
	let (mut i, mut j) = (0usize, 0usize);
	let mut out: Vec<i32> = vec![];

	while i < a.len() && j < b.len() {
		if a[i] < b[j] { i += 1; }
		else if a[i] > b[j] { j += 1; }
		else { out.push(a[i]); i += 1; j += 1; }
	}
	out
}
fn main() {}

0350 - Intersection of Two Arrays II

Solution 1 - Counter (Hash Map)

Solution 2 - Sorting + Two Pointers