3281. Maximize Score of Numbers in Ranges - Solution

The problem

You are given an array of integers start and an integer d, representing n intervals [start[i], start[i] + d].

You are asked to choose n integers where the i^th integer must belong to the i^th interval. The score of the chosen integers is defined as the minimum absolute difference between any two integers that have been chosen.

Return the maximum possible score of the chosen integers.

Example 1:

Input: start = [6,0,3], d = 2

Output: 4

Explanation:

The maximum possible score can be obtained by choosing integers: 8, 0, and 4. The score of these chosen integers is min(|8 - 0|, |8 - 4|, |0 - 4|) which equals 4.

Example 2:

Input: start = [2,6,13,13], d = 5

Output: 5

Explanation:

The maximum possible score can be obtained by choosing integers: 2, 7, 13, and 18. The score of these chosen integers is min(|2 - 7|, |2 - 13|, |2 - 18|, |7 - 13|, |7 - 18|, |13 - 18|) which equals 5.

Constraints:

2 <= start.length <= 10⁵
0 <= start[i] <= 10⁹
0 <= d <= 10⁹

Approach overview

Problem Overview: You are given multiple numeric ranges. From each range, you must pick exactly one number. The goal is to maximize the minimum difference between any two chosen numbers after ordering them. This turns the task into spacing selections as far apart as possible while staying inside each interval.

Approach 1: Greedy Selection from Intervals (O(n log n) time, O(1) space)

Sort the ranges by their starting value using sorting. Then iterate through the intervals and always pick the smallest feasible number that keeps the difference from the previously chosen number as large as possible. The greedy rule is simple: choose max(range_start, prev + diff) while ensuring the value does not exceed the interval's end. This works because selecting the earliest valid number leaves the most room for later intervals. The approach relies on interval ordering and greedy placement to maintain spacing.

Approach 2: Binary Search for Optimal Difference (O(n log n + n log D) time, O(1) space)

The optimal solution uses binary search on the answer. Instead of directly maximizing the score, guess a candidate minimum difference d. Then verify if it's possible to pick numbers from each interval such that every chosen value is at least d apart. The feasibility check runs greedily: iterate through sorted intervals and place the earliest allowed value that is ≥ prev + d. If the value exceeds the interval end, the candidate difference is impossible. Because feasibility is monotonic (if d works, smaller values also work), binary search efficiently finds the largest valid difference.

The greedy feasibility check leverages the ordered structure of intervals and ensures each placement keeps future choices flexible. This pattern—binary searching the answer while validating with a greedy pass—is common in spacing problems involving arrays, greedy strategies, and interval constraints.

Recommended for interviews: The binary search on the answer combined with a greedy feasibility check is the approach most interviewers expect. It demonstrates understanding of monotonic properties and interval placement. Implementing the greedy check first helps validate the idea, while the binary search layer shows algorithmic optimization.

Approach 1: Greedy Selection from Intervals

This approach leverages a simple greedy strategy to select the number at the upper bound of each interval if possible. This choice maximizes the subsequent space for the next interval and hence the difference between the numbers chosen from consecutive intervals.

Sorting the intervals from smallest to largest ensures that we're optimizing space allocation sequentially.

Python

def maxScore(start, d):
    start.sort()
    min_diff = d + 1
    for i in range(1, len(start)):
        diff = start[i] - start[i - 1]
        if diff > d:
            curr_diff = diff - d
            min_diff = min(min_diff, curr_diff)
    return min_diff

# Example usage
start = [6, 0, 3]
d = 2
print(maxScore(start, d))  # Output: 4

Java

import java.util.Arrays;

public class MaxScore {
    public static int maxScore(int[] start, int d) {
        Arrays.sort(start);
        int minDiff = d + 1;
        for (int i = 1; i < start.length; i++) {
            int diff = start[i] - start[i - 1];
            if (diff > d) {
                int currDiff = diff - d;
                minDiff = Math.min(minDiff, currDiff);
            }
        }
        return minDiff;
    }

    public static void main(String[] args) {
        int[] start = {6, 0, 3};
        int d = 2;
        System.out.println(maxScore(start, d)); // Output: 4
    }
}

C++

#include <iostream>
#include <vector>
#include <algorithm>

