378. Kth Smallest Element in a Sorted Matrix LeetCode Solution

In this guide, you will get 378. Kth Smallest Element in a Sorted Matrix LeetCode Solution with the best time and space complexity. The solution to Kth Smallest Element in a Sorted Matrix 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
Complexity Analysis
Kth Smallest Element in a Sorted Matrix solution in C++
Kth Smallest Element in a Sorted Matrix solution in Java
Kth Smallest Element in a Sorted Matrix solution in Python
Additional Resources

378. Kth Smallest Element in a Sorted Matrix LeetCode Solution image

Problem Statement of Kth Smallest Element in a Sorted Matrix

Given an n x n matrix where each of the rows and columns is sorted in ascending order, return the kth smallest element in the matrix.
Note that it is the kth smallest element in the sorted order, not the kth distinct element.
You must find a solution with a memory complexity better than O(n2).

Example 1:

Input: matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
Output: 13
Explanation: The elements in the matrix are [1,5,9,10,11,12,13,13,15], and the 8th smallest number is 13

Example 2:

Input: matrix = [[-5]], k = 1
Output: -5

Constraints:

n == matrix.length == matrix[i].length
1 <= n <= 300
-109 <= matrix[i][j] <= 109
All the rows and columns of matrix are guaranteed to be sorted in non-decreasing order.
1 <= k <= n2

Follow up:

Could you solve the problem with a constant memory (i.e., O(1) memory complexity)?
Could you solve the problem in O(n) time complexity? The solution may be too advanced for an interview but you may find reading this paper fun.

Complexity Analysis

Time Complexity: O(x + k\log x), where x = \min(n, k)
Space Complexity: O(x), where x = \min(n, k)

378. Kth Smallest Element in a Sorted Matrix LeetCode Solution in C++

struct T {
  int i;
  int j;
  int num;  // matrix[i][j]
};

class Solution {
 public:
  int kthSmallest(vector<vector<int>>& matrix, int k) {
    auto compare = [&](const T& a, const T& b) { return a.num > b.num; };
    priority_queue<T, vector<T>, decltype(compare)> minHeap(compare);

    for (int i = 0; i < k && i < matrix.size(); ++i)
      minHeap.emplace(i, 0, matrix[i][0]);

    while (k-- > 1) {
      const auto [i, j, _] = minHeap.top();
      minHeap.pop();
      if (j + 1 < matrix[0].size())
        minHeap.emplace(i, j + 1, matrix[i][j + 1]);
    }

    return minHeap.top().num;
  }
};
/* code provided by PROGIEZ */

378. Kth Smallest Element in a Sorted Matrix LeetCode Solution in Java

class T {
  public int i;
  public int j;
  public int num; // matrix[i][j]
  public T(int i, int j, int num) {
    this.i = i;
    this.j = j;
    this.num = num;
  }
}

class Solution {
  public int kthSmallest(int[][] matrix, int k) {
    Queue<T> minHeap = new PriorityQueue<>((a, b) -> Integer.compare(a.num, b.num));

    for (int i = 0; i < k && i < matrix.length; ++i)
      minHeap.offer(new T(i, 0, matrix[i][0]));

    while (k-- > 1) {
      final int i = minHeap.peek().i;
      final int j = minHeap.poll().j;
      if (j + 1 < matrix[0].length)
        minHeap.offer(new T(i, j + 1, matrix[i][j + 1]));
    }

    return minHeap.peek().num;
  }
}
// code provided by PROGIEZ

378. Kth Smallest Element in a Sorted Matrix LeetCode Solution in Python

class Solution:
  def kthSmallest(self, matrix: list[list[int]], k: int) -> int:
    minHeap = []  # (matrix[i][j], i, j)

    i = 0
    while i < k and i < len(matrix):
      heapq.heappush(minHeap, (matrix[i][0], i, 0))
      i += 1

    while k > 1:
      k -= 1
      _, i, j = heapq.heappop(minHeap)
      if j + 1 < len(matrix[0]):
        heapq.heappush(minHeap, (matrix[i][j + 1], i, j + 1))

    return minHeap[0][0]
 # code by PROGIEZ