3844. Longest Almost-Palindromic Substring

MediumTwo PointersStringDynamic Programming

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given a string s consisting of lowercase English letters.

A substring is a contiguous, non-empty sequence of characters within the string. A substring is called almost-palindromic if it becomes a palindrome after removing exactly one character from it.

A palindrome is a string that reads the same forwards and backwards.

Your task is to return an integer denoting the length of the longest almost-palindromic substring in s.

In other words, you need to find the longest contiguous substring of s such that, by deleting exactly one character from it, the remaining characters form a palindrome. The answer is the length of that original substring (before the deletion).

Example walkthrough:

Consider the substring "aba" plus an extra character, like "abca". By removing the character c, we get "aba", which is a palindrome. So "abca" is almost-palindromic with length 4.
For a substring like "abba", which is already a palindrome of even length, removing exactly one character (for instance, removing one b to get "aba") still results in a palindrome. So it qualifies as almost-palindromic as well.

You must consider every possible substring of s, check whether it can be turned into a palindrome by deleting exactly one character, and return the maximum length among all such valid substrings.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Two pointers?

This problem maps to Two pointers through a short path in the full flowchart.

Center-expansion with two pointers finds the longest almost-palindromic substring.

Open in Flowchart

Intuition

When we think about finding palindromes inside a string, a very natural idea is to enumerate the center of the palindrome and then expand outward. Every palindrome has a center: if its length is odd, the center is a single character; if its length is even, the center sits between two characters. By trying each possible center and stretching the two pointers l and r outward as long as s[l] == s[r], we can find the longest pure palindrome around each center.

Now, the twist in this problem is that we are allowed to delete exactly one character to obtain a palindrome. So instead of stopping forever when we hit a mismatch, we should think about what a single deletion lets us do.

Imagine we expand from the center and at some point the characters no longer match, i.e., s[l] != s[r] (or one pointer runs off the edge). This is exactly the spot where a deletion becomes useful. We have two choices:

Skip the left character: pretend s[l] was removed, and continue expanding from (l - 1, r).
Skip the right character: pretend s[r] was removed, and continue expanding from (l, r + 1).

Each choice consumes our one allowed deletion, so after making it, we simply keep expanding while the characters match, and we are no longer permitted to skip again. We compute the resulting length for both choices and take the larger one, because either deletion might lead to a longer almost-palindromic substring.

This is why the function f(l, r) works in three phases:

Expand the matching pair as far as possible (this is the "free" palindrome part).
At the first mismatch, branch into two scenarios — one skipping the left side, one skipping the right side.
Continue expanding in each branch, then report the maximum length found.

One important detail is that since we must delete exactly one character, an already-perfect palindrome still counts as almost-palindromic. For example, with "abba" we can remove one b to get "aba". The expand-and-branch logic naturally captures this: even when the whole window matches, we still attempt the skip step, which accounts for that mandatory deletion. We also cap the answer at n using min(n, ...) so the computed length never exceeds the actual string length.

By repeating this process for every center (both the single-character centers (i, i) and the between-character centers (i, i + 1)) and keeping track of the maximum length, we cover all possible almost-palindromic substrings and arrive at the final answer.

Pattern Learn more about Two Pointers and Dynamic Programming patterns.

Solution Approach

We use the technique of enumerating the center position of the palindrome combined with two-pointer expansion.

Let's denote the length of string s as n.

We define a helper function f(l, r), which computes the length of the longest almost-palindromic substring obtained by starting from positions l and r, expanding towards both sides, and deleting exactly one character.

Inside the function f(l, r):

First expansion (the matching core). We move outward as long as the boundaries are valid and the characters match:
```
while l >= 0 and r < n and s[l] == s[r]:
    l -= 1
    r += 1
```
When this loop ends, either we have stepped out of bounds, or we have found a mismatch at s[l] != s[r]. This is the point where our one deletion comes into play.
Branch into two deletion choices. From the mismatch point, we set up two pairs of pointers:
- Skip the left character: l1, r1 = l - 1, r
- Skip the right character: l2, r2 = l, r + 1

