Simple prefix sum solutions for both B and C(or Q2 and Q3) questions with explaination
Intuition and Approach\nLet\'s take a number n in input nums array, we can find all the numbers it can be modified to using numbers within [-k,k] as the numbers
# Intuition and Approach\nLet\'s take a number `n` in input `nums` array, we can find all the numbers it can be modified to using numbers within `[-k,k]` as the numbers it can be modified to are sequential we can use prefix sum instead of looping all modified numbers\n\n# Complexity\n- Time complexity: O(n)\n    -  n -> Loop through `nums`\n    - 1e5 -> Loop through `prefixArray`\n\n- Space complexity: O(n)\n    -  n -> For `freqMap`\n    - 1e5 -> for `prefixArray`\n\n# Code\n```java []\nclass Solution {\n    public static final int MAX = (int) 1e5;\n\n    public int maxFrequency(int[] nums, int k, int numOperations) {\n        //Stores the frequency of a number in `nums`\n        var freqMap = new HashMap<Integer, Integer>();\n        //This array will be used to know the maximum frequency possible for a number\n        var prefixArray = new int[MAX + 1];\n\n        for (var n : nums) {\n            //Update or insert number in `freqMap`\n            freqMap.compute(n, (key, val) -> val == null ? 1 : (val + 1));\n            \n            //To avoid index out of bounds\n            if (n + k + 1 < MAX) prefixArray[n + k + 1]--;\n\n            if (n - k < 0) prefixArray[0]++;\n            else prefixArray[n - k]++;\n        }\n\n        int ans = 0, prefixSum = 0;\n        for (int i = 0; i < prefixArray.length; i++) {\n            prefixSum += prefixArray[i];\n            var freq = freqMap.getOrDefault(i, 0);\n            // Here `Math.min(prefixSum - freq, numOperations)` indicates that count of numbers which can be updated to match `i`\n            // Remove `freq` to exclude the numbers which are already matching `i`\n            ans = Math.max(Math.min(prefixSum - freq, numOperations) + freq, ans);\n        }\n\n        return ans;\n    }\n}\n```\n\n# Space Optimization\nThe above solution will not work for C or Q3 problem because the space will become `1e9` because of `nums[i]` range\nSo to optimize space here what can we do?\nIf we observe the previous solution prefixArray can a number which doesn\'t get updated while updating prefix array can become number with max possible frequency? No, so we can avoid storing prefix for this numbers by maintaing a `prefixMap` instead of `prefixArray`\n\n# Time Complexity change\nAs we are using tree map TC will become O(nlogn)\n\n# Code\n```java []\npublic int maxFrequency(int[] nums, int k, int numOperations) {\n        //Stores the frequency of a number in nums\n        var freqMap = new HashMap<Integer, Integer>();\n        //This map will be used to know the maximum frequency possible for a number\n        var prefixMap = new TreeMap<Integer, Integer>();\n\n        for (var n : nums) {\n            //Update or insert number in freqMap\n            freqMap.compute(n, (key, val) -> val == null ? 1 : (val + 1));\n\n            //Make sure number exists prefixMap, so that number will be considered while calculating the prefixSum\n            //Because we are using map no need to worry about index out bounds issue\n            prefixMap.putIfAbsent(n, 0);\n            prefixMap.compute(n + k + 1, (key, val) -> val == null ? -1 : (val - 1));\n            prefixMap.compute((n - k), (key, val) -> val == null ? 1 : (val + 1));\n        }\n\n        int ans = 0, prefixSum = 0;\n        for (var entry : prefixMap.entrySet()) {\n            prefixSum += entry.getValue();\n            var freq = freqMap.getOrDefault(entry.getKey(), 0);\n            // Here Math.min(prefixSum - freq, numOperations) indicates that count of numbers which can be updated to match entry.getValue()\n            // Remove freq to exclude the numbers which are already matching entry.getValue()\n            ans = Math.max(Math.min(prefixSum - freq, numOperations) + freq, ans);\n        }\n\n        return ans;\n    }\n```
['Java']