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

Frequency of the Most Frequent Element

Number: 1966

Difficulty: Medium

Paid? No

Companies: Bloomberg, Google, Amazon, Uber, Goldman Sachs, Microsoft, Meta, PhonePe, Apple, Deutsche Bank, Pony.ai

Problem Description

Given an array of integers nums and an integer k, you can perform at most k operations where in one operation you can increment any element by 1. The goal is to maximize the frequency of an element by turning some contiguous subarray elements equal. Return the maximum possible frequency of an element after performing at most k operations.

Key Insights

  • Sorting the array simplifies the problem by allowing us to work with contiguous subarrays.
  • A sliding window approach efficiently finds the largest window where all elements can be made equal with at most k operations.
  • Maintain a running sum of the current window to compute the cost of increasing all elements to match the current maximum.
  • If the cost exceeds k, shrink the window from the left until the cost is within limits.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting, plus O(n) for the sliding window traversal. Space Complexity: O(1) if sorting is done in-place (or O(n) otherwise).

Solution

Sort the input array and use a sliding window approach. For each new element considered at the right pointer, calculate the cost to convert all elements within the window to match the current element (nums[right]). This cost is computed as: cost = nums[right] * window_length - sum(window)

If the cost is greater than k, move the left pointer to shrink the window until the cost is acceptable. The length of the window at any point reflects the frequency of the most frequent element that can be obtained. Update the maximum frequency accordingly.

Code Solutions

# Python solution with line-by-line comments
class Solution:
    def maxFrequency(self, nums: List[int], k: int) -> int:
        # Sort the array to group similar values together
        nums.sort()
        left = 0  # left pointer of the sliding window
        total_sum = 0  # sum of elements in the current window
        max_freq = 0  # the maximum frequency found
        
        # Iterate through the array using right pointer
        for right in range(len(nums)):
            # Add the current element to the running sum
            total_sum += nums[right]
            # Calculate cost to make all elements in window equal to nums[right]
            # If cost exceeds k, move left pointer to shrink the window
            while nums[right] * (right - left + 1) - total_sum > k:
                total_sum -= nums[left]
                left += 1
            # Update maximum frequency if the current window is larger
            max_freq = max(max_freq, right - left + 1)
            
        return max_freq
← Back to All Questions