3281. Maximize Score of Numbers in Ranges LeetCode Solution

In this guide, you will get 3281. Maximize Score of Numbers in Ranges LeetCode Solution with the best time and space complexity. The solution to Maximize Score of Numbers in Ranges problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Maximize Score of Numbers in Ranges solution in C++
Maximize Score of Numbers in Ranges solution in Java
Maximize Score of Numbers in Ranges solution in Python
Additional Resources

3281. Maximize Score of Numbers in Ranges LeetCode Solution image

Problem Statement of Maximize Score of Numbers in Ranges

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 ith integer must belong to the ith 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 <= 105
0 <= start[i] <= 109
0 <= d <= 109

Complexity Analysis

Time Complexity: O(n\log(\max – \min))
Space Complexity: O(\texttt{sort})

3281. Maximize Score of Numbers in Ranges LeetCode Solution in C++

class Solution {
 public:
  int maxPossibleScore(vector<int>& start, int d) {
    ranges::sort(start);

    long l = 0;
    long r = (start.back() + d) - start.front() + 1;

    while (l < r) {
      const long m = (l + r) / 2;
      if (isPossible(start, d, m))
        l = m + 1;
      else
        r = m;
    }

    return l - 1;
  }

 private:
  bool isPossible(const vector<int>& start, int d, long m) {
    int lastPick = start[0];
    for (int i = 1; i < start.size(); ++i) {
      if (lastPick + m > start[i] + d)
        return false;
      lastPick = max(lastPick + m, static_cast<long>(start[i]));
    }
    return true;
  }
};
/* code provided by PROGIEZ */

3281. Maximize Score of Numbers in Ranges LeetCode Solution in Java

class Solution {
  public int maxPossibleScore(int[] start, int d) {
    Arrays.sort(start);

    long l = 0;
    long r = (start[start.length - 1] + d) - start[0] + 1;

    while (l < r) {
      final long m = (l + r) / 2;
      if (isPossible(start, d, m))
        l = m + 1;
      else
        r = m;
    }

    return (int) (l - 1);
  }

  private boolean isPossible(int[] start, int d, long m) {
    long lastPick = start[0];
    for (int i = 1; i < start.length; ++i) {
      if (lastPick + m > start[i] + d)
        return false;
      lastPick = Math.max(lastPick + m, (long) start[i]);
    }
    return true;
  }
}
// code provided by PROGIEZ

3281. Maximize Score of Numbers in Ranges LeetCode Solution in Python

class Solution:
  def maxPossibleScore(self, start: list[int], d: int) -> int:
    def isPossible(m: int) -> bool:
      lastPick = start[0]
      for i in range(1, len(start)):
        if lastPick + m > start[i] + d:
          return False
        lastPick = max(lastPick + m, start[i])
      return True

    start.sort()

    maxScore = (start[-1] + d) - start[0] + 1
    l = bisect.bisect_left(range(maxScore), True,
                           key=lambda m: not isPossible(m))
    return l - 1
 # code by PROGIEZ