Algorithm Problem 001: Maximum Possible Score of an Array

Problem

Problem Source: NowCoder Online Test

Given an array $nums$ indexing from $0$ and a non-negative integer $k$.

In one operation, you can perform the following:

• Choose an index $i$ not chosen before, where $i$ is in the range $[0, nums.length - 1]$.
• Replace $nums[i]$ with any integer in the range $[nums[i] - k, nums[i] + k]$ (inclusive).

After applying any times of operations, return the maximum possible score of the array $nums$.

The array’s score is defined as the “maximum number of repeated elements in the array”.

Note that you can only apply the operation once for each index.

Examples

Example 1

Input:

[4,6,1,2]
2

Output:

3

Explanation:

In this example, we perform the following operations:

• Choose index 1, replace it with 4 (range [4, 8]), nums = [4,4,1,2].
• Choose index 3, replace it with 4 (range [0, 4]), nums = [4,4,1,4].

After applying these operations, the score of array nums is 3 (subsequence composed of indices 0, 1, and 3). It can be proved that 3 is the maximum possible length we can achieve.

Example 2

Input:

[1,1,1,1]
10

Output:

4

Explanation:

In this example, no operations are needed.

The score of array nums is 4 (the entire array).

Approach

Rereading the Problem

Let’s restate the problem:

Given an array $nums$ and a natural number $k$.

For any index $i$, we can replace the element $nums[i]$ with any integer in the range $[nums[i] - k, nums[i] + k]$. An index can only be operated on once, or not at all.

Return the maximum possible count of repeated elements in the array $nums$ after any times of operations.

Observation 1: Sorting

To maximize the number of repeated elements, we need to operate on elements that are close in value to make them equal.

How to find elements that are close in value? — Sorting

Observation 2: Finding a Pattern

Assume, after sorting, we attempt to make elements in the interval $[i, j]$ equal after operations. What conditions should $i$ and $j$ satisfy?

• After sorting, we know that $nums[i] \le nums[i + 1] \le \cdots \le nums[j - 1] \le nums[j]$.
• The replacement range for $nums[i]$ is $[nums[i] - k, nums[i] + k]$, and for $nums[j]$ is $[nums[j] - k, nums[j] + k]$.
• Therefore, $nums[i] + k \ge nums[j] - k$.
• Simplifying, we get $0 \le nums[j] - nums[i] \le 2k$.

It can be seen that when $i$ is fixed, to maximize the range $j - i + 1$, we need to find a $j$ such that $nums[j] - nums[i]$ is as close to $2k$ as possible. This way, the interval range $j - i + 1$ could be the desired answer.

Observation 3: Sliding Window

After our analysis, this problem becomes:

• For a sorted array $nums$ and a natural number $k$.
• When index $i$ is fixed, we need to find the maximum index $j$ such that $0 \le nums[j] - nums[i] \le 2k$.
• Among all possible intervals $[i, j]$, the maximum $j - i + 1$ is the answer.

Now, using the sliding window algorithm can reduce the time complexity from $O(n^2)$ (brute-force) to $O(n)$.

Code

Java

import java.util.Arrays;

public class Solution {
    public int maximumScore(int[] nums, int k) {
        int n = nums.length;

        Arrays.sort(nums);

        // sliding window
        int ans = 1;
        for (int i = 0, j = 0; i < n; i++) {
            while (j < n && nums[j] <= nums[i] + 2 * k) j++;
            ans = Math.max(ans, j - i);
        }

        return ans;
    }
}