Hash the smaller collection09.04
Building a set costs memory and insert time proportional to that collection. Put the smaller one in the set, scan the larger with contains. Expected time O(n+m), extra space O(min(n,m)).
If you always hash a, a huge a and tiny b wastes space.
worked examples
Same skill, three traces. Read all three before you try it.
01a smaller - given
a = [4, 1],b = [9, 1, 4, 8]- walk
set size
2scan
4values- result
- hash
a
02b smaller - given
a = [4, 1, 9, 8],b = [1, 8]- walk
set size
2scan
4values- result
- hash
b
03empty - given
a = [],b = [4, 1, 9]- walk
set
{}- result
- hash
a, every query misses
Write
a and
Return which array to put in the set: the smaller one. If lengths are equal, either is fine.
hashWhich(a, b).a and
b are arrays of integers.Return which array to put in the set: the smaller one. If lengths are equal, either is fine.
a = [4, 1], b = [9, 1, 4, 8] → hash a.a = [4, 1, 9, 8], b = [1, 8] → hash b.a = [], b = [4, 1, 9] → hash a, every query misses.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.