271. Is One a Subset of the Other
Core1000 ms256 MBSolved by 0%
Print Yes if every value in the second list also appears in the first, with
at least as many copies. Print No otherwise.
Multiplicity counts. 1 1 is a subset of 1 1 2, and 1 1 1 is not,
because the first list has only two ones.
The lists arrive in any order. Sort both and a single two-pointer sweep answers
it, which is O(n log n) and beats checking each value against the whole first
list.
Constraints - `1 ≤ n ≤ 200000` - `1 ≤ m ≤ 200000` - `-1000000000 ≤ values ≤ 1000000000`
Input
The first line contains two integers n and m.
The second line contains n integers.
The third line contains m integers.
Output
Print Yes or No on one line.
Input4 2
1 2 3 4
2 4
OutputYes
Noteis a plain subset
Input3 1
1 2 3
4
OutputNo
Noteasks for a value that is not present at all
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.
Hint 1Where to start
Hint 2The approachOpen hint 1 first. This one carries on from it.
Hint 3PseudocodeOpen hint 2 first. This one carries on from it.
Hint 4Full solutionOpen hint 3 first. This one carries on from it.