3346. Maximum Frequency of an Element After Performing Operations I

[mah-shamim]

Topics: Array, Binary Search, Sliding Window, Sorting, Prefix Sum, Biweekly Contest 143

You are given an integer array nums and two integers k and numOperations.

You must perform an operation numOperations times on nums, where in each operation you:

• Select an index i that was not selected in any previous operations.
• Add an integer in the range [-k, k] to nums[i].

Return the maximum possible frequency¹ of any element in nums after performing the operations.

Example 1:

• Input: nums = [1,4,5], k = 1, numOperations = 2
• Output: 2
• Explanation: We can achieve a maximum frequency of two by:
  • Adding 0 to nums[1]. nums becomes [1, 4, 5].
  • Adding -1 to nums[2]. nums becomes [1, 4, 4].

Example 2:

• Input: nums = [5,11,20,20], k = 5, numOperations = 1
• Output: 2
• Explanation: We can achieve a maximum frequency of two by:
  • Adding 0 to nums[1].

Constraints:

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

Hint:

1. Sort the array and try each value in range as a candidate.

Footnotes

1. Frequency: The frequency of an element x is the number of times it occurs in the array. ↩

[mah-shamim]

We need to find the maximum frequency of any element after performing operations where we can add values in the range [-k, k] to distinct elements.

Approach

The key insight is that for any target value x, the number of elements that can be transformed to x is:

• Elements already equal to x
• Plus elements within range [x-k, x+k] that can be transformed to x
• But limited by the number of operations available

The solution works by:

1. Finding the range of possible target values (from minV-k to maxV+k)
2. Using a difference array to efficiently count how many elements can reach each possible target
3. For each target value, calculating the maximum possible frequency considering both the elements that can reach it and the operations available

Let's implement this solution in PHP: 3346. Maximum Frequency of an Element After Performing Operations I

<?php
/**
 * @param Integer[] $nums
 * @param Integer $k
 * @param Integer $numOperations
 * @return Integer
 */
function maxFrequency($nums, $k, $numOperations) {
    $n = count($nums);
    if ($n === 0) return 0;

    // Find the range of possible target values
    $minV = min($nums);
    $maxV = max($nums);
    $L = $minV - $k;
    $R = $maxV + $k;
    $size = $R - $L + 1;
    $offset = -$L; // To map values to array indices

    // Initialize arrays
    $diff = array_fill(0, $size + 1, 0);
    $exact = array_fill(0, $size, 0);

    // For each element, mark the range of values it can be transformed to
    foreach ($nums as $v) {
        // The element v can be transformed to any value in [v-k, v+k]
        $left = max(0, $v - $k + $offset);
        $right = min($size - 1, $v + $k + $offset);

        $diff[$left] += 1;
        if ($right + 1 < count($diff)) {
            $diff[$right + 1] -= 1;
        }

        // Count exact occurrences
        $exactPos = $v + $offset;
        if ($exactPos >= 0 && $exactPos < $size) {
            $exact[$exactPos] += 1;
        }
    }

    // Calculate prefix sums to get coverage count for each position
    $ans = 0;
    $current = 0;
    for ($i = 0; $i < $size; $i++) {
        $current += $diff[$i];
        $coverage = $current;  // Elements that can reach value (L + i)
        $already = $exact[$i]; // Elements already equal to (L + i)

        // Maximum frequency is limited by:
        // 1. Number of elements that can reach this value
        // 2. Number of exact matches plus available operations
        $possible = min($coverage, $already + $numOperations);
        if ($possible > $ans) {
            $ans = $possible;
        }
    }

    return $ans;
}

// Test cases
$nums1 = [1, 4, 5];
$k1 = 1;
$numOperations1 = 2;
echo "Output 1: " . maxFrequency($nums1, $k1, $numOperations1) . "\n"; // Expected: 2

$nums2 = [5, 11, 20, 20];
$k2 = 5;
$numOperations2 = 1;
echo "Output 2: " . maxFrequency($nums2, $k2, $numOperations2) . "\n"; // Expected: 2

// Example 3
$nums = [88, 53];
$k = 27;
$numOperations = 2;
echo "Output: " . maxFrequency($nums, $k, $numOperations) . "\n"; // Expected: 2

// Example 4
$nums = [2,70,73];
$k = 39;
$numOperations = 2;
echo "Output: " . maxFrequency($nums, $k, $numOperations) . "\n"; // Expected: 2

// Example 5
$nums = [58,80,5];
$k = 58;
$numOperations = 3;
echo "Output: " . maxFrequency($nums, $k, $numOperations) . "\n"; // Expected: 3

// Example 6
$nums = [2,49];
$k = 58;
$numOperations = 0;
echo "Output: " . maxFrequency($nums, $k, $numOperations) . "\n"; // Expected: 1
?>

Explanation:

1. Range Calculation: We determine the range of possible target values by considering the minimum and maximum values in the array, extended by ±k.

2. Difference Array: We use a difference array technique to efficiently mark ranges. For each element v, it can contribute to all target values in [v-k, v+k].

3. Exact Count: We also track how many elements are exactly equal to each possible target value.

4. Frequency Calculation: For each target value x, the maximum frequency is the minimum of:

   • Number of elements that can reach x (coverage)
   • Number of exact matches at x plus available operations

5. Result: We return the maximum frequency found across all possible target values.

Complexity Analysis

• Time Complexity: O(n + range), where n is the length of nums and range is (maxV - minV) + 2*k + 1
• Space Complexity: O(range) for the difference and exact arrays

[kovatz]

Thanks for solving the problem of "Maximum Frequency of an Element After Performing Operations I"

[mah-shamim]

Thanks