int maxScore(std::vector<int>& start, int d) {
    std::sort(start.begin(), start.end());
    int minDiff = d + 1;
    for (size_t i = 1; i < start.size(); ++i) {
        int diff = start[i] - start[i - 1];
        if (diff > d) {
            int currDiff = diff - d;
            minDiff = std::min(minDiff, currDiff);
        }
    }
    return minDiff;
}

int main() {
    std::vector<int> start = {6, 0, 3};
    int d = 2;
    std::cout << maxScore(start, d) << std::endl; // Output: 4
    return 0;
}

JavaScript

function maxScore(start, d) {
    start.sort((a, b) => a - b);
    let minDiff = d + 1;
    for (let i = 1; i < start.length; i++) {
        let diff = start[i] - start[i - 1];
        if (diff > d) {
            let currDiff = diff - d;
            minDiff = Math.min(minDiff, currDiff);
        }
    }
    return minDiff;
}

// Example usage
let start = [6, 0, 3];
let d = 2;
console.log(maxScore(start, d)); // Output: 4

#include <stdio.h>
#include <stdlib.h>

int compare(const void *a, const void *b) {
    return (*(int *)a - *(int *)b);
}

int maxScore(int* start, int startSize, int d) {
    qsort(start, startSize, sizeof(int), compare);
    int minDiff = d + 1;
    for (int i = 1; i < startSize; i++) {
        int diff = start[i] - start[i - 1];
        if (diff > d) {
            int currDiff = diff - d;
            if (currDiff < minDiff) minDiff = currDiff;
        }
    }
    return minDiff;
}

int main() {
    int start[] = {6, 0, 3};
    int d = 2;
    printf("%d\n", maxScore(start, 3, d)); // Output: 4
    return 0;
}

using System;

public class MaxScoreCalculator {
    public static int MaxScore(int[] start, int d) {
        Array.Sort(start);
        int minDiff = d + 1;
        for (int i = 1; i < start.Length; i++) {
            int diff = start[i] - start[i - 1];
            if (diff > d) {
                int currDiff = diff - d;
                minDiff = Math.Min(minDiff, currDiff);
            }
        }
        return minDiff;
    }
    
    public static void Main() {
        int[] start = {6, 0, 3};
        int d = 2;
        Console.WriteLine(MaxScore(start, d)); // Output: 4
    }
}

Python's solution is concise, utilizing built-in list sort and simple loop iteration. The primary logic follows the same approach as the others: finding where to minimize distance covered within bounds.

Complexity

Time Complexity: O(n log n) due to list sorting
Space Complexity: O(1), as list operations are in-place.

Try this approach in the editor

Approach 2: Binary Search for Optimal Difference

This approach leverages binary search to identify the maximum score possible through repeatedly checking if a specific minimum difference is feasible. Adjusting the range and verifying selections ensures a balanced computational load while persistently searching for the exact maximum.

Binary search allows pruning of feasible solutions, narrowing results efficiently.

Python

def isFeasible(start, d, minDiff):
    prev = start[0] + d
    for i in range(1, len(start)):
        max_val = start[i] + d
        if prev + minDiff > max_val:
            prev = start[i]
        else:
            prev = prev + minDiff
    return prev > start[-1]


def maxScore(start, d):
    start.sort()
    low, high = 0, start[-1] + d - start[0]
    ans = 0
    while low <= high:
        mid = low + (high - low) // 2
        if isFeasible(start, d, mid):
            ans = mid
            low = mid + 1
        else:
            high = mid - 1
    return ans

# Example usage
start = [6, 0, 3]
d = 2
print(maxScore(start, d))  # Output: 4

Java

import java.util.Arrays;

public class MaxScore {
    private static boolean isFeasible(int[] start, int d, int minDiff) {
        int prev = start[0] + d;
        for (int i = 1; i < start.length; i++) {
            int maxVal = start[i] + d;
            if (prev + minDiff > maxVal) {
                prev = start[i];
            } else {
                prev = prev + minDiff;
            }
        }
        return prev > start[start.length - 1];
    }

