Largest Element in an Array after Merge Operations solution and explanation
Google
9 more videos on this problem
Leetcode Weekly contest 355 - Medium - Largest Element in an Array after Merge OperationsPrakhar Agrawal · 9:59 · 1K views
6915. Largest Element in an Array after Merge Operations | leetcode Weekly Contest 355| In Comment.Optimization · 0:13 · 1K views
2789. Largest Element in an Array after Merge Operations || Weekly Contest 355 || Leetcode || HindiAshish Kumar · 6:32 · 533 views
2789. Largest Element in an Array after Merge Operations (Leetcode Medium)Programming Live with Larry · 5:15 · 453 views
Largest Element in an Array after Merge Operations | Leetcode 2789 | Greedy | Contest 355Tech Courses · 10:14 · 450 views
Largest Element in an array after merge operations | LeetCode : 2789 | Medium Level | Java | GreedyElegant Engineer · 9:22 · 356 views
Master Array in Python: LeetCode 2789. Largest Element in an Array after Merge OperationsvanAmsen · 6:14 · 68 views
Leetcode 2789 : Largest Element in an Array after Merge Operations (Medium)TechieGanesh · 6:35 · 61 views
Leetcode 2789 | Largest Element in an Array after Merge OperationsLCReviewer · 15:59 · 38 views
C++ Leetcode 2789 Largest Element in an Array after Merge Operations solution.anany pandey · 23:56 · 15 views
The problem
You are given a 0-indexed array nums consisting of positive integers.
You can do the following operation on the array any number of times:
- Choose an integer
isuch that0 <= i < nums.length - 1andnums[i] <= nums[i + 1]. Replace the elementnums[i + 1]withnums[i] + nums[i + 1]and delete the elementnums[i]from the array.
Return the value of the largest element that you can possibly obtain in the final array.
Example 1:
Input: nums = [2,3,7,9,3] Output: 21 Explanation: We can apply the following operations on the array: - Choose i = 0. The resulting array will be nums = [5,7,9,3]. - Choose i = 1. The resulting array will be nums = [5,16,3]. - Choose i = 0. The resulting array will be nums = [21,3]. The largest element in the final array is 21. It can be shown that we cannot obtain a larger element.
Example 2:
Input: nums = [5,3,3] Output: 11 Explanation: We can do the following operations on the array: - Choose i = 1. The resulting array will be nums = [5,6]. - Choose i = 0. The resulting array will be nums = [11]. There is only one element in the final array, which is 11.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 106
Approach overview
Problem Overview: You are given an array where you can repeatedly merge two adjacent elements if the left value is less than or equal to the right value. The merge replaces them with their sum. The goal is to determine the largest possible element that can appear after performing any sequence of valid merges.
Approach 1: Greedy Approach with Cumulative Merge (O(n) time, O(1) space)
This approach scans the array from right to left and greedily accumulates values when merging is valid. Maintain a running value current initialized to the last element. For each element moving left, check if nums[i] ≤ current. If true, merge them by adding the value to current. Otherwise, reset current to nums[i]. Track the maximum value seen during this process. The key insight: merging from the right guarantees that every valid chain of merges is captured without explicitly modifying the array. Time complexity is O(n) and space complexity is O(1). This solution relies on a simple greedy observation about how merges propagate. See related concepts in greedy algorithms and array problems.
Approach 2: Simulating Merge Process with Stack (O(n) time, O(n) space)
This approach explicitly simulates the merge rule using a stack. Iterate through the array and push elements onto the stack. Whenever the top two elements satisfy the condition left ≤ right, pop them and push their sum back onto the stack. Continue merging while the condition holds. The stack represents the current merged structure of the array. After processing all elements, scan the stack to find the maximum value produced. Time complexity remains O(n) because each element is pushed and popped at most once, while space complexity is O(n) due to the stack storage. This method is useful when you want a clearer simulation of the merging rules using a stack.
Recommended for interviews: The greedy right-to-left accumulation is the expected optimal solution. It reduces the entire merge process to a single pass and constant memory. Showing the stack simulation first demonstrates you understand the merge mechanics, but implementing the greedy insight proves stronger algorithmic intuition.
Approach 1: Greedy Approach with Cumulative Merge
This approach focuses on sequentially merging elements in the array by iterating from left to right. If a current element is less than or equal to the successor, they are merged. This operation continues until the end of the array is reached. This approach ensures that the maximum value is obtained by accumulating the largest possible total from each consecutive merge.
def find_largest_element(nums):
max_element = nums[0]
for i in range(len(nums) - 1):
if nums[i] <= nums[i + 1]:
nums[i + 1] += nums[i]
max_element = max(max_element, nums[i + 1])
return max_element
nums = [2, 3, 7, 9, 3]
print(find_largest_element(nums))public class LargestElementArray {
public static int findLargestElement(int[] nums) {
int maxElement = nums[0];
for (int i = 0; i < nums.length - 1; i++) {
if (nums[i] <= nums[i + 1]) {
nums[i + 1] += nums[i];
}
maxElement = Math.max(maxElement, nums[i + 1]);
}
return maxElement;
}
public static void main(String[] args) {
int[] nums = {2, 3, 7, 9, 3};
System.out.println(findLargestElement(nums));
}
}#include <vector>
#include <iostream>
int findLargestElement(std::vector<int>& nums) {
int maxElement = nums[0];
for (size_t i = 0; i < nums.size() - 1; ++i) {
if (nums[i] <= nums[i + 1]) {
nums[i + 1] += nums[i];
}
maxElement = std::max(maxElement, nums[i + 1]);
}
return maxElement;
}
int main() {
std::vector<int> nums = {2, 3, 7, 9, 3};
std::cout << findLargestElement(nums);
return 0;
}function findLargestElement(nums) {
let maxElement = nums[0];
for (let i = 0; i < nums.length - 1; i++) {
if (nums[i] <= nums[i + 1]) {
nums[i + 1] += nums[i];
}
maxElement = Math.max(maxElement, nums[i + 1]);
}
return maxElement;
}
const nums = [2, 3, 7, 9, 3];
console.log(findLargestElement(nums));#include <stdio.h>
int findLargestElement(int* nums, int numsSize) {
int maxElement = nums[0];
for (int i = 0; i < numsSize - 1; ++i) {
if (nums[i] <= nums[i + 1]) {
nums[i + 1] += nums[i];
}
if (nums[i + 1] > maxElement) {
maxElement = nums[i + 1];
}
}
return maxElement;
}
int main() {
int nums[] = {2, 3, 7, 9, 3};
int numsSize = sizeof(nums) / sizeof(nums[0]);
printf("%d", findLargestElement(nums, numsSize));
return 0;
}using System;
class LargestElementArray {
public static int FindLargestElement(int[] nums) {
int maxElement = nums[0];
for (int i = 0; i < nums.Length - 1; i++) {
if (nums[i] <= nums[i + 1]) {
nums[i + 1] += nums[i];
}
maxElement = Math.Max(maxElement, nums[i + 1]);
}
return maxElement;
}
static void Main(string[] args) {
int[] nums = {2, 3, 7, 9, 3};
Console.WriteLine(FindLargestElement(nums));
}
}This Python function efficiently merges elements of the list in-place by updating subsequent elements when the condition 'nums[i] <= nums[i + 1]' is met. As it traverses the list, it updates the maximum seen value for use as the result.
Time Complexity: O(n)
Space Complexity: O(1) (modifies input in place)
Approach 2: Simulating Merge Process with Stack
This approach uses a stack to simulate merging operations. By utilizing stack operations (push and pop), we can easily manage merges and keep track of the cumulative sum of merged elements. This method is more intuitive for some as it reflects the explicit merges rather than relying on in-place modifications.
def find_largest_element_with_stack(nums):
stack = []
for num in nums:
while stack and stack[-1] <= num:
num += stack.pop()
stack.append(num)
return max(stack)
nums = [2, 3, 7, 9, 3]
print(find_largest_element_with_stack(nums))import java.util.Stack;
public class LargestElementStack {
public static int findLargestElementWithStack(int[] nums) {
Stack<Integer> stack = new Stack<>();
for (int num : nums) {
while (!stack.isEmpty() && stack.peek() <= num) {
num += stack.pop();
}
stack.push(num);
}
int maxElement = 0;
while (!stack.isEmpty()) {
maxElement = Math.max(maxElement, stack.pop());
}
return maxElement;
}
public static void main(String[] args) {
int[] nums = {2, 3, 7, 9, 3};
System.out.println(findLargestElementWithStack(nums));
}
}#include <vector>
#include <iostream>
#include <stack>
int findLargestElementWithStack(std::vector<int>& nums) {
std::stack<int> s;
for (int num : nums) {
while (!s.empty() && s.top() <= num) {
num += s.top();
s.pop();
}
s.push(num);
}
int maxElement = 0;
while (!s.empty()) {
maxElement = std::max(maxElement, s.top());
s.pop();
}
return maxElement;
}
int main() {
std::vector<int> nums = {2, 3, 7, 9, 3};
std::cout << findLargestElementWithStack(nums);
return 0;
}function findLargestElementWithStack(nums) {
const stack = [];
for (let num of nums) {
while (stack.length > 0 && stack[stack.length - 1] <= num) {
num += stack.pop();
}
stack.push(num);
}
return Math.max(...stack);
}
const nums = [2, 3, 7, 9, 3];
console.log(findLargestElementWithStack(nums));#include <stdio.h>
#define MAX_SIZE 100000
int findLargestElementWithStack(int* nums, int numsSize) {
int stack[MAX_SIZE];
int top = -1;
for (int i = 0; i < numsSize; ++i) {
while (top != -1 && stack[top] <= nums[i]) {
nums[i] += stack[top--];
}
stack[++top] = nums[i];
}
int maxElement = 0;
for (int i = 0; i <= top; ++i) {
if (stack[i] > maxElement) {
maxElement = stack[i];
}
}
return maxElement;
}
int main() {
int nums[] = {2, 3, 7, 9, 3};
int numsSize = sizeof(nums) / sizeof(nums[0]);
printf("%d", findLargestElementWithStack(nums, numsSize));
return 0;
}using System;
using System.Collections.Generic;
class LargestElementStack {
public static int FindLargestElementWithStack(int[] nums) {
Stack<int> stack = new Stack<int>();
foreach (int num in nums) {
int elem = num;
while (stack.Count > 0 && stack.Peek() <= elem) {
elem += stack.Pop();
}
stack.Push(elem);
}
int maxElement = 0;
foreach (int stackElement in stack) {
maxElement = Math.Max(maxElement, stackElement);
}
return maxElement;
}
static void Main(string[] args) {
int[] nums = {2, 3, 7, 9, 3};
Console.WriteLine(FindLargestElementWithStack(nums));
}
}This Python solution logically tracks and orderly manages the amalgamation of integers using a stack paradigm, which efficiently handles the popping and pushing of merged numbers while subsequently maintaining a running tally of the largest figure obtained throughout the iterative merge summation.
Time Complexity: O(n)
Space Complexity: O(n) with stack handling.
Approach 3: Merge in Reverse Order
According to the problem description, in order to maximize the maximum element in the merged array, we should merge the elements on the right first, making the elements on the right as large as possible, so as to perform as many merge operations as possible and finally get the maximum element.
Therefore, we can traverse the array from right to left. For each position i, where i \in [0, n - 2], if nums[i] leq nums[i + 1], we update nums[i] to nums[i] + nums[i + 1]. Doing so is equivalent to merging nums[i] and nums[i + 1] and deleting nums[i].
In the end, the maximum element in the array is the maximum element in the merged array.
The time complexity is O(n), where n is the length of the array. The space complexity is O(1).
function maxArrayValue(nums: number[]): number {
for (let i = nums.length - 2; i >= 0; --i) {
if (nums[i] <= nums[i + 1]) {
nums[i] += nums[i + 1];
}
}
return Math.max(...nums);
}func maxArrayValue(nums []int) int64 {
n := len(nums)
ans, t := nums[n-1], nums[n-1]
for i := n - 2; i >= 0; i-- {
if nums[i] <= t {
t += nums[i]
} else {
t = nums[i]
}
ans = max(ans, t)
}
return int64(ans)
}Complexity comparison
| Approach | Complexity |
|---|---|
| Greedy Approach with Cumulative Merge | Time Complexity: O(n) |
| Simulating Merge Process with Stack | Time Complexity: O(n) |
| Merge in Reverse Order | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Cumulative Merge (Right-to-Left) | O(n) | O(1) | Best general solution; minimal memory and fastest implementation |
| Stack-based Merge Simulation | O(n) | O(n) | Useful when explicitly simulating merge behavior or explaining the process step-by-step |
Frequently asked questions
Is Largest Element in an Array after Merge Operations easy or hard?
The problem is rated Medium because the merge rule appears to require simulation, but the optimal solution relies on a greedy observation. Recognizing that right-to-left accumulation captures all valid merges is the key insight.
Largest Element in an Array after Merge Operations Python/Java solution
Most implementations use the greedy right-to-left scan. In Python or Java, maintain a running sum initialized with the last element and iterate backward through the array. Merge when the current value is less than or equal to the running sum, otherwise reset it.
How to solve Largest Element in an Array after Merge Operations in O(n)?
Traverse the array from right to left and keep a running value representing the current merged segment. If nums[i] is less than or equal to the running value, add it to the running sum. Otherwise, reset the running value to nums[i]. Track the maximum value seen during the traversal.
What is the best approach for Largest Element in an Array after Merge Operations?
The optimal approach is a greedy right-to-left traversal that cumulatively merges values. If the current element is less than or equal to the accumulated value, you merge them by adding it. Otherwise, you reset the accumulator. This runs in O(n) time and O(1) space and avoids explicitly simulating merges.
Is Largest Element in an Array after Merge Operations asked at Google/Amazon/Meta?
This problem reflects patterns commonly seen in Google and Amazon interviews, especially greedy array processing and merge simulation questions. Variants involving cumulative merging or monotonic processing appear in technical screens and online assessments.
What data structure is used in Largest Element in an Array after Merge Operations?
The optimal solution uses only a variable to track the cumulative merged value, making it a greedy array traversal. An alternative implementation uses a stack to simulate the merge process explicitly, which helps visualize how adjacent elements combine.
What is the time complexity of Largest Element in an Array after Merge Operations?
The optimal greedy solution runs in O(n) time because the array is scanned once from right to left. Each element participates in at most one merge decision. Space complexity is O(1) since only a running sum and maximum value are stored.