LeetCode 2789 - Largest Element in an Array after Merge Operations

The problem gives us an array of positive integers and allows a special merge operation between adjacent elements.

leetcodemediumarraygreedy

LeetCode Problem 2789

Difficulty: 🟡 Medium
Topics: Array, Greedy

Solution

Problem Understanding

The problem gives us an array of positive integers and allows a special merge operation between adjacent elements. We may choose an index i such that:

nums[i] <= nums[i + 1]

When this condition is satisfied, we merge the two elements by adding nums[i] into nums[i + 1], then removing nums[i] from the array. In effect, the pair:

[a, b]

becomes:

[a + b]

as long as a <= b.

The goal is to maximize the value of the largest element that can appear after performing any number of valid merge operations.

The important detail is that merges only happen from left to right, because the smaller or equal left value is absorbed into the right value. This directional constraint is what makes the problem interesting.

The input size can be as large as 10^5, so any solution that repeatedly simulates all possible merge sequences will be too slow. We need a linear or near-linear algorithm.

The values themselves can be up to 10^6, and repeated merges may create very large sums. This means we must carefully use sufficiently large integer types. In Python this is automatic, but in Go we should use int64.

Several edge cases are important:

  • Arrays of length 1, where no operation is possible.
  • Strictly decreasing arrays, where no merges can ever occur.
  • Strictly increasing arrays, where everything can eventually merge into one giant value.
  • Arrays with repeated equal values, since equality is allowed in the merge condition.
  • Large cumulative sums that exceed 32-bit integer limits.

Because all numbers are positive, merged values only grow larger. This observation becomes central to the greedy solution.

Approaches

Brute Force Approach

A brute-force solution would try every possible valid merge operation recursively. At each step, we would scan the array for every index i satisfying:

nums[i] <= nums[i + 1]

For each valid merge, we create a new array state and continue exploring all future possibilities.

This approach is correct because it exhaustively checks every sequence of operations and therefore guarantees finding the maximum achievable element.

However, it is far too slow. The number of possible merge sequences grows exponentially with the array size. Even moderate inputs would produce an enormous search tree.

Since n can be 100000, brute force is completely impractical.

Key Insight

The critical observation is that merges are most naturally analyzed from right to left.

Suppose we already have a large accumulated value on the right side. If the current element on the left is less than or equal to that accumulated value, then it can eventually merge into it.

Because all numbers are positive, every successful merge increases the accumulated value, making future merges even easier.

This creates a greedy process:

  • Start from the last element.
  • Maintain the current merged value.
  • Move leftward.
  • If the current number is less than or equal to the accumulated value, merge it.
  • Otherwise, start a new accumulation.

This works because once an element cannot merge into the current accumulated value, no future operation can make it possible. The accumulated value only comes from the right side, and we are already considering the maximum possible value obtainable there.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force Exponential Exponential Tries all possible merge sequences
Optimal O(n) O(1) Greedy right-to-left accumulation

Algorithm Walkthrough

  1. Initialize a variable current_sum with the last element of the array.

We start from the rightmost element because merges always flow toward the right. 2. Initialize another variable maximum_value with current_sum.

This tracks the largest value we have seen so far. 3. Traverse the array from right to left, starting from index n - 2.

At each step, we decide whether the current element can merge into the accumulated value on its right. 4. For each element nums[i], check whether:

nums[i] <= current_sum

If this condition is true, then the current element can merge into the right segment. 5. If the merge is possible, update:

current_sum += nums[i]

This simulates repeatedly merging the current element into the accumulated right-side value. 6. Otherwise, reset:

current_sum = nums[i]

This means the current element cannot participate in the existing merged segment, so it starts a new segment. 7. After each step, update:

maximum_value = max(maximum_value, current_sum)
  1. After the traversal completes, return maximum_value.

Why it works

The algorithm maintains the invariant that current_sum represents the maximum value obtainable from a contiguous suffix ending at the current position.

When nums[i] <= current_sum, the merge condition guarantees that nums[i] can eventually be absorbed into the accumulated segment. Since all numbers are positive, every successful merge only increases the merged value, preserving future merge possibilities.

If nums[i] > current_sum, then merging is impossible because the left element is already too large. No sequence of future operations can change that fact, so we must begin a new segment.

This greedy choice is always optimal.

Python Solution

from typing import List

class Solution:
    def maxArrayValue(self, nums: List[int]) -> int:
        current_sum = nums[-1]
        maximum_value = current_sum

        for i in range(len(nums) - 2, -1, -1):
            if nums[i] <= current_sum:
                current_sum += nums[i]
            else:
                current_sum = nums[i]

            maximum_value = max(maximum_value, current_sum)

        return maximum_value

The implementation directly follows the greedy strategy.

We initialize current_sum with the last element because the rightmost value forms the initial mergeable segment.

The loop iterates backward through the array. At every position, we determine whether the current element can merge into the accumulated segment on the right.

