New Problem Solution - "1838. Frequency of the Most Frequent Element"

haoel · haoel · commit 37209a7b99c5 · 2021-04-25T16:33:38.000+08:00
diff --git a/README.md b/README.md
@@ -11,6 +11,7 @@ LeetCode
 |---| ----- | -------- | ---------- |
 |1840|[Maximum Building Height](https://leetcode.com/problems/maximum-building-height/) | [C++](./algorithms/cpp/maximumBuildingHeight/MaximumBuildingHeight.cpp)|Hard|
 |1839|[Longest Substring Of All Vowels in Order](https://leetcode.com/problems/longest-substring-of-all-vowels-in-order/) | [C++](./algorithms/cpp/longestSubstringOfAllVowelsInOrder/LongestSubstringOfAllVowelsInOrder.cpp)|Medium|
+|1838|[Frequency of the Most Frequent Element](https://leetcode.com/problems/frequency-of-the-most-frequent-element/) | [C++](./algorithms/cpp/frequencyOfTheMostFrequentElement/FrequencyOfTheMostFrequentElement.cpp)|Medium|
 |1835|[Find XOR Sum of All Pairs Bitwise AND](https://leetcode.com/problems/find-xor-sum-of-all-pairs-bitwise-and/) | [C++](./algorithms/cpp/findXorSumOfAllPairsBitwiseAnd/FindXorSumOfAllPairsBitwiseAnd.cpp)|Hard|
 |1834|[Single-Threaded CPU](https://leetcode.com/problems/single-threaded-cpu/) | [C++](./algorithms/cpp/singleThreadedCpu/SingleThreadedCpu.cpp)|Medium|
 |1833|[Maximum Ice Cream Bars](https://leetcode.com/problems/maximum-ice-cream-bars/) | [C++](./algorithms/cpp/maximumIceCreamBars/MaximumIceCreamBars.cpp)|Medium|
@@ -544,3 +545,4 @@ LeetCode
 |1|[Search in a big sorted array](http://www.lintcode.com/en/problem/search-in-a-big-sorted-array/)|[Java](./algorithms/java/src/searchInABigSortedArray/searchInABigSortedArray.java)|Medium|
 |2|[Search Range in Binary Search Tree](http://www.lintcode.com/en/problem/search-range-in-binary-search-tree/) | [Java](./algorithms/java/src/searchRangeInBinarySearchTree/searchRangeInBinarySearchTree.java)|Medium|
 
+
diff --git a/algorithms/cpp/frequencyOfTheMostFrequentElement/FrequencyOfTheMostFrequentElement.cpp b/algorithms/cpp/frequencyOfTheMostFrequentElement/FrequencyOfTheMostFrequentElement.cpp
@@ -0,0 +1,63 @@
+// Source : https://leetcode.com/problems/frequency-of-the-most-frequent-element/
+// Author : Hao Chen
+// Date   : 2021-04-25
+
+/***************************************************************************************************** 
+ *
+ * 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
+ ******************************************************************************************************/
+
+class Solution {
+public:
+    int maxFrequency(vector<int>& nums, int k) {
+        sort(nums.begin(), nums.end());
+        int m = 1;
+        int start = 0;
+        int i = 1;
+        for(; i<nums.size(); i++){
+            long delta = nums[i] - nums[i-1];
+            k -= delta * (i - start);;
+            if (k < 0 )  {
+                // remove the first one
+                k += (nums[i] - nums[start]) ;
+                start++;
+            }
+            m = max(m, i - start +1);
+            
+        }
+        return m;
+    }
+};
