Problem

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 theminimum number of operations needed to turn the array into a palindrome.

Examples

Example 1:

1
2
3
4
5
6
7

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:

1
2
3

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 <= 10^5
  • 1 <= nums[i] <= 10^6

Solution

Method 1 – Two Pointers and Greedy Merge

Intuition

To make the array a palindrome with minimum operations, use two pointers from both ends. If the values are equal, move both pointers inward. If not, merge the smaller value with its neighbor, incrementing the operation count, and continue until the array is a palindrome.

Approach

  1. Initialize two pointers: l = 0 (left), r = n - 1 (right).
  2. While l < r:
    • If nums[l] == nums[r], move both pointers inward.
    • If nums[l] < nums[r], merge nums[l] with nums[l+1], increment operation count, and move left pointer.
    • If nums[l] > nums[r], merge nums[r] with nums[r-1], increment operation count, and move right pointer.
  3. Repeat until l >= r.
  4. Return the operation count.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    int minimumOperations(vector<int>& nums) {
        int l = 0, r = nums.size() - 1, ans = 0;
        while (l < r) {
            if (nums[l] == nums[r]) {
                ++l; --r;
            } else if (nums[l] < nums[r]) {
                nums[l + 1] += nums[l];
                ++l; ++ans;
            } else {
                nums[r - 1] += nums[r];
                --r; ++ans;
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

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

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

class Solution {
    fun minimumOperations(nums: IntArray): Int {
        var l = 0; var r = nums.size - 1; var ans = 0
        while (l < r) {
            if (nums[l] == nums[r]) {
                l++; r--
            } else if (nums[l] < nums[r]) {
                nums[l + 1] += nums[l]
                l++; ans++
            } else {
                nums[r - 1] += nums[r]
                r--; ans++
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

def minimum_operations(nums: list[int]) -> int:
    l, r = 0, len(nums) - 1
    ans = 0
    while l < r:
        if nums[l] == nums[r]:
            l += 1; r -= 1
        elif nums[l] < nums[r]:
            nums[l + 1] += nums[l]
            l += 1; ans += 1
        else:
            nums[r - 1] += nums[r]
            r -= 1; ans += 1
    return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

impl Solution {
    pub fn minimum_operations(nums: &mut Vec<i32>) -> i32 {
        let (mut l, mut r, mut ans) = (0, nums.len() - 1, 0);
        while l < r {
            if nums[l] == nums[r] {
                l += 1; r -= 1;
            } else if nums[l] < nums[r] {
                nums[l + 1] += nums[l];
                l += 1; ans += 1;
            } else {
                nums[r - 1] += nums[r];
                r -= 1; ans += 1;
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    minimumOperations(nums: number[]): number {
        let l = 0, r = nums.length - 1, ans = 0;
        while (l < r) {
            if (nums[l] === nums[r]) {
                l++; r--;
            } else if (nums[l] < nums[r]) {
                nums[l + 1] += nums[l];
                l++; ans++;
            } else {
                nums[r - 1] += nums[r];
                r--; ans++;
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n), each element is visited at most once.
  • 🧺 Space complexity: O(1), only pointers and counters used.