priority-queue

Practice › LeetCode › LeetCode (archived) › LeetCode 10xx ›

LeetCode 1046: Last Stone Weight

Problem Restatement We have a collection of stones, each with a positive weight. In each round, we smash the two heaviest stones together: If equal: both are destroyed. If not equal: the lighter is destroyed and the heavier remains with weight heavier - lighter . We repeat until at most one stone is left. Return the weight of the last stone, or 0 if none remain. The official constraints state...

Practice › LeetCode › LeetCode (archived) › LeetCode 08xx ›

LeetCode 871: Minimum Number of Refueling Stops

Problem Restatement A car starts at position 0 and needs to reach a destination target miles away. The car starts with startFuel liters of fuel. It consumes: 1 liter of fuel per mile There are gas stations along the way. Each station is represented as: [position, fuel] When the car reaches a station, it may stop and take all fuel from that station. The tank has infinite capacity. Return the...

Practice › LeetCode › LeetCode (archived) › LeetCode 07xx ›

LeetCode 786: K-th Smallest Prime Fraction

Problem Restatement We are given a sorted array arr . The array contains 1 and some prime numbers. All values are unique. For every pair of indices i and j where: 0 <= i < j < len(arr) we form the fraction: arr[i] / arr[j] Return the k -th smallest fraction. The answer should be returned as: [numerator, denominator] Input and Output Item Meaning Input A sorted array arr and...

Practice › LeetCode › LeetCode (archived) › LeetCode 06xx ›

LeetCode 632: Smallest Range Covering Elements from K Lists

Problem Restatement We are given k sorted lists of integers. We need to find the smallest range [a, b] such that the range contains at least one number from every list. A number x is inside the range [a, b] if: a <= x <= b A range [a, b] is smaller than another range [c, d] if: b - a < d - c If both ranges have the...

Practice › LeetCode › LeetCode (archived) › LeetCode 07xx ›

LeetCode 703: Kth Largest Element in a Stream

Problem Restatement We need to design a class called KthLargest . The class receives: k nums nums is the initial stream of integers. After that, the class supports an operation: add(val) This adds val to the stream and returns the kth largest element among all numbers seen so far. The kth largest element means the element at position k if all numbers are sorted from largest to smallest. Duplicates count...

Practice › LeetCode › LeetCode (archived) › LeetCode 07xx ›

LeetCode 778: Swim in Rising Water