Second expansion for each branch. We continue expanding each branch while the characters keep matching, since the single deletion has already been used:

while l1 >= 0 and r1 < n and s[l1] == s[r1]:
    l1 -= 1
    r1 += 1
while l2 >= 0 and r2 < n and s[l2] == s[r2]:
    l2 -= 1
    r2 += 1

Return the best length. For a window with final pointers l and r, the substring length is r - l - 1 (the count of characters strictly between the two out-of-range or mismatched boundaries). We take the maximum of the two branches and cap it at n:
```
return min(n, max(r1 - l1 - 1, r2 - l2 - 1))
```
The min(n, ...) guard ensures the result never exceeds the actual string length, which protects against overcounting when the entire string already matches and the deletion step would otherwise inflate the count.

In the main routine:

We initialize ans = 0, then enumerate every center position i from 0 to n - 1. For each i, we consider two kinds of centers:

An odd-length center (i, i), where a single character sits at the middle:
```
a = f(i, i)
```
An even-length center (i, i + 1), where the middle sits between two characters:
```
b = f(i, i + 1)
```

We update the running maximum with both results:

ans = max(ans, a, b)

After all centers are processed, ans holds the length of the longest almost-palindromic substring, which we return.

Complexity Analysis:

Time complexity: O(n^2). There are O(n) center positions, and for each center the two-pointer expansion takes O(n) time in the worst case.
Space complexity: O(1). We only use a constant number of pointer variables, ignoring the input.

Example Walkthrough

Let's trace the algorithm on a small input string:

s = "abca"
n = 4

Our goal is to find the length of the longest almost-palindromic substring — a substring that becomes a palindrome after deleting exactly one character.

We enumerate every center position i from 0 to 3, and for each we call f(i, i) (odd center) and f(i, i + 1) (even center). We start with ans = 0.

Center `i = 0`

Odd center f(0, 0) — start at l = 0, r = 0 ('a').

First expansion: s[0] == s[0] �('a'='a'), so l → -1, r → 1. Now l = -1 is out of bounds, loop stops.
Branch into deletions:
- Skip left: l1, r1 = -2, 1
- Skip right: l2, r2 = -1, 2
Second expansion: both branches are already out of bounds (l1 < 0, l2 < 0), so neither moves.
Result: max(r1 - l1 - 1, r2 - l2 - 1) = max(1 - (-2) - 1, 2 - (-1) - 1) = max(2, 2) = 2, capped at n = 4 → 2.

(This corresponds to substring "ab" — delete one char to leave a single-char palindrome.)

Even center f(0, 1) — start at l = 0, r = 1 ('a' vs 'b').

First expansion: s[0] != s[1], loop doesn't run. Mismatch right at the start.
Branch:
- Skip left: l1, r1 = -1, 1
- Skip right: l2, r2 = 0, 2
Second expansion:
- Branch 1: l1 = -1 out of bounds, stops.
- Branch 2: s[0] == s[2]? ('a' vs 'c') → no, stops.
Result: max(1 - (-1) - 1, 2 - 0 - 1) = max(1, 1) = 1 → 1.

Update: ans = max(0, 2, 1) = 2.

Center `i = 1`

Odd center f(1, 1) ('b').

First expansion: s[1] == s[1], so l → 0, r → 2. Now check s[0] vs s[2] → 'a' vs 'c', mismatch, stop. (l = 0, r = 2)
Branch:
- Skip left: l1, r1 = -1, 2
- Skip right: l2, r2 = 0, 3
Second expansion:
- Branch 1: l1 = -1 out of bounds, stops.
- Branch 2: s[0] == s[3]? ('a' vs 'a') → ✔, so l2 → -1, r2 → 4. Now both out of bounds, stop.
Result: max(2 - (-1) - 1, 4 - (-1) - 1) = max(2, 4) = 4, capped at 4 → 4.

(This is the substring "abca" — delete 'c' to get "aba", a palindrome!)

Even center f(1, 2) ('b' vs 'c').