If merging is allowed, we add the current number into current_sum. Otherwise, we reset the accumulation because the current value is too large to merge.

The variable maximum_value continuously stores the best result encountered during traversal.

The algorithm only uses a few integer variables and scans the array once, making it highly efficient.

Go Solution

func maxArrayValue(nums []int) int64 {
    n := len(nums)

    currentSum := int64(nums[n-1])
    maximumValue := currentSum

    for i := n - 2; i >= 0; i-- {
        if int64(nums[i]) <= currentSum {
            currentSum += int64(nums[i])
        } else {
            currentSum = int64(nums[i])
        }

        if currentSum > maximumValue {
            maximumValue = currentSum
        }
    }

    return maximumValue
}

The Go implementation is almost identical to the Python version, but there are a few language-specific considerations.

The most important detail is the use of int64. Repeated merges can create values much larger than a standard 32-bit integer can hold. Using int64 guarantees correctness for large inputs.

Go arrays are represented as slices, so we use len(nums) to determine the size. The backward traversal uses a standard decrementing loop.

Unlike Python, Go does not provide automatic arbitrary-precision integers, so explicit type conversion is necessary during arithmetic operations.

Worked Examples

Example 1

Input:

nums = [2,3,7,9,3]

We process from right to left.

Index nums[i] current_sum before Can Merge? current_sum after maximum_value
Start 3 - - 3 3
3 9 3 No 9 9
2 7 9 Yes 16 16
1 3 16 Yes 19 19
0 2 19 Yes 21 21

Final answer:

21

Example 2

Input:

nums = [5,3,3]
Index nums[i] current_sum before Can Merge? current_sum after maximum_value
Start 3 - - 3 3
1 3 3 Yes 6 6
0 5 6 Yes 11 11

Final answer:

11

Complexity Analysis

Measure Complexity Explanation
Time O(n) Single backward traversal of the array
Space O(1) Only a few variables are used

The algorithm visits each element exactly once and performs constant-time work per iteration. No auxiliary data structures are required, so the memory usage remains constant regardless of input size.

Test Cases

from typing import List

class Solution:
    def maxArrayValue(self, nums: List[int]) -> int:
        current_sum = nums[-1]
        maximum_value = current_sum

        for i in range(len(nums) - 2, -1, -1):
            if nums[i] <= current_sum:
                current_sum += nums[i]
            else:
                current_sum = nums[i]

            maximum_value = max(maximum_value, current_sum)

        return maximum_value

sol = Solution()

assert sol.maxArrayValue([2, 3, 7, 9, 3]) == 21  # provided example 1
assert sol.maxArrayValue([5, 3, 3]) == 11  # provided example 2

assert sol.maxArrayValue([10]) == 10  # single element array
assert sol.maxArrayValue([5, 4, 3, 2, 1]) == 5  # strictly decreasing
assert sol.maxArrayValue([1, 2, 3, 4, 5]) == 15  # strictly increasing
assert sol.maxArrayValue([3, 3, 3]) == 9  # equal values can merge
assert sol.maxArrayValue([1, 1, 1, 1]) == 4  # repeated small merges
assert sol.maxArrayValue([1000000, 1000000]) == 2000000  # large values
assert sol.maxArrayValue([8, 1, 2, 10]) == 21  # multiple chained merges
assert sol.maxArrayValue([20, 1, 1, 1]) == 20  # left value too large to merge
assert sol.maxArrayValue([4, 6, 2, 8]) == 20  # mixed merge opportunities

Test Case Summary

Test Why
[2,3,7,9,3] Validates the primary example
[5,3,3] Validates repeated merges
[10] Tests minimum array size
[5,4,3,2,1] Ensures no invalid merges occur
[1,2,3,4,5] Ensures full-array merge works
[3,3,3] Confirms equality condition works
[1,1,1,1] Tests repeated accumulation
[1000000,1000000] Tests large integer handling
[8,1,2,10] Tests chained rightward merges
[20,1,1,1] Ensures large left values remain separate
[4,6,2,8] Tests mixed merge scenarios

Edge Cases

A single-element array is the simplest edge case. Since no adjacent pair exists, no operations are possible. A careless implementation might assume at least two elements and attempt invalid indexing. This implementation handles the case naturally because the backward loop never executes.

Strictly decreasing arrays are another important case. For example:

[9, 7, 5, 3]

No element satisfies the merge condition because every left value is larger than the right value. A buggy greedy solution might incorrectly force merges. Here, the algorithm correctly resets current_sum at every step, leaving the maximum element unchanged.

Arrays with equal adjacent values can also cause mistakes if the implementation uses a strict inequality instead of <=. For example:

[3, 3, 3]

All elements should merge successfully into 9. The implementation explicitly uses <=, ensuring equal values merge correctly.

Large cumulative sums are another critical edge case. Consider:

[1000000, 1000000, 1000000, ...]

Repeated merges may exceed 32-bit integer limits. Python automatically handles arbitrary-size integers, while the Go implementation uses int64 to safely store large results.