Problem Restatement We are given an n x n grid. Each cell grid[i][j] is the elevation of that square. Rain starts falling. At time t , the water level is also t . We can swim from one cell to a 4-directionally adjacent cell only if both cells have elevation at most t . We start at the top-left cell: (0, 0) We want to reach the bottom-right cell: (n...

Practice › LeetCode › LeetCode (archived) › LeetCode 05xx ›

LeetCode 502: IPO

Problem Restatement We are given n projects. Each project has: Array Meaning profits[i] The pure profit gained after finishing project i capital[i] The minimum capital needed to start project i We start with capital w . We can finish at most k distinct projects. After finishing a project, its profit is added to our capital. We need to return the maximum final capital possible after choosing at most k projects....

Practice › LeetCode › LeetCode (archived) › LeetCode 03xx ›

LeetCode 373: Find K Pairs with Smallest Sums

Problem Restatement We are given two sorted integer arrays: nums1 nums2 We define a pair: (u, v) where: Value Comes from u nums1 v nums2 The pair sum is: u + v We need to return the k pairs with the smallest sums. The arrays are already sorted in ascending order. The official example is: nums1 = [1, 7, 11] nums2 = [2, 4, 6] k = 3 Output: [[1,...

Practice › LeetCode › LeetCode (archived) › LeetCode 02xx ›

LeetCode 295: Find Median from Data Stream

Problem Restatement We need to design a class called MedianFinder . It supports two operations: addNum(num) findMedian() addNum(num) adds one integer from the data stream. findMedian() returns the median of all numbers added so far. The median is the middle value in a sorted list. If the list has an even number of values, the median is the average of the two middle values. The answer is accepted if it...

Practice › LeetCode › LeetCode (archived) › LeetCode 02xx ›

LeetCode 218: The Skyline Problem

Problem Restatement We are given a list of buildings. Each building is represented as: [left, right, height] Meaning: Field Meaning left Left x-coordinate right Right x-coordinate height Building height We need to return the skyline formed by these buildings. The skyline is represented as a list of key points: [x, height] Each key point means: at x-coordinate x, the skyline height changes to height The last point must end with...

Practice › LeetCode › LeetCode (archived) › LeetCode 04xx ›

LeetCode 407: Trapping Rain Water II

Problem Restatement We are given an m x n matrix called heightMap . Each cell represents the height of one unit block in a 2D elevation map. After rain, water may be trapped in lower cells if surrounding boundaries prevent it from flowing out. Return the total amount of trapped water. Water can move through the four main directions: up, down, left, right Diagonal movement does not matter. Boundary cells...

Practice › LeetCode › LeetCode (archived) › LeetCode 00xx ›

LeetCode 23: Merge k Sorted Lists

Problem Restatement We are given an array of linked lists: lists Each linked list is sorted in ascending order. We need to merge all linked lists into one sorted linked list and return its head. The constraints say: Constraint Value k == lists.length Number of linked lists 0 <= k <= 10^4 Number of lists 0 <= lists[i].length <= 500 Length of each list Total nodes across all lists At...

Practice › LeetCode › LeetCode (archived) › LeetCode 03xx ›

LeetCode 355: Design Twitter

Problem Restatement We need to design a simplified Twitter system. The system supports four operations: Method Meaning postTweet(userId, tweetId) User userId posts a tweet with ID tweetId getNewsFeed(userId) Return up to 10 most recent tweet IDs visible to userId follow(followerId, followeeId) followerId starts following followeeId unfollow(followerId, followeeId) followerId stops following followeeId A user's news feed contains: Tweets posted by the user themself. Tweets posted by users they follow. The feed...

Practice › LeetCode › LeetCode (archived) › LeetCode 02xx ›

LeetCode 253: Meeting Rooms II

Problem Restatement We are given a list of meeting intervals. Each interval is: [start, end] A meeting room can host only one meeting at a time. We need to determine the minimum number of meeting rooms required so that all meetings can happen without overlap. Input and Output Item Meaning Input A list of meeting intervals Output Minimum number of rooms required Interval [start, end] Goal Schedule all meetings without...

Wiki › Algorithms › 02. Data Structures › 1. Core Data Structures and Operations ›

1.5 Heaps and Priority Queues

1.5 Heaps and priority queues, 55 index slug name 1 binary-heap Binary Heap 2 min-heap Min Heap 3 max-heap Max Heap 4 heap-insert Heap Insert 5 heap-extract-min Extract Minimum 6 heap-extract-max Extract Maximum 7 heap-peek Heap Peek 8 heap-sift-up Sift Up 9 heap-sift-down Sift Down 10 heapify Heapify 11 bottom-up-heap-construction Bottom-Up Heap Construction 12 top-down-heap-construction Top-Down Heap Construction 13 heap-replace Heap Replace 14 heap-push-pop Heap Push Pop 15 heap-decrease-key Decrease...

#priority-queue

LeetCode 1046: Last Stone Weight

LeetCode 871: Minimum Number of Refueling Stops

LeetCode 786: K-th Smallest Prime Fraction

LeetCode 632: Smallest Range Covering Elements from K Lists

LeetCode 703: Kth Largest Element in a Stream

LeetCode 778: Swim in Rising Water

LeetCode 502: IPO

LeetCode 373: Find K Pairs with Smallest Sums

LeetCode 295: Find Median from Data Stream

LeetCode 218: The Skyline Problem

LeetCode 407: Trapping Rain Water II

LeetCode 23: Merge k Sorted Lists

LeetCode 355: Design Twitter

LeetCode 253: Meeting Rooms II

1.5 Heaps and Priority Queues