3534. Path Existence Queries in a Graph II

HardArrayTwo PointersBinary SearchDynamic ProgrammingGreedyBit ManipulationGraphSorting

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given n nodes, labeled from 0 to n - 1, together with an integer array nums of length n and an integer maxDiff.

These inputs define an undirected, unweighted graph implicitly: nodes i and j are joined by an edge exactly when their values differ by at most maxDiff, that is, when |nums[i] - nums[j]| <= maxDiff.

You are also given a 2D integer array queries, where each query queries[i] = [ui, vi] names two nodes. For each query, determine the minimum number of edges on a path between ui and vi. If the two nodes cannot reach each other at all, the answer for that query is -1.

Return an integer array answer where answer[i] is the result of the i-th query.

Example 1:

Input: n = 5, nums = [1, 8, 3, 4, 2], maxDiff = 3, queries = [[0, 3], [2, 4]] Output: [1, 1]

Nodes 0 and 3 carry the values 1 and 4. Their difference is exactly 3, so a direct edge joins them and the distance is 1. Nodes 2 and 4 carry the values 3 and 2, which differ by 1, so they are also adjacent and the distance is again 1.

Example 2:

Input: n = 5, nums = [5, 3, 1, 9, 10], maxDiff = 2, queries = [[0, 1], [0, 2], [2, 3], [4, 3]] Output: [1, 2, -1, 1]

Nodes 0 and 1 (values 5 and 3) differ by 2, so one edge suffices. Nodes 0 and 2 (values 5 and 1) differ by 4, which is too far for a direct edge, but the path 0 → 1 → 2 works because each step changes the value by exactly 2; the distance is 2. Node 2 (value 1) can never reach node 3 (value 9): no chain of edges crosses the gap between the values 5 and 9, so the answer is -1. Nodes 4 and 3 (values 10 and 9) are adjacent, giving 1.

Example 3:

Input: n = 3, nums = [3, 6, 1], maxDiff = 1, queries = [[0, 0], [0, 1], [1, 2]] Output: [0, -1, -1]

Every pair of distinct values differs by more than 1, so the graph contains no edges at all. A node reaches itself with 0 edges, and both remaining queries return -1.

Constraints:

1 <= n == nums.length <= 10^5
0 <= nums[i] <= 10^5
0 <= maxDiff <= 10^5
1 <= queries.length <= 10^5
queries[i] == [ui, vi]
0 <= ui, vi < n

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Greedy Algorithms?

This problem maps to Greedy Algorithms through a short path in the full flowchart.

Each query asks for a minimum hop count; after sorting by value, always jumping to the farthest reachable position is the optimal move, and binary lifting batches those greedy jumps so every query runs in logarithmic time.

Open in Flowchart

Intuition

The direct approach — build the adjacency lists and run a BFS for every query — collapses under the constraints. If many values sit close together (for instance, all values equal), every pair of nodes is adjacent and the graph holds about n²/2 edges. With n and the number of queries both up to 10^5, we can neither store that graph nor afford a full traversal per query.

The structure worth noticing is that node labels are irrelevant; only values matter. Sort the values. In sorted order, the nodes a given node can reach in one hop form one contiguous block: from the node at sorted position r, every position whose value lies within maxDiff of vals[r] is a neighbor, and those positions sit consecutively around r. So the graph is really a line of sorted values where each position can jump anywhere inside its block.

Now consider a query. Map both endpoints to their sorted positions and call the left one a and the right one b. Walking toward smaller values never helps, because reach grows with value: if position p sits left of position p', then the farthest position reachable from p is no farther right than the one reachable from p'. Stepping backward can only shrink (never extend) how far right the next hop lands, so some shortest path moves monotonically to the right.

Once the walk is one-directional, minimizing hops becomes the same problem as Jump Game II: from the current position, the best move is to jump to the farthest position reachable in one hop. An exchange argument shows why this greedy walk is optimal. Take any shortest path and compare it hop by hop with the greedy walk: after the first hop, the greedy walker stands at least as far right as the path does, and because farther-right positions reach at least as far, this lead is preserved after every subsequent hop. The greedy walk therefore never needs more hops than the optimal path — it is optimal.

