LeetCode 378: Kth Smallest Element in a Sorted Matrix Solution in Python – A Step-by-Step Guide

What Is LeetCode 378: Kth Smallest Element in a Sorted Matrix?

LeetCode 378: Kth Smallest Element in a Sorted Matrix provides an n x n matrix where each row and column is sorted in ascending order, and an integer k. Your task is to return the kth smallest element in the matrix (1-based index, not the kth distinct element). It’s a problem that tests your ability to leverage sorted properties for efficient searching!

Problem Statement

• Input:
• matrix: n x n list of integers, sorted by row and column.
• k: Integer representing the kth smallest element to find (1-based).
• Output: Integer - The kth smallest element.
• Rules:
• Matrix is n x n, each row and column sorted ascending.
• k is 1-based (k=1 means smallest, k=n² means largest).
• Return the kth smallest value, not distinct.

Constraints

• 1 <= n <= 300
• -10⁹ <= matrix[i][j] <= 10⁹
• 1 <= k <= n²

Examples

• Input: matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
• Output: 13
• Elements: [1, 5, 9, 10, 11, 12, 13, 13, 15], 8th smallest = 13.
• Input: matrix = [[1,2],[1,3]], k = 2
• Output: 1
• Elements: [1, 1, 2, 3], 2nd smallest = 1.
• Input: matrix = [[1]], k = 1
• Output: 1
• Single element, 1st = 1.

These show the kth smallest hunt—let’s solve it!

Understanding the Problem: Finding the Kth Smallest

To tackle LeetCode 378 in Python, we need to: 1. Find the kth smallest element in an n x n sorted matrix. 2. Use the row and column sorting to optimize the search. 3. Handle duplicates (kth smallest, not distinct).

A naive approach might flatten and sort, but that’s O(n² log n²). Instead, we’ll use:

• Best Solution: Min-heap—O(k log k) time, O(k) space—fast and efficient.
• Alternative Solution: Binary search—O(n log n log M) time, O(1) space—clever but slower for small k.

Let’s optimize with the best solution!

Best Solution: Min-Heap

Why This Is the Best Solution

The min-heap approach runs in O(k log k) time by maintaining a priority queue of the smallest elements, starting at the top-left corner and expanding only as needed. It leverages the sorted properties to avoid processing all n² elements—making it the most efficient for typical k values (often smaller than n²)!

How It Works

Think of it like a treasure hunt:

• Heap: Min-heap of (value, row, col) tuples, starting with matrix[0][0].
• Expand: Pop smallest, push next elements in row and column (if not seen).
• Repeat: k times to get the kth smallest.
• Track: Use a set to avoid duplicates.
• Result: The kth popped value.

It’s like picking the next smallest gem from a sorted grid!

Step-by-Step Example

For matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8:

• Init: Heap = [(1, 0, 0)], Seen = {(0, 0)}, Count = 0.
• Step 1: Pop (1, 0, 0), Count = 1, Push (5, 0, 1), (10, 1, 0).
• Heap = [(5, 0, 1), (10, 1, 0)].
• Step 2: Pop (5, 0, 1), Count = 2, Push (9, 0, 2), (11, 1, 1).
• Heap = [(9, 0, 2), (10, 1, 0), (11, 1, 1)].
• Step 3: Pop (9, 0, 2), Count = 3, Push (13, 1, 2).
• Heap = [(10, 1, 0), (11, 1, 1), (13, 1, 2)].
• Step 4: Pop (10, 1, 0), Count = 4, Push (12, 2, 0).
• Heap = [(11, 1, 1), (12, 2, 0), (13, 1, 2)].
• Step 5: Pop (11, 1, 1), Count = 5, Push (13, 2, 1).
• Heap = [(12, 2, 0), (13, 1, 2), (13, 2, 1)].
• Step 6: Pop (12, 2, 0), Count = 6, Push (13, 2, 1) (seen), skip.
• Heap = [(13, 1, 2), (13, 2, 1)].
• Step 7: Pop (13, 1, 2), Count = 7, Push (15, 2, 2).
• Heap = [(13, 2, 1), (15, 2, 2)].
• Step 8: Pop (13, 2, 1), Count = 8, Heap = [(15, 2, 2)].
• Result: 13 (8th smallest).

For nums = [[1,2],[1,3]], k = 2:

• Init: Heap = [(1, 0, 0)], Count = 0.
• Step 1: Pop (1, 0, 0), Count = 1, Push (2, 0, 1), (1, 1, 0).
• Step 2: Pop (1, 1, 0), Count = 2, Push (3, 1, 1).
• Result: 1 (2nd smallest).

Code with Explanation

Here’s the Python code using a min-heap:

Copy codefrom heapq import heappush, heappop

