1246. Palindrome Removal


Problem Description

The problem gives us an integer array arr and asks us to remove palindromic subarrays using as few moves as possible. A subarray is palindromic if it reads the same backward as forward, for example [1, 2, 2, 1]. Each time you remove such a subarray, the remaining parts of the array close in to fill the gap. The task is to determine the minimum number of these moves required to remove all elements from the array.

Intuition

The intuition behind the solution is grounded in dynamic programming. We understand that trying all possible subarrays and checking if they are palindromic would be inefficient. Therefore, to optimize our approach, we can break down the problem:

  1. We can start by understanding that if a single element is always a palindrome, thus it can be removed in one move.
  2. For two elements, they can be removed in one move if they are the same or two moves if they are different, which can be the basis for our dynamic programming transition.
  3. For a larger subarray, the number of moves depends on whether the ends of the subarray match. If they do, the subarray could potentially be removed in one move (if the entire subarray is a palindrome), or the minimum moves could be achieved by splitting the subarray at some other point.
  4. For subarrays that don't have matching ends, we know that they can't be palindromic by themselves, so we look for where to split the subarray into two parts, each of which can be further split into palindromic subarrays.
  5. A dynamic programming table f can store the minimum number of moves required to remove a subarray arr[i:j]. Initially, all entries are set to zero, except for subarrays of length 1, which are set to 1.

By approaching the problem in this way, we incrementally build up the solution using information from smaller subarrays, storing and reusing these results to make the algorithm efficient.

Solution Approach

We create a 2D array f to use as a dynamic programming table, where f[i][j] represents the minimum number of moves needed to remove the subarray starting at i and ending at j. We initialize a diagonal of this table with ones since any single element can be removed in one move.

The next step is to fill in the table for larger subarrays. We consider each possible size of subarray starting from the smallest (2) and going up to the size of the entire array.

For each size, we iterate over all possible starting indices. The table is filled in a manner that for each subarray arr[i:j]:

  • If arr[i] equals arr[j], it means we can potentially remove the subarray in one move if the inside part arr[i+1:j-1] is also a palindrome (which we know from f[i+1][j-1]).
  • If arr[i] is not equal to arr[j], it means we need to split the array into two parts and the number of moves is the sum of moves for each part at the optimal splitting point. To find this point, we iterate through all possible ways to split the subarray arr[i:j] into two parts arr[i:k] and arr[k+1:j], and keep the minimum number of moves.

Once we fill in the table, the answer to the problem is the entry that represents the number of moves to remove the entire array, which is stored in f[0][n - 1], where n is the length of the array.

Learn more about Dynamic Programming patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

What is the space complexity of the following code?

1int sum(int n) {
2  if (n <= 0) {
3    return 0;
4  }
5  return n + sum(n - 1);
6}

Solution Approach

The solution uses dynamic programming, which is a method where we break down a complex problem into simpler subproblems and store the results of these subproblems to avoid redundant computations.

The algorithm uses a two-dimensional array f with dimensions n by n, where n is the length of the input array arr. Each entry f[i][j] in this table will eventually contain the minimum number of moves required to remove the subarray arr[i...j].

Here's the detailed process of implementing the solution:

  1. Initialization:

    • First, we initialize the array f with zeros and then we fill the diagonal f[i][i] with 1, because a single element is a palindrome and can be removed in one move.
  2. Filling the DP Table:

    • We then fill in the table in a bottom-up manner. To do this, we need to iterate over the subarrays starting from the smaller ones to the larger ones.
    • First, we iterate over the possible lengths of subarrays. Then for each length, we iterate over all possible starting points i.
    • For each subarray arr[i...j], we check:
      • If arr[i] and arr[j] are equal and we have already calculated the minimum moves for arr[i+1...j-1] in f[i+1][j-1], then the entire subarray is potentially a palindrome.
      • If arr[i] and arr[j] are the same and the inner subarray arr[i+1...j-1] is a palindrome, the entire subarray can be removed in one move—hence, f[i][j] gets the value of f[i+1][j-1].
      • If arr[i] and arr[j] are not equal, or if the inner subarray is not a palindrome, we need to split the subarray at some point. To find the optimal splitting point, we iterate through all possible k to split arr[i...j] into arr[i...k] and arr[k+1...j]. We calculate the sum of moves for these parts, and f[i][j] gets the minimum value among all possible splits.
    • This process continues until we fill in the entry for the entire array f[0][n-1].
  3. End Result:

    • After completly filling up the DP table, the solution to the problem—which is the minimum number of moves needed to remove all elements from the array—is found in f[0][n-1].

This dynamic programming approach is more efficient than brute force because we only compute the minimum moves for each subarray once, and we use these precomputed values to calculate the moves for larger subarrays.

The implementation is a classical DP solution where overlapping subproblems are solved just once and their solutions are stored, which reduces the time complexity significantly compared to a naive recursive approach. This showcases the power of dynamic programming in optimizing problem-solving strategies for specific types of problems.