First expansion: mismatch immediately, loop doesn't run.
Branch:
- Skip left: l1, r1 = 0, 2
- Skip right: l2, r2 = 1, 3
Second expansion:
- Branch 1: s[0] == s[2]? ('a' vs 'c') → no.
- Branch 2: s[1] == s[3]? ('b' vs 'a') → no.
Result: max(2 - 0 - 1, 3 - 1 - 1) = max(1, 1) = 1 → 1.

Update: ans = max(2, 4, 1) = 4.

Centers `i = 2` and `i = 3`

By symmetry and the remaining short windows, these produce lengths no greater than 4. For example, f(2, 3) ('c' vs 'a') yields 1, and f(3, 3) yields 2. None exceed the current best.

Final Answer

After processing all centers, the maximum recorded is:

ans = 4

The longest almost-palindromic substring is "abca" (length 4), which becomes the palindrome "aba" after deleting exactly one character ('c').

This walkthrough highlights the core mechanics: expand from each center until a mismatch, then branch by skipping one side to spend the single allowed deletion, and finally take the largest window found across all centers.

Solution Implementation

1class Solution:
2    def almostPalindromic(self, s: str) -> int:
3        def expand(left: int, right: int) -> int:
4            # First, expand outward while characters match perfectly.
5            # This finds the largest strict palindrome from the given center.
6            while left >= 0 and right < n and s[left] == s[right]:
7                left -= 1
8                right += 1
9
10            # At this point, s[left] != s[right] (or we hit a boundary).
11            # We now allow exactly one mismatch. There are two ways to
12            # "skip" the mismatched pair while keeping the center fixed:
13
14            # Option 1: skip the left mismatched character.
15            # Treat the current right boundary as matched and move left pointer inward.
16            left1, right1 = left - 1, right
17            while left1 >= 0 and right1 < n and s[left1] == s[right1]:
18                left1 -= 1
19                right1 += 1
20
21            # Option 2: skip the right mismatched character.
22            # Treat the current left boundary as matched and move right pointer outward.
23            left2, right2 = left, right + 1
24            while left2 >= 0 and right2 < n and s[left2] == s[right2]:
25                left2 -= 1
26                right2 += 1
27
28            # The length of each candidate palindromic span is (right - left - 1).
29            # Take the better of the two skip options, capped by the string length n.
30            return min(n, max(right1 - left1 - 1, right2 - left2 - 1))
31
32        n = len(s)
33        ans = 0
34        for i in range(n):
35            # Consider an odd-length center (single character at index i).
36            odd_len = expand(i, i)
37            # Consider an even-length center (between index i and i + 1).
38            even_len = expand(i, i + 1)
39            ans = max(ans, odd_len, even_len)
40        return ans
41

1class Solution {
2    // Length of the input string
3    private int length;
4    // Character array view of the input string for fast index access
5    private char[] chars;
6
7    /**
8     * Returns the length of the longest "almost palindromic" substring,
9     * i.e. a substring that becomes a palindrome after allowing at most
10     * one character to be skipped on a mismatch.
11     */
12    public int almostPalindromic(String s) {
13        length = s.length();
14        this.chars = s.toCharArray();
15        int answer = 0;
16        // Treat every index (and every gap between indices) as a potential center,
17        // then expand outward to evaluate the best result for that center.
18        for (int center = 0; center < length; center++) {
19            // Odd-length center (single character).
20            answer = Math.max(answer, expand(center, center));
21            // Even-length center (between two adjacent characters).
22            answer = Math.max(answer, expand(center, center + 1));
23        }
24        return answer;
25    }
26
27    /**
28     * Expands around the given two-pointer center [left, right].
29     * First it consumes the longest matching palindrome core, then it
30     * accounts for a single allowed skip on either side of the first mismatch.
31     *
32     * @param left  initial left pointer of the center
33     * @param right initial right pointer of the center
34     * @return the best achievable length when skipping at most one character
35     */
36    private int expand(int left, int right) {
37        // Grow the palindrome while both ends keep matching.
38        while (left >= 0 && right < length && chars[left] == chars[right]) {
39            left--;
40            right++;
41        }
42
43        // Option 1: skip the mismatching character on the LEFT side.
44        // Move the left pointer past the mismatch and continue matching.
45        int leftSkipL = left - 1;
46        int leftSkipR = right;
47
48        // Option 2: skip the mismatching character on the RIGHT side.
49        // Move the right pointer past the mismatch and continue matching.
50        int rightSkipL = left;
51        int rightSkipR = right + 1;
52
53        // Continue expanding for Option 1 (left character skipped).
54        while (leftSkipL >= 0 && leftSkipR < length && chars[leftSkipL] == chars[leftSkipR]) {
55            leftSkipL--;
56            leftSkipR++;
57        }
58        // Continue expanding for Option 2 (right character skipped).
59        while (rightSkipL >= 0 && rightSkipR < length && chars[rightSkipL] == chars[rightSkipR]) {
60            rightSkipL--;
61            rightSkipR++;
62        }
63
64        // The achieved span for each option is (rightPointer - leftPointer - 1).
65        // Take the better of the two skip options, capped by the string length.
66        int lengthSkipLeft = leftSkipR - leftSkipL - 1;
67        int lengthSkipRight = rightSkipR - rightSkipL - 1;
68        return Math.min(length, Math.max(lengthSkipLeft, lengthSkipRight));
69    }
70}
71

