New Problem Solution -"1738. Find Kth Largest XOR Coordinate Value"

haoel · haoel · commit 6ef88aa9fb80 · 2021-03-31T19:47:48.000+08:00
diff --git a/README.md b/README.md
@@ -56,6 +56,7 @@ LeetCode
 |1748|[Sum of Unique Elements](https://leetcode.com/problems/sum-of-unique-elements/) | [C++](./algorithms/cpp/sumOfUniqueElements/SumOfUniqueElements.cpp)|Easy|
 |1743|[Restore the Array From Adjacent Pairs](https://leetcode.com/problems/restore-the-array-from-adjacent-pairs/) | [C++](./algorithms/cpp/restoreTheArrayFromAdjacentPairs/RestoreTheArrayFromAdjacentPairs.cpp)|Medium|
 |1742|[Maximum Number of Balls in a Box](https://leetcode.com/problems/maximum-number-of-balls-in-a-box/) | [C++](./algorithms/cpp/maximumNumberOfBallsInABox/MaximumNumberOfBallsInABox.cpp)|Easy|
+|1738|[Find Kth Largest XOR Coordinate Value](https://leetcode.com/problems/find-kth-largest-xor-coordinate-value/) | [C++](./algorithms/cpp/findKthLargestXorCoordinateValue/FindKthLargestXorCoordinateValue.cpp)|Medium|
 |1736|[Latest Time by Replacing Hidden Digits](https://leetcode.com/problems/latest-time-by-replacing-hidden-digits/) | [C++](./algorithms/cpp/latestTimeByReplacingHiddenDigits/LatestTimeByReplacingHiddenDigits.cpp)|Easy|
 |1734|[Decode XORed Permutation](https://leetcode.com/problems/decode-xored-permutation/) | [C++](./algorithms/cpp/decodeXORedPermutation/DecodeXoredPermutation.cpp)|Medium|
 |1733|[Minimum Number of People to Teach](https://leetcode.com/problems/minimum-number-of-people-to-teach/) | [C++](./algorithms/cpp/minimumNumberOfPeopleToTeach/MinimumNumberOfPeopleToTeach.cpp)|Medium|
diff --git a/algorithms/cpp/findKthLargestXorCoordinateValue/FindKthLargestXorCoordinateValue.cpp b/algorithms/cpp/findKthLargestXorCoordinateValue/FindKthLargestXorCoordinateValue.cpp
@@ -0,0 +1,96 @@
+// Source : https://leetcode.com/problems/find-kth-largest-xor-coordinate-value/
+// Author : Hao Chen
+// Date   : 2021-03-31
+
+/***************************************************************************************************** 
+ *
+ * You are given a 2D matrix of size m x n, consisting of non-negative integers. You are also given an 
+ * integer k.
+ * 
+ * The value of coordinate (a, b) of the matrix is the XOR of all matrix[i][j] where 0 <= i <= a < m 
+ * and 0 <= j <= b < n (0-indexed).
+ * 
+ * Find the k^th largest value (1-indexed) of all the coordinates of matrix.
+ * 
+ * Example 1:
+ * 
+ * Input: matrix = [[5,2],[1,6]], k = 1
+ * Output: 7
+ * Explanation: The value of coordinate (0,1) is 5 XOR 2 = 7, which is the largest value.
+ * 
+ * Example 2:
+ * 
+ * Input: matrix = [[5,2],[1,6]], k = 2
+ * Output: 5
+ * Explanation: The value of coordinate (0,0) is 5 = 5, which is the 2nd largest value.
+ * 
+ * Example 3:
+ * 
+ * Input: matrix = [[5,2],[1,6]], k = 3
+ * Output: 4
+ * Explanation: The value of coordinate (1,0) is 5 XOR 1 = 4, which is the 3rd largest value.
+ * 
+ * Example 4:
+ * 
+ * Input: matrix = [[5,2],[1,6]], k = 4
+ * Output: 0
+ * Explanation: The value of coordinate (1,1) is 5 XOR 2 XOR 1 XOR 6 = 0, which is the 4th largest 
+ * value.
+ * 
+ * Constraints:
+ * 
+ * 	m == matrix.length
+ * 	n == matrix[i].length
+ * 	1 <= m, n <= 1000
+ * 	0 <= matrix[i][j] <= 10^6
+ * 	1 <= k <= m * n
+ ******************************************************************************************************/
+
+class Solution {
+private:
+    void print(vector<vector<int>>& m) {
+        int row = m.size();
+        int col = m[0].size();
+        for (int i=0; i<row; i++) {
+            for(int j=0; j<col-1; j++) {
+                cout << setw(3) << m[i][j] << ",";
+            }
+            cout << setw(3) << m[i][col-1] << endl;
+        }
+        cout << endl;
+    }
+public:
+    int kthLargestValue(vector<vector<int>>& matrix, int k) {
+        int row = matrix.size();
+        int col = matrix[0].size();
+        vector<vector<int>> xmatrix(row, vector<int>(col, 0));
+        priority_queue<int> minHeap;
+        
+        xmatrix[0][0] = matrix[0][0];
+        minHeap.push(xmatrix[0][0]);
+ 
+        for (int i=1; i<row; i++) {
+            xmatrix[i][0] = xmatrix[i-1][0] ^ matrix[i][0];
+            minHeap.push(xmatrix[i][0]);
+        }
+        for (int i=1; i<col; i++) {
+            xmatrix[0][i] = xmatrix[0][i-1] ^ matrix[0][i];
+            minHeap.push(xmatrix[0][i]);
+        }
+        
+        for (int i=1; i<row; i++) {
+            for(int j=1; j<col; j++) {
+                xmatrix[i][j] = matrix[i][j] ^ 
+                    xmatrix[i-1][j] ^ xmatrix[i][j-1] ^ xmatrix[i-1][j-1];
+                minHeap.push(xmatrix[i][j]);
+            }
+        }
+        //print(matrix);
+        //print(xmatrix);
+        while( k-- > 1) {
+            minHeap.pop();
+        }
+        
+        return minHeap.top();
+    }
+};
