\n# 1st Method :- Two Pointers / Sliding Window\uD83D\uDD25\n\n## Intuition \uD83D\uDE80\nThe goal of the problem is to find the maximum frequency of an element in an array after performing certain operations. The operations involve adding or subtracting a given value `k` to elements in the array. To achieve this, the code uses a sliding window approach.\n\nThe intuition behind the sliding window is to maintain a valid subarray (window) that satisfies the given condition. By adjusting the window based on the sum of elements and the condition, the code efficiently explores different subarrays to find the maximum frequency.\n\n## Approach \uD83D\uDE80\n\n1. **Sorting:**\n - The array `nums` is sorted in ascending order. Sorting is crucial for the sliding window approach, as it allows us to efficiently adjust the window based on the current element.\n\n2. **Sliding Window:**\n - Two pointers, `left` and `right`, are used to define the subarray. The `right` pointer is advanced to include elements in the current subarray, while the `left` pointer is adjusted to maintain a valid subarray.\n\n3. **Subarray Sum and Adjustments:**\n - `currentSum` represents the sum of elements in the current subarray. The code adds the current element (`nums[right]`) to this sum.\n - A while loop checks if the current subarray violates the condition (`sum + k < nums[right] * length`). If it does, the code adjusts the subarray by removing the leftmost element and updating the sum. This ensures that the condition is satisfied.\n\n4. **Update Maximum Frequency:**\n - The maximum frequency (`maxFrequency`) is updated by comparing it with the length of the current subarray (`right - left + 1`). The length represents the number of elements in the valid subarray.\n\n5. **Return Result:**\n - The final result is the maximum frequency found after processing the entire array.\n\nIn summary, the approach involves efficiently exploring different subarrays using a sliding window and adjusting the window based on the sum of elements and the given condition. Sorting the array is a key step to simplify the sliding window process. The code efficiently finds the maximum frequency by maintaining a valid subarray and updating the frequency as the window moves through the array.\n\n\n## \u2712\uFE0FCode\n``` Java []\nclass Solution {\n public int maxFrequency(int[] nums, int k) {\n int maxFrequency = 0; // Initialize the maximum frequency\n long currentSum = 0; // Initialize the current sum of the subarray elements\n\n Arrays.sort(nums); // Sort the array in ascending order\n\n for (int left = 0, right = 0; right < nums.length; ++right) {\n currentSum += nums[right]; // Include the current element in the subarray sum\n\n // Check if the current subarray violates the condition (sum + k < nums[right] * length)\n while (currentSum + k < (long) nums[right] * (right - left + 1)) {\n currentSum -= nums[left]; // Adjust the subarray sum by removing the leftmost element\n left++; // Move the left pointer to the right\n }\n\n // Update the maximum frequency based on the current subarray length\n maxFrequency = Math.max(maxFrequency, right - left + 1);\n }\n\n return maxFrequency;\n }\n}\n\n```\n``` C++ []\nclass Solution {\npublic:\n int maxFrequency(vector& nums, int k) {\n int maxFrequency = 0; // Initialize the maximum frequency\n long currentSum = 0; // Initialize the current sum of the subarray elements\n\n std::sort(nums.begin(), nums.end()); // Sort the array in ascending order\n\n for (int left = 0, right = 0; right < nums.size(); ++right) {\n currentSum += nums[right]; // Include the current element in the subarray sum\n\n // Check if the current subarray violates the condition (sum + k < nums[right] * length)\n while (currentSum + k < static_cast(nums[right]) * (right - left + 1)) {\n currentSum -= nums[left]; // Adjust the subarray sum by removing the leftmost element\n left++; // Move the left pointer to the right\n }\n\n // Update the maximum frequency based on the current subarray length\n maxFrequency = std::max(maxFrequency, right - left + 1);\n }\n\n return maxFrequency;\n }\n};\n\n```\n``` Python []\nclass Solution(object):\n def maxFrequency(self, nums, k):\n maxFrequency = 0 # Initialize the maximum frequency\n currentSum = 0 # Initialize the current sum of the subarray elements\n\n nums.sort() # Sort the array in ascending order\n\n left = 0\n for right in range(len(nums)):\n currentSum += nums[right] # Include the current element in the subarray sum\n\n # Check if the current subarray violates the condition (sum + k < nums[right] * length)\n while currentSum + k < nums[right] * (right - left + 1):\n currentSum -= nums[left] # Adjust the subarray sum by removing the leftmost element\n left += 1 # Move the left pointer to the right\n\n # Update the maximum frequency based on the current subarray length\n maxFrequency = max(maxFrequency, right - left + 1)\n\n return maxFrequency\n\n```\n``` JavaScript []\nvar maxFrequency = function(nums, k) {\n let maxFrequency = 0; // Initialize the maximum frequency\n let currentSum = 0; // Initialize the current sum of the subarray\n\n nums.sort((a, b) => a - b); // Sort the array in ascending order\n\n for (let left = 0, right = 0; right < nums.length; ++right) {\n currentSum += nums[right]; // Include the current element in the subarray sum\n\n // Check if the current subarray violates the condition (sum + k < nums[right] * length)\n while (currentSum + k < nums[right] * (right - left + 1)) {\n currentSum -= nums[left]; // Adjust the subarray sum by removing the leftmost element\n left++; // Move the left pointer to the right\n }\n\n // Update the maximum frequency based on the current subarray length\n maxFrequency = Math.max(maxFrequency, right - left + 1);\n }\n\n return maxFrequency;\n};\n\n```\n``` C# []\npublic class Solution {\n public int MaxFrequency(int[] nums, int k) {\n int maxFrequency = 0; // Initialize the maximum frequency\n long currentSum = 0; // Initialize the current sum of the subarray\n\n Array.Sort(nums); // Sort the array in ascending order\n\n for (int left = 0, right = 0; right < nums.Length; ++right) {\n currentSum += nums[right]; // Include the current element in the subarray sum\n\n // Check if the current subarray violates the condition (sum + k < nums[right] * length)\n while (currentSum + k < (long)nums[right] * (right - left + 1)) {\n currentSum -= nums[left]; // Adjust the subarray sum by removing the leftmost element\n left++; // Move the left pointer to the right\n }\n\n // Update the maximum frequency based on the current subarray length\n maxFrequency = Math.Max(maxFrequency, right - left + 1);\n }\n\n return maxFrequency;\n }\n}\n\n```\n\n## Complexity \uD83D\uDE81\n### \uD83C\uDFF9Time complexity: O(n log n)\n- The code sorts the array, which has a time complexity of O(n log n), where n is the length of the input array `nums`.\n- The main loop iterates through each element in the sorted array once, so it has a time complexity of O(n), where n is the length of the input array.\n- Overall, the dominant factor is the sorting operation, making the time complexity O(n log n).\n\n### \uD83C\uDFF9Space complexity: O(1)\n- The space complexity is O(1) because the code uses a constant amount of extra space, regardless of the size of the input array. The additional space is used for variables like `maxFrequency`, `currentSum`, and loop variables (`left` and `right`), and it does not depend on the input size. Hence, the space complexity is constant.\n\n\n![vote.jpg](https://assets.leetcode.com/users/images/a9fb3fe9-d8bf-4716-822b-fd5a3789134e_1700267842.9579122.jpeg)\n\n---\n# 2nd Method :- Sliding Window & Greedy\uD83D\uDD25\n\n## Intuition \uD83D\uDE80\nThe goal of the problem is to find the maximum frequency of any element in a subarray after performing operations on the array. The operations involve adjusting the subarray by removing elements to minimize the difference between the product of the element and the length of the subarray and the sum of the subarray.\n\n## Approach \uD83D\uDE80\n\n1. **Counting Sort:**\n - The initial step involves sorting the array in non-decreasing order using counting sort. This step ensures that elements are processed in ascending order during the main iteration.\n\n2. **Sliding Window:**\n - The code uses a sliding window approach with two pointers (`start` and `i`) to define the current subarray.\n - `start` represents the leftmost index of the subarray, and `i` represents the rightmost index.\n\n3. **Product and Sum Calculation:**\n - For each element in the sorted array, the code calculates the product of the element and the length of the current subarray (`subarrayProduct = nums[i] * subarrayLength`).\n - It also maintains the sum of elements in the current subarray (`subarraySum += nums[i]`).\n\n4. **Adjustment of Subarray:**\n - If the difference between the product and the sum of the subarray exceeds the given limit (`k`), the subarray is adjusted.\n - The adjustment involves removing elements from the left of the subarray (`subarraySum -= nums[start]`) and updating the subarray length until the condition is satisfied.\n\n5. **Update Maximum Frequency:**\n - The code updates the maximum frequency (`maxFrequency`) by comparing it with the length of the current subarray.\n - The length of the subarray represents the frequency of the current element in the subarray.\n\n6. **Iteration Through Array:**\n - The iteration through the array continues until all elements are processed.\n\n7. **Return Result:**\n - The final result returned is the maximum frequency found after processing the entire array.\n\n### Summary:\n\nThe approach involves maintaining a sliding window and adjusting it as needed to satisfy the given condition. The code efficiently finds the maximum frequency by considering the product of elements and the length of the subarray, with counting sort aiding in sorting the array initially. The sliding window adjusts to minimize the difference between the product and the sum of the subarray, ensuring an optimal solution to the problem.\n\n\n## \u2712\uFE0FCode\n``` Java []\nclass Solution {\n public int maxFrequency(int[] nums, int k) {\n countingSort(nums); // Sort the array using counting sort\n int start = 0; // Start index of the current subarray\n int subarraySum = 0; // Sum of elements in the current subarray\n int maxFrequency = 1; // Initialize the maximum frequency to 1\n\n // Iterate through the sorted array\n for (int i = 0; i < nums.length; i++) {\n int subarrayLength = i - start + 1; // Length of the current subarray\n int subarrayProduct = nums[i] * subarrayLength; // Product of element and subarray length\n subarraySum += nums[i]; // Add the current element to the subarray sum\n\n // Adjust the subarray to satisfy the condition (product - sum <= k)\n while (subarrayProduct - subarraySum > k) {\n subarraySum -= nums[start]; // Remove the leftmost element from the subarray\n start++; // Move the start index to the right\n subarrayLength--; // Decrease the length of the subarray\n subarrayProduct = nums[i] * subarrayLength; // Recalculate the product\n }\n\n // Update the maximum frequency based on the current subarray length\n maxFrequency = Math.max(maxFrequency, subarrayLength);\n }\n\n return maxFrequency; // Return the final result\n }\n\n // Counting Sort to sort the array in non-decreasing order\n private void countingSort(int[] nums) {\n int maxElement = Integer.MIN_VALUE;\n\n // Find the maximum element in the array\n for (int num : nums) {\n maxElement = Math.max(maxElement, num);\n }\n\n // Create an array to store the count of each element\n int[] countMap = new int[maxElement + 1];\n\n // Count the occurrences of each element in the array\n for (int num : nums) {\n countMap[num]++;\n }\n\n int index = 0;\n\n // Reconstruct the sorted array\n for (int i = 0; i <= maxElement; i++) {\n while (countMap[i]-- > 0) {\n nums[index++] = i;\n }\n }\n }\n}\n\n```\n``` C++ []\nclass Solution {\npublic:\n int maxFrequency(std::vector& nums, int k) {\n countingSort(nums); // Sort the array using counting sort\n int start = 0; // Start index of the current subarray\n long long subarraySum = 0; // Sum of elements in the current subarray\n int maxFrequency = 1; // Initialize the maximum frequency to 1\n\n // Iterate through the sorted array\n for (int i = 0; i < nums.size(); i++) {\n int subarrayLength = i - start + 1; // Length of the current subarray\n long long subarrayProduct = (long long)nums[i] * subarrayLength; // Use long long to avoid overflow\n subarraySum += nums[i]; // Add the current element to the subarray sum\n\n // Adjust the subarray to satisfy the condition (product - sum <= k)\n while (subarrayProduct - subarraySum > k) {\n subarraySum -= nums[start]; // Remove the leftmost element from the subarray\n start++; // Move the start index to the right\n subarrayLength--; // Decrease the length of the subarray\n subarrayProduct = (long long)nums[i] * subarrayLength; // Recalculate the product\n }\n\n // Update the maximum frequency based on the current subarray length\n maxFrequency = std::max(maxFrequency, subarrayLength);\n }\n\n return maxFrequency; // Return the final result\n }\n\nprivate:\n // Counting Sort to sort the array in non-decreasing order\n void countingSort(std::vector& nums) {\n int maxElement = INT_MIN;\n\n // Find the maximum element in the array\n for (int num : nums) {\n maxElement = std::max(maxElement, num);\n }\n\n // Create an array to store the count of each element\n std::vector countMap(maxElement + 1, 0);\n\n // Count the occurrences of each element in the array\n for (int num : nums) {\n countMap[num]++;\n }\n\n int index = 0;\n\n // Reconstruct the sorted array\n for (int i = 0; i <= maxElement; i++) {\n while (countMap[i]-- > 0) {\n nums[index++] = i;\n }\n }\n }\n};\n\n```\n``` Python []\nclass Solution:\n def maxFrequency(self, nums, k):\n self.countingSort(nums) # Sort the array using counting sort\n start = 0 # Start index of the current subarray\n subarray_sum = 0 # Sum of elements in the current subarray\n max_frequency = 1 # Initialize the maximum frequency to 1\n\n # Iterate through the sorted array\n for i in range(len(nums)):\n subarray_length = i - start + 1 # Length of the current subarray\n subarray_product = nums[i] * subarray_length # Product of element and subarray length\n subarray_sum += nums[i] # Add the current element to the subarray sum\n\n # Adjust the subarray to satisfy the condition (product - sum <= k)\n while subarray_product - subarray_sum > k:\n subarray_sum -= nums[start] # Remove the leftmost element from the subarray\n start += 1 # Move the start index to the right\n subarray_length -= 1 # Decrease the length of the subarray\n subarray_product = nums[i] * subarray_length # Recalculate the product\n\n # Update the maximum frequency based on the current subarray length\n max_frequency = max(max_frequency, subarray_length)\n\n return max_frequency # Return the final result\n\n # Counting Sort to sort the array in non-decreasing order\n def countingSort(self, nums):\n max_element = max(nums)\n\n # Create an array to store the count of each element\n count_map = [0] * (max_element + 1)\n\n # Count the occurrences of each element in the array\n for num in nums:\n count_map[num] += 1\n\n index = 0\n\n # Reconstruct the sorted array\n for i in range(max_element + 1):\n while count_map[i] > 0:\n nums[index] = i\n index += 1\n count_map[i] -= 1\n\n\n```\n``` JavaScript []\nvar maxFrequency = function(nums, k) {\n countingSort(nums); // Sort the array using counting sort\n let start = 0; // Start index of the current subarray\n let subarraySum = 0; // Sum of elements in the current subarray\n let maxFrequency = 1; // Initialize the maximum frequency to 1\n\n // Iterate through the sorted array\n for (let i = 0; i < nums.length; i++) {\n let subarrayLength = i - start + 1; // Length of the current subarray\n let subarrayProduct = nums[i] * subarrayLength; // Product of element and subarray length\n subarraySum += nums[i]; // Add the current element to the subarray sum\n\n // Adjust the subarray to satisfy the condition (product - sum <= k)\n while (subarrayProduct - subarraySum > k) {\n subarraySum -= nums[start]; // Remove the leftmost element from the subarray\n start++; // Move the start index to the right\n subarrayLength--; // Decrease the length of the subarray\n subarrayProduct = nums[i] * subarrayLength; // Recalculate the product\n }\n\n // Update the maximum frequency based on the current subarray length\n maxFrequency = Math.max(maxFrequency, subarrayLength);\n }\n\n return maxFrequency; // Return the final result\n}\n\n/**\n * Counting Sort to sort the array in non-decreasing order.\n * @param {number[]} nums - The input array of numbers.\n */\nfunction countingSort(nums) {\n const maxElement = Math.max(...nums); // Find the maximum element in the array\n const countMap = Array(maxElement + 1).fill(0); // Create an array to store the count of each element\n let index = 0;\n\n // Count the occurrences of each element in the array\n for (const num of nums) {\n countMap[num]++;\n }\n\n // Reconstruct the sorted array\n for (let i = 0; i <= maxElement; i++) {\n while (countMap[i]-- > 0) {\n nums[index++] = i;\n }\n }\n}\n\n```\n``` C# []\npublic class Solution {\n public int MaxFrequency(int[] nums, int k) {\n CountingSort(nums); // Sort the array using counting sort\n int start = 0; // Start index of the current subarray\n int subarraySum = 0; // Sum of elements in the current subarray\n int maxFrequency = 1; // Initialize the maximum frequency to 1\n\n // Iterate through the sorted array\n for (int i = 0; i < nums.Length; i++) {\n int subarrayLength = i - start + 1; // Length of the current subarray\n int subarrayProduct = nums[i] * subarrayLength; // Product of element and subarray length\n subarraySum += nums[i]; // Add the current element to the subarray sum\n\n // Adjust the subarray to satisfy the condition (product - sum <= k)\n while (subarrayProduct - subarraySum > k) {\n subarraySum -= nums[start]; // Remove the leftmost element from the subarray\n start++; // Move the start index to the right\n subarrayLength--; // Decrease the length of the subarray\n subarrayProduct = nums[i] * subarrayLength; // Recalculate the product\n }\n\n // Update the maximum frequency based on the current subarray length\n maxFrequency = Math.Max(maxFrequency, subarrayLength);\n }\n\n return maxFrequency; // Return the final result\n }\n\n // Counting Sort to sort the array in non-decreasing order\n private void CountingSort(int[] nums) {\n int maxElement = int.MinValue;\n\n // Find the maximum element in the array\n foreach (int num in nums) {\n maxElement = Math.Max(maxElement, num);\n }\n\n int[] countMap = new int[maxElement + 1]; // Create an array to store the count of each element\n int index = 0;\n\n // Count the occurrences of each element in the array\n foreach (int num in nums) {\n countMap[num]++;\n }\n\n // Reconstruct the sorted array\n for (int i = 0; i <= maxElement; i++) {\n while (countMap[i]-- > 0) {\n nums[index++] = i;\n }\n }\n }\n\n}\n\n```\n\n## Complexity \uD83D\uDE81\n### \uD83C\uDFF9Time complexity: O(N + K)\n- **Counting Sort (sorting step):** O(N + K), where N is the length of the input array `nums`, and K is the range of values (maximum element in `nums`).\n - Counting sort has a linear time complexity because it iterates through the input array once to count the occurrences of each element and then reconstructs the sorted array.\n\n- **Main Loop (sliding window):** O(N), where N is the length of the input array `nums`.\n - The main loop iterates through each element of the sorted array once.\n\nThe overall time complexity is dominated by the counting sort step, making the total time complexity O(N + K).\n\n### \uD83C\uDFF9Space complexity: O(K)\n- **Counting Sort (sorting step):** O(K), where K is the range of values (maximum element in `nums`).\n - The space required for counting sort is proportional to the range of values in the input array.\n\n- **Other Variables:** O(1).\n - The space required for variables such as `start`, `subarraySum`, `maxFrequency`, etc., is constant and does not depend on the input size.\n\nThe overall space complexity is O(K), where K is the range of values in the input array.\n\nNote: The space complexity of the counting sort step dominates the overall space complexity. If the range of values (K) is significantly smaller than the length of the input array (N), the space complexity can be considered linear (O(N)).\n\n![vote.jpg](https://assets.leetcode.com/users/images/0697137f-5e0d-4801-9bb6-e98914f7deb4_1700270810.8473003.jpeg)\n\n---\n# 3rd Method :- Binary Search with Prefix Sum\uD83D\uDD25\n## The least efficient approach\n\n## Intuition \uD83D\uDE80\nThe problem requires finding the maximum frequency of an element in a subarray after performing certain operations. The operations involve changing the elements in the subarray to make the difference between the maximum and minimum elements within a specified limit (k). The provided solution tackles this problem using a binary search approach.\n\n## Approach \uD83D\uDE80\n\n1. **Sort the Array:**\n - The array is sorted in ascending order. Sorting simplifies the calculation of differences between adjacent elements.\n\n2. **Calculate Differences and Prefix Sums:**\n - Differences between adjacent elements are calculated and stored in the `differences` array.\n - Prefix sums of the differences are calculated and stored in the `prefixSums` array. This aids in efficiently computing the sum of differences in subarrays.\n\n3. **Binary Search for Maximum Frequency:**\n - A binary search is employed to find the maximum frequency that satisfies the given conditions.\n - The search space is narrowed down by adjusting the low and high pointers.\n\n4. **isPossible Function:**\n - The `isPossible` function checks if it\'s possible to achieve a certain frequency with the allowed difference `k`.\n - It initializes the `times` variable based on the frequency and the last element in the subarray.\n - It iterates through the array, updating the `times` variable by considering the difference in prefix sums and new differences.\n - The minimum `times` is tracked, and the function returns true if the minimum `times` is within the allowed difference `k`.\n\n### Explanation of Binary Search:\nThe binary search in this context is applied to find the maximum frequency efficiently. The search space is the potential frequencies that we can achieve. The `isPossible` function checks whether it\'s possible to achieve a given frequency with the allowed difference. The binary search updates the search space based on the result of this check until it finds the maximum frequency.\n\n### Overall:\nThe approach leverages sorting, prefix sums, and binary search to efficiently find the maximum frequency of an element in a subarray while considering the allowed difference. The `isPossible` function plays a crucial role in determining the feasibility of achieving a certain frequency. The binary search optimally explores the space of potential frequencies.\n\n\n## \u2712\uFE0FCode\n``` Java []\nclass Solution {\n public int maxFrequency(int[] nums, int k) {\n // Sort the array in ascending order\n Arrays.sort(nums);\n\n int length = nums.length;\n\n // Calculate the differences between adjacent elements\n long[] differences = new long[length];\n for (int i = 1; i < length; i++)\n differences[i] = (long) nums[i] - (long) nums[i - 1];\n\n // Calculate the prefix sums of the differences\n long[] prefixSums = new long[length];\n for (int i = 1; i < length; i++)\n prefixSums[i] = prefixSums[i - 1] + differences[i];\n\n int low = 1, high = length;\n\n // Binary search for the maximum frequency\n while (low < high) {\n int mid = (high - low + 1) / 2 + low;\n\n // Check if it\'s possible to achieve the given frequency with the allowed difference\n if (isPossible(nums, differences, prefixSums, mid, k))\n low = mid;\n else\n high = mid - 1;\n }\n\n return low;\n }\n\n // Function to check if it\'s possible to achieve the given frequency with the allowed difference\n public boolean isPossible(int[] nums, long[] differences, long[] prefixSums, int freq, int k) {\n int length = differences.length;\n\n long times = 0;\n\n // Calculate the initial times based on the frequency and the last element in the subarray\n for (int i = freq - 2; i >= 0; i--)\n times += (long) nums[freq - 1] - (long) nums[i];\n\n long minTimes = times;\n\n // Iterate from freq-th element to the end of the array\n for (int i = freq; i < length; i++) {\n // Update times by considering the difference in prefix sums and new differences\n times = times - (prefixSums[i - 1] - prefixSums[i - freq]) + differences[i] * (freq - 1);\n minTimes = Math.min(minTimes, times);\n }\n\n // Check if the minimum times is within the allowed difference (k)\n return minTimes <= (long) k;\n }\n}\n\n```\n``` C++ []\nclass Solution {\npublic:\n int maxFrequency(std::vector& nums, int k) {\n // Sort the array in ascending order\n std::sort(nums.begin(), nums.end());\n\n int length = nums.size();\n\n // Calculate the differences between adjacent elements\n std::vector differences(length);\n for (int i = 1; i < length; i++)\n differences[i] = static_cast(nums[i]) - static_cast(nums[i - 1]);\n\n // Calculate the prefix sums of the differences\n std::vector prefixSums(length);\n for (int i = 1; i < length; i++)\n prefixSums[i] = prefixSums[i - 1] + differences[i];\n\n int low = 1, high = length;\n\n // Binary search for the maximum frequency\n while (low < high) {\n int mid = (high - low + 1) / 2 + low;\n\n // Check if it\'s possible to achieve the given frequency with the allowed difference\n if (isPossible(nums, differences, prefixSums, mid, k))\n low = mid;\n else\n high = mid - 1;\n }\n\n return low;\n }\n\nprivate:\n // Function to check if it\'s possible to achieve the given frequency with the allowed difference\n bool isPossible(const std::vector& nums, const std::vector& differences, const std::vector& prefixSums, int freq, int k) {\n int length = differences.size();\n\n long times = 0;\n\n // Calculate the initial times based on the frequency and the last element in the subarray\n for (int i = freq - 2; i >= 0; i--)\n times += static_cast(nums[freq - 1]) - static_cast(nums[i]);\n\n long minTimes = times;\n\n // Iterate from freq-th element to the end of the array\n for (int i = freq; i < length; i++) {\n // Update times by considering the difference in prefix sums and new differences\n times = times - (prefixSums[i - 1] - prefixSums[i - freq]) + differences[i] * (freq - 1);\n minTimes = std::min(minTimes, times);\n }\n\n // Check if the minimum times is within the allowed difference (k)\n return minTimes <= static_cast(k);\n }\n};\n\n```\n``` Python []\nclass Solution:\n def maxFrequency(self, nums, k):\n # Sort the array in ascending order\n nums.sort()\n\n length = len(nums)\n\n # Calculate the differences between adjacent elements\n differences = [0] * length\n for i in range(1, length):\n differences[i] = nums[i] - nums[i - 1]\n\n # Calculate the prefix sums of the differences\n prefix_sums = [0] * length\n for i in range(1, length):\n prefix_sums[i] = prefix_sums[i - 1] + differences[i]\n\n low, high = 1, length\n\n # Binary search for the maximum frequency\n while low < high:\n mid = (high - low + 1) // 2 + low\n\n # Check if it\'s possible to achieve the given frequency with the allowed difference\n if self.isPossible(nums, differences, prefix_sums, mid, k):\n low = mid\n else:\n high = mid - 1\n\n return low\n\n def isPossible(self, nums, differences, prefix_sums, freq, k):\n length = len(differences)\n\n times = 0\n\n # Calculate the initial times based on the frequency and the last element in the subarray\n for i in range(freq - 2, -1, -1):\n times += nums[freq - 1] - nums[i]\n\n min_times = times\n\n # Iterate from freq-th element to the end of the array\n for i in range(freq, length):\n # Update times by considering the difference in prefix sums and new differences\n times = times - (prefix_sums[i - 1] - prefix_sums[i - freq]) + differences[i] * (freq - 1)\n min_times = min(min_times, times)\n\n # Check if the minimum times is within the allowed difference (k)\n return min_times <= k\n\n```\n``` JavaScript []\nvar maxFrequency = function(nums, k) {\n/**\n * Function to find the maximum frequency of an element in a subarray\n * after performing certain operations.\n * @param {number[]} nums - The input array of numbers.\n * @param {number} k - The allowed difference for operations.\n * @returns {number} - The maximum frequency.\n */\n // Sort the array in ascending order\n nums.sort((a, b) => a - b);\n\n const length = nums.length;\n\n // Calculate the differences between adjacent elements\n const differences = new Array(length).fill(0);\n for (let i = 1; i < length; i++)\n differences[i] = nums[i] - nums[i - 1];\n\n // Calculate the prefix sums of the differences\n const prefixSums = new Array(length).fill(0);\n for (let i = 1; i < length; i++)\n prefixSums[i] = prefixSums[i - 1] + differences[i];\n\n let low = 1, high = length;\n\n // Binary search for the maximum frequency\n while (low < high) {\n const mid = Math.floor((high - low + 1) / 2) + low;\n\n // Check if it\'s possible to achieve the given frequency with the allowed difference\n if (isPossible(nums, differences, prefixSums, mid, k))\n low = mid;\n else\n high = mid - 1;\n }\n\n return low;\n}\n\n/**\n * Function to check if it\'s possible to achieve the given frequency with the allowed difference.\n * @param {number[]} nums - The input array of numbers.\n * @param {number[]} differences - The array of differences between adjacent elements.\n * @param {number[]} prefixSums - The array of prefix sums of differences.\n * @param {number} freq - The current frequency being considered.\n * @param {number} k - The allowed difference for operations.\n * @returns {boolean} - True if the given frequency is possible; otherwise, false.\n */\nfunction isPossible(nums, differences, prefixSums, freq, k) {\n const length = differences.length;\n\n let times = 0;\n\n // Calculate the initial times based on the frequency and the last element in the subarray\n for (let i = freq - 2; i >= 0; i--)\n times += nums[freq - 1] - nums[i];\n\n let minTimes = times;\n\n // Iterate from freq-th element to the end of the array\n for (let i = freq; i < length; i++) {\n // Update times by considering the difference in prefix sums and new differences\n times = times - (prefixSums[i - 1] - prefixSums[i - freq]) + differences[i] * (freq - 1);\n minTimes = Math.min(minTimes, times);\n }\n\n // Check if the minimum times is within the allowed difference (k)\n return minTimes <= k;\n}\n\n\n```\n``` C# []\nusing System;\n\npublic class Solution {\n public int MaxFrequency(int[] nums, int k) {\n // Sort the array in ascending order\n Array.Sort(nums);\n\n int length = nums.Length;\n\n // Calculate the differences between adjacent elements\n long[] differences = new long[length];\n for (int i = 1; i < length; i++)\n differences[i] = nums[i] - nums[i - 1];\n\n // Calculate the prefix sums of the differences\n long[] prefixSums = new long[length];\n for (int i = 1; i < length; i++)\n prefixSums[i] = prefixSums[i - 1] + differences[i];\n\n int low = 1, high = length;\n\n // Binary search for the maximum frequency\n while (low < high) {\n int mid = (high - low + 1) / 2 + low;\n\n // Check if it\'s possible to achieve the given frequency with the allowed difference\n if (IsPossible(nums, differences, prefixSums, mid, k))\n low = mid;\n else\n high = mid - 1;\n }\n\n return low;\n }\n\n // Function to check if it\'s possible to achieve the given frequency with the allowed difference\n public bool IsPossible(int[] nums, long[] differences, long[] prefixSums, int freq, int k) {\n int length = differences.Length;\n\n long times = 0;\n\n // Calculate the initial times based on the frequency and the last element in the subarray\n for (int i = freq - 2; i >= 0; i--)\n times += nums[freq - 1] - nums[i];\n\n long minTimes = times;\n\n // Iterate from freq-th element to the end of the array\n for (int i = freq; i < length; i++) {\n // Update times by considering the difference in prefix sums and new differences\n times = times - (prefixSums[i - 1] - prefixSums[i - freq]) + differences[i] * (freq - 1);\n minTimes = Math.Min(minTimes, times);\n }\n\n // Check if the minimum times is within the allowed difference (k)\n return minTimes <= k;\n }\n\n}\n\n```\n\n## Complexity \uD83D\uDE81\n### \uD83C\uDFF9Time complexity: O(n log n)\n1. **Sorting:**\n - The initial sorting of the array takes O(n log n) time, where n is the length of the array.\n\n2. **Differences and Prefix Sums:**\n - Calculating differences and prefix sums involves iterating through the array once, which takes O(n) time.\n\n3. **Binary Search:**\n - The binary search iterates log(n) times.\n\n4. **isPossible Function:**\n - The `isPossible` function iterates through the array once, making it O(n).\n\nThe overall time complexity is dominated by the sorting step, making it O(n log n).\n\n### \uD83C\uDFF9Space complexity: O(n)\n\n1. **Differences and Prefix Sums:**\n - Additional space is used to store the arrays `differences` and `prefixSums`, each of size n. Therefore, the space complexity for these arrays is O(n).\n\n2. **Other Variables:**\n - Other variables like `low`, `high`, `mid`, `times`, and `minTimes` use constant space.\n\nThe overall space complexity is O(n) due to the additional arrays created for differences and prefix sums.\n\n\n\n\n\n\n![upvote.png](https://assets.leetcode.com/users/images/58da450e-464f-4115-ad34-ee38d0c8cca0_1700269138.6219409.png)\n\n# Up Vote Guys\n\n\n\n\n\n\n

Frequency of the Most Frequent Element

Problem Description

Problem Description

Answer Panel