One greedy walk can still take up to n hops, which is too slow for 10^5 queries. The fix is binary lifting: precompute up[k][r], the position reached from r after 2^k greedy hops, by doubling (up[k][r] = up[k-1][up[k-1][r]]). To answer a query, take the largest jumps that keep the walker strictly left of b, accumulate their hop counts, and finish with one final hop. If even that final hop cannot reach b's position, the two nodes lie in different connected components and the answer is -1. Each query then costs O(log n).

Pattern Learn more about Greedy, Binary Search and Graph patterns.

Solution Approach

Step 1: Sort nodes by value

Sort the node indices by their values. Keep three arrays: order[r] (which original node sits at sorted position r), rank[i] (the sorted position of original node i), and vals[r] = nums[order[r]] (the values in non-decreasing order). All later work happens on sorted positions; rank translates each query's node labels into that coordinate system.

Step 2: Compute the farthest one-hop reach

For every sorted position r, find far[r], the largest position j with vals[j] - vals[r] <= maxDiff. This is the farthest position reachable from r in a single hop when moving right. Because vals is sorted, the threshold vals[r] + maxDiff only grows as r grows, so a two-pointer sweep computes the whole array in O(n): advance j while vals[j + 1] - vals[r] <= maxDiff, and never move it back. (A binary search per position works equally well at O(n log n).) Note that far[r] >= r always holds, since a value is within maxDiff of itself.

Step 3: Build the binary lifting table

Let LOG be the smallest number of doublings that covers n positions. Define up[0] = far and fill

up[k][r] = up[k - 1][up[k - 1][r]]

so that up[k][r] is the position reached from r after 2^k greedy hops. The table has O(n log n) entries and each entry is filled in constant time. If a position cannot move (far[r] == r), every level maps it to itself, which is exactly the behavior the query phase relies on to detect dead ends.

Step 4: Answer each query

For a query (u, v):

If u == v, the distance is 0.
Otherwise set a = min(rank[u], rank[v]) and b = max(rank[u], rank[v]).
If far[a] >= b, one hop suffices; the answer is 1.
Otherwise walk cur from a using the table, from the highest level down: whenever up[k][cur] < b, take that jump (cur = up[k][cur]) and add 2^k to the hop count. This leaves cur at the farthest position reachable with some number of hops that is still strictly left of b.
Take one final hop: if far[cur] >= b, the answer is the accumulated count plus one. If not, the walk is stuck before b — the two nodes are in different components — and the answer is -1.

The descent works because after processing level k, the remaining distance to b needs fewer than 2^k additional hops of that size; choosing greedily from the top level down reproduces exactly the hop count of the plain greedy walk, just in O(log n) table lookups instead of one lookup per hop.

Complexity Analysis:

Time complexity: O((n + q) log n), where q is the number of queries — sorting costs O(n log n), the far array O(n), the lifting table O(n log n), and each query O(log n).
Space complexity: O(n log n) for the lifting table, plus O(n) for the sorted arrays.

Example Walkthrough

Take Example 2: n = 5, nums = [5, 3, 1, 9, 10], maxDiff = 2, queries = [[0, 1], [0, 2], [2, 3], [4, 3]].

Setup: sort by value

Sorting the nodes by value gives:

Sorted position `r`	0	1	2	3	4
Original node	2	1	0	3	4
`vals[r]`	1	3	5	9	10

So rank = [2, 1, 0, 3, 4] (node 0 sits at sorted position 2, node 1 at position 1, and so on).

Farthest one-hop reach

With maxDiff = 2, the two-pointer sweep produces:

`r`	`vals[r]`	Largest value allowed (`vals[r] + 2`)	`far[r]`
0	1	3	1
1	3	5	2
2	5	7	2
3	9	11	4
4	10	12	4

