Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1838.html

1838. Frequency of the Most Frequent Element

Level

Medium

Description

The frequency of an element is the number of times it occurs in an array.

You are given an integer array nums and an integer k. In one operation, you can choose an index of nums and increment the element at that index by 1.

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

Example 1:

Input: nums = [1,2,4], k = 5

Output: 3

Explanation: Increment the first element three times and the second element two times to make nums = [4,4,4].

4 has a frequency of 3.

Example 2:

Input: nums = [1,4,8,13], k = 5

Output: 2

Explanation: There are multiple optimal solutions:

  • Increment the first element three times to make nums = [4,4,8,13]. 4 has a frequency of 2.
  • Increment the second element four times to make nums = [1,8,8,13]. 8 has a frequency of 2.
  • Increment the third element five times to make nums = [1,4,13,13]. 13 has a frequency of 2.

Example 3:

Input: nums = [3,9,6], k = 2

Output: 1

Constraints:

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

Solution

Sort the array nums. Calculate a new array differences as the differences of adjacent elements in nums, and calculate the prefix sums of differences. Then use binary search to find the maximum frequency of the most frequent element.

  • class Solution {
    public int maxFrequency(int[] nums, int k) {
        Arrays.sort(nums);
        int length = nums.length;
        long[] differences = new long[length];
        for (int i = 1; i < length; i++)
            differences[i] = (long) nums[i] - (long) nums[i - 1];
        long[] prefixSums = new long[length];
        for (int i = 1; i < length; i++)
            prefixSums[i] = prefixSums[i - 1] + differences[i];
        int low = 1, high = length;
        while (low < high) {
            int mid = (high - low + 1) / 2 + low;
            if (isPossible(nums, differences, prefixSums, mid, k))
                low = mid;
            else
                high = mid - 1;
        }
        return low;
    }

    public boolean isPossible(int[] nums, long[] differences, long[] prefixSums, int freq, int k) {
        int length = differences.length;
        long times = 0;
        for (int i = freq - 2; i >= 0; i--)
            times += (long) nums[freq - 1] - (long) nums[i];
        long minTimes = times;
        for (int i = freq; i < length; i++) {
            times = times - (prefixSums[i - 1] - prefixSums[i - freq]) + differences[i] * (freq - 1);
            minTimes = Math.min(minTimes, times);
        }
        return minTimes <= (long) k;
    }
}

############

class Solution {
    public int maxFrequency(int[] nums, int k) {
        Arrays.sort(nums);
        int n = nums.length;
        int ans = 1, window = 0;
        for (int l = 0, r = 1; r < n; ++r) {
            window += (nums[r] - nums[r - 1]) * (r - l);
            while (window > k) {
                window -= (nums[r] - nums[l++]);
            }
            ans = Math.max(ans, r - l + 1);
        }
        return ans;
    }
}

  • // OJ: https://leetcode.com/problems/frequency-of-the-most-frequent-element/
// Time: O(NlogN)
// Space: O(1)
class Solution {
public:
    int maxFrequency(vector<int>& A, int k) {
        sort(begin(A), end(A));
        long i = 0, N = A.size(), ans = 1, sum = 0;
        for (int j = 0; j < N; ++j) {
            sum += A[j];
            while ((j - i + 1) * A[j] - sum > k) sum -= A[i++];
            ans = max(ans, j - i + 1);
        }
        return ans;
    }
};

  • class Solution:
    def maxFrequency(self, nums: List[int], k: int) -> int:
        nums.sort()
        ans = 1
        window = 0
        l, r, n = 0, 1, len(nums)
        while r < n:
            window += (nums[r] - nums[r - 1]) * (r - l)
            r += 1
            while window > k:
                window -= nums[r - 1] - nums[l]
                l += 1
            ans = max(ans, r - l)
        return ans

############

# 1838. Frequency of the Most Frequent Element
# https://leetcode.com/problems/frequency-of-the-most-frequent-element/

class Solution:
    def maxFrequency(self, nums: List[int], k: int) -> int:
        res = s = i = 0
        n = len(nums)
        
        nums.sort()
        
        for j in range(n):
            s += nums[j]
            
            while nums[j] * (j - i + 1) - s > k:
                s -= nums[i]
                i += 1
            
            res = max(res, j - i + 1)
        
        return res


  • func maxFrequency(nums []int, k int) int {
	sort.Ints(nums)
	ans, window := 1, 0
	for l, r := 0, 1; r < len(nums); r++ {
		window += (nums[r] - nums[r-1]) * (r - l)
		for window > k {
			window -= nums[r] - nums[l]
			l++
		}
		ans = max(ans, r-l+1)
	}
	return ans
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

  • function maxFrequency(nums: number[], k: number): number {
    nums.sort((a, b) => a - b);
    let ans = 1;
    let window = 0;
    const n = nums.length;
    for (let l = 0, r = 1; r < n; ++r) {
        window += (nums[r] - nums[r - 1]) * (r - l);
        while (window > k) {
            window -= nums[r] - nums[l++];
        }
        ans = Math.max(ans, r - l + 1);
    }
    return ans;
}


  • /**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var maxFrequency = function (nums, k) {
    nums.sort((a, b) => a - b);
    let ans = 1;
    let window = 0;
    const n = nums.length;
    for (let l = 0, r = 1; r < n; ++r) {
        window += (nums[r] - nums[r - 1]) * (r - l);
        while (window > k) {
            window -= nums[r] - nums[l++];
        }
        ans = Math.max(ans, r - l + 1);
    }
    return ans;
};

All Problems

All Solutions