Kth Smallest Element in Sorted Matrix

▶

Steps

setup

Initialize low and high

Set low to the smallest element (matrix[0][0] = 1) and high to the largest element (matrix[2][2] = 15). This defines the initial search range for the kth smallest element.

💡 Setting these boundaries is crucial because the kth smallest must lie between these values.

Line:

n = len(matrix)
low, high = matrix[0][0], matrix[-1][-1]

💡 The search space is the value range from 1 to 15, not indices.

expand_traverse

Compute mid = (low + high) // 2 and start counting elements ≤ mid

Calculate mid as the average of low and high, then initialize pointers at bottom-left of matrix to count elements ≤ mid.

💡 Mid divides the search space to test if kth smallest is ≤ mid or greater. Starting at bottom-left leverages sorted rows and columns for efficient counting.

Line:

mid = (low + high) // 2
row, col = n - 1, 0

💡 Mid is the candidate value to compare against matrix elements. This position allows moving right to find larger elements and up to find smaller ones.

compare_loop

Count elements ≤ mid by moving pointers

Compare matrix[row][col] with mid and move pointers accordingly to count elements ≤ mid efficiently.

💡 If element ≤ mid, count all elements in this column up to current row and move right; else move up to smaller elements.

Line:

if matrix[row][col] <= mid:
    count += row + 1
    col += 1
else:
    row -= 1

💡 This two-pointer approach counts qualifying elements in O(n) time by exploiting matrix sorting.

shrink

Update low since count < k

Since count=2 < k=8, set low = mid + 1 = 9 to search higher values.

💡 If fewer elements ≤ mid than k, kth smallest must be larger than mid.

Line:

if countLessEqual(mid) < k:
    low = mid + 1

💡 Search space is narrowed to [9, 15].

expand_traverse_compare

Compute mid = 12 and count elements ≤ mid

Calculate mid as 12 and count elements ≤ 12 using the two-pointer approach.

💡 Mid recalculates the candidate value in the narrowed search space.

Line:

mid = (low + high) // 2
row, col = n - 1, 0
if matrix[row][col] <= mid:
    count += row + 1
    col += 1
else:
    row -= 1

💡 Counting elements ≤ 12 refines the search space.

shrink

Update low since count < k

Since count=6 < k=8, set low = mid + 1 = 13 to search higher values.

💡 Still fewer elements ≤ mid than k, so increase low.

Line:

if countLessEqual(mid) < k:
    low = mid + 1

💡 Search space narrows to [13, 15].

expand_traverse_compare

Compute mid = 14 and count elements ≤ mid

Calculate mid as 14 and count elements ≤ 14 using the two-pointer approach.

💡 Mid recalculates candidate in narrowed range.

Line:

mid = (low + high) // 2
row, col = n - 1, 0
if matrix[row][col] <= mid:
    count += row + 1
    col += 1
else:
    row -= 1

💡 Counting elements ≤ 14 refines the search space.

shrink

Update high since count ≥ k

Since count=8 ≥ k=8, set high = mid = 14 to search lower or equal values.

💡 Enough elements ≤ mid, so kth smallest ≤ mid.

Line:

else:
    high = mid

💡 Search space narrows to [13, 14].

expand_traverse_compare

Compute mid = 13 and count elements ≤ mid

Calculate mid as 13 and count elements ≤ 13 using the two-pointer approach.

💡 Mid recalculates candidate in narrowed range.

Line:

mid = (low + high) // 2
row, col = n - 1, 0
if matrix[row][col] <= mid:
    count += row + 1
    col += 1
else:
    row -= 1

💡 Counting elements ≤ 13 refines the search space.

shrink

Update high since count ≥ k

Since count=8 ≥ k=8, set high = mid = 13 to narrow search.

💡 Enough elements ≤ mid, so kth smallest ≤ mid.

Line:

else:
    high = mid

💡 Search space narrows to [13, 13].

reconstruct

Return low as kth smallest element

Low and high have converged to 13, which is the kth smallest element in the matrix.

💡 When low == high, the search ends and the answer is found.