Position 2 (value 5) cannot move at all — the next value, 9, is out of range — so far[2] = 2. That frozen entry is how the algorithm will detect the broken component.

Binary lifting table

With n = 5 we need LOG = 3 levels:

up[0] = far = [1, 2, 2, 4, 4]
up[1][r] = up[0][up[0][r]] = [2, 2, 2, 4, 4]
up[2][r] = up[1][up[1][r]] = [2, 2, 2, 4, 4]

Query `[0, 1]` — answer `1`

Ranks are 2 and 1, so a = 1, b = 2. Since far[1] = 2 >= 2, one hop reaches the target. Answer: 1.

Query `[0, 2]` — answer `2`

Ranks are 2 and 0, so a = 0, b = 2. far[0] = 1 < 2, so we descend the table with cur = 0, steps = 0:

k = 2: up[2][0] = 2, not strictly left of b = 2 — skip.
k = 1: up[1][0] = 2 — skip.
k = 0: up[0][0] = 1 < 2 — jump. Now cur = 1, steps = 1.

Final hop: far[1] = 2 >= 2, so the answer is steps + 1 = 2. This matches the path 0 → 1 → 2 in original labels (values 5 → 3 → 1).

Query `[2, 3]` — answer `-1`

Ranks are 0 and 3, so a = 0, b = 3. far[0] = 1 < 3. During the descent the walker reaches position 2 (value 5) and then stops moving: up[k][2] = 2 at every level, because far[2] = 2. After the descent cur = 2, and the final check far[2] = 2 >= 3 fails. The walk is stuck strictly left of b, so nodes 2 and 3 lie in different components. Answer: -1. (Whatever hop count accumulated during the descent is discarded on this branch.)

Query `[4, 3]` — answer `1`

Ranks are 4 and 3, so a = 3, b = 4. far[3] = 4 >= 4, so the nodes are adjacent. Answer: 1.

Final output: [1, 2, -1, 1], matching the expected result.

Solution Implementation

1from typing import List
2
3
4class Solution:
5    def pathExistenceQueries(
6        self, n: int, nums: List[int], maxDiff: int, queries: List[List[int]]
7    ) -> List[int]:
8        # Sort node indices by value. rank[i] = sorted position of node i,
9        # vals[r] = value at sorted position r.
10        order = sorted(range(n), key=lambda i: nums[i])
11        rank = [0] * n
12        for r, i in enumerate(order):
13            rank[i] = r
14        vals = [nums[i] for i in order]
15
16        # far[r] = farthest sorted position reachable from r in one hop.
17        # Both pointers only move right, so this pass is O(n).
18        far = [0] * n
19        j = 0
20        for r in range(n):
21            if j < r:
22                j = r
23            while j + 1 < n and vals[j + 1] - vals[r] <= maxDiff:
24                j += 1
25            far[r] = j
26
27        # Binary lifting table: up[k][r] = position after 2^k greedy hops.
28        LOG = max(1, (n - 1).bit_length())
29        up = [far]
30        for k in range(1, LOG):
31            prev = up[k - 1]
32            up.append([prev[prev[r]] for r in range(n)])
33
34        ans = []
35        for u, v in queries:
36            if u == v:
37                # A node reaches itself with zero edges.
38                ans.append(0)
39                continue
40            # Work on sorted positions; always walk left to right.
41            a, b = rank[u], rank[v]
42            if a > b:
43                a, b = b, a
44            if far[a] >= b:
45                # The target block is reachable in a single hop.
46                ans.append(1)
47                continue
48            # Take the largest jumps that still land strictly left of b.
49            steps = 0
50            cur = a
51            for k in range(LOG - 1, -1, -1):
52                nxt = up[k][cur]
53                if nxt < b:
54                    steps += 1 << k
55                    cur = nxt
56            # One final hop either reaches b or the walk is stuck.
57            if far[cur] >= b:
58                ans.append(steps + 1)
59            else:
60                ans.append(-1)
61        return ans
62

