tag

#heap

41 pages tagged

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...
leetcode array heap priority-queue May 14, 2026
Practice › LeetCode › LeetCode (archived) › LeetCode 10xx ›

LeetCode 1054: Distant Barcodes

Problem Restatement We are given an array of barcodes. We need to rearrange the barcodes so that no two adjacent barcodes are equal. It is guaranteed that a valid rearrangement always exists. The official constraints state that 1 <= barcodes.length <= 10000 and 1 <= barcodes[i] <= 10000 . Input and Output Item Meaning Input Array barcodes Output Rearranged array with no two adjacent equal elements Function shape: def rearrangeBarcodes(barcodes:...
leetcode array hash-table greedy sorting heap May 14, 2026
Practice › LeetCode › LeetCode (archived) › LeetCode 10xx ›

LeetCode 1094: Car Pooling

Problem Restatement We have a car with capacity seats. We are given a list of trips: each trip [numPassengers, from, to] means numPassengers passengers board at from and alight at to . We need to return true if it is possible to pick up all passengers without exceeding capacity at any point. The official constraints state that 1 <= trips.length <= 1000 , 1 <= numPassengers <= 100 , and...
leetcode array sorting heap simulation prefix-sum May 14, 2026
Practice › LeetCode › LeetCode (archived) › LeetCode 09xx ›

LeetCode 973: K Closest Points to Origin

Problem Restatement We are given an array points , where each item is a point on the 2D plane: [x, y] We are also given an integer k . Return the k points closest to the origin: (0, 0) The distance is Euclidean distance. The answer may be returned in any order, and the answer is guaranteed to be unique except for order. The official constraints are 1 <= k...
leetcode array math sorting heap May 12, 2026
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...
leetcode greedy heap priority-queue array May 12, 2026
Practice › LeetCode › LeetCode (archived) › LeetCode 07xx ›

LeetCode 767: Reorganize String

Problem Restatement We are given a string s . We need to rearrange its characters so that no two adjacent characters are the same. Return any valid rearrangement. If no valid rearrangement exists, return an empty string. The problem allows any correct answer, not one specific output. The official statement says to rearrange the characters so adjacent characters are not equal, or return "" if impossible. Input and Output Item...
leetcode string greedy heap hash-table May 12, 2026
Practice › LeetCode › LeetCode (archived) › LeetCode 07xx ›

LeetCode 743: Network Delay Time

Problem Restatement We are given a directed weighted graph with n nodes labeled from 1 to n . The input times contains directed edges: [u, v, w] This means a signal can travel from node u to node v in w time. A signal starts from node k . We need to return the minimum time needed for all nodes to receive the signal. If some node cannot receive the...
leetcode graph heap shortest-path dijkstra May 12, 2026
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...
leetcode array heap priority-queue sorting May 12, 2026
Practice › LeetCode › LeetCode (archived) › LeetCode 06xx ›

LeetCode 692: Top K Frequent Words

Problem Restatement We are given a list of words and an integer k . We need to return the k most frequent words. The ordering rules are: Rule Meaning Higher frequency first More common words come earlier Lexicographical tie-break If two words have the same frequency, the smaller alphabetical word comes first The official statement defines lexicographical order using normal alphabetical string comparison. Input and Output Item Meaning Input words...
leetcode hash-map sorting heap string May 12, 2026
Practice › LeetCode › LeetCode (archived) › LeetCode 08xx ›

LeetCode 882: Reachable Nodes In Subdivided Graph

Problem Restatement We are given an undirected graph with original nodes numbered from 0 to n - 1 . Each edge is written as: [u, v, cnt] This means the original edge between u and v is subdivided by adding cnt new nodes between them. For example: [0, 1, 3] becomes: 0 - x1 - x2 - x3 - 1 So moving from 0 to 1 through this edge takes...
leetcode graph dijkstra shortest-path heap May 12, 2026
Practice › LeetCode › LeetCode (archived) › LeetCode 08xx ›

LeetCode 857: Minimum Cost to Hire K Workers

Problem Restatement We are given n workers. Each worker has: Data Meaning quality[i] The quality value of worker i wage[i] The minimum wage worker i must receive We need to hire exactly k workers. The payment must satisfy two rules: Every hired worker must be paid at least their minimum wage. In the hired group, pay must be proportional to quality. That means if one worker has twice the quality...
leetcode array sorting heap greedy May 12, 2026
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...
leetcode array heap priority-queue sliding-window May 12, 2026
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...
leetcode heap priority-queue design data-stream May 11, 2026
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...
leetcode graph heap priority-queue dijkstra matrix May 11, 2026
Practice › LeetCode › LeetCode (archived) › LeetCode 06xx ›

LeetCode 630: Course Schedule III

Problem Restatement We are given a list of courses. Each course is represented as: [duration, lastDay] duration is how many days the course takes. lastDay is the latest day by which the course must be finished. We start on day 1 . We can take only one course at a time. We need to return the maximum number of courses we can finish before or on their deadlines. Input and...
leetcode array greedy heap sorting May 11, 2026
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....
leetcode greedy heap priority-queue sorting May 11, 2026
Practice › LeetCode › LeetCode (archived) › LeetCode 04xx ›

LeetCode 499: The Maze III

Problem Restatement We are given a maze represented by a 2D grid. Value Meaning 0 Empty cell 1 Wall A ball starts at ball . There is also a hole at hole . The ball can roll in four directions: Letter Direction u Up d Down l Left r Right Once the ball starts rolling, it keeps moving in that direction until one of two things happens: It hits a...
leetcode graph dijkstra heap matrix shortest-path May 10, 2026
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,...
leetcode heap priority-queue array best-first-search May 10, 2026
Practice › LeetCode › LeetCode (archived) › LeetCode 03xx ›

LeetCode 347: Top K Frequent Elements

Problem Restatement We are given an integer array nums and an integer k . Return the k most frequent elements in the array. The answer may be returned in any order. The problem guarantees that the answer is unique. The constraints allow nums.length up to 10^5 , so the solution must be better than O(n^2) . Input and Output Item Meaning Input Integer array nums and integer k Output The...
leetcode array hash-table bucket-sort heap May 10, 2026
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...
leetcode heap priority-queue design data-stream May 10, 2026
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...
leetcode heap sweep-line geometry priority-queue May 10, 2026
Practice › LeetCode › LeetCode (archived) › LeetCode 02xx ›

LeetCode 215: Kth Largest Element in an Array

Problem Restatement We are given an integer array nums and an integer k . We need to return the k th largest element in the array. Important detail: this means the k th largest element in sorted order, not the k th distinct element. Duplicates count separately. The official constraints are 1 <= k <= nums.length <= 10^5 and -10^4 <= nums[i] <= 10^4 . Input and Output Item Meaning...
leetcode array heap quickselect divide-and-conquer May 10, 2026
Practice › LeetCode › LeetCode (archived) › LeetCode 03xx ›

LeetCode 313: Super Ugly Number

Problem Restatement A super ugly number is a positive integer whose prime factors all come from the array primes . We are given: n primes Return the n th super ugly number. The sequence starts with 1 . The number 1 is included even though it has no prime factors. The official statement says the n th super ugly number is guaranteed to fit in a 32-bit signed integer. The...
leetcode dynamic-programming math heap May 10, 2026
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...
leetcode heap priority-queue bfs matrix graph May 10, 2026
Practice › LeetCode › LeetCode (archived) › LeetCode 03xx ›

LeetCode 358: Rearrange String k Distance Apart

Problem Restatement We are given a non-empty lowercase string s and an integer k . We need to rearrange the characters of s so that the same characters are at least distance k from each other. If this is possible, return any valid rearranged string. If this is impossible, return an empty string "" . For example, if character a appears at index i , then the next a can...
leetcode string greedy heap queue May 10, 2026
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...
leetcode linked-list heap priority-queue divide-and-conquer May 10, 2026
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...
leetcode design hash-table heap priority-queue May 10, 2026
Practice › LeetCode › LeetCode (archived) › LeetCode 04xx ›

LeetCode 480: Sliding Window Median

Problem Restatement We are given an integer array nums and an integer k . A window of size k starts at the left side of the array and moves one step to the right each time. For every window, we need to return the median of the numbers inside that window. The median is defined like this: Window size Median Odd The middle value after sorting Even The average of...
leetcode array hash-table sliding-window heap May 10, 2026
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...
leetcode intervals heap priority-queue sorting May 10, 2026
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Kth Smallest Fraction

Kth Smallest Fraction Kth Smallest Fraction selects the k-th smallest value among fractions of the form: $$ \frac{A[i]}{A[j]} $$ where the array $A$ is sorted and: $$ 0 \le i < j < n $$ This problem appears in number theory and ranking problems. Direct enumeration gives $O(n^2)$ fractions, which is too large. Problem Given a sorted array $A$ of positive integers and an integer $k$, return the k-th smallest...
algorithms selection fractions heap binary-search
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...
algorithms data-structures heap priority-queue
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Kth Largest in Stream

Kth Largest in Stream Kth Largest in Stream maintains the k-th largest value of all values seen so far. It uses a min heap of size $k$. The heap stores the current top $k$ values. The smallest value in that heap is the k-th largest value overall. Problem Given a stream of values $$ x_1, x_2, \dots, x_n $$ support two operations: add(x): insert a new value query(): return the...
algorithms selection streaming heap
Wiki › Algorithms › 01. Searching and Sorting › 7. Divide and Conquer Sorting ›

Heapsort

Heapsort Heapsort is a comparison based sorting algorithm that uses a binary heap. It first transforms the array into a heap, then repeatedly extracts the maximum element and places it at the end of the array. It provides a strict worst case guarantee of $O(n \log n)$ and uses constant extra space. Problem Given an array $A$ of length $n$, reorder it such that: $$ A[0] \le A[1] \le \dots...
algorithms sorting heapsort heap
Wiki › Algorithms › 01. Searching and Sorting › 7. Divide and Conquer Sorting ›

Ternary Heapsort

Ternary Heapsort Ternary heapsort replaces the binary heap with a ternary heap, where each node has up to three children instead of two. This reduces the height of the heap, which can reduce the number of levels traversed during heap operations. The tradeoff is that each step may require more comparisons to select the largest child. Problem Given an array $A$ of length $n$, reorder it such that: $$ A[0]...
algorithms sorting heapsort heap
Wiki › Algorithms › 01. Searching and Sorting › 9. Partial, Online, and Adaptive Sorting ›

K Sorted Array Sort

K Sorted Array Sort K sorted array sort handles a nearly sorted array where every element is at most ( k ) positions away from its final sorted position. This stronger assumption allows a heap based method faster than general sorting. You use it when the disorder is locally bounded. Problem Given an array ( A ) of length ( n ), where each element is at most ( k...
algorithms sorting adaptive heap k-sorted-array
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Streaming Top K

Streaming Top K Streaming Top K maintains the largest $k$ elements of a data stream. The input does not need to fit in memory, and the algorithm can update the answer after each new value. The standard method keeps a min heap of size $k$. The smallest value in the heap is the current cutoff for membership in the top $k$. Problem Given a stream of values $$ x_1, x_2,...
algorithms selection streaming top-k heap
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Heap Select

Heap Select Heap Select finds an order statistic by using a heap to keep only the part of the input that can still contain the answer. For the k-th smallest element, it is common to keep a max heap of size $k + 1$. The heap stores the smallest values seen so far. Whenever a new value is smaller than the heap maximum, the maximum is removed and the new...
algorithms selection heap order-statistics
Wiki › Algorithms › 01. Searching and Sorting › 7. Divide and Conquer Sorting ›

Bottom Up Heapsort

Bottom Up Heapsort Bottom up heapsort improves the heapify operation used in heapsort. Instead of repeatedly comparing and swapping down the heap, it first follows a path to a leaf, then moves upward to place the element in its correct position. This reduces the number of comparisons and improves performance while keeping the same asymptotic complexity. Problem Given an array $A$ of length $n$, reorder it such that: $$ A[0]...
algorithms sorting heapsort heap
Wiki › Algorithms › 01. Searching and Sorting › 10. External Memory, Cache, and Database Sorting ›

Replacement Selection Run Generation

Replacement Selection Run Generation Replacement selection run generation is the first phase of an external sort. It produces sorted runs from an input stream using a heap. Unlike simple chunk sorting, which creates runs of about memory size, replacement selection often creates runs about twice as large when input order is random. Longer runs reduce the number of later merge passes. Problem Given an input stream too large for memory,...
algorithms sorting external-memory heap
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Top K by Heap

Top K by Heap Top K by Heap finds the largest or smallest $k$ elements without sorting the whole input. It keeps a heap of size $k$ and discards values that cannot belong to the final answer. For the $k$ largest elements, use a min heap. The heap root is the smallest value among the current candidates. When a new value is larger than the root, replace the root. Problem...
algorithms selection top-k heap
Wiki › Algorithms › 01. Searching and Sorting › 9. Partial, Online, and Adaptive Sorting ›

Min Heap K Sorted Sort

Min Heap K Sorted Sort Min heap k sorted sort is the canonical heap based method for sorting a k sorted array. It maintains a sliding window of size ( k + 1 ) in a min heap and repeatedly extracts the next smallest element. This is the standard optimal solution for k sorted input. Problem Given an array ( A ) where each element is at most ( k...
algorithms sorting heap k-sorted-array