1class Solution {
2public:
3    int almostPalindromic(string s) {
4        int n = s.size();
5
6        // Expand around a center (defined by indices left and right).
7        // Returns the length of the longest substring centered here that
8        // becomes a palindrome after allowing at most one character mismatch.
9        auto expand = [&](int left, int right) {
10            // First, extend the matching palindromic core as far as possible.
11            while (left >= 0 && right < n && s[left] == s[right]) {
12                --left;
13                ++right;
14            }
15
16            // At this point s[left] != s[right] (or we hit a boundary).
17            // We are allowed one mismatch, so try "skipping" the mismatch
18            // in two ways and continue extending:
19
20            // Option 1: treat the left character as the single allowed change,
21            // so move the left pointer one step further inward (to left - 1)
22            // while keeping the right pointer fixed.
23            int leftSkipLeft = left - 1, rightSkipLeft = right;
24
25            // Option 2: treat the right character as the single allowed change,
26            // so move the right pointer one step further outward (to right + 1)
27            // while keeping the left pointer fixed.
28            int leftSkipRight = left, rightSkipRight = right + 1;
29
30            // Continue expanding for Option 1.
31            while (leftSkipLeft >= 0 && rightSkipLeft < n &&
32                   s[leftSkipLeft] == s[rightSkipLeft]) {
33                --leftSkipLeft;
34                ++rightSkipLeft;
35            }
36
37            // Continue expanding for Option 2.
38            while (leftSkipRight >= 0 && rightSkipRight < n &&
39                   s[leftSkipRight] == s[rightSkipRight]) {
40                --leftSkipRight;
41                ++rightSkipRight;
42            }
43
44            // The substring length for a pair of pointers (l, r) that have
45            // moved one past the valid range is (r - l - 1).
46            // Clamp by n as an upper bound and take the better of the two options.
47            int lengthSkipLeft = rightSkipLeft - leftSkipLeft - 1;
48            int lengthSkipRight = rightSkipRight - leftSkipRight - 1;
49            return min(n, max(lengthSkipLeft, lengthSkipRight));
50        };
51
52        int ans = 0;
53        for (int i = 0; i < n; ++i) {
54            // Odd-length centers (single character center).
55            ans = max(ans, expand(i, i));
56            // Even-length centers (gap between two characters).
57            ans = max(ans, expand(i, i + 1));
58        }
59
60        return ans;
61    }
62};
63

