LeetCode 378: Kth Smallest Element in a Sorted Matrix Solution

Master LeetCode problem 378 (Kth Smallest Element in a Sorted Matrix), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

378. Kth Smallest Element in a Sorted Matrix

Medium

Array Binary Search Sorting Heap (Priority Queue)Matrix

Problem Explanation

Explanation:

To find the kth smallest element in a sorted matrix, we can use a min heap approach. We start by adding the first element of each row to a min heap. Then, at each step, we extract the smallest element from the heap and add the element from the same row as the extracted element, but in the next column. This way, we maintain the sorted order while finding the kth smallest element.

Algorithm:
1. Create a min heap and add the first element of each row to the heap.
2. Repeat the following steps k times:
  - Extract the smallest element from the heap.
  - If the extracted element has a next element in the same row, add that next element to the heap.
3. The kth extracted element is the kth smallest element in the matrix.
Time Complexity: O(k log n)
Space Complexity: O(n)

Solution Code

import java.util.PriorityQueue;

class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        int n = matrix.length;
        
        for (int i = 0; i < n; i++) {
            minHeap.offer(new int[]{matrix[i][0], i, 0});
        }
        
        for (int i = 0; i < k - 1; i++) {
            int[] curr = minHeap.poll();
            int row = curr[1];
            int col = curr[2];
            
            if (col < n - 1) {
                minHeap.offer(new int[]{matrix[row][col + 1], row, col + 1});
            }
        }
        
        return minHeap.poll()[0];
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 378 (Kth Smallest Element in a Sorted Matrix)?

This page provides optimized solutions for LeetCode problem 378 (Kth Smallest Element in a Sorted Matrix) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 378 (Kth Smallest Element in a Sorted Matrix)?

The time complexity for LeetCode 378 (Kth Smallest Element in a Sorted Matrix) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 378 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 378 in Java, C++, or Python.

Back to LeetCode Solutions