1class Solution {
2    /**
3     * Answers each query with the minimum number of edges between two nodes,
4     * where an edge joins nodes whose values differ by at most maxDiff.
5     *
6     * @param n       number of nodes
7     * @param nums    value assigned to each node
8     * @param maxDiff maximum allowed value difference for an edge
9     * @param queries pairs of nodes to measure the distance between
10     * @return minimum hop counts, or -1 where no path exists
11     */
12    public int[] pathExistenceQueries(int n, int[] nums, int maxDiff, int[][] queries) {
13        // Sort node indices by value. rank[i] = sorted position of node i,
14        // vals[r] = value at sorted position r.
15        Integer[] order = new Integer[n];
16        for (int i = 0; i < n; i++) {
17            order[i] = i;
18        }
19        Arrays.sort(order, (x, y) -> nums[x] - nums[y]);
20        int[] rank = new int[n];
21        int[] vals = new int[n];
22        for (int r = 0; r < n; r++) {
23            rank[order[r]] = r;
24            vals[r] = nums[order[r]];
25        }
26
27        // far[r] = farthest sorted position reachable from r in one hop.
28        // Both pointers only move right, so this pass is O(n).
29        int[] far = new int[n];
30        int j = 0;
31        for (int r = 0; r < n; r++) {
32            if (j < r) {
33                j = r;
34            }
35            while (j + 1 < n && vals[j + 1] - vals[r] <= maxDiff) {
36                j++;
37            }
38            far[r] = j;
39        }
40
41        // Binary lifting table: up[k][r] = position after 2^k greedy hops.
42        int log = 1;
43        while ((1 << log) < n) {
44            log++;
45        }
46        int[][] up = new int[log][];
47        up[0] = far;
48        for (int k = 1; k < log; k++) {
49            up[k] = new int[n];
50            for (int r = 0; r < n; r++) {
51                up[k][r] = up[k - 1][up[k - 1][r]];
52            }
53        }
54
55        int m = queries.length;
56        int[] ans = new int[m];
57        for (int i = 0; i < m; i++) {
58            int u = queries[i][0];
59            int v = queries[i][1];
60            if (u == v) {
61                // A node reaches itself with zero edges.
62                ans[i] = 0;
63                continue;
64            }
65            // Work on sorted positions; always walk left to right.
66            int a = Math.min(rank[u], rank[v]);
67            int b = Math.max(rank[u], rank[v]);
68            if (far[a] >= b) {
69                // The target position is reachable in a single hop.
70                ans[i] = 1;
71                continue;
72            }
73            // Take the largest jumps that still land strictly left of b.
74            int steps = 0;
75            int cur = a;
76            for (int k = log - 1; k >= 0; k--) {
77                int next = up[k][cur];
78                if (next < b) {
79                    steps += 1 << k;
80                    cur = next;
81                }
82            }
83            // One final hop either reaches b or the walk is stuck.
84            ans[i] = far[cur] >= b ? steps + 1 : -1;
85        }
86        return ans;
87    }
88}
89

