Find Minimum Operations to Make an Array Palindrome

Understanding the Problem

The goal is to determine the minimum number of merge operations required to make an array a palindrome.

Method 1: Two-Pointer Approach

This method uses a two-pointer technique to check and merge elements as needed.

def min_operations(arr):
    i, j = 0, len(arr) - 1
    operations = 0
    while i < j:
        if arr[i] == arr[j]:
            i += 1
            j -= 1
        elif arr[i] < arr[j]:
            arr[i + 1] += arr[i]
            i += 1
            operations += 1
        else:
            arr[j - 1] += arr[j]
            j -= 1
            operations += 1
    return operations

arr = [1, 4, 5, 1]
print("Minimum operations:", min_operations(arr))
            

Output:

Minimum operations: 1

Method 2: Recursion

This method uses a recursive approach to count the operations.

def min_ops_recursive(arr, i, j):
    if i >= j:
        return 0
    if arr[i] == arr[j]:
        return min_ops_recursive(arr, i + 1, j - 1)
    if arr[i] < arr[j]:
        arr[i + 1] += arr[i]
        return 1 + min_ops_recursive(arr, i + 1, j)
    else:
        arr[j - 1] += arr[j]
        return 1 + min_ops_recursive(arr, i, j - 1)

arr = [1, 4, 5, 1]
print("Minimum operations:", min_ops_recursive(arr, 0, len(arr) - 1))
            

Output:

Minimum operations: 1

Method 3: Dynamic Programming

This method utilizes a DP table to compute the minimum operations.

def min_ops_dp(arr):
    n = len(arr)
    dp = [[0] * n for _ in range(n)]
    for gap in range(1, n):
        for i in range(n - gap):
            j = i + gap
            if arr[i] == arr[j]:
                dp[i][j] = dp[i + 1][j - 1]
            else:
                dp[i][j] = 1 + min(dp[i + 1][j], dp[i][j - 1])
    return dp[0][n - 1]

arr = [1, 4, 5, 1]
print("Minimum operations:", min_ops_dp(arr))
            

Output:

Minimum operations: 1