# Golang solution using priority queue

• First, fetch all `0` th elements of each array in matrix and initialize priority queue, whose priority is a value in matrix.
Then we can run `heap.Pop` one by one. And after every call of `Pop`, if popped element is `matrix[i][j]` add `matrix[i][j+1]` to the priority queue. By doing so, we can ensure always `[elements in priority queue] < [elements remaining in matrix]`,
therefore `k` th popped element is what we want.

``````func kthSmallest(matrix [][]int, k int) int {
mlen, nlen := len(matrix), len(matrix[0])
var pq Elems
for i := 0; i < mlen; i++ {
pq = append(pq, Elem{m: i, n: 0, val: matrix[i][0]})
}

heap.Init(&pq)
var res int
for i := 0; i < k; i++ {
e, _ := heap.Pop(&pq).(Elem)
if e.n < nlen-1 {
heap.Push(&pq, Elem{m: e.m, n: e.n + 1, val: matrix[e.m][e.n+1]})
}
res = e.val
}
return res
}

// Below code is Golang boiler plate to suffice priority queue interface.
// Refer https://golang.org/pkg/container/heap/
type Elem struct {
m   int
n   int
val int
}

type Elems []Elem

func (pq Elems) Swap(i, j int) {
pq[i], pq[j] = pq[j], pq[i]
}

func (pq Elems) Len() int {
return len(pq)
}

func (pq Elems) Less(i, j int) bool {
return pq[i].val < pq[j].val
}

func (pq *Elems) Pop() interface{} {
vpq := *pq
x := vpq[len(vpq)-1]
*pq = vpq[:len(vpq)-1]
return x
}

func (pq *Elems) Push(num interface{}) {
numElm, _ := num.(Elem)
*pq = append(*pq, numElm)
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.