2422. Merge Operations to Turn Array Into a Palindrome


Problem Description

You are given an array called nums that contains only positive integers. Your task is to make this array a palindrome. A palindrome is a sequence that reads the same forward and backward. To do this, you are allowed to perform as many operations as you want. An operation consists of selecting any two adjacent elements in nums and replacing them with their sum. The goal is to find the minimum number of such operations required to turn the array into a palindrome.

Intuition

The key to solving this problem lies in understanding how a palindrome is structured: the values on the left side of the array must be mirrored on the right side. The strategy is to iteratively make the sums of the values from both ends (left and right) of the array equal, so they form a palindrome.

To implement this strategy, two pointers approach is used, one starting at the left end (beginning of the array) and one at the right end (end of the array). We compare the sums of the elements at these pointers.

  • If the left sum is less than the right sum, this means we need to increase the left sum by moving the left pointer to the right and adding the value at the new pointer position to the left sum, counting this action as one operation.
  • Conversely, if the right sum is less than the left sum, we move the right pointer to the left, add the value at the new pointer to the right sum, and count it as an operation as well.
  • When both sums are equal, we effectively have a palindrome within those boundaries. We move both pointers inward, skipping over the elements we just confirmed as part of the palindrome because they do not need any more operations.
  • This process repeats until the pointers meet, which would mean the entire array has become a palindrome.

The trick here is that we donā€™t need to actually replace numbers or keep track of the modified array; instead, we just need to know the count of operations required, which is tallied every time we move either pointer to adjust the sums.

The solution's complexity is O(n), where n is the length of the array, because we possibly go through the array only once with our two pointers.

Learn more about Greedy and Two Pointers patterns.

Solution Approach

The solution uses a two-pointers algorithm to walk through the array from both ends towards the center. This approach helps in reducing the problem to smaller subproblems by considering the current sum at both ends. Here's a step-by-step walkthrough:

  • Initialize two pointers, i at the start and j at the end of the array.
  • Initialize two variables, a and b, to keep track of the sum of the numbers pointed by i and j. Initially, a is assigned nums[i], and b is assigned nums[j].
  • Initialize a counter ans with the value 0 to keep track of the number of operations performed.
  • Enter a while loop, which will continue to execute as long as i < j (ensuring that we are not comparing the same element with itself or crossing over, which would mean the entire array is a palindrome):
    • Compare the values of a and b.
    • If a < b, we need to increase a to eventually match b. We do so by incrementing i (move the left pointer to the right), adding nums[i] to a, and incrementing the counter ans to represent an operation performed.
    • If b < a, similarly, we need to increase b to match a. Decrement j (move the right pointer to the left), add nums[j] to b, and increment the counter ans.
    • If a == b, it means that the values from nums[i] to nums[j] can be part of the palindrome. Therefore, we increment i, decrement j, and update a and b with the values at the new indices nums[i] and nums[j], respectively. No operation is counted in this case as a and b are already equal.
  • Continue the loop until all elements have been accounted for in pairs that form the palindrome.
  • The iterator ans is returned as it now contains the minimum number of operations needed to make the array a palindrome.

This simple yet elegant solution leverages the two-pointer technique, which is efficient when you need to compare or pair up elements from opposite ends of an array. It skillfully avoids the need for extra space to store interim arrays, mutating only counters and making the solution very space-efficient (O(1) space complexity).

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider an example to understand the solution approach:

Suppose we are given the following array nums:

nums = [1, 3, 4, 2, 2]

To make nums a palindrome using the fewest operations, we will follow the steps outlined:

  1. Initialize two pointers, i at the start (0) and j at the end (4) of the array.
  2. Initialize variables a with nums[i] (which is 1) and b with nums[j] (which is 2).
  3. Initialize the operation counter ans to 0.

So, the initial setting looks like:

i = 0 ā†’ [1, 3, 4, 2, 2] ā† j = 4
a = 1
b = 2
ans = 0

Now, we start iterating:

  • Since a (1) < b (2), we increment i to 1 and update a by adding nums[i], which makes a = 1 + 3 = 4 and ans becomes 1.
  • At this point, a (4) == b (2), but for the array to be palindrome, a and b must have the same sum. Thus, we decrease j to 3 and update b by adding nums[j], now b = 2 + 2 = 4, and ans becomes 2.
  • Now a (4) == b (4), so we increment i to 2, and decrement j to 2, effectively skipping over the elements we just confirmed to form the correct structure in our palindrome.

Finally, since i now equals j, we've considered the entire array, so we finish.

At the end of the process, ans equals 2, indicating the minimum number of operations required to turn the array into a palindrome.

So, our example array nums can be transformed into a palindrome with a minimum of 2 operations:

  • Combine nums[0] and nums[1] to form [4, 4, 2, 2]
  • Combine nums[2] and nums[3] to form [4, 6, 2]
  • No further operations are needed, as [4, 6, 2] is already a palindrome.

Solution Implementation

