LeetCode 2422. Merge Operations to Turn Array Into a Palindrome Solution in Java, C++, Python & Go | Explanation + Code

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.

  <ul>
  	<li>For example, if <code>nums = [1,<u>2,3</u>,1]</code>, you can apply one operation to make it <code>[1,5,1]</code>.</li>
  </ul>
  </li>
  

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 ← i + 1, then add the value of the element pointed to by i to a, i.e., a ← a + nums[i], and increment the operation count by one, i.e., ans ← ans + 1.

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

Otherwise, it means a = b, at this time we move the pointer i one step to the right, i.e., i ← i + 1, move the pointer j one step to the left, i.e., j ← j - 1, and update the values of a and b, i.e., a ← nums[i] and b ← 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).

PythonJavaC++Go

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(code-box)

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; } }(code-box)

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; } };(code-box)

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 }(code-box)