🚀 Beats 100% | Java, C++, Python | Non queue solution
\u26A0\uFE0F Disclaimer: The original solution was crafted in Java. Thus, when we mention "Beats 100%" it applies specifically to Java submissions. The performa
> \u26A0\uFE0F **Disclaimer**: The original solution was crafted in Java. Thus, when we mention "Beats 100%" it applies specifically to Java submissions. The performance may vary for other languages.\n\nDont forget to upvote if you like the content below. \uD83D\uDE43\n\n# Intuition\nGiven the problem, we should always aim to negate the smallest number in the array in each iteration to maximize the final sum. However, we can use a micro-optimization by calculating the sum once at the beginning and then adjusting it after each negation.\n\n# Approach\nWe start by creating a frequency array, $$numbers$$, with the index representing the number in the original array + $$100$$. This allows us to handle negative numbers seamlessly.\n\nNext, we iterate through the $$nums$$ array, count the frequencies, and calculate the sum. Simultaneously, we keep track of the maximum absolute value in the array ($$maxAbs$$), which we will use later to determine the start index for the negation process.\n\nIf $$maxAbs$$ is zero after the first pass, it means all elements in the array are zero, and we return $$0$$, as negating zero doesn\'t change the sum.\n\nThen, we perform $$k$$ negations. For each negation, we start at the index $$i$$ equal to $$100 - maxAbs$$, which represents the smallest possible number in the array. We find the first index with a non-zero frequency, decrement its frequency, increment the frequency of its negation $$(200 - i)$$, and adjust the sum by subtracting twice the current number (since we have negated it).\n\n# Complexity\n- Time complexity:\nThe time complexity is $$O(n + k)$$, where $$n$$ is the length of the array and $$k$$ is the number of negations. $$n$$ is for the initial iteration through the nums array, and $$k$$ is for the negations.\n\n- Space complexity:\nThe space complexity is $$O(1)$$, as we only use a constant amount of extra space. The numbers array\'s size is a constant $$201$$, accommodating all possible values from $$-100$$ to $$100$$.\n\nThis solution is optimal for the problem constraints. While a PriorityQueue-based solution could also work, it might not be as fast due to overheads associated with creating and managing the PriorityQueue. Our solution avoids these overheads by using a simple frequency count array and a single pass through the array. The index calculation $$(number + 100)$$ and the negation index calculation $$(200 - index)$$ are straightforward and efficient, making this solution particularly suitable for the given constraints.\n\n# Code\n```java []\nclass Solution {\n    public int largestSumAfterKNegations(int[] nums, int k) {\n        int[] numbers = new int[201];\n        int sum = 0;\n        int maxAbs = 0;\n        for (int n: nums) {\n            maxAbs = Math.max(maxAbs, Math.abs(n));\n            numbers[100 + n]++;\n            sum += n;\n        }\n\n        if (maxAbs == 0) {\n            return 0;\n        }\n\n        while (k-- != 0) {\n            int i = 100 - maxAbs;\n            while (numbers[i] == 0) {\n                i++;\n            }\n            numbers[i]--;\n            numbers[200 - i]++;\n            sum -= 2 * (i - 100);\n        }\n\n        return sum;\n    }\n}\n```\n```cpp []\nclass Solution {\npublic:\n    int largestSumAfterKNegations(vector<int>& nums, int k) {\n        vector<int> numbers(201, 0);\n        int sum = 0;\n        int maxAbs = 0;\n        for (int n : nums) {\n            maxAbs = max(maxAbs, abs(n));\n            numbers[100 + n]++;\n            sum += n;\n        }\n\n        if (maxAbs == 0) {\n            return 0;\n        }\n\n        while (k-- != 0) {\n            int i = 100 - maxAbs;\n            while (numbers[i] == 0) {\n                i++;\n            }\n            numbers[i]--;\n            numbers[200 - i]++;\n            sum -= 2 * (i - 100);\n        }\n\n        return sum;\n    }\n};\n```\n```python []\nclass Solution:\n    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:\n        numbers = [0] * 201\n        total_sum = 0\n        max_abs = 0\n        \n        for n in nums:\n            max_abs = max(max_abs, abs(n))\n            numbers[100 + n] += 1\n            total_sum += n\n\n        if max_abs == 0:\n            return 0\n\n        while k > 0:\n            k -= 1\n            i = 100 - max_abs\n            while numbers[i] == 0:\n                i += 1\n            numbers[i] -= 1\n            numbers[200 - i] += 1\n            total_sum -= 2 * (i - 100)\n\n        return total_sum\n\n```
['Counting', 'C++', 'Java', 'Python3']