medium Frequency of the Most Frequent Element

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

import java.util.Arrays;

class Solution {

  // Method to find the maximum length of subarray that can be made equal to `elements[index]` using at most `maxOperations`.
  private int findMaxSubarrayLength(
    int index,
    int maxOperations,
    int[] elements,
    long[] cumulativeSum
  ) {
    int target = elements[index]; // The target number we want to make others equal to.
    int start = 0; // Start of the search range.
    int end = index; // End of the search range, we consider subarrays ending at `index`.
    int bestLength = index; // This will store the best start position for the longest valid subarray.

    while (start <= end) {
      int mid = (start + end) / 2; // Midpoint of the current search range.
      long count = index - mid + 1; // Number of elements from `mid` to `index`.
      long requiredSum = count * target; // If all elements are `target`, this is the total they would sum to.
      long existingSum =
        cumulativeSum[index] - (mid > 0 ? cumulativeSum[mid - 1] : 0); // Current sum from `mid` to `index`.
      long operationsRequired = requiredSum - existingSum; // How many increments are needed to make all equal to `target`.

      if (operationsRequired > maxOperations) {
        start = mid + 1; // If more operations are required than allowed, move the start up.
      } else {
        bestLength = mid; // Update bestLength as this is a valid subarray.
        end = mid - 1; // Try for a longer valid subarray.
      }
    }

    return index - bestLength + 1; // Return the length of the longest valid subarray.
  }

  // Method to calculate the maximum frequency of any element after at most `maxOperations` increments.
  public int maxFrequency(int[] elements, int maxOperations) {
    Arrays.sort(elements); // Sort the array to facilitate the equalization to the highest element.
    long[] cumulativeSum = new long[elements.length]; // Array to store cumulative sums.
    cumulativeSum[0] = elements[0]; // Initialize the first element of cumulative sum.

    for (int i = 1; i < elements.length; i++) {
      cumulativeSum[i] = elements[i] + cumulativeSum[i - 1]; // Build the cumulative sum array.
    }

    int maximumFrequency = 0;
    for (int i = 0; i < elements.length; i++) {
      maximumFrequency = Math.max(
        maximumFrequency,
        findMaxSubarrayLength(i, maxOperations, elements, cumulativeSum)
      ); // Compute max frequency for each end position.
    }

    return maximumFrequency; // Return the maximum frequency found.
  }

  // Main method to test the algorithm with example inputs.
  public static void main(String[] args) {
    Solution solution = new Solution();

    // Example 1: Expected output is 4
    int[] nums1 = { 1, 2, 3 };
    int k1 = 3;
    System.out.println(
      "Example 1: Output: " + solution.maxFrequency(nums1, k1)
    );

    // Example 2: Expected output is 3
    int[] nums2 = { 4, 4, 4, 1 };
    int k2 = 2;
    System.out.println(
      "Example 2: Output: " + solution.maxFrequency(nums2, k2)
    );

    // Example 3: Expected output is 3
    int[] nums3 = { 10, 9, 9, 4, 8 };
    int k3 = 5;
    System.out.println(
      "Example 3: Output: " + solution.maxFrequency(nums3, k3)
    );
  }
}

Complexity Analysis

Time Complexity

1. Sorting the array: The time complexity of sorting an array is , where (n) is the number of elements in the array.
2. Building the cumulative sum array: The cumulative sum array is constructed in .
3. Finding the maximum frequency for each element: For each element, the binary search within the findMaxSubarrayLength method runs in . Since this binary search is performed for each of the (n) elements, the total time complexity for this part is .

Thus, the overall time complexity of the algorithm is dominated by the sorting and the per-element binary search, both , resulting in a total time complexity of .

Space Complexity

1. Space for the cumulative sum array: , where (n) is the number of elements in the array.
2. Space for the sorted array: This modifies the array in place, hence additional space if we disregard the input space. However, including input space, it is .