We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Apply Operations to Maximize Frequency Score

Number: 3196

Difficulty: Hard

Paid? No

Companies: PhonePe, Deutsche Bank

Problem Description

Given an integer array nums and an integer k, you can perform at most k operations where in each operation, you can increment or decrement an element by 1. The score of the array is defined as the frequency of the most frequent element in the array after performing the operations. The goal is to maximize this score by strategically applying the operations.

Key Insights

  • Sorting the array is useful because elements that are close can be changed to a common value with fewer operations.
  • Use a sliding window approach to consider subarrays where all elements can be made equal to the rightmost element within the window.
  • Maintain a cumulative sum of the subarray to compute the number of operations required quickly.
  • The necessary operations for a window from index l to r (with r as the target value) is: nums[r] * window_size - (sum of window).
  • Adjust the window (increment l) if the operations exceed k; the largest window length found gives the maximum frequency possible.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting, plus O(n) for the sliding window iteration. Space Complexity: O(n) if considering the space for sorting; otherwise O(1) extra space is used.

Solution

We start by sorting the array to allow a contiguous segment to be potentially converged to a single value with minimal adjustments. With a sliding window, we try to extend our window by including the next element (targeting the rightmost element’s value as the desired common value) while keeping track of the sum of the numbers in the window.

For each new element at index r, compute the total operations needed to convert all elements in the current window to nums[r]. This can be computed as: operations_needed = nums[r] * window_size - current_window_sum. If operations_needed is within k, update the maximum frequency possible. Otherwise, slide the window from the left by moving the left pointer and subtracting the corresponding value from the sum. This greedy approach ensures that we always consider the longest valid window.

Code Solutions

# Python solution with line-by-line comments

class Solution:
    def maxFrequency(self, nums, k):
        # Sort the array to use sliding window
        nums.sort()
        max_freq = 1  # at least one element is always present
        total = 0  # sum of elements in the current window
        left = 0

        # Iterate over the array with the right pointer
        for right in range(len(nums)):
            # Add the current element to the total sum of the window
            total += nums[right]
            # When window is invalid (operations required are more than k)
            while (nums[right] * (right - left + 1) - total) > k:
                total -= nums[left]  # shrink window from left
                left += 1
            # Update maximum frequency with window length
            max_freq = max(max_freq, right - left + 1)
        return max_freq

# Example usage:
# solution = Solution()
# print(solution.maxFrequency([1,2,6,4], 3))  # Expected output: 3
← Back to All Questions