1from typing import List
2
3class Solution:
4    def minimumOperations(self, nums: List[int]) -> int:
5        # Initialize two pointers for the start and end of the list
6        left_index, right_index = 0, len(nums) - 1
7      
8        # Initialize the sums of elements from the start and from the end
9        left_sum, right_sum = nums[left_index], nums[right_index]
10      
11        # Initialize a variable to count the number of operations performed
12        operations_count = 0
13      
14        # Loop until the two pointers meet or cross each other
15        while left_index < right_index:
16          
17            # If the sum on the left is less than the sum on the right,
18            # move the left pointer to the right and add the new element to left_sum
19            if left_sum < right_sum:
20                left_index += 1
21                left_sum += nums[left_index]
22                operations_count += 1
23            # If the sum on the right is less than the sum on the left,
24            # move the right pointer to the left and add the new element to right_sum
25            elif right_sum < left_sum:
26                right_index -= 1
27                right_sum += nums[right_index]
28                operations_count += 1
29            # If the sums are equal, move both pointers and update the sums
30            else:
31                left_index += 1
32                right_index -= 1
33                # Check if pointers are still within the array bounds
34                if left_index < right_index:
35                    left_sum = nums[left_index]
36                    right_sum = nums[right_index]
37      
38        # Return the total number of operations to make segments equal
39        return operations_count
40
1class Solution {
2  
3    /**
4     * Find minimum number of operations to make sum of elements on the left 
5     * equal to the sum of elements on the right.
6     * 
7     * @param nums Array of integers.
8     * @return The minimum number of operations required.
9     */
10    public int minimumOperations(int[] nums) {
11        // Initialize pointers for the left and right parts.
12        int leftIndex = 0;
13        int rightIndex = nums.length - 1;
14      
15        // Initialize sums for the left and right parts.
16        long leftSum = nums[leftIndex];
17        long rightSum = nums[rightIndex];
18      
19        // Variable to keep track of the number of operations performed.
20        int operationsCount = 0;
21      
22        // Loop until the pointers meet.
23        while (leftIndex < rightIndex) {
24            // If the left sum is smaller, move the left pointer to the right and add the value to leftSum.
25            if (leftSum < rightSum) {
26                leftSum += nums[++leftIndex];
27                operationsCount++;
28            // If the right sum is smaller, move the right pointer to the left and add the value to rightSum.
29            } else if (rightSum < leftSum) {
30                rightSum += nums[--rightIndex];
31                operationsCount++;
32            // If both sums are equal, move both pointers and reset the sums.
33            } else {
34                // Ensure that we do not cross the pointers.
35                if (leftIndex + 1 < rightIndex - 1) {
36                    leftSum = nums[++leftIndex];
37                    rightSum = nums[--rightIndex];
38                } else {
39                    // Pointers will cross after this step, hence we should break the loop.
40                    break;
41                }
42            }
43        }
44      
45        // Return the number of operations performed to make the sums equal.
46        return operationsCount;
47    }
48}
49
1class Solution {
2public:
3    int minimumOperations(vector<int>& nums) {
4        // Initialize two pointers from both ends of the array
5        int leftIndex = 0, rightIndex = nums.size() - 1;
6        // Initialize sum variables for the two pointers
7        long leftSum = nums[leftIndex], rightSum = nums[rightIndex];
8        // Initialize a variable to count the number of operations performed
9        int operationCount = 0;
10
11        // Loop until the two pointers meet
12        while (leftIndex < rightIndex) {
13            if (leftSum < rightSum) {
14                // If the left sum is smaller, move the left pointer to the right
15                // and add the next number to the left sum.
16                leftSum += nums[++leftIndex];
17                // Increment the number of operations
18                ++operationCount;
19            } else if (rightSum < leftSum) {
20                // If the right sum is smaller, move the right pointer to the left
21                // and add the next number to the right sum.
22                rightSum += nums[--rightIndex];
23                // Increment the number of operations
24                ++operationCount;
25            } else {
26                // If the sums are equal, move both pointers towards the centre
27                // and start the next comparisons with the next outermost numbers
28                leftSum = nums[++leftIndex];
29                rightSum = nums[--rightIndex];
30            }
31        }
32        // Return the number of operations performed to make sums equal
33        return operationCount;
34    }
35};
36
1/**
2 * Calculates the minimum number of operations to make the left sum
3 * and right sum equal by only moving elements from one end to the other.
4 * @param nums - The array of numbers.
5 * @return The number of operations needed to equate the two sums.
6 */
7function minimumOperations(nums: Array<number>): number {
8    // Initialize pointers for both ends of the array
9    let leftIndex: number = 0;
10    let rightIndex: number = nums.length - 1;
11
12    // Initialize sum variables for the pointers
13    let leftSum: number = nums[leftIndex];
14    let rightSum: number = nums[rightIndex];
15
16    // Initialize the count of operations
17    let operationCount: number = 0;
18
19    // Loop until the pointers meet or cross
20    while (leftIndex < rightIndex) {
21        if (leftSum < rightSum) {
22            // If left sum is smaller, include the next element into the left sum
23            leftSum += nums[++leftIndex];
24            operationCount++;
25        } else if (rightSum < leftSum) {
26            // If right sum is smaller, include the next element into the right sum
27            rightSum += nums[--rightIndex];
28            operationCount++;
29        } else {
30            // If sums are equal, move to the next elements
31            leftSum = nums[++leftIndex];
32            rightSum = nums[--rightIndex];
33        }
34    }
35
36    // Return the total number of operations performed
37    return operationCount;
38}
39

Time and Space Complexity

Time Complexity

The given code iterates through the nums list using two pointers i and j that start at opposite ends of the list and move towards the center. The main loop runs while i < j, so in the worst case, it may iterate through all the elements once. Therefore, the worst-case time complexity is O(n), where n is the number of elements in the nums list.

In each iteration of the while loop, the code performs constant-time operationsā€”comparisons and basic arithmeticā€”so these do not affect the overall O(n) time complexity.

Space Complexity

Since the algorithm operates in place and the amount of additional memory used does not depend on the input size (nums list), the space complexity is O(1). Only a fixed number of variables i, j, a, b, and ans are used, which occupies constant space irrespective of the input size.

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


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Is the following code DFS or BFS?

void search(Node root) {
  if (!root) return;
  visit(root);
  root.visited = true;
  for (Node node in root.adjacent) {
    if (!node.visited) {
      search(node);
    }
  }
}

Recommended Readings

Want a Structured Path to Master System Design Too? Donā€™t Miss This!


Load More