We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find the Kth Smallest Sum of a Matrix With Sorted Rows

Difficulty: Hard

Problem Description

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 k-th smallest array sum among all possible arrays.

Key Insights

  • The matrix rows are sorted, allowing efficient traversal of sums.
  • We need to consider combinations of elements from each row to form sums.
  • A min-heap is suitable for efficiently retrieving the smallest sums.
  • The problem can be reduced to finding the k-th smallest element in a specific combination of sums.

Space and Time Complexity

Time Complexity: O(k * log(m)), where m is the number of rows in the matrix. Space Complexity: O(m), to store the current sums in the priority queue.

Solution

To solve the problem, we can utilize a min-heap (priority queue) to explore the smallest sums. Initially, we insert the smallest possible sum (the first elements of each row) into the heap. Then, we iteratively extract the smallest sum from the heap and generate new sums by replacing one element from the corresponding row with the next element in that row (if available). We continue this process until we have extracted the k-th smallest sum.

Code Solutions

import heapq

def kthSmallest(mat, k):
    m, n = len(mat), len(mat[0])
    min_heap = []
    initial_sum = sum(row[0] for row in mat)
    min_heap.append((initial_sum, [0] * m))  # (sum, indices of elements)

    for _ in range(k):
        current_sum, indices = heapq.heappop(min_heap)

        for r in range(m):
            if indices[r] + 1 < n:
                new_indices = indices[:]
                new_indices[r] += 1
                new_sum = current_sum - mat[r][indices[r]] + mat[r][new_indices[r]]
                heapq.heappush(min_heap, (new_sum, new_indices))

    return current_sum
← Back to All Questions