By walking through the solution implementation, we see the application of the dynamic programming pattern, specifically the use of a 2D DP table, initialization based on base cases, filling in the table based on recursive relationships, and retrieval of the solution from the filled table.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

Example Walkthrough

Let's walk through a small example to illustrate the solution approach. Consider the integer array arr = [1, 2, 1, 3, 2, 2].

  1. Initialization: We create a matrix f of size 6x6 because our array arr has 6 elements. We then fill the diagonal from f[0][0] to f[5][5] with 1 because a single element is a palindrome and can be removed in one move.

  2. Filling the DP Table:

    • For subarrays of length 2, we compare each pair of elements:
      • arr[0] and arr[1] are not equal, so f[0][1] will be set to 2 (1 move for each element).
      • arr[1] and arr[2] are not equal, so f[1][2] will also be set to 2.
      • arr[2] and arr[3] are not equal, so f[2][3] will be set to 2.
      • arr[3] and arr[4] are not equal, so f[3][4] will be set to 2.
      • arr[4] and arr[5] are equal, so f[4][5] will be set to 1, since [2, 2] is a palindrome and can be removed in one move.
    • For subarrays longer than 2, we consider their internal splits:
      • arr[0:2] could potentially be palindromic if arr[0] and arr[2] are equal, which they are, so we check if f[1][1] is a palindrome, and indeed it is (since it's a single element). Hence, f[0][2] is set to 1.
      • We continue this process for subarrays arr[1:3], arr[2:4], arr[3:5], checking the ends and the internal sections of the subarrays, updating our table as we find palindromes.
  3. End Result:

    • After filling out the table, if we want to compute f[0][5], which is the minimum number of moves to remove all elements in the array, we check:
      • The array ends with arr[0] and arr[5] are not the same, so we must split the array.
      • We try all possible splits, looking for the minimum f[i][j] values for i to k and k+1 to j subarrays.
      • We find the minimum moves for all splits, and f[0][5] will have the minimum of these values.

As a result, f[0][5] holds the minimum number of moves required to remove all elements from arr by removing palindromic subarrays. This process reduces the problem into smaller, manageable steps that dynamically build upon each other to find the most efficient solution.

Not Sure What to Study? Take the 2-min Quiz:

Which of the two traversal algorithms (BFS and DFS) can be used to find whether two nodes are connected?

Python Solution

1from typing import List
2
3class Solution:
4    def minimum_moves(self, arr: List[int]) -> int:
5        # The length of the array
6        n = len(arr)
7      
8        # Initialize a 2D array to store the minimum number of moves for each subarray
9        dp = [[0] * n for _ in range(n)]
10      
11        # Base case: A single element requires one move to become a palindrome
12        for i in range(n):
13            dp[i][i] = 1
14      
15        # Start from the second to last element down to the first element
16        for i in range(n-2, -1, -1):
17            # For each starting position, process subarrays with different lengths
18            for j in range(i+1, n):
19                # If we have a subarray of length 2, check if the elements are the same
20                if i + 1 == j:
21                    dp[i][j] = 1 if arr[i] == arr[j] else 2
22                else:
23                    # If the current elements are the same, compare with the inner subarray
24                    # excluding both ends
25                    moves = dp[i+1][j-1] if arr[i] == arr[j] else float('inf')
26                    # Try all possible partitions of the subarray, and
27                    # take the minimum number of moves required
28                    for k in range(i, j):
29                        moves = min(moves, dp[i][k] + dp[k+1][j])
30                    dp[i][j] = moves
31      
32        # Return the minimum number of moves needed to make the entire array a palindrome
33        return dp[0][n-1]
34
35# Example of usage
36# sol = Solution()
37# print(sol.minimum_moves([1,3,4,1,5])) # Example input to get output
38

Java Solution

1class Solution {
2    public int minimumMoves(int[] arr) {
3        // Get the length of the array.
4        int length = arr.length;
5        // Initialize the memoization table with dimensions of the array length.
6        int[][] dpMinMoves = new int[length][length];
7
8        // Base case: single elements require one move to create a palindrome.
9        for (int i = 0; i < length; ++i) {
10            dpMinMoves[i][i] = 1;
11        }
12
13        // Fill the table in reverse order to ensure that
14        // all sub-problems are solved before the bigger ones.
15        for (int start = length - 2; start >= 0; --start) {
16            for (int end = start + 1; end < length; ++end) {
17                // If we're checking a pair of adjacent elements,
18                // we can make a palindrome with one move if they're equal,
19                // or with two moves if they are not.
20                if (start + 1 == end) {
21                    dpMinMoves[start][end] = arr[start] == arr[end] ? 1 : 2;
22                } else {
23                     // If the elements at the start and end are equal,
24                     // we can potentially remove them both with a single move.
25                     // Start with an initial large value to not affect the minimum comparison.
26                    int minMoves = arr[start] == arr[end] ? dpMinMoves[start + 1][end - 1] : Integer.MAX_VALUE;
27                    // Sweep through the array and split at every possible point to find
28                    // the minimum moves for this start and end combination.
29                    for (int split = start; split < end; ++split) {
30                        minMoves = Math.min(minMoves, dpMinMoves[start][split] + dpMinMoves[split + 1][end]);
31                    }
32                    // Record the minimum moves needed for this subarray.
33                    dpMinMoves[start][end] = minMoves;
34                }
35            }
36        }
37      
38        // Return the minimum moves needed to make the entire array a palindrome.
39        return dpMinMoves[0][length - 1];
40    }
41}
42

C++ Solution

1class Solution {
2public:
3    int minimumMoves(vector<int>& arr) {
4        int length = arr.size();
5      
6        // Create dp (Dynamic Programming) table and initialize with zeros
7        vector<vector<int>> dp(length, vector<int>(length, 0));
8
9        // Base case: single element requires only one move
10        for (int i = 0; i < length; ++i) {
11            dp[i][i] = 1;
12        }
13
14        // Fill up the DP table for substrings of length >= 2
15        for (int start = length - 2; start >= 0; --start) {
16            for (int end = start + 1; end < length; ++end) {
17                if (start + 1 == end) {
18                    // If there are only two elements and they are equal, 1 move is required
19                    // Otherwise 2 moves are required: one for each element
20                    dp[start][end] = arr[start] == arr[end] ? 1 : 2;
21                } else {
22                    // Set initial value high for comparison purposes
23                    int moves = arr[start] == arr[end] ? dp[start + 1][end - 1] : INT_MAX;
24                    // Check for the minimum moves by dividing the range at different points
25                    for (int split = start; split < end; ++split) {
26                        moves = min(moves, dp[start][split] + dp[split + 1][end]);
27                    }
28                    dp[start][end] = moves;
29                }
30            }
31        }
32
33        // Return the minimum number of moves to make the full array a palindrome
34        return dp[0][length - 1];
35    }
36};
37

Typescript Solution

1// Define the array type for ease of reference
2type Array2D = number[][];
3
4// Function to calculate the minimum number of moves to make the array a palindrome
5function minimumMoves(arr: number[]): number {
6    const length: number = arr.length;
7  
8    // Create dp (Dynamic Programming) table and initialize with zeros
9    let dp: Array2D = Array.from({ length }, () => Array(length).fill(0));
10
11    // Base case: single element requires only one move
12    for (let i = 0; i < length; ++i) {
13        dp[i][i] = 1;
14    }
15
16    // Fill up the DP table for substrings of length >= 2
17    for (let start = length - 2; start >= 0; --start) {
18        for (let end = start + 1; end < length; ++end) {
19            if (arr[start] == arr[end]) {
20                // If the elements at the start and end are equal, this can potentially
21                // be folded into a palindrome, so check the inner subrange for moves
22                dp[start][end] = dp[start + 1][end - 1];
23            } else {
24                // If elements are different, it requires at least 2 moves;
25                // initialize with the worst case (1 move for each element)
26                dp[start][end] = 2;
27                // Check for the minimum moves by dividing the range at different points
28                for (let split = start; split < end; ++split) {
29                    dp[start][end] = Math.min(dp[start][end], dp[start][split] + dp[split + 1][end]);
30                }
31            }
32        }
33    }
34
35    // Return the minimum number of moves to make the full array a palindrome
36    return dp[0][length - 1];
37}
38
39// Minimum number of moves for a specific array can be found by calling the function.
40// Example:
41// const arr: number[] = [1, 2, 3, 4, 1]; 
42// const moves: number = minimumMoves(arr); 
43// console.log(moves); // Output would be the number of moves needed
44
Fast Track Your Learning with Our Quick Skills Quiz:

Depth first search can be used to find whether two components in a graph are connected.

Time and Space Complexity

Time Complexity

The given code employs dynamic programming to find the minimum number of moves to make a palindrome by merging elements in the array. The time complexity is determined by the nested loops and the operations performed within them.

  1. There are two nested loops, where one loops in a backward manner from n-2 to 0 and the other loops from i+1 to n. Each of these loops has O(n) iterations resulting in O(n^2) for the nested loops combined.
  2. Inside the inner loop, there is another loop that ranges from i to j. In the worst-case scenario, this loop can iterate n times.
  3. The innermost computation, however, is just a min comparison which is O(1).

Multiplying all these together, the worst-case time complexity is O(n^3).

Space Complexity

The space complexity is derived from the storage used for the dynamic programming table f.

  1. The f table is a 2D array with dimensions n x n, containing n^2 elements.
  2. None of the loops use additional significant space.

Thus, the space complexity of the code is O(n^2).

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


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