0% completed
Solution: Smallest Number Range
.....
.....
.....
Anonymous
· 3 years ago
The question states "Given ‘M’ sorted arrays", however, there is a test case that contradicts this statement.
Input: [[1, 2, 3], [4, 13, 6], [7, 2, 7]] Expected: [3,7]
Even if we assume that we sort these arrays to form:
Input: [[1, 2, 3], [4, 6, 13], [2, 7, 7]]
Shouldn't the expected answer be:
Expected: [2,4]
Since '2' exists in array 0 and 3, and '4' exists in array 1?
Anonymous
· 4 years ago
The key insight/ intuition (non-obvious) is that- if you did a worked example first- you'd find that the heap always contains ONLY 1 element from each list/ row array. The heap NEVER contains 2 or more elements from the SAME list.
This is important because it means that the range calculated at every iteration is always guaranteed to be a range that has exactly 1 element from every single list!
I think the description lacks this key detail, as it's just asserted that the stated solution works but it's not immediately obvious that it should.
Reading Progress
0%