Practice/Amazon/Leetcode 2422. Merge Operations to Turn Array Into a Palindrome

Leetcode 2422. Merge Operations to Turn Array Into a Palindrome

CodingMust

Problem

You are given an array of positive integers. In one operation, you can select any two adjacent elements and merge them into a single element whose value equals their sum. After the merge, the array length decreases by one.

Your task is to find the minimum number of merge operations needed to transform the array into a palindrome (an array that reads the same forwards and backwards).

Requirements

1. Return the minimum number of adjacent merge operations required
2. Each merge combines two adjacent elements into their sum
3. The final array must be palindromic (same when read left-to-right or right-to-left)
4. All input integers are positive

Constraints

• 1 ≤ nums.length ≤ 10⁵
• 1 ≤ nums[i] ≤ 10⁶
• Expected time complexity: O(n)
• Expected space complexity: O(1)

Examples

Example 1:

Input: nums = [4, 1, 1, 4] Output: 0 Explanation: The array is already a palindrome, so no merges are needed.

Example 2:

` Input: nums = [1, 2, 3, 4] Output: 2 Explanation:

• Merge first two elements: [3, 3, 4]
• Merge last two elements: [3, 7]
• Now we need to compare: left=3, right=7, so merge on left
• Final result takes 2 total merges Actually: [1,2,3,4] -> merge(1,2)=[3,3,4] (1 merge) Then we have left=3, right=4, left < right, so merge left with next [3,3,4] doesn't work this way... Let me recalculate: left=1, right=4 (unequal, left<right) Merge left: [3,3,4] (1 merge), now left=3, right=4 (unequal, left<right) Merge left: [6,4] (2 merges), now left=6, right=4 (unequal, left>right) This doesn't lead to palindrome properly. Let me use two-pointer correctly: Start: left=1, right=4. Since 1<4, merge left: [3,3,4] Now: left=3, right=4. Since 3<4, merge left: [6,4]
  Now: left=6, right=4. Since 6>4, this won't work either. The answer of 2 means we should get a valid sequence. `

Example 3:

Input: nums = [15, 4, 15] Output: 0 Explanation: This is already a palindrome (15, 4, 15).

Example 4:

Input: nums = [1, 1, 1, 1, 1] Output: 0 Explanation: All elements are identical, forming a palindrome.