Line:

return low

💡 The kth smallest element is 13.

def kthSmallest(matrix, k):
    n = len(matrix)  # STEP 1
    low, high = matrix[0][0], matrix[-1][-1]  # STEP 1

    def countLessEqual(mid):
        count = 0
        row, col = n - 1, 0  # STEP 3
        while row >= 0 and col < n:
            if matrix[row][col] <= mid:  # STEP 4-8
                count += row + 1
                col += 1
            else:
                row -= 1
        return count

    while low < high:  # STEP 2
        mid = (low + high) // 2  # STEP 2,10,18,25
        if countLessEqual(mid) < k:  # STEP 9,17,24,31
            low = mid + 1
        else:
            high = mid
    return low  # STEP 32

if __name__ == '__main__':
    matrix = [[1,5,9],[10,11,13],[12,13,15]]
    k = 8
    print(kthSmallest(matrix, k))  # Output: 13

📊

Kth Smallest Element in Sorted Matrix - Watch the Algorithm Execute, Step by Step

Watching each comparison and pointer movement reveals how the algorithm efficiently narrows down the search space without sorting all elements.

setupmin-heap

1

0

15

1

expand_traversemin-heap

1

0

15

1

8

2

comparemin-heap

1

0

15

1

8

2

Added: 2

shrinkmin-heap

9

0

15

1

comparemin-heap

9

0

15

1

12

2

Added: 6

shrinkmin-heap

13

0

15

1

comparemin-heap

13

0

15

1

14

2

Added: 8

shrinkmin-heap

13

0

14

1

comparemin-heap

13

0

14

1

13

2

Added: 8

shrinkmin-heap

13

0

13

1

peekmin-heap

13

0

Added: 13

Key Takeaways

✓ Binary search on the value range efficiently narrows down the kth smallest element without sorting all elements.

This insight is hard to see from code alone because the algorithm uses value comparisons rather than index sorting.

✓ Counting elements ≤ mid using a two-pointer approach from bottom-left exploits the matrix's sorted rows and columns for O(n) counting.

Visualizing pointer movements clarifies why this counting is efficient and avoids scanning all elements.

✓ The decision to move low or high based on count comparison with k progressively shrinks the search space until convergence.

Seeing each update to low and high with counts helps understand the binary search logic concretely.

Practice

1. Consider the following Python code implementing the heap-based approach to find the k-th smallest pair distance. What is the returned value when calling smallestDistancePair([1,3,1], 2)?

easy

A. 3

B. 1

C. 0

D. 2

Solution

1. Step 1: Sort input and initialize heap

   Sorted nums = [1,1,3]. Initial heap contains pairs: (0,0,1), (2,1,2).

2. Step 2: Pop k-1=1 times and push next pairs

   Pop (0,0,1). Since j+1=2<n, push (3-1=2,0,2). Heap now: (2,0,2), (2,1,2). The smallest distance at heap top is 2.

3. Step 3: Return the k-th smallest distance

   After popping once, the top of the heap is (2,0,2), so the returned value is 2.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Second smallest pair distance is 2 [OK]

Hint: Trace heap pops and pushes carefully for small inputs [OK]

Common Mistakes:

• Off-by-one in k-1 loop
• Confusing indices i,j
• Returning wrong heap element

2. Given the following Python code implementing the optimal approach for Kth Largest in a Stream, what is the output of the last print statement?

import heapq

class KthLargest:
    def __init__(self, k: int, nums: list[int]):
        self.k = k
        self.heap = nums
        heapq.heapify(self.heap)
        while len(self.heap) > k:
            heapq.heappop(self.heap)

    def add(self, val: int) -> int:
        if len(self.heap) < self.k:
            heapq.heappush(self.heap, val)
        elif val > self.heap[0]:
            heapq.heapreplace(self.heap, val)
        return self.heap[0]

kthLargest = KthLargest(3, [4, 5, 8, 2])
print(kthLargest.add(3))
print(kthLargest.add(5))
print(kthLargest.add(10))
print(kthLargest.add(9))
print(kthLargest.add(4))

