Algoschool

Explore

Level 1

Heap problems

⁠

https://leetcode.com/problems/merge-k-sorted-lists⁠

⁠

import heapq

# Definition for singly-linked list.

# class ListNode:

# def __init__(self, val=0, next=None):

# self.val = val

# self.next = next

class Solution:

def mergeKLists(self, lists: List[ListNode]) -> ListNode:

if not lists:

return None

h = []

for i, l in enumerate(lists):

if l:

heapq.heappush(h, (l.val, i, l))

dummy = ListNode()

head = dummy

while h:

minEl, i, l = heapq.heappop(h)

dummy.next = ListNode(minEl)

dummy = dummy.next

l = l.next

if l:

heapq.heappush(h, (l.val, i, l))

return head.next

⁠

https://leetcode.com/problems/top-k-frequent-elements/⁠

⁠

import heapq

from collections import Counter

class Solution:

def topKFrequent(self, nums: List[int], k: int) -> List[int]:

c = Counter(nums)

h = [] # k

for val, c in c.items(): # n

heapq.heappush(h, (c, val)) # log k

if len(h) > k:

heapq.heappop(h)

return [x[1] for x in h]

⁠

https://leetcode.com/problems/k-closest-points-to-origin/⁠

⁠

import heapq

import math

class Solution:

def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:

h = [] # k

for point in points:

dist = math.sqrt(point[0] ** 2 + point[1] ** 2)

heapq.heappush(h, (-dist, point))

if len(h) > k:

heapq.heappop(h)

return [x[1] for x in h]

Want to print your doc?
This is not the way.

Try clicking the ⋯ next to your doc name or using a keyboard shortcut (

CtrlP

) instead.