Largest Element in an Array after Merge Operations

Largest Element in an Array after Merge Operations - Problem

Array Greedy Medium

You are given a 0-indexed array nums consisting of positive integers.

You can perform the following operation on the array any number of times:

Choose an index i such that 0 <= i < nums.length - 1 and nums[i] <= nums[i + 1]
Replace the element nums[i + 1] with nums[i] + nums[i + 1] and delete the element nums[i] from the array

Return the largest element that you can possibly obtain in the final array after performing the merge operations optimally.

Input & Output

Example 1 — Basic Merging

$ Input: nums = [2,1,3,4]

› Output: 10

💡 Note: Working right-to-left: Start with 4. Since 3 ≤ 4, merge to get 7. Since 1 ≤ 7, merge to get 8. Since 2 ≤ 8, merge to get 10. Final answer is 10.

Example 2 — Cannot Merge All

$ Input: nums = [5,3,3]

› Output: 6

💡 Note: Start with 3. Since 3 ≤ 3, merge to get 6. Since 5 > 6, cannot merge. Maximum between 5 and 6 is 6.

Example 3 — Single Element

$ Input: nums = [1]

› Output: 1

💡 Note: Only one element, so the maximum possible value is 1.

Constraints

1 ≤ nums.length ≤ 10⁵
1 ≤ nums[i] ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input Array

Array [2,1,3,4] with merge rule: left ≤ right

Valid Merges

Find positions where nums[i] ≤ nums[i+1]

Optimal Result

Maximum possible value after all beneficial merges

Key Takeaway

🎯 Key Insight: Process from right to left - each element can absorb all smaller elements to its left

Asked in

G Google 45 a Amazon 38 M Microsoft 32 f Meta 28

The key insight is to process the array from right to left. Each element can potentially absorb all smaller elements to its left through merge operations. The optimal greedy approach achieves O(n) time and O(1) space by maintaining the current accumulated value and tracking the maximum seen.

Common Approaches

Approach	Time	Space	Notes
✓ Greedy Right-to-Left	O(n)	O(1)	Process array from right to left, greedily absorbing smaller elements
Brute Force Simulation	O(2ⁿ)	O(n)	Try all possible merge operations until no more merges are possible

Greedy Right-to-Left — Algorithm Steps

Start from the rightmost element
Move left, checking if current element can merge with the accumulated value
If current ≤ accumulated, merge them
Track the maximum value seen

Visualization

Tap to expand

Step-by-Step Walkthrough

Start Right

Begin with rightmost element as current value

Move Left

Check if left element can merge (left ≤ current)

Merge or Reset

Either absorb left element or start new sequence

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

long long solution(int* nums, int size) {
    if (size == 0) return 0;
    
    // Start from the rightmost element
    long long current = nums[size - 1];
    long long maxVal = current;
    
    // Process from right to left
    for (int i = size - 2; i >= 0; i--) {
        if (nums[i] <= current) {
            // Can merge: nums[i] gets absorbed into current
            current += nums[i];
        } else {
            // Cannot merge: start new sequence from nums[i]
            current = nums[i];
        }
        
        if (current > maxVal) {
            maxVal = current;
        }
    }
    
    return maxVal;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int size = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[size++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    printf("%lld\n", solution(nums, size));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through the array from right to left

✓ Linear Growth

Space Complexity

O(1)

Only using a few variables to track current and maximum values

✓ Linear Space

23.4K Views

Medium Frequency

~25 min Avg. Time

847 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy Right-to-Left — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler