LeetCode 1246 - Palindrome Removal

The problem requires us to remove all elements from an integer array arr in the minimum number of moves, where a move consists of removing a contiguous palindromic subarray. A palindromic subarray reads the same forwards and backwards.

leetcodehardarraydynamic-programming

LeetCode Problem 1246

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming

Solution

Problem Understanding

The problem requires us to remove all elements from an integer array arr in the minimum number of moves, where a move consists of removing a contiguous palindromic subarray. A palindromic subarray reads the same forwards and backwards. After removing a subarray, the elements to the left and right shift to fill the gap.

The input is an array of integers where 1 <= arr.length <= 100 and each element is between 1 and 20. This constraint suggests that a brute-force solution that tries all possible sequences of removals would be too slow because the number of potential subarrays grows quadratically, and the number of sequences grows exponentially.

The expected output is a single integer, the minimum number of moves to completely remove the array. Important edge cases include arrays of length 1, arrays where all elements are the same (fully palindromic), and arrays where no two adjacent elements are equal, forcing single-element removals.

Approaches

The brute-force approach would attempt every possible sequence of palindromic removals. At each step, it would try removing all possible palindromic subarrays, recursively computing the minimum moves for the resulting array. While this guarantees a correct answer, its time complexity is exponential, which is infeasible for arr.length = 100.

The optimal approach relies on dynamic programming. Define dp[i][j] as the minimum number of moves to remove the subarray arr[i:j+1]. The key insight is that if arr[i] == arr[j], we can consider removing both together after removing the middle subarray arr[i+1:j]. Otherwise, we split at some k between i and j, recursively removing the left and right segments. By storing results for subarrays, we avoid recomputation.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n) O(n) Recursively try every palindromic removal sequence
Optimal O(n^3) O(n^2) DP on subarrays with splitting and merging palindromes

Algorithm Walkthrough

  1. Initialize a 2D array dp of size n x n where n = len(arr). Each entry dp[i][j] represents the minimum number of moves to remove arr[i:j+1]. Initialize all values to a large number.
  2. Set the base case: dp[i][i] = 1 because a single element can be removed in one move.
  3. Iterate over subarray lengths from 2 to n.
  4. For each subarray arr[i:j+1], first assume the last element is removed separately, i.e., dp[i][j] = dp[i][j-1] + 1.
  5. Then, iterate over all positions k from i to j-1. If arr[k] == arr[j], consider removing arr[k+1:j] first and merging arr[k] with arr[j]. Update dp[i][j] = min(dp[i][j], dp[i][k-1] + dp[k+1][j-1]). Handle k=i carefully to avoid out-of-bounds.
  6. After filling the table, dp[0][n-1] contains the minimum moves to remove the whole array.

Why it works: The DP ensures that for every subarray, we consider all ways to remove palindromes either by splitting or merging matching ends. By building from smaller subarrays to larger, all dependencies are resolved, guaranteeing the correct minimum.

Python Solution

from typing import List

class Solution:
    def minimumMoves(self, arr: List[int]) -> int:
        n = len(arr)
        dp = [[0] * n for _ in range(n)]
        
        for i in range(n-1, -1, -1):
            dp[i][i] = 1
            for j in range(i+1, n):
                dp[i][j] = dp[i][j-1] + 1
                for k in range(i, j):
                    if arr[k] == arr[j]:
                        if k == i:
                            dp[i][j] = min(dp[i][j], dp[k+1][j-1] if k+1 <= j-1 else 0)
                        else:
                            dp[i][j] = min(dp[i][j], dp[i][k-1] + (dp[k+1][j-1] if k+1 <= j-1 else 0))
        return dp[0][n-1]

Implementation walkthrough: We first initialize dp[i][i] as 1 for single-element subarrays. For larger subarrays, we start by assuming the last element is removed separately. Then we iterate over all possible positions k that match the last element, attempting to merge palindromes efficiently. The careful handling of edge cases ensures no index errors.

Go Solution

func minimumMoves(arr []int) int {
    n := len(arr)
    dp := make([][]int, n)
    for i := 0; i < n; i++ {
        dp[i] = make([]int, n)
    }

    for i := n-1; i >= 0; i-- {
        dp[i][i] = 1
        for j := i + 1; j < n; j++ {
            dp[i][j] = dp[i][j-1] + 1
            for k := i; k < j; k++ {
                if arr[k] == arr[j] {
                    var middle int
                    if k+1 <= j-1 {
                        middle = dp[k+1][j-1]
                    } else {
                        middle = 0
                    }
                    if k == i {
                        if middle < dp[i][j] {
                            dp[i][j] = middle
                        }
                    } else {
                        if dp[i][k-1]+middle < dp[i][j] {
                            dp[i][j] = dp[i][k-1] + middle
                        }
                    }
                }
            }
        }
    }
    return dp[0][n-1]
}

Go-specific notes: We use slices to implement the 2D DP array. Index bounds are carefully checked when calculating middle. There is no concern for integer overflow given problem constraints.

Worked Examples

Example 1: arr = [1,2]

i j dp[i][j]
0 0 1
1 1 1
0 1 dp[0][0] + 1 = 2

Output: 2

Example 2: arr = [1,3,4,1,5]

i j dp[i][j] calculation
0 0 1
1 1 1
2 2 1
3 3 1
4 4 1
0 1 dp[0][0] + 1 = 2
1 3 dp[1][2] + 1 = 2, then merge arr[1] and arr[3]: dp[2][2]=1 -> dp[1][3]=1+1=2
0 4 remove last separately: dp[0][3]+1=3, merge arr[0] and arr[3]: dp[1][2]+0=2 -> min=3

Output: 3

Complexity Analysis

Measure Complexity Explanation
Time O(n^3) Triple loop: subarray length, start index, and potential split positions
Space O(n^2) 2D DP table storing results for each subarray

The O(n^3) time is acceptable for n ≤ 100, as 1,000,000 operations are feasible.

Test Cases

# Provided examples
assert Solution().minimumMoves([1,2]) == 2  # minimal array
assert Solution().minimumMoves([1,3,4,1,5]) == 3  # requires splitting and merging

# Single element
assert Solution().minimumMoves([7]) == 1  # one move for single element

# Fully palindromic
assert Solution().minimumMoves([2,2,2,2]) == 1  # entire array is palindrome

# No palindromes longer than 1
assert Solution().minimumMoves([1,2,3,4]) == 4  # must remove each element individually

# Palindrome in the middle
assert Solution().minimumMoves([1,2,3,2,1]) == 1  # entire array is palindrome

# Alternating repeats
assert Solution().minimumMoves([1,2,1,2,1]) == 3  # remove [1], [2,1,2], [1]
Test Why
[1,2] minimal array, simplest non-palindromic
[1,3,4,1,5] requires merging and splitting
[7