Grokking the Coding Interview: Patterns for Coding Questions

0% completed

​

Solution: Smallest Number Range

Problem Statement

Given ‘M’ sorted arrays, find the smallest range that includes at least one number from each of the ‘M’ lists.

Example 1:

Input: L1=[1, 5, 8], L2=[4, 12], L3=[7, 8, 10]
Output: [4, 7]
Explanation: The range [4, 7] includes 5 from L1, 4 from L2 and 7 from L3.

Example 2:

Input: L1=[1, 9], L2=[4, 12], L3=[7, 10, 16]
Output: [9, 12]
Explanation: The range [9, 12] includes 9 from L1, 12 from L2 and 10 from L3

Solution

This problem follows the K-way merge pattern and we can follow a similar approach as discussed in Merge K Sorted Lists.

.....

.....

.....

Like the course? Get enrolled and start learning!
W

Will

· 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.

Manas Sambare

Manas Sambare

· 2 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?

Show 1 reply