Skip to content

2422. Merge Operations to Turn Array Into a Palindrome πŸ”’

Description

You are given an array nums consisting of positive integers.

You can perform the following operation on the array any number of times:

  • Choose any two adjacent elements and replace them with their sum.
    • For example, if nums = [1,2,3,1], you can apply one operation to make it [1,5,1].

Return the minimum number of operations needed to turn the array into a palindrome.

 

Example 1:

Input: nums = [4,3,2,1,2,3,1]
Output: 2
Explanation: We can turn the array into a palindrome in 2 operations as follows:
- Apply the operation on the fourth and fifth element of the array, nums becomes equal to [4,3,2,3,3,1].
- Apply the operation on the fifth and sixth element of the array, nums becomes equal to [4,3,2,3,4].
The array [4,3,2,3,4] is a palindrome.
It can be shown that 2 is the minimum number of operations needed.

Example 2:

Input: nums = [1,2,3,4]
Output: 3
Explanation: We do the operation 3 times in any position, we obtain the array [10] at the end which is a palindrome.

 

Constraints:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 106

Solutions

Solution 1: Greedy + Two Pointers

Define two pointers \(i\) and \(j\), pointing to the beginning and end of the array respectively, use variables \(a\) and \(b\) to represent the values of the first and last elements, and variable \(ans\) to represent the number of operations.

If \(a < b\), we move the pointer \(i\) one step to the right, i.e., \(i \leftarrow i + 1\), then add the value of the element pointed to by \(i\) to \(a\), i.e., \(a \leftarrow a + nums[i]\), and increment the operation count by one, i.e., \(ans \leftarrow ans + 1\).

If \(a > b\), we move the pointer \(j\) one step to the left, i.e., \(j \leftarrow j - 1\), then add the value of the element pointed to by \(j\) to \(b\), i.e., \(b \leftarrow b + nums[j]\), and increment the operation count by one, i.e., \(ans \leftarrow ans + 1\).

Otherwise, it means \(a = b\), at this time we move the pointer \(i\) one step to the right, i.e., \(i \leftarrow i + 1\), move the pointer \(j\) one step to the left, i.e., \(j \leftarrow j - 1\), and update the values of \(a\) and \(b\), i.e., \(a \leftarrow nums[i]\) and \(b \leftarrow nums[j]\).

Repeat the above process until \(i \ge j\), return the operation count \(ans\).

The time complexity is \(O(n)\), where \(n\) is the length of the array. The space complexity is \(O(1)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
    def minimumOperations(self, nums: List[int]) -> int:
        i, j = 0, len(nums) - 1
        a, b = nums[i], nums[j]
        ans = 0
        while i < j:
            if a < b:
                i += 1
                a += nums[i]
                ans += 1
            elif b < a:
                j -= 1
                b += nums[j]
                ans += 1
            else:
                i, j = i + 1, j - 1
                a, b = nums[i], nums[j]
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int minimumOperations(int[] nums) {
        int i = 0, j = nums.length - 1;
        long a = nums[i], b = nums[j];
        int ans = 0;
        while (i < j) {
            if (a < b) {
                a += nums[++i];
                ++ans;
            } else if (b < a) {
                b += nums[--j];
                ++ans;
            } else {
                a = nums[++i];
                b = nums[--j];
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int minimumOperations(vector<int>& nums) {
        int i = 0, j = nums.size() - 1;
        long a = nums[i], b = nums[j];
        int ans = 0;
        while (i < j) {
            if (a < b) {
                a += nums[++i];
                ++ans;
            } else if (b < a) {
                b += nums[--j];
                ++ans;
            } else {
                a = nums[++i];
                b = nums[--j];
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
func minimumOperations(nums []int) int {
    i, j := 0, len(nums)-1
    a, b := nums[i], nums[j]
    ans := 0
    for i < j {
        if a < b {
            i++
            a += nums[i]
            ans++
        } else if b < a {
            j--
            b += nums[j]
            ans++
        } else {
            i, j = i+1, j-1
            a, b = nums[i], nums[j]
        }
    }
    return ans
}

Comments