1class Solution {
2public:
3    vector<int> pathExistenceQueries(int n, vector<int>& nums, int maxDiff,
4                                     vector<vector<int>>& queries) {
5        // Sort node indices by value. rank_[i] = sorted position of node i,
6        // vals[r] = value at sorted position r.
7        vector<int> order(n);
8        iota(order.begin(), order.end(), 0);
9        sort(order.begin(), order.end(),
10             [&](int x, int y) { return nums[x] < nums[y]; });
11        vector<int> rank_(n), vals(n);
12        for (int r = 0; r < n; ++r) {
13            rank_[order[r]] = r;
14            vals[r] = nums[order[r]];
15        }
16
17        // far[r] = farthest sorted position reachable from r in one hop.
18        // Both pointers only move right, so this pass is O(n).
19        vector<int> far(n);
20        int j = 0;
21        for (int r = 0; r < n; ++r) {
22            if (j < r) {
23                j = r;
24            }
25            while (j + 1 < n && vals[j + 1] - vals[r] <= maxDiff) {
26                ++j;
27            }
28            far[r] = j;
29        }
30
31        // Binary lifting table: up[k][r] = position after 2^k greedy hops.
32        int log2n = 1;
33        while ((1 << log2n) < n) {
34            ++log2n;
35        }
36        vector<vector<int>> up(log2n, vector<int>(n));
37        up[0] = far;
38        for (int k = 1; k < log2n; ++k) {
39            for (int r = 0; r < n; ++r) {
40                up[k][r] = up[k - 1][up[k - 1][r]];
41            }
42        }
43
44        vector<int> ans;
45        ans.reserve(queries.size());
46        for (auto& q : queries) {
47            int u = q[0], v = q[1];
48            if (u == v) {
49                // A node reaches itself with zero edges.
50                ans.push_back(0);
51                continue;
52            }
53            // Work on sorted positions; always walk left to right.
54            int a = min(rank_[u], rank_[v]);
55            int b = max(rank_[u], rank_[v]);
56            if (far[a] >= b) {
57                // The target position is reachable in a single hop.
58                ans.push_back(1);
59                continue;
60            }
61            // Take the largest jumps that still land strictly left of b.
62            int steps = 0;
63            int cur = a;
64            for (int k = log2n - 1; k >= 0; --k) {
65                int next = up[k][cur];
66                if (next < b) {
67                    steps += 1 << k;
68                    cur = next;
69                }
70            }
71            // One final hop either reaches b or the walk is stuck.
72            ans.push_back(far[cur] >= b ? steps + 1 : -1);
73        }
74        return ans;
75    }
76};
77

1/**
2 * Answers each query with the minimum number of edges between two nodes,
3 * where an edge joins nodes whose values differ by at most maxDiff.
4 *
5 * @param n - number of nodes
6 * @param nums - value assigned to each node
7 * @param maxDiff - maximum allowed value difference for an edge
8 * @param queries - pairs of nodes to measure the distance between
9 * @returns minimum hop counts, or -1 where no path exists
10 */
11function pathExistenceQueries(
12    n: number,
13    nums: number[],
14    maxDiff: number,
15    queries: number[][],
16): number[] {
17    // Sort node indices by value. rank[i] = sorted position of node i,
18    // vals[r] = value at sorted position r.
19    const order: number[] = Array.from({ length: n }, (_, i) => i);
20    order.sort((x, y) => nums[x] - nums[y]);
21    const rank: number[] = new Array(n);
22    const vals: number[] = new Array(n);
23    for (let r = 0; r < n; r++) {
24        rank[order[r]] = r;
25        vals[r] = nums[order[r]];
26    }
27
28    // far[r] = farthest sorted position reachable from r in one hop.
29    // Both pointers only move right, so this pass is O(n).
30    const far: number[] = new Array(n);
31    let j = 0;
32    for (let r = 0; r < n; r++) {
33        if (j < r) {
34            j = r;
35        }
36        while (j + 1 < n && vals[j + 1] - vals[r] <= maxDiff) {
37            j++;
38        }
39        far[r] = j;
40    }
41
42    // Binary lifting table: up[k][r] = position after 2^k greedy hops.
43    let log = 1;
44    while (1 << log < n) {
45        log++;
46    }
47    const up: number[][] = [far];
48    for (let k = 1; k < log; k++) {
49        const prev = up[k - 1];
50        const cur: number[] = new Array(n);
51        for (let r = 0; r < n; r++) {
52            cur[r] = prev[prev[r]];
53        }
54        up.push(cur);
55    }
56
57    const ans: number[] = [];
58    for (const [u, v] of queries) {
59        if (u === v) {
60            // A node reaches itself with zero edges.
61            ans.push(0);
62            continue;
63        }
64        // Work on sorted positions; always walk left to right.
65        const a = Math.min(rank[u], rank[v]);
66        const b = Math.max(rank[u], rank[v]);
67        if (far[a] >= b) {
68            // The target position is reachable in a single hop.
69            ans.push(1);
70            continue;
71        }
72        // Take the largest jumps that still land strictly left of b.
73        let steps = 0;
74        let cur = a;
75        for (let k = log - 1; k >= 0; k--) {
76            const next = up[k][cur];
77            if (next < b) {
78                steps += 1 << k;
79                cur = next;
80            }
81        }
82        // One final hop either reaches b or the walk is stuck.
83        ans.push(far[cur] >= b ? steps + 1 : -1);
84    }
85    return ans;
86}
87