class Solution:
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        n = len(matrix)
        if k == 1:
            return matrix[0][0]
        if k == n * n:
            return matrix[n-1][n-1]

        # Min-heap: (value, row, col)
        heap = [(matrix[0][0], 0, 0)]
        seen = {(0, 0)}
        count = 0

        # Pop k times to get kth smallest
        while heap:
            val, row, col = heappop(heap)
            count += 1
            if count == k:
                return val

            # Add next elements in row and column
            if col + 1 < n and (row, col + 1) not in seen:
                heappush(heap, (matrix[row][col + 1], row, col + 1))
                seen.add((row, col + 1))
            if row + 1 < n and (row + 1, col) not in seen:
                heappush(heap, (matrix[row + 1][col], row + 1, col))
                seen.add((row + 1, col))

        return -1  # Shouldn't reach here

Explanation

• Lines 6-9: Handle edge cases: k=1 (smallest), k=n² (largest).
• Lines 11-12: heap: Min-heap of (value, row, col), start with (0,0), seen: Track visited.
• Lines 14-24: Heap loop:
• Pop smallest, increment count.
• If count = k, return value.
• Push next in row (col+1) and column (row+1) if valid and unseen.
• Time: O(k log k)—k heap operations, log k for heap size.
• Space: O(k)—heap and seen set.

This is like a treasure hunt—grab the kth gem fast!

Alternative Solution: Binary Search

Why an Alternative Approach?

The binary search solution runs in O(n log n log M) time (M is value range) by guessing a value and counting how many matrix elements are ≤ it, adjusting the range. It’s clever—great for understanding range-based optimization, though slower for small k!

How It Works

• Range: Binary search on value range (min to max matrix element).
• Count: For each guess, count elements ≤ guess in O(n log n).
• Adjust: If count < k, guess higher; if ≥ k, guess lower.
• Result: Find smallest value where count ≥ k.

Step-by-Step Example

For matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8:

• Range: left=1, right=15.
• Step 1: mid=8, count ≤ 8 = 4 (1,5,9,10) < 8, left=9.
• Step 2: mid=12, count ≤ 12 = 6 (1,5,9,10,11,12) < 8, left=13.
• Step 3: mid=14, count ≤ 14 = 8 (1,5,9,10,11,12,13,13) = 8, right=13.
• Step 4: mid=13, count ≤ 13 = 8 ≥ 8, right=12.
• Step 5: left=13, right=12, left > right, return 13.

Code with Explanation

Copy codeclass Solution:
    def kthSmallest(self, matrix: List[int], k: int) -> int:
        n = len(matrix)

        # Count elements <= x in matrix
        def count_less_equal(x):
            count = 0
            row, col = 0, n - 1  # Start at top-right
            while row < n and col >= 0:
                if matrix[row][col] <= x:
                    count += col + 1  # All in row up to col
                    row += 1
                else:
                    col -= 1
            return count

        # Binary search on value range
        left, right = matrix[0][0], matrix[n-1][n-1]
        while left <= right:
            mid = left + (right - left) // 2
            if count_less_equal(mid) < k:
                left = mid + 1
            else:
                right = mid - 1

        return left

Explanation

• Lines 6-14: count_less_equal:
• Start at top-right, count elements ≤ x in O(n).
• If ≤ x, add col+1 (row elements), move down; else move left.
• Lines 16-23: Binary search:
• Range: min (top-left) to max (bottom-right).
• If count < k, search higher; else lower.
• Line 25: Return left (smallest value where count ≥ k).
• Time: O(n log n log M)—log M binary search steps, O(n) per count.
• Space: O(1)—no extra space.

It’s like guessing the value—range-based!

Comparing the Two Solutions

• Min-Heap (Best):
• Time: O(k log k)—heap ops.
• Space: O(k)—heap.
• Pros: Fast for small k, intuitive.
• Cons: Space grows with k.
• Binary Search (Alternative):
• Time: O(n log n log M)—range search.
• Space: O(1)—minimal.
• Pros: Space-efficient, clever.
• Cons: Slower for small k.

Min-heap wins for typical k values!

Additional Examples and Edge Cases

• [[1]], k=1: 1.
• [[1,2],[3,4]], k=4: 4.
• Large k: Heap adapts, binary search consistent.

Both work, heap is faster for small k.

Complexity Breakdown

• Min-Heap:
• Time: O(k log k).
• Space: O(k).
• Binary Search:
• Time: O(n log n log M).
• Space: O(1).

Heap excels for efficiency with small k.

Key Takeaways

• Min-Heap: Pick k smallest—fast and smart!
• Binary Search: Guess the value—clever and lean!
• Matrix: Sorting helps.
• Python Tip: Heapq rocks—see [Python Basics](/python/basics).

Final Thoughts: Find That Kth Element

LeetCode 378: Kth Smallest Element in a Sorted Matrix in Python is a matrix search challenge. Min-heap is the efficiency champ for most cases, while binary search offers a space-saving alternative. Want more? Try LeetCode 215: Kth Largest Element or LeetCode 373: Find K Pairs with Smallest Sums. Ready to search? Visit Solve LeetCode 378 on LeetCode and grab that kth element today!