Palindrome Removal solution and explanation
5 more videos on this problem
Leetcode 1246. Palindrome RemovalAlgorithms Casts · 27:45 · 4K views
【LeetCode习题讲解】 1246. Palindrome RemovalSean Kkk · 28:44 · 782 views
Leetcode 1246. Palindrome Removal (range dp, interval dp)LetsCode · 15:22 · 184 views
Leetcode 1246. Palindrome RemovalAlgorithms for Big Bucks · 11:31 · 127 views
Leetcode 1246. Palindrome RemovalFearless Learner · 6:34 · 115 views
LeetCode 1246: Palindrome RemovalAlitaCode · 32:50 · 13 views
The problem
You are given an integer array arr.
In one move, you can select a palindromic subarray arr[i], arr[i + 1], ..., arr[j] where i <= j, and remove that subarray from the given array. Note that after removing a subarray, the elements on the left and on the right of that subarray move to fill the gap left by the removal.
Return the minimum number of moves needed to remove all numbers from the array.
Example 1:
Input: arr = [1,2] Output: 2
Example 2:
Input: arr = [1,3,4,1,5] Output: 3 Explanation: Remove [4] then remove [1,3,1] then remove [5].
Constraints:
1 <= arr.length <= 1001 <= arr[i] <= 20
Approach overview
Problem Overview: You are given an integer array and can remove any contiguous subarray that forms a palindrome. The goal is to remove the entire array using the minimum number of operations. Each operation deletes one palindromic segment, so the challenge is finding the optimal sequence of removals.
Approach 1: Brute Force Recursion (Exponential Time, O(n!) time, O(n) space)
The straightforward idea is to try removing every possible palindromic subarray and recursively solve the remaining array. For each step, iterate through all subarray boundaries (i, j), check if the segment is a palindrome, remove it, and continue searching for the minimum operations. This approach quickly becomes infeasible because the number of removal orders grows factorially. It’s useful conceptually because it exposes the overlapping subproblems that later motivate dynamic programming.
Approach 2: Top-Down Dynamic Programming (Interval DP) (O(n^3) time, O(n^2) space)
Define dp(l, r) as the minimum moves needed to remove the subarray from index l to r. The base case is a single element, which takes one move. The simplest transition removes arr[l] alone, giving 1 + dp(l+1, r). The key optimization appears when another element matches arr[l]. If arr[l] == arr[k], the two values can become part of the same palindrome after removing the middle segment. That leads to a transition like dp(l+1, k-1) + dp(k+1, r). Memoization stores results for every interval, preventing repeated work. This structure is a classic interval DP problem over an array.
Approach 3: Bottom-Up Interval DP (O(n^3) time, O(n^2) space)
The same recurrence can be implemented iteratively. Create a 2D table dp[i][j] representing the minimum removals for the subarray i..j. Fill the table by increasing subarray length. For each interval, start with removing the first element alone (1 + dp[i+1][j]). Then iterate through all indices k where arr[i] == arr[k]. If the values match, combine the operations so that the two elements disappear in the same palindrome removal, reducing the total operations. This bottom-up order guarantees all smaller intervals are computed before they are needed.
Recommended for interviews: Interviewers typically expect the interval DP solution with O(n^3) time and O(n^2) space. Starting from the brute-force idea shows you understand the problem structure, but recognizing overlapping subproblems and converting them into a memoized or bottom-up DP demonstrates stronger algorithmic reasoning. Interval DP patterns appear frequently in problems involving palindromes, merging segments, or optimal partitioning.
Solution
We define f[i][j] as the minimum number of operations required to delete all numbers in the index range [i,..j]. Initially, f[i][i] = 1, which means that when there is only one number, one deletion operation is needed.
For f[i][j], if i + 1 = j, i.e., there are only two numbers, if arr[i]=arr[j], then f[i][j] = 1, otherwise f[i][j] = 2.
For the case of more than two numbers, if arr[i]=arr[j], then f[i][j] can be f[i + 1][j - 1], or we can enumerate k in the index range [i,..j-1], take the minimum value of f[i][k] + f[k + 1][j]. Assign the minimum value to f[i][j].
The answer is f[0][n - 1].
The time complexity is O(n^3), and the space complexity is O(n^2). Where n is the length of the array.
class Solution:
def minimumMoves(self, arr: List[int]) -> int:
n = len(arr)
f = [[0] * n for _ in range(n)]
for i in range(n):
f[i][i] = 1
for i in range(n - 2, -1, -1):
for j in range(i + 1, n):
if i + 1 == j:
f[i][j] = 1 if arr[i] == arr[j] else 2
else:
t = f[i + 1][j - 1] if arr[i] == arr[j] else inf
for k in range(i, j):
t = min(t, f[i][k] + f[k + 1][j])
f[i][j] = t
return f[0][n - 1]class Solution {
public int minimumMoves(int[] arr) {
int n = arr.length;
int[][] f = new int[n][n];
for (int i = 0; i < n; ++i) {
f[i][i] = 1;
}
for (int i = n - 2; i >= 0; --i) {
for (int j = i + 1; j < n; ++j) {
if (i + 1 == j) {
f[i][j] = arr[i] == arr[j] ? 1 : 2;
} else {
int t = arr[i] == arr[j] ? f[i + 1][j - 1] : 1 << 30;
for (int k = i; k < j; ++k) {
t = Math.min(t, f[i][k] + f[k + 1][j]);
}
f[i][j] = t;
}
}
}
return f[0][n - 1];
}
}class Solution {
public:
int minimumMoves(vector<int>& arr) {
int n = arr.size();
int f[n][n];
memset(f, 0, sizeof f);
for (int i = 0; i < n; ++i) {
f[i][i] = 1;
}
for (int i = n - 2; i >= 0; --i) {
for (int j = i + 1; j < n; ++j) {
if (i + 1 == j) {
f[i][j] = arr[i] == arr[j] ? 1 : 2;
} else {
int t = arr[i] == arr[j] ? f[i + 1][j - 1] : 1 << 30;
for (int k = i; k < j; ++k) {
t = min(t, f[i][k] + f[k + 1][j]);
}
f[i][j] = t;
}
}
}
return f[0][n - 1];
}
};function minimumMoves(arr: number[]): number {
const n = arr.length;
const f: number[][] = Array.from({ length: n }, () => Array(n).fill(0));
for (let i = 0; i < n; ++i) {
f[i][i] = 1;
}
for (let i = n - 2; i >= 0; --i) {
for (let j = i + 1; j < n; ++j) {
if (i + 1 === j) {
f[i][j] = arr[i] === arr[j] ? 1 : 2;
} else {
let t = arr[i] === arr[j] ? f[i + 1][j - 1] : Infinity;
for (let k = i; k < j; ++k) {
t = Math.min(t, f[i][k] + f[k + 1][j]);
}
f[i][j] = t;
}
}
}
return f[0][n - 1];
}func minimumMoves(arr []int) int {
n := len(arr)
f := make([][]int, n)
for i := range f {
f[i] = make([]int, n)
f[i][i] = 1
}
for i := n - 2; i >= 0; i-- {
for j := i + 1; j < n; j++ {
if i+1 == j {
f[i][j] = 2
if arr[i] == arr[j] {
f[i][j] = 1
}
} else {
t := 1 << 30
if arr[i] == arr[j] {
t = f[i+1][j-1]
}
for k := i; k < j; k++ {
t = min(t, f[i][k]+f[k+1][j])
}
f[i][j] = t
}
}
}
return f[0][n-1]
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Recursion | O(n!) | O(n) | Conceptual understanding of all possible palindrome removals |
| Top-Down Dynamic Programming (Memoized Interval DP) | O(n^3) | O(n^2) | Clear recursive formulation with overlapping subproblems |
| Bottom-Up Interval DP | O(n^3) | O(n^2) | Preferred implementation for interviews and production due to predictable iteration order |
Frequently asked questions
Is Palindrome Removal easy or hard?
Palindrome Removal is categorized as a Hard problem because it requires recognizing an interval dynamic programming pattern and designing transitions that merge matching elements across subarrays.
Palindrome Removal Python/Java solution
Most implementations follow the same interval DP recurrence regardless of language. A 2D dp array is filled either with memoized recursion or bottom-up iteration. FleetCode provides complete implementations in Python, Java, C++, Go, and TypeScript.
How to solve Palindrome Removal in O(n)?
An O(n) solution is not known for this problem because each interval can interact with many other positions when forming larger palindromes. The best known solution uses interval dynamic programming with O(n^3) time and O(n^2) memory.
What is the best approach for Palindrome Removal?
The most effective approach is interval dynamic programming. Define dp[i][j] as the minimum moves required to remove the subarray from index i to j. The recurrence tries removing the first element alone or merging it with later matching values to form a larger palindrome. This solution runs in O(n^3) time with O(n^2) space.
Is Palindrome Removal asked at Google/Amazon/Meta?
Palindrome-based dynamic programming problems frequently appear in interviews at large tech companies including Google, Amazon, and Meta. Variants such as palindrome partitioning, minimum removals, and interval DP optimization are common in algorithm interview rounds.
What data structure is used in Palindrome Removal?
The solution primarily uses a 2D dynamic programming table over an array. Each entry dp[i][j] stores the minimum operations needed to remove the subarray between indices i and j.
What is the time complexity of Palindrome Removal?
The optimal interval DP solution runs in O(n^3) time and uses O(n^2) space. The cubic factor comes from evaluating every subarray pair (i, j) and iterating through possible matching positions k within that interval.