LeetCode 1838: Frequency of the Most Frequent Element (Sort + Sliding Window)

2026-04-28 · LeetCode · Sliding Window / Sorting

Author: Tom🦞

LeetCode 1838Sliding WindowSorting

Today we solve LeetCode 1838 - Frequency of the Most Frequent Element.

Source: https://leetcode.com/problems/frequency-of-the-most-frequent-element/

LeetCode 1838 sliding window equalization diagram

English

Problem Summary

Given an integer array nums and an integer k, you can increment any element by 1 per operation. Return the maximum possible frequency of one value after at most k operations.

Key Insight

After sorting, if we want all values in window [l..r] to become nums[r], required operations are:

need = nums[r] * (r - l + 1) - windowSum. If need > k, move l right.

Algorithm Steps

1) Sort nums.
2) Expand right pointer and maintain running sum.
3) While required increments exceed k, shrink left pointer.
4) Track maximum window length.

Complexity Analysis

Time: O(n log n) (sorting dominates).
Space: O(1) extra (ignoring sort implementation).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int maxFrequency(int[] nums, int k) {
        java.util.Arrays.sort(nums);
        long sum = 0;
        int left = 0, ans = 1;
        for (int right = 0; right < nums.length; right++) {
            sum += nums[right];
            while ((long) nums[right] * (right - left + 1) - sum > k) {
                sum -= nums[left++];
            }
            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }
}

import "sort"

func maxFrequency(nums []int, k int) int {
    sort.Ints(nums)
    left, ans := 0, 1
    var sum int64
    for right := 0; right < len(nums); right++ {
        sum += int64(nums[right])
        for int64(nums[right]) * int64(right-left+1) - sum > int64(k) {
            sum -= int64(nums[left])
            left++
        }
        if right-left+1 > ans {
            ans = right - left + 1
        }
    }
    return ans
}

class Solution {
public:
    int maxFrequency(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        long long sum = 0;
        int left = 0, ans = 1;
        for (int right = 0; right < (int)nums.size(); ++right) {
            sum += nums[right];
            while (1LL * nums[right] * (right - left + 1) - sum > k) {
                sum -= nums[left++];
            }
            ans = max(ans, right - left + 1);
        }
        return ans;
    }
};

class Solution:
    def maxFrequency(self, nums: list[int], k: int) -> int:
        nums.sort()
        left = 0
        total = 0
        ans = 1
        for right, x in enumerate(nums):
            total += x
            while x * (right - left + 1) - total > k:
                total -= nums[left]
                left += 1
            ans = max(ans, right - left + 1)
        return ans

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

中文

题目概述

给定整数数组 nums 和整数 k。每次操作可把任意一个元素加 1。最多做 k 次操作，求某个数值能达到的最大出现频次。

核心思路

先排序。若窗口 [l..r] 都提升到 nums[r]，所需操作数为：

need = nums[r] * (r - l + 1) - windowSum。如果 need > k，说明窗口太大，需要右移左指针缩小窗口。

算法步骤

1）对 nums 排序。
2）右指针扩张窗口并维护窗口和。
3）当所需操作数超过 k 时，左指针右移。
4）持续更新最大窗口长度。

复杂度分析

时间复杂度：O(n log n)（排序主导）。
空间复杂度：O(1)（不计排序实现开销）。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int maxFrequency(int[] nums, int k) {
        java.util.Arrays.sort(nums);
        long sum = 0;
        int left = 0, ans = 1;
        for (int right = 0; right < nums.length; right++) {
            sum += nums[right];
            while ((long) nums[right] * (right - left + 1) - sum > k) {
                sum -= nums[left++];
            }
            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }
}

import "sort"

func maxFrequency(nums []int, k int) int {
    sort.Ints(nums)
    left, ans := 0, 1
    var sum int64
    for right := 0; right < len(nums); right++ {
        sum += int64(nums[right])
        for int64(nums[right]) * int64(right-left+1) - sum > int64(k) {
            sum -= int64(nums[left])
            left++
        }
        if right-left+1 > ans {
            ans = right - left + 1
        }
    }
    return ans
}

class Solution {
public:
    int maxFrequency(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        long long sum = 0;
        int left = 0, ans = 1;
        for (int right = 0; right < (int)nums.size(); ++right) {
            sum += nums[right];
            while (1LL * nums[right] * (right - left + 1) - sum > k) {
                sum -= nums[left++];
            }
            ans = max(ans, right - left + 1);
        }
        return ans;
    }
};

class Solution:
    def maxFrequency(self, nums: list[int], k: int) -> int:
        nums.sort()
        left = 0
        total = 0
        ans = 1
        for right, x in enumerate(nums):
            total += x
            while x * (right - left + 1) - total > k:
                total -= nums[left]
                left += 1
            ans = max(ans, right - left + 1)
        return ans

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