Create Find the Kth Smallest Sum of a Matrix With Sorted Rows.java

varunu28 · web-flow · commit 9d404d95b873 · 2022-10-18T10:34:56.000-07:00
diff --git a/Hard/Find the Kth Smallest Sum of a Matrix With Sorted Rows.java b/Hard/Find the Kth Smallest Sum of a Matrix With Sorted Rows.java
@@ -0,0 +1,19 @@
+class Solution {
+  public int kthSmallest(int[][] mat, int k) {
+    PriorityQueue<Integer> prevSum = new PriorityQueue<>(Collections.reverseOrder());
+    prevSum.add(0);
+    for (int[] row : mat) {
+      PriorityQueue<Integer> nextSum = new PriorityQueue<>(Collections.reverseOrder());
+      for (int sum : prevSum) {
+        for (int c = 0; c < mat[0].length; c++) {
+          nextSum.add(sum + row[c]);
+          if (nextSum.size() > k) {
+            nextSum.poll();
+          }
+        }
+      }
+      prevSum = nextSum;
+    }
+    return prevSum.poll();
+  }
+}
