Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2422.html

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)$.

• Java
• C++
• Python
• Go

• 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
  }
  

All Problems

All Solutions