Min Heap (O(n + k * log (n)) time / O(1) space)
Hi LeetCoders \uD83D\uDC4B\nHere is my simple and clean solution to this problem with use of min-heap.\n\nCode:\n\nfrom heapq import heapify, heapreplace\n\ncla
Hi LeetCoders \uD83D\uDC4B\nHere is my simple and clean solution to this problem with use of min-heap.\n\n**Code:**\n```\nfrom heapq import heapify, heapreplace\n\nclass Solution:\n    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:\n        heapify(nums)\n        while k and nums[0] < 0:\n            heapreplace(nums, -nums[0])\n            k -= 1\n        if k % 2:\n            heapreplace(nums, -nums[0])\n        return sum(nums)\n```\n\n**Idea explanation:**\n* negate negative numbers as many as you can\n* if ```k % 2 == 1``` negate the smallest element in the heap\n\n**Notes:**\nAvoid using ```heappush + heappop``` because it takes ```O(2 * log (n))``` time, use ```heapreplace``` instead and pay just ```O(log (n))```. Isn\'t that a great deal?\n\n**Algorithm complexity:**\n*n = len(nums)*\n*Time complexity: O(n + k * log (n))*\n*Space complexity: O(1)*\n\nIf you like my solution, I will really appreciate your upvoting. It will help other python-developers to find it faster. And as always, I hope you learned something and wish you an enjoyable time on LeetCode. \uD83D\uDE0A
['Heap (Priority Queue)', 'Python3']