FastPrep
Problem · Array

Choose One from Each Set to Minimize the Range

Learn this problem
● HardInMobi logoInMobiFULLTIMEOA

Problem statement

You are given several non-empty integer sets, represented as an array sets. Every set contains the same number of integers. Choose exactly one integer from each set.

The range of a selection is the difference between its maximum and minimum selected values.

Return the minimum possible range over all valid selections.

Function

minimumSelectionRange(sets: int[][]) → long

Examples

Example 1

sets = [[30,20,10,40],[22,33,44,99],[16,17,18,19]]return = 3

Choose 20, 22, and 19. The range is 22 - 19 = 3, and no selection has a smaller range.

Example 2

sets = [[1,5],[4,8]]return = 1

Choosing 5 from the first set and 4 from the second produces range 1.

Example 3

sets = [[-5],[10],[3]]return = 15

Every set has only one choice, so the range is 10 - (-5) = 15.

Constraints

  • 1 ≤ sets.length ≤ 1,000
  • 1 ≤ sets[i].length
  • sets[i].length = sets[0].length for every valid i.
  • The total number of integers across all sets is at most 200,000.
  • Every value fits in a signed 32-bit integer.

More InMobi problems

drafts saved locally
public long minimumSelectionRange(int[][] sets) {
  // write your code here
}
sets[[30,20,10,40],[22,33,44,99],[16,17,18,19]]
expected3
checking account