    public static int maxScore(int[] start, int d) {
        Arrays.sort(start);
        int low = 0, high = start[start.length - 1] + d - start[0], ans = 0;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (isFeasible(start, d, mid)) {
                ans = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        int[] start = {6, 0, 3};
        int d = 2;
        System.out.println(maxScore(start, d)); // Output: 4
    }
}

C++

#include <iostream>
#include <vector>
#include <algorithm>

bool isFeasible(const std::vector<int>& start, int d, int minDiff) {
    int prev = start[0] + d;
    for (size_t i = 1; i < start.size(); ++i) {
        int maxVal = start[i] + d;
        if (prev + minDiff > maxVal) {
            prev = start[i];
        } else {
            prev = prev + minDiff;
        }
    }
    return prev > start.back();
}

int maxScore(std::vector<int>& start, int d) {
    std::sort(start.begin(), start.end());
    int low = 0, high = start.back() + d - start.front(), ans = 0;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (isFeasible(start, d, mid)) {
            ans = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return ans;
}

int main() {
    std::vector<int> start = {6, 0, 3};
    int d = 2;
    std::cout << maxScore(start, d) << std::endl; // Output: 4
    return 0;
}

JavaScript

function isFeasible(start, d, minDiff) {
    let prev = start[0] + d;
    for (let i = 1; i < start.length; i++) {
        let maxVal = start[i] + d;
        if (prev + minDiff > maxVal) {
            prev = start[i];
        } else {
            prev = prev + minDiff;
        }
    }
    return prev > start[start.length - 1];
}

function maxScore(start, d) {
    start.sort((a, b) => a - b);
    let low = 0, high = start[start.length - 1] + d - start[0];
    let ans = 0;
    while (low <= high) {
        let mid = low + Math.floor((high - low) / 2);
        if (isFeasible(start, d, mid)) {
            ans = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return ans;
}

// Example usage
let start = [6, 0, 3];
let d = 2;
console.log(maxScore(start, d)); // Output: 4

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

int compare(const void *a, const void *b) {
    return (*(int *)a - *(int *)b);
}

bool isFeasible(int *start, int startSize, int d, int minDiff) {
    int prev = start[0] + d;
    for (int i = 1; i < startSize; i++) {
        int maxVal = start[i] + d;
        if (prev + minDiff > maxVal) {
            prev = start[i];
        } else {
            prev = prev + minDiff;
        }
    }
    return prev > start[startSize - 1];
}

int maxScore(int* start, int startSize, int d) {
    qsort(start, startSize, sizeof(int), compare);
    int low = 0, high = start[startSize - 1] + d - start[0], ans = 0;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (isFeasible(start, startSize, d, mid)) {
            ans = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return ans;
}

int main() {
    int start[] = {6, 0, 3};
    int d = 2;
    printf("%d\n", maxScore(start, 3, d)); // Output: 4
    return 0;
}

using System;

public class MaxScoreCalculator {
    private static bool IsFeasible(int[] start, int d, int minDiff) {
        int prev = start[0] + d;
        for (int i = 1; i < start.Length; i++) {
            int maxVal = start[i] + d;
            if (prev + minDiff > maxVal) {
                prev = start[i];
            } else {
                prev = prev + minDiff;
            }
        }
        return prev > start[^1];
    }

    public static int MaxScore(int[] start, int d) {
        Array.Sort(start);
        int low = 0, high = start[^1] + d - start[0], ans = 0;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (IsFeasible(start, d, mid)) {
                ans = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return ans;
    }
    
    public static void Main() {
        int[] start = {6, 0, 3};
        int d = 2;
        Console.WriteLine(MaxScore(start, d)); // Output: 4
    }
}

The Python solution involves recursive checking within a binary search layout, adhering to feasibility constraints and updating low/high ranges to pinpoint the maximum allowable score value.

Complexity

Time Complexity: O(n log(maxDifference)), typically iterative refinement cycles.
Space Complexity: O(1), aside from temporary indices and references.

Try this approach in the editor

Approach 3: Sorting + Binary Search

We can first sort the start array. Then, we consider selecting integers from left to right, where the score is equal to the minimum difference between any two adjacent selected integers.

If a difference x satisfies the condition, then any x' < x will also satisfy the condition. Therefore, we can use binary search to find the largest difference that satisfies the condition.

We define the left boundary of the binary search as l = 0 and the right boundary as r = start[-1] + d - start[0]. Each time, we take the middle value mid = \left\lfloor \frac{l + r + 1}{2} \right\rfloor and check whether it satisfies the condition.

We define a function check(mi) to determine whether the condition is satisfied, implemented as follows:

We define a variable last = -infty, representing the last selected integer.
We traverse the start array. If last + mi > st + d, it means we cannot select the integer st, and we return false. Otherwise, we update last = max(st, last + mi).
If we traverse the entire start array and all conditions are satisfied, we return true.

The time complexity is O(n times log M), where n and M are the length and the maximum value of the start array, respectively. The space complexity is O(1).

TypeScript

function maxPossibleScore(start: number[], d: number): number {
    start.sort((a, b) => a - b);
    let [l, r] = [0, start.at(-1)! + d - start[0]];
    const check = (mi: number): boolean => {
        let last = -Infinity;
        for (const st of start) {
            if (last + mi > st + d) {
                return false;
            }
            last = Math.max(st, last + mi);
        }
        return true;
    };
    while (l < r) {
        const mid = l + ((r - l + 1) >> 1);
        if (check(mid)) {
            l = mid;
        } else {
            r = mid - 1;
        }
    }
    return l;
}

func maxPossibleScore(start []int, d int) int {
	check := func(mi int) bool {
		last := math.MinInt64
		for _, st := range start {
			if last+mi > st+d {
				return false
			}
			last = max(st, last+mi)
		}
		return true
	}
	sort.Ints(start)
	l, r := 0, start[len(start)-1]+d-start[0]
	for l < r {
		mid := (l + r + 1) >> 1
		if check(mid) {
			l = mid
		} else {
			r = mid - 1
		}
	}
	return l
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Greedy Selection from Intervals	Time Complexity: O(n log n) due to list sorting Space Complexity: O(1), as list operations are in-place.
Binary Search for Optimal Difference	Time Complexity: O(n log(maxDifference)), typically iterative refinement cycles. Space Complexity: O(1), aside from temporary indices and references.
Sorting + Binary Search	–

Complexity analysis

Approach	Time	Space	When to Use
Greedy Selection from Intervals	O(n log n)	O(1)	When verifying feasibility of placements or building the greedy core logic for interval selection
Binary Search for Optimal Difference	O(n log n + n log D)	O(1)	General case to maximize the minimum distance between chosen values across ranges

Frequently asked questions

Is Maximize Score of Numbers in Ranges easy or hard?

The problem is generally classified as Medium. The greedy feasibility check is straightforward, but recognizing that the answer can be optimized with binary search requires experience with spacing and monotonic decision problems.

Maximize Score of Numbers in Ranges Python/Java solution

In Python or Java, the typical implementation sorts the intervals, performs binary search over the possible difference range, and runs a greedy check to place numbers. The greedy step tracks the last selected value and ensures the next chosen value is at least the candidate difference away.

How to solve Maximize Score of Numbers in Ranges in O(n)?

A pure O(n) solution is not typical because the intervals generally must be sorted first. After sorting, each feasibility check runs in O(n) using a greedy placement strategy. The complete optimal approach becomes O(n log n + n log D) due to sorting and binary search.

What is the best approach for Maximize Score of Numbers in Ranges?

The most efficient approach uses binary search on the minimum difference combined with a greedy feasibility check. After sorting the ranges, binary search guesses the minimum spacing and verifies whether numbers can be chosen from each interval while maintaining that distance. This reduces the problem to O(n log n + n log D) time.

Is Maximize Score of Numbers in Ranges asked at Google/Amazon/Meta?

Problems involving maximizing minimum distance with binary search and greedy placement frequently appear in interviews at companies like Google, Amazon, and Meta. Variants include aggressive cows, placing routers, and interval spacing problems.

What data structure is used in Maximize Score of Numbers in Ranges?

The main structure is a sorted array of intervals. The algorithm relies on greedy iteration across the array while maintaining the previously selected value. Binary search is used to optimize the minimum allowed difference.

What is the time complexity of Maximize Score of Numbers in Ranges?

The optimal solution runs in O(n log n + n log D) time. Sorting the ranges takes O(n log n), and each binary search step performs a linear greedy check over the intervals. Space complexity is O(1) beyond the input array.

Maximize Score of Numbers in Ranges solution and explanation

The problem

Approach overview

Approach 1: Greedy Selection from Intervals

Approach 2: Binary Search for Optimal Difference

Approach 3: Sorting + Binary Search

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Maximize Score of Numbers in Ranges solution and explanation

The problem

Approach overview

Approach 1: Greedy Selection from Intervals

Approach 2: Binary Search for Optimal Difference

Approach 3: Sorting + Binary Search

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems