Welcome to Subscribe On Youtube
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].
- For example, if
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 <= 1051 <= 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)$.
-
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; } } -
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; } }; -
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 -
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 }