Skip to content

2422. Merge Operations to Turn Array Into a Palindrome 👍

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
 public:
  int minimumOperations(vector<int>& nums) {
    int ans = 0;
    int l = 0;
    int r = nums.size() - 1;
    long leftSum = nums.front();
    long rightSum = nums.back();

    while (l < r)
      if (leftSum < rightSum) {
        leftSum += nums[++l];
        ++ans;
      } else if (leftSum > rightSum) {
        rightSum += nums[--r];
        ++ans;
      } else {  // leftSum == rightSum
        leftSum = nums[++l];
        rightSum = nums[--r];
      }

    return ans;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
  public int minimumOperations(int[] nums) {
    int ans = 0;
    int l = 0;
    int r = nums.length - 1;
    long leftSum = nums[l];
    long rightSum = nums[r];

    while (l < r)
      if (leftSum < rightSum) {
        leftSum += nums[++l];
        ++ans;
      } else if (leftSum > rightSum) {
        rightSum += nums[--r];
        ++ans;
      } else { // LeftSum == rightSum
        leftSum = nums[++l];
        rightSum = nums[--r];
      }

    return ans;
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
  def minimumOperations(self, nums: List[int]) -> int:
    ans = 0
    l = 0
    r = len(nums) - 1
    leftSum = nums[0]
    rightSum = nums[-1]

    while l < r:
      if leftSum < rightSum:
        l += 1
        leftSum += nums[l]
        ans += 1
      elif leftSum > rightSum:
        r -= 1
        rightSum += nums[r]
        ans += 1
      else:  # leftSum == rightSum
        l += 1
        r -= 1
        leftSum = nums[l]
        rightSum = nums[r]

    return ans