Dashboard
LC #23

Merge k Sorted Lists

Pattern · ?AmazonMetaGoogleMicrosoftBloomberg

Problem

Merge k sorted linked lists into one sorted linked list.

Constraints

  • 0 ≤ lists.length ≤ 10⁴
  • 0 ≤ lists[i].length ≤ 500
  • -10⁴ ≤ lists[i][j] ≤ 10⁴
  • Total nodes ≤ 10⁴

Example

Input
lists = [[1,4,5],[1,3,4],[2,6]]
Output
[1,1,2,3,4,4,5,6]
Why
Merge all 3 sorted linked lists using a min-heap to always pick the smallest next node

Spot the pattern

Which pattern cracks it?

Hints

One at a time
Solve on LeetCode ↗