Time and Space Complexity

Time Complexity: O((n + q) log n)

Let n be the number of nodes and q the number of queries. The work splits into four phases:

Sorting: Ordering the node indices by value costs O(n log n).
Farthest reach: The two-pointer sweep that fills far moves each pointer at most n times in total, so it costs O(n).
Lifting table: The table has LOG = O(log n) levels of n entries each, and every entry is a single array lookup of the previous level, giving O(n log n).
Queries: Each query performs at most one table lookup per level plus a constant amount of extra work, so it costs O(log n), and all queries together cost O(q log n).

Adding the phases gives O(n log n + q log n) = O((n + q) log n).

Space Complexity: O(n log n)

The dominant structure is the binary lifting table with O(log n) rows of n integers each. The auxiliary arrays order, rank, vals, and far each hold n integers, adding O(n). The output array is O(q) and is usually not counted as auxiliary space.

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Building the graph and running BFS per query

The edge rule looks like an invitation to materialize an adjacency list and answer each query with a breadth-first search. That approach fails on size alone. If all values are equal (say nums = [7, 7, ..., 7] with any maxDiff >= 0), every pair of nodes is adjacent and the graph holds n(n-1)/2 edges — about 5 × 10^9 for n = 10^5, which does not fit in memory. Even with a sparser graph, one BFS costs O(n + edges) and 10^5 queries multiply that into a timeout.

Solution: Never build the edges. Sort the values and represent one hop as "move to any position whose value is within maxDiff," which reduces each query to jumping along a line.

Pitfall 2: Skipping the `u == v` check or mixing up labels and ranks

Two bookkeeping mistakes produce wrong answers on valid inputs:

Same-node queries. After mapping to sorted positions, the query logic sets a = b when u == v, and the one-hop test far[a] >= b is then always true, returning 1 instead of 0. Example 3 contains exactly this trap: query [0, 0] must return 0. Handle u == v before anything else.
Original labels vs. sorted positions. The arrays far and up are indexed by sorted position, but queries arrive as original node labels. Using u and v directly (without rank) happens to work on inputs where nums is already sorted — which is how Path Existence Queries in a Graph I presents its data — and silently breaks on this problem's unsorted nums. Always translate through rank first.

if u == v:
    ans.append(0)          # zero edges, not one
    continue
a, b = rank[u], rank[v]    # sorted positions, not labels

Pitfall 3: Wrong boundary in the binary lifting descent

The descent must jump only while the walker stays strictly left of the target position b, and then add one final hop:

if nxt < b:          # correct: stay strictly left of b
    steps += 1 << k
    cur = nxt

Using nxt <= b overcounts. Suppose the greedy walk needs exactly two hops and up[1][a] == b: the <= version jumps straight onto b (recording 2 hops), then the final-hop check far[b] >= b still succeeds and returns 3.

A related mistake is replacing the descent with a plain loop such as while cur < b: cur = far[cur] without checking for progress. When the two nodes are disconnected, the walker reaches a position with far[cur] == cur and the loop never terminates — Example 2's query [2, 3] hangs exactly this way, since far freezes at the position holding value 5. The table-descent structure avoids both problems: jumps that do not move the walker change nothing, and the final far[cur] >= b test cleanly separates "one more hop reaches the target" from "stuck, return -1."

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10]

[100, 33, 30]

[10, 12, 20]

I don't know

Core Learning

LLD/OOP Interview

Live Training

Additional Resources

AI Engineering