1439. Find the Kth Smallest Sum of a Matrix With Sorted Rows LeetCode Solution
In this guide, you will get 1439. Find the Kth Smallest Sum of a Matrix With Sorted Rows LeetCode Solution with the best time and space complexity. The solution to Find the Kth Smallest Sum of a Matrix With Sorted Rows problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Find the Kth Smallest Sum of a Matrix With Sorted Rows
You are given an m x n matrix mat that has its rows sorted in non-decreasing order and an integer k.
You are allowed to choose exactly one element from each row to form an array.
Return the kth smallest array sum among all possible arrays.
Example 1:
Input: mat = [[1,3,11],[2,4,6]], k = 5
Output: 7
Explanation: Choosing one element from each row, the first k smallest sum are:
[1,2], [1,4], [3,2], [3,4], [1,6]. Where the 5th sum is 7.
Example 2:
Input: mat = [[1,3,11],[2,4,6]], k = 9
Output: 17
Example 3:
Input: mat = [[1,10,10],[1,4,5],[2,3,6]], k = 7
Output: 9
Explanation: Choosing one element from each row, the first k smallest sum are:
[1,1,2], [1,1,3], [1,4,2], [1,4,3], [1,1,6], [1,5,2], [1,5,3]. Where the 7th sum is 9.
m == mat.length
n == mat.length[i]
1 <= m, n <= 40
1 <= mat[i][j] <= 5000
1 <= k <= min(200, nm)
mat[i] is a non-decreasing array.
Complexity Analysis
Time Complexity: O(|\texttt{mat}| \cdot k\log k)
Space Complexity: O(k)
1439. Find the Kth Smallest Sum of a Matrix With Sorted Rows LeetCode Solution in C++
struct T {
int i;
int j;
int sum; // nums1[i] + nums2[j]
};
class Solution {
public:
int kthSmallest(vector<vector<int>>& mat, int k) {
vector<int> row = mat[0];
for (int i = 1; i < mat.size(); ++i)
row = kSmallestPairSums(row, mat[i], k);
return row.back();
}
private:
// Similar to 373. Find K Pairs with Smallest Sums
vector<int> kSmallestPairSums(vector<int>& nums1, vector<int>& nums2, int k) {
vector<int> ans;
auto compare = [&](const T& a, const T& b) { return a.sum > b.sum; };
priority_queue<T, vector<T>, decltype(compare)> minHeap(compare);
for (int i = 0; i < k && i < nums1.size(); ++i)
minHeap.emplace(i, 0, nums1[i] + nums2[0]);
while (!minHeap.empty() && ans.size() < k) {
const auto [i, j, _] = minHeap.top();
minHeap.pop();
ans.push_back(nums1[i] + nums2[j]);
if (j + 1 < nums2.size())
minHeap.emplace(i, j + 1, nums1[i] + nums2[j + 1]);
}
return ans;
}
}; /* code provided by PROGIEZ */
1439. Find the Kth Smallest Sum of a Matrix With Sorted Rows LeetCode Solution in Java
class Solution {
public int kthSmallest(int[][] mat, int k) {
int[] row = mat[0];
for (int i = 1; i < mat.length; ++i)
row = kSmallestPairSums(row, mat[i], k);
return row[k - 1];
}
private record T(int i, int j, int sum) {}
// Similar to 373. Find K Pairs with Smallest Sums
private int[] kSmallestPairSums(int[] nums1, int[] nums2, int k) {
List<Integer> ans = new ArrayList<>();
Queue<T> minHeap = new PriorityQueue<>((a, b) -> Integer.compare(a.sum, b.sum));
for (int i = 0; i < k && i < nums1.length; ++i)
minHeap.offer(new T(i, 0, nums1[i] + nums2[0]));
while (!minHeap.isEmpty() && ans.size() < k) {
final int i = minHeap.peek().i;
final int j = minHeap.poll().j;
ans.add(nums1[i] + nums2[j]);
if (j + 1 < nums2.length)
minHeap.offer(new T(i, j + 1, nums1[i] + nums2[j + 1]));
}
return ans.stream().mapToInt(Integer::intValue).toArray();
}
} // code provided by PROGIEZ
1439. Find the Kth Smallest Sum of a Matrix With Sorted Rows LeetCode Solution in Python