1/**
2 * Finds the length of the longest "almost palindromic" substring.
3 * An almost palindrome allows skipping one mismatched character on either side
4 * during the center-expansion process.
5 *
6 * @param s - The input string.
7 * @returns The maximum length of an almost palindromic substring.
8 */
9function almostPalindromic(s: string): number {
10    const n: number = s.length;
11
12    /**
13     * Expands around a center defined by indices [left, right].
14     * First expands while characters match (the strict palindrome part),
15     * then attempts to continue past one mismatch in two possible ways:
16     *   - skip the left mismatched character
17     *   - skip the right mismatched character
18     *
19     * @param left  - Left boundary of the initial center.
20     * @param right - Right boundary of the initial center.
21     * @returns The best achievable length allowing one skip.
22     */
23    const expand = (left: number, right: number): number => {
24        // Expand the matching core outward as long as characters are equal.
25        while (left >= 0 && right < n && s[left] === s[right]) {
26            left--;
27            right++;
28        }
29
30        // Branch 1: skip the character on the left side of the mismatch.
31        let left1: number = left - 1;
32        let right1: number = right;
33
34        // Branch 2: skip the character on the right side of the mismatch.
35        let left2: number = left;
36        let right2: number = right + 1;
37
38        // Continue expanding branch 1 while characters match.
39        while (left1 >= 0 && right1 < n && s[left1] === s[right1]) {
40            left1--;
41            right1++;
42        }
43
44        // Continue expanding branch 2 while characters match.
45        while (left2 >= 0 && right2 < n && s[left2] === s[right2]) {
46            left2--;
47            right2++;
48        }
49
50        // The valid length of each branch is (rightBoundary - leftBoundary - 1).
51        // Take the larger branch, capped at n.
52        return Math.min(n, Math.max(right1 - left1 - 1, right2 - left2 - 1));
53    };
54
55    let ans: number = 0;
56    for (let i = 0; i < n; i++) {
57        // Odd-length centers: a single character.
58        ans = Math.max(ans, expand(i, i));
59        // Even-length centers: between two characters.
60        ans = Math.max(ans, expand(i, i + 1));
61    }
62
63    return ans;
64}
65

Time and Space Complexity

Time Complexity: O(n^2), where n is the length of string s. The outer loop iterates over each index i from 0 to n-1, which contributes a factor of O(n). For each index i, the function f is called twice (once for odd-length centers f(i, i) and once for even-length centers f(i, i + 1)). Inside f, there are three sequential while loops, each expanding outward from the center; in the worst case, each expansion can traverse up to O(n) characters. Therefore, each call to f takes O(n) time, and the total time complexity is O(n) * O(n) = O(n^2).
Space Complexity: O(1). The algorithm only uses a constant number of extra variables (such as l, r, l1, r1, l2, r2, a, b, ans), and no additional data structures that grow with the input size are allocated. Thus, the space complexity is constant.

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

Common Pitfalls

Pitfall 1: Forgetting that the deletion must be exactly one character (not "at most" one)

