Skip to main content

Minimal Span Containing All Colour Groups

hard
ArrayTwo PointersSortingSliding WindowHash TableSliding WindowTwo Pointer Pair Sum
Asked atGoogleAmazonMetaBloomberg

Problem Description

You are given `k` groups of integers (representing colours), where `groups[i]` is a sorted list of integers belonging to colour `i`. Each group is sorted in ascending order.

Find the smallest range `[lo, hi]` such that there is at least one integer from each colour group within `[lo, hi]`. If multiple ranges have the same length, return the lexicographically smallest one (i.e., the one with the smaller `lo`).

Return the range as an array `[lo, hi]`.

**Example 1:**
```
Input: groups = [[4, 10, 15, 24], [0, 9, 12, 20], [5, 18, 22, 30]]
Output: [20, 24]
Explanation: groups[0][3]=24, groups[1][3]=20, groups[2][2]=22 all lie in [20,24], span = 4.
```

**Example 2:**
```
Input: groups = [[1, 5], [3, 9], [7, 11]]
Output: [5, 7]
Explanation: 5 (group 0), 7 (group 2), and we need 3 or 9 from group 1 — use [5, 9] span 4? Actually [7,9]: 7 from group 2, 9 from group 1, 5 is NOT in [7,9] for group 0 — use indices: [5,7] doesn't cover group 1 (min is 3 or 9). Correct answer is [3, 7]: 5∈[3,7], 3∈[3,7], 7∈[3,7]. Output: [3, 7]
```

**Example 2 (corrected):**
```
Input: groups = [[1, 5], [3, 9], [7, 11]]
Output: [5, 9]
Explanation: 5 from group 0, 9 from group 1, 7 from group 2. All in [5, 9], span = 4. No smaller span covers all groups.
```

Constraints

  • 1 <= groups.length <= 100
  • 1 <= groups[i].length <= 500
  • -10^5 <= groups[i][j] <= 10^5
  • groups[i] is sorted in non-decreasing order

Follow-up

What if elements can belong to multiple groups? How would you adapt the sliding-window approach?

Hints

Try the problem first. If you get stuck, you can reveal hints one at a time.

Solution

Leaderboard

No entries yet for python.

Be the first — submit an accepted solution.