Find common values with a set09.01
Common values are the intersection. Put the first array into a set, scan the second, keep a value when contains hits (and maybe delete it if you want each common value once).
If both arrays are huge, hash the smaller. Nested loops are O(n m). This is expected O(n+m).
worked examples
Same skill, three traces. Read all three before you try it.
01overlap - given
a = [4, 1, 9],b = [1, 8, 4]- walk
set
a, scanb, hits1and4- result
{1, 4}
02none - given
a = [4, 1, 9],b = [8, 2]- walk
no contains
- result
{}
03empty - given
a = [],b = [4, 1, 9]- walk
empty set
- result
{}
Write
a and
Put a into a set. Scan
commons(a, b).a and
b are arrays of integers.Put a into a set. Scan
b. Return each common value once (delete-on-hit if b repeats).a = [4, 1, 9], b = [1, 8, 4] → {1, 4}.a = [4, 1, 9], b = [8, 2] → {}.a = [], b = [4, 1, 9] → {}.constraintsa and b are lists of integers and may be empty.
- Intersection of Two Arrays0/2 skills ready · hash sets · easyopen
- Intersection of Two Arrays0/2 skills ready · hash sets · easyopen
Every Check with Awel is frozen here. Open one to read the code or load it back into the editor.