The single most dangerous trap in this problem is the word "exactly". The problem states that an almost-palindromic substring becomes a palindrome after removing exactly one character. This has a subtle but critical consequence: an odd-length palindrome that is already a palindrome can be a valid answer (you remove its center and it's still a palindrome), but you must verify the deletion logic does not silently count substrings that are not valid.

Consider the string s = "aba":

It is already a palindrome of length 3.
Remove the single center b → "aa", a palindrome. ✓ So "aba" is almost-palindromic with length 3.

Now consider s = "ab":

It is length 2. Remove exactly one character → "a" or "b", both palindromes. ✓ Length 2 is valid.

The danger is when developers write an "at most one mismatch" palindrome checker but fail to confirm a deletion actually happened or could happen. In the center-expansion approach above, the first loop expands a perfect palindrome core, and the two branches force a skip (deletion). The min(n, ...) guard is what prevents over-inflation, but it hides a deeper issue, explained below.

Pitfall 2: The `min(n, ...)` cap masks an off-by-one over-count, and can return a value with zero deletions

This is the most insidious bug. Look at what happens for a string that is already a full palindrome of odd length, e.g. s = "aba" (n = 3):

When expanding from center (1, 1):

First loop expands l → -1, r → 3 (entire string matches perfectly).
Branch 1: left1, right1 = -2, 3; loop doesn't run. Span = right1 - left1 - 1 = 3 - (-2) - 1 = 4.
Branch 2: left2, right2 = -1, 4; loop doesn't run. Span = 4 - (-1) - 1 = 4.
Return min(3, 4) = 3.

Here the raw computation produced 4, which is larger than the entire string — a clear over-count. The min(n, ...) silently clamps it to 3. While 3 happens to be the correct answer here, relying on the clamp to fix arithmetic is fragile: the clamp only protects the global boundary case (full-string palindrome) and does not protect against intermediate over-counts where the inflated span is still ≤ n.

Concrete failure example: Consider s = "abacd" (n = 5). Expanding from center (1,1):

First loop: s[1]==s[1], then s[0]='a'==s[2]='a' → l=-1, r=3. Mismatch/boundary.
Branch 2: left2, right2 = -1, 4; span = 4 - (-1) - 1 = 4.

This reports length 4 for substring s[0..3] = "abac". Is "abac" almost-palindromic? Remove c → "aba" ✓. So 4 is correct here. But the arithmetic that produced it (right2 - left2 - 1 with left2 = -1) only worked because the left boundary fell exactly at -1. When the left pointer is deeper out of bounds (as in "aba" above, where it reaches -2), the formula over-counts and only survives due to the clamp.

Solution: Make the deletion-count explicit and verify with a clean helper

A more robust formulation tracks how many deletions were used and validates the result against the actual substring, rather than depending on a min clamp. Below is a version that computes the candidate window, then explicitly verifies it is almost-palindromic with an independent checker:

class Solution:
    def almostPalindromic(self, s: str) -> int:
        n = len(s)

        def is_palindrome(i: int, j: int) -> bool:
            while i < j:
                if s[i] != s[j]:
                    return False
                i += 1
                j -= 1
            return True

        def is_almost(i: int, j: int) -> bool:
            # substring s[i..j], must become palindrome after deleting EXACTLY one char
            length = j - i + 1
            if length < 2:               # need at least 2 chars to delete one and remain non-empty
                return False
            while i < j:
                if s[i] != s[j]:
                    # one mismatch found: try skipping either side, no further deletions allowed
                    return is_palindrome(i + 1, j) or is_palindrome(i, j - 1)
                i += 1
                j -= 1
            # No mismatch => already a palindrome.
            # Deleting exactly one char keeps it a palindrome ONLY if its length is odd
            # (remove center) OR length is even (remove one of the equal middle pair).
            # In both cases an already-palindrome of length >= 2 stays a palindrome
            # after removing the appropriate central character.
            return True

        ans = 0
        # Center-expansion to bound candidates, then verify explicitly.
        def expand(left: int, right: int) -> int:
            best = 0
            while left >= 0 and right < n:
                if is_almost(left, right):
                    best = max(best, right - left + 1)
                if s[left] != s[right]:
                    break
                left -= 1
                right += 1
            return best

        for i in range(n):
            ans = max(ans, expand(i, i), expand(i, i + 1))
        return ans

Key corrections this version makes:

length < 2 guard in is_almost: a single character cannot have "exactly one character" removed while leaving a non-empty palindrome, so length-1 substrings are correctly excluded.
No magical min(n, ...) clamp: lengths are computed directly as right - left + 1 on real, in-bounds indices, so there is never an over-count to hide.
Explicit two-branch verification (is_palindrome(i+1, j) or is_palindrome(i, j-1)): mirrors the original two deletion options but checks them concretely rather than via pointer arithmetic that can drift out of bounds.

Pitfall 3: Even-length already-palindromes and the "exactly one" subtlety

For an even-length palindrome like "abba", removing exactly one character (one b) yields "aba", still a palindrome — so it qualifies. For an odd-length palindrome like "aba", removing the center b yields "aa" — also valid. A frequent mistake is to special-case these and accidentally reject already-palindromic substrings, assuming "deleting a char must fix a mismatch." In reality, any palindrome of length ≥ 2 remains a palindrome after deleting its central character, so it is always almost-palindromic. The is_almost helper above handles this by returning True in the no-mismatch branch (guarded by the length < 2 check), ensuring these valid cases are counted.

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

Additional Resources

AI Engineering