Kth Smallest in Matrix

Medium

Python

def kth_smallest(matrix,k):
    import heapq
    heap=[]
    for row in matrix:
        for val in row: heapq.heappush(heap,val)
    for _ in range(k-1): heapq.heappop(heap)
    return heapq.heappop(heap)

Java

public int kthSmallest(int[][] matrix,int k){
    PriorityQueue<Integer> pq=new PriorityQueue<>(Collections.reverseOrder());
    for(int[] row:matrix)
        for(int val:row){
            pq.offer(val);
            if(pq.size()>k) pq.poll();
        }
    return pq.poll();
}

Key Insight

Python heapq is min-heap. Java PriorityQueue is max-heap by default — reverseOrder() needed.

Python → Java Differences

Python heapq min-heap vs Java PriorityQueue
heapq module vs built-in PQ
Heap-based k-smallest

Python

def kth_smallest(matrix,k):
    import heapq
    heap=[]
    for row in matrix:
        for val in row: heapq.heappush(heap,val)
    for _ in range(k-1): heapq.heappop(heap)
    return heapq.heappop(heap)

Java

public int kthSmallest(int[][] matrix,int k){
    PriorityQueue<Integer> pq=new PriorityQueue<>(Collections.reverseOrder());
    for(int[] row:matrix)
        for(int val:row){
            pq.offer(val);
            if(pq.size()>k) pq.poll();
        }
    return pq.poll();
}

Algorithm Steps

1. Use heap to find kth smallest

← Previous All Arrays