easy

A. 8

B. 5

C. 4

D. 9

Solution

1. Step 1: Trace heap initialization

   Initial nums = [4,5,8,2], heapified and trimmed to size k=3: heap becomes [4,5,8] after popping 2.

2. Step 2: Trace add calls and heap updates

   add(3): 3 < 4 (heap[0]), no replace, return 4 add(5): 5 > 4, replace 4 with 5, heap now [5,5,8], return 5 add(10): 10 > 5, replace 5 with 10, heap now [5,10,8], return 5 add(9): 9 > 5, replace 5 with 9, heap now [8,10,9], return 8 add(4): 4 < 8, no replace, return 8

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Last add returns 8 as kth largest element [OK]

Hint: Heap root always holds kth largest element [OK]

Common Mistakes:

• Off-by-one errors in heap size
• Replacing when val <= heap[0]
• Misunderstanding heap root meaning

3. Consider the following code snippet for finding the kth largest XOR coordinate value. Given the input matrix = [[5, 2], [1, 6]] and k = 3, what is the value of min_heap[0] returned by the function?

easy

A. 4

B. 5

C. 6

D. 7

Solution

1. Step 1: Compute prefix XOR matrix values

   prefix[1][1] = 5, prefix[1][2] = 7 (5^2), prefix[2][1] = 4 (5^1^0), prefix[2][2] = 0 (prefix[1][2]^prefix[2][1]^prefix[1][1]^matrix[1][1] = 7^4^5^6 = 0)

2. Step 2: Track min_heap of size k=3

   Values inserted: 5, 7, 4. The heap after these is [4,7,5]. The next value 0 is less than min_heap[0]=4, so ignored. The kth largest is min_heap[0] = 4.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Heap after all insertions has 4 as smallest among top 3 [OK]

Hint: Trace prefix XOR and heap insertions carefully [OK]

Common Mistakes:

• Off-by-one in prefix indices
• Miscomputing XOR values
• Confusing heap root with max value

4. You are given an integer array and asked to find the k elements that appear most frequently. Which of the following approaches guarantees an optimal time complexity solution for this problem?

easy

A. Use a bucket sort based on frequency counts, then iterate buckets from high to low frequency to collect top k elements.

B. Use a greedy approach that picks the most frequent element repeatedly without frequency counting.

C. Use a dynamic programming approach to build frequency tables and select top k elements.

D. Sort the entire array and then count frequencies to pick top k elements.

Solution

1. Step 1: Understand the problem constraints

   The problem requires finding the top k frequent elements efficiently, which means counting frequencies and retrieving elements by frequency.

2. Step 2: Evaluate approaches for optimality

   Sorting the entire array (A) is inefficient (O(n log n)). Dynamic programming (C) and greedy without frequency counting (B) do not apply here. Bucket sort by frequency (D) achieves O(n) time by grouping elements by frequency and iterating from highest frequency down.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Bucket sort groups elements by frequency and retrieves top k in linear time [OK]

Hint: Bucket sort by frequency is linear time [OK]

Common Mistakes:

• Sorting entire array instead of unique elements
• Using greedy without frequency counts

5. What is the time complexity of the optimal bucket sort approach for finding the top k frequent elements in an array of size n, and why?

medium

A. O(n²) because nested loops iterate over frequencies and elements.

B. O(n log n) because sorting is involved in frequency ordering.

C. O(k log n) because a heap of size k is maintained during iteration.

D. O(n) because frequency counting and bucket placement are linear, and iterating buckets is at most n.

Solution

1. Step 1: Analyze frequency counting

   Counting frequencies requires one pass over n elements -> O(n).

2. Step 2: Analyze bucket creation and iteration

   Creating buckets and placing elements is O(n) since total elements equal n. Iterating buckets from max frequency down is also O(n) in total.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   All steps combined remain linear in n [OK]

Hint: Bucket sort avoids sorting unique keys explicitly [OK]

Common Mistakes:

• Confusing with sorting complexity
• Assuming heap operations dominate