Problem Statement

You are given an nums array containing n integers and an integer k. In a single operation, you can choose any index i and increment the nums[i] by 1.

Return the maximum possible frequency of any element of nums after performing at most k operations.

Examples

Example 1:

• Input: nums = [1, 2, 3], k = 3
• Expected Output: 3
• Explanation: We can increment the number 1 two times and 2 one time. The final array will be [3, 3, 3]. Now, the number 3 appears 3 times in the array [3, 3, 3].

Example 2:

• Input: nums = [4, 4, 4, 1], k = 2
• Expected Output: 3
• Explanation: We can increment the number 1 two times (1 -> 2 -> 3). Now, the number 4 still appears 3 times, which is the maximum frequency that can be achieved with 2 operations.

Example 3:

• Input: nums = [10, 9, 9, 4, 8], k = 5
• Expected Output: 4
• Explanation: We can increment the number 9 one time and the number 8 two times (9 -> 10, 9 -> 10; 8 -> 9 -> 10). The number 10 will then appear 4 times in the array [10, 10, 10, 4, 10].

Constraints:

• 1 <= nums.length <= 10⁵
• 1 <= nums[i] <= 10⁵
• 1 <= k <= 10⁵

Solution

To solve the problem of finding the maximum frequency of an element after at most k increments using a binary search approach, we first sort the array. Sorting helps to position similar numbers next to each other, facilitating the application of binary search for efficient checking of possible solutions.

The core idea is to use binary search to find the largest possible subarray ending at each element nums[i] that can be converted into nums[i] within the allowed operations. For each position i, we calculate the total operations needed to make all elements from an earlier position mid up to i equal to nums[i]. This calculation is done using a prefix sum array, which helps in obtaining the sum of any subarray in constant time. We adjust the search range based on whether the operations exceed k or not. This method ensures optimal time complexity as compared to a simple iterative approach.

Step-by-Step Algorithm

1. Sort the Input Array:

   • Begin by sorting the array elements in ascending order. This simplifies the process of attempting to equalize elements to the value of a target element, as we can consider consecutive segments of the array from left to right.

2. Initialize Cumulative Sum Array:

   • Create an array cumulativeSum to store the sum of elements up to each index. This allows for quick calculation of the sum of any subarray which aids in determining the number of operations needed.
   • Set the first element of cumulativeSum equal to the first element of elements.
   • For each subsequent element, accumulate the sum: cumulativeSum[i] = elements[i] + cumulativeSum[i-1].

3. Define the Binary Search Method:

   • For each element elements[index], define it as the target value you might want to achieve for other elements in a subarray ending at this index.
   • Initialize start at 0 and end at index to cover potential subarrays.
   • Use a binary search between start and end:
     • Calculate the midpoint mid.
     • Determine the number of elements from mid to index and the total sum if all these elements were equal to target.
     • Calculate the existing sum of the subarray from mid to index using the cumulativeSum.
     • Determine the operations required to make all elements from mid to index equal to target.
     • If the required operations exceed maxOperations, move the start up to search for a shorter valid subarray. Otherwise, update bestLength to potentially increase the subarray size by moving end down.

4. Iterate Over Each Element to Find Maximum Frequency:

   • For each index in elements, call the findMaxSubarrayLength method to find the maximum length of a valid subarray that can be transformed to have all elements equal to elements[index].
   • Track the maximum value of these lengths to determine the maximum possible frequency.

5. Return the Result:

   • After examining all possible subarrays, return the maximum frequency achieved.

Algorithm Walkthrough

Let's consider the Input: nums = [10, 9, 9, 4, 8], k = 5

• Initial Setup:
  • Sorted array: nums = [4, 8, 9, 9, 10]
  • Cumulative sums: [4, 12, 21, 30, 40]

Processing Each Element

Iteration 1: Checking maximum frequency for nums[0] = 4

• Only one element, maximum frequency is 1.

Iteration 2: Checking maximum frequency for nums[1] = 8

• Target: 8
• Binary Search:
  • Start: 0, End: 1
    • Mid calculation 1:
      • Mid: 0
      • Required sum: 8 * 2 = 16 (to make both 4 and 8 into 8)
      • Existing sum: cumulativeSum[1] = 12
      • Operations Required: 16 - 12 = 4 (within k=5)
      • Update End: End = -1 (found valid subarray from 0 to 1)
    • Resulting Maximum Frequency: 2 (both 4 and 8 changed to 8)

Iteration 3: Checking maximum frequency for nums[2] = 9

• Target: 9
• Binary Search:
  • Start: 0, End: 2
    • Mid calculation 1:
      • Mid: 1
      • Required sum: 9 * 2 = 18 (to make [8, 9] into 9s)
      • Existing sum: cumulativeSum[2] - cumulativeSum[0] = 21 - 4 = 17
      • Operations Required: 18 - 17 = 1 (within k=5)
      • Update End: End = 0 (try finding a larger valid subarray)
    • Mid calculation 2:
      • Mid: 0
      • Required sum: 9 * 3 = 27 (to make [4, 8, 9] all 9)
      • Existing sum: cumulativeSum[2] = 21
      • Operations Required: 27 - 21 = 6 (exceeds k=5)
      • Update Start: Start = 1 (shrink subarray)
    • Resulting Maximum Frequency: 2 (from elements [8, 9] to both be 9)

Iteration 4: Checking maximum frequency for nums[3] = 9

• The resulting maximum frequency will be 3 for [8, 8, 9] array.

Iteration 5: Checking maximum frequency for nums[4] = 10

• Target: 10
• Binary Search:
  • Start: 0, End: 4
    • Mid calculation 1:
      • Mid: 2
      • Required sum: 10 * 3 = 30 (to make [9, 9, 10] all 10)
      • Existing sum: cumulativeSum[4] - cumulativeSum[1] = 40 - 12 = 28
      • Operations Required: 30 - 28 = 2 (within k=5)
      • Update End: End = 1 (try for a larger valid subarray)
    • Mid calculation 2:
      • Mid: 1
      • Required sum: 10 * 4 = 40 (to make [8, 9, 9, 10] all 10)
      • Existing sum: cumulativeSum[4] - cumulativeSum[0] = 40 - 4 = 36
      • Operations Required: 40 - 36 = 4 (within k=5)
      • Update End: End = 0 (try for the largest valid subarray)
    • Mid calculation 3:
      • Mid: 0
      • Required sum: 10 * 5 = 50 (to make [4, 8, 9, 9, 10] all 10)
      • Existing sum: cumulativeSum[4] = 40
      • Operations Required: 50 - 40 = 10 (exceeds k=5)
      • Update Start: Start = 1 (shrink subarray)
    • Resulting Maximum Frequency: 4 (from elements [8, 9, 9, 10] to all be 10)

Code