Frequency of the Most Frequent Element — LeetCode 1838 Python Solution
MediumGreedyArrayBinary SearchPrefix SumSortingSliding Window
- Problem
- #1838
- Pattern
- Sliding Window
- Reading time
- 3 min
- Source
- leetcode.com
The problem
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.
Example
- 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].
Python solution
Python
class Solution:
def maxFrequency(self, nums: List[int], k: int) -> int:
def check(m: int) -> bool:
for i in range(m, n + 1):
if nums[i - 1] * m - (s[i] - s[i - m]) <= k:
return True
return False
n = len(nums)
nums.sort()
s = list(accumulate(nums, initial=0))
l, r = 1, n
while l < r:
mid = (l + r + 1) >> 1
if check(mid):
l = mid
else:
r = mid - 1
return lComplexity
| Measure | Complexity |
|---|---|
| Time | O(n \times \log n) |
| Space | O(n) auxiliary |
Pattern: Sliding Window
Collapse a nested loop over every subarray into a single pass with two indices. LeetCode 1838. Frequency of the Most Frequent Element is filed here because LeetCode tags it Sliding Window, which is the vocabulary this hub collects.
The sliding window guide has the Python template for the pattern and the 116 LeetCode problems that use it.
Related problems
LeetCode 2271Maximum White Tiles Covered by a CarpetMediumLeetCode 2234Maximum Total Beauty of the GardensHardLeetCode 2528Maximize the Minimum Powered CityHardLeetCode 611Valid Triangle NumberMediumLeetCode 826Most Profit Assigning WorkMediumLeetCode 1589Maximum Sum Obtained of Any PermutationMedium
Frequently asked questions
- How hard is LeetCode 1838. Frequency of the Most Frequent Element?
- LeetCode 1838. Frequency of the Most Frequent Element is rated Medium on LeetCode.
- What is the time complexity of LeetCode 1838. Frequency of the Most Frequent Element?
- The Python solution on this page runs in O(n \times \log n).
- What is the space complexity of LeetCode 1838. Frequency of the Most Frequent Element?
- The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 1838. Frequency of the Most Frequent Element cover?
- LeetCode 1838. Frequency of the Most Frequent Element is tagged Greedy, Array, Binary Search, Prefix Sum, Sorting and Sliding Window on LeetCode.