Javascript | DP Solution (Bonus: Max-Heap) w/ Explanation | beats 100% / 100%
(Note: This is part of a series of Leetcode solution explanations (index). If you like this solution or find it useful, please upvote this post.)\n\n---\n\nIdea
*(Note: This is part of a series of Leetcode solution explanations ([**index**](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you like this solution or find it useful,* ***please upvote*** *this post.)*\n\n---\n\n***Idea:***\n\nSolving this problem with no regard for time complexity would be a simple matter, which means that the main issue is going to be finding a shortcut to not having to do the long calculations for each iteration. Since each new value that we\'re asked to find contains as a subset a value we\'ve already found, it naturally brings to mind a **dynamic programming** solution.\n\nFirst, each cell in our matrix **M** will have its own value, so **DP** will have to have the same dimensions as **M**. Next, let\'s say we\'re trying to find the value for **X = DP[4][6]**. From the instructions we know that it will be equal to each cell in the shaded area **bitwise XOR**\'d together:\n\n![image](https://assets.leetcode.com/users/images/1614f5e5-32a6-4e83-b9d0-3e41b2e31dd1_1611554767.23081.png)\n\nSince our **DP** matrix is being built top-to-bottom and left-to-right, we can get close to the necessary value with either **A = DP[3][6]** or **B = DP[4][5]**:\n\n![image](https://assets.leetcode.com/users/images/a1b69f1a-4e96-4596-ada5-d77813533e0c_1611554790.5519903.png)\n\nBut even those shortcuts would allow the time complexity to increase exponentially with the size of **M**, since we\'d still have to iterate through a whole row or column to get the other values we need for **X**. We could get even closer if we use *both* **A** and **B**, but they overlap quite a bit.\n\nThis is where it\'s important to realize that the **bitwise XOR** operation is its own inverse function:\n```javascript\n if:    x ^ y = z\n  \u21D2:    z ^ y = x\n  \u21D2:    x ^ y ^ y = x\n```\nThis means that the overlapping sections of **A** and **B** would effectively cancel each other out, as those numbers would be **XOR**\'d twice each:\n\n![image](https://assets.leetcode.com/users/images/746bd1e2-b978-4ae4-9b8f-5965e1f5b493_1611554831.013172.png)\n\nThis opens up the immediate possibility of using a *third* **DP** value (**C = DP[4][4]**) in conjunction with **A** and **B** to leave us only one cell away from the value of **X**. That means that we can find out the **DP** value of each new cell by combing only four other cell values:\n\n![image](https://assets.leetcode.com/users/images/07d328ee-d2d6-4f24-9ed1-b328fa48f80c_1611554843.5071309.png)\n\nAt that point, we only need to account for **i = 0** and **j = 0** values to complete our **DP** matrix. Since we won\'t need any previous original cell values in order to complete the **DP** matrix, we can also solve the **DP** matrix in-place.\n\nThe final step for this problem is to then sort the values in the **DP** matrix in order to find the **K**th highest value. Normally, this would call for a **max-heap** implementation, as the numbers can be readily inserted into the heap as **M** is being rewritten.\n\nFor Javascript, however, we can achieve a much faster sort through a typed array .sort() than we can with a max-heap implementation. (*Note: I\'ve included a version of the code with a max-heap implementation below, for comparison.*)\n\nSince the original cell values of **M** are limited to **1e6**, which is a **20**-bit binary number, the **DP** values are therefore limited to between **0** and  **2^20 - 1**. This means that we can use a **Uint32Array** to store the values more efficiently.\n\nAfter a basic sort, we can **return** the Kth highest value.\n\n---\n\n***Javascript Code:***\n\nThe best result for the code below is **168ms / 61.9MB**.\n```javascript\nvar kthLargestValue = function(M, K) {\n    let y = M.length, x = M[0].length, ans = new Uint32Array(x*y), h = 0\n    for (let i = 0; i < y; i++)\n        for (let j = 0; j < x; j++) {\n            let cell = M[i][j]\n            if (i > 0) cell ^= M[i-1][j]\n            if (j > 0) cell ^= M[i][j-1]\n            if (i > 0 && j > 0) cell ^= M[i-1][j-1]\n            ans[h++] = M[i][j] = cell\n        }\n    return ans.sort()[x*y-K]\n};\n```\n\n---\n\n***Javascript Code w/ Max-Heap:***\n\nThe best result for the code below is **360ms / 63.4MB**.\n```javascript\nvar kthLargestValue = function(M, K) {\n    let y = M.length, x = M[0].length,\n        heap = new Uint32Array(x*y), hix = 0\n    const heapify = num => {\n        heap[hix] = num\n        let i = hix++, par = (i - 1) >> 1\n        while (heap[par] < heap[i]) {\n            [heap[par],heap[i]] = [heap[i],heap[par]]\n            i = par, par = (i - 1) >> 1\n        }\n    }\n    const extract = () => {\n        let max = heap[0], left, right\n        heap[0] = heap[--hix], heap[hix] = 0\n        let i = 0, child = heap[2] > heap[1] ? 2 : 1\n        while (heap[i] < heap[child]) {\n            [heap[i],heap[child]] = [heap[child],heap[i]]\n            i = child, left = (i + 1) << 1, right = left - 1\n            child = heap[right] > heap[left] ? right : left\n        }\n        return max\n    }\n    for (let i = 0; i < y; i++)\n        for (let j = 0; j < x; j++) {\n            let cell = M[i][j]\n            if (i > 0) cell ^= M[i-1][j]\n            if (j > 0) cell ^= M[i][j-1]\n            if (i > 0 && j > 0) cell ^= M[i-1][j-1]\n            heapify(M[i][j] = cell)\n        }\n    for (let i = K-1; i; i--) extract()\n    return extract()\n};\n```
['JavaScript']