Frequency of the Most Frequent Element

Frequency of the Most Frequent Element is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Sliding Window pattern, in the Variable Size (Condition-Based) subpattern.

Problem statement

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 <= 105

- 1 <= nums[i] <= 105

- 1 <= k <= 105

Topics and companies

Topics: Array, Binary Search, Greedy, Sliding Window, Sorting, Prefix Sum.

Reported in interviews at Facebook.

How to practise Frequency of the Most Frequent Element on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(nlogn) time and O(n) space.

Open Frequency of the Most Frequent Element in the code editor, or read the Frequency of the Most Frequent Element editorial for a worked solution with its approach and complexity analysis.

Where Frequency of the Most Frequent Element sits in the DSA pattern sheet

• Sliding Window pattern guide
• Variable Size (Condition-Based) subpattern
• The full DSA patterns sheet
• All coding practice problems

Problems related to Frequency of the Most Frequent Element

Other problems that use the same Variable Size (Condition-Based) and Sliding Window techniques:

• Contains Duplicate II — Easy, same subpattern
• Continuous Subarrays — Medium, same subpattern
• Find Longest Special Substring That Occurs Thrice I — Medium, same subpattern
• Fruit Into Baskets — Medium, same subpattern
• Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit — Medium, same subpattern
• Longest Repeating Character Replacement — Medium, same subpattern