---
# System prepended metadata

title: '20211207'

---

# 20211207

## Question

Find the kth smallest number in a row and column sorted matrix.


```cpp=
int kthSmallest(vector<vector<int>> &matrix, int k) {
    
}
```

```python=
def kthSmallest(matrix, k): # matrix [[], []]
    h = len(matrix)
    w = len(matrix[0])
    
    value = 0
    
    idx = [0] * len(matrix)
    
    sorted_list = []
    for k_idx in range(k):
        
        cur_list = []
        for i in range(h):
            if idx[i] < w:
                cur_list.append(matrix[i][idx[i]])
            
        min_value = min(cur_list)
        min_row = cur_list.index(min_value)
        
        idx[min_row] += 1
        
        sorted_list.append(min_value)
            
    return sorted_list[-1]
    
```

example:

0 5 7
0 6 7
3 8 10

k = 4
return 5;

res [0, 0, 3] 

idx[0] 1 -> 5
idx[1] 1 -> 6
idx[2] 0 -> 3

Complexity Discssion

N = H x W 
H = height
W = width

1) sort vector of size (N) - N log N = HW log (HW)

2) exploit that it is already sorted per row - H x W x O (H) = N x O(N)

3): 2) + priority queue: - H x W x O(logH) = N x O(N)

3): 2) + priority queue: - O(k) x O(logH)
