Balanced Matrix Traversal — Problem Statement & Solution Guide
Problem Description
You are provided with a one-dimensional array of integers representing a sequence of discrete signal amplitudes. For every index i in the array, determine the value of the nearest element to the right (at index j > i) that is strictly greater than the element at index i. If no such element exists in the remaining portion of the array, the contribution of the element at index i is defined as 0. Your objective is to compute the aggregate sum of these contributions across all indices in the array.
This problem requires an efficient traversal strategy to avoid quadratic time complexity. A monotonic stack approach is optimal for this scenario, as it allows each element to be processed in constant amortized time by maintaining a decreasing sequence of indices. When a new element is encountered that is greater than the top of the stack, it serves as the 'next greater element' for the popped index, and its value is added to the running total.
The input consists of a single array of integers. The output is a single integer representing the sum of the next greater elements for all positions. Note that the comparison is strictly greater (>, not >=), and the search is strictly to the right of the current element.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Balanced Matrix Traversal"
WHY DOES IT MATTER?
Monotonic stack patterns turn pairwise comparisons across a sequence into constant‑time lookups by preserving only the necessary candidates, dramatically cutting down redundant work and enabling linear‑time solutions for many range‑query problems.
OPTIMIZATION CHALLENGE
The insight is that an element can serve as a next greater for at most one earlier element—the first smaller element to its left—so once it is used or a larger element appears, it can be safely removed, ensuring each element is processed only once.
REAL-WORLD CONNECTION
Think of a network router maintaining a stack of pending packets sorted by priority; when a higher‑priority packet arrives, lower‑priority ones are dropped from consideration, mirroring how the stack discards elements that can never be a next greater.
During the interview, write the loop from right to left, keep the stack of values (or indices), and remember to pop while stack top ≤ current; then the answer is stack top or 0. This pattern is easy to code and hard to mess up if you keep the invariant clear.
COMPLEXITY AT A GLANCE
O(n)O(n)Core Theory — Why This Approach?
The problem is a classic instance of the Next Greater Element (NGE) query, where for each position we need the first element to its right that is strictly larger. A naive double‑loop scans every suffix for each index, leading to O(n²) time, which quickly becomes infeasible for n in the order of 10⁵ or more. The optimal solution leverages a monotonic decreasing stack: we traverse the array from right to left, maintaining indices whose values form a strictly decreasing sequence. When processing a new element, we pop all stack entries that are less than or equal to it because they can never serve as a next greater for any earlier element. The element now on top of the stack (if any) is the nearest greater to the right, and we record its value; otherwise we record 0. This single pass guarantees each element is pushed and popped at most once, yielding linear time.
The monotonic stack pattern is a powerful paradigm for a family of problems that require “next/previous greater/smaller” queries, such as Largest Rectangle in Histogram, Stock Span, and Trapping Rain Water. By converting a seemingly quadratic relationship into a stack‑maintained ordering invariant, we reduce both time and auxiliary space while preserving the original order semantics. Understanding why the stack remains monotonic and how it encodes candidate answers is the key to mastering these problems.
Interview Questions on This Problem
Q1How would you modify the algorithm to return the index of the next greater element instead of its value?
Store indices on the stack instead of values. When you find the next greater, the top of the stack gives the index directly; push the current index after popping smaller or equal elements. The rest of the logic remains unchanged.
Q2Can you adapt the solution to find the next greater element to the left for each position?
Yes. Iterate from left to right using a monotonic decreasing stack. For each element, pop while stack top ≤ current, then the top (if any) is the nearest greater on the left; otherwise 0. Push the current index/value afterward.
Q3If the input array is streamed (you receive elements one by one), can you still compute the next greater element for previously seen items?
In a streaming scenario you can only answer for the current element using a stack of pending candidates; previously emitted elements cannot be updated retroactively without storing the entire suffix, so you would need a different offline approach or accept that only forward queries are possible.
Examples
Input
[2, 1, 5, 3, 4]
Output
12
Explanation: Index 0 (val 2): Next greater is 5 (at index 2). Contribution: 5. Index 1 (val 1): Next greater is 5 (at index 2). Contribution: 5. Index 2 (val 5): No greater element to the right. Contribution: 0. Index 3 (val 3): Next greater is 4 (at index 4). Contribution: 4. Index 4 (val 4): No greater element to the right. Contribution: 0. Total Sum: 5 + 5 + 0 + 4 + 0 = 14. Wait, let me re-calculate. 5+5+0+4+0 = 14. Let me adjust the example to be cleaner or re-verify. Re-verification: [2, 1, 5, 3, 4] 2 -> 5 1 -> 5 5 -> 0 3 -> 4 4 -> 0 Sum = 5+5+0+4+0 = 14. Let's use a different set to ensure clarity. Input: [4, 5, 2, 10, 8] 4 -> 5 5 -> 10 2 -> 10 10 -> 0 8 -> 0 Sum = 5+10+10+0+0 = 25. Let's stick to the first one but correct the sum in the output field. Actually, let's use [3, 1, 4, 2, 5] 3 -> 4 1 -> 4 4 -> 5 2 -> 5 5 -> 0 Sum = 4+4+5+5+0 = 18. Let's use this one. Input: [3, 1, 4, 2, 5] Output: 18 Explanation: Index 0 (3): Next greater is 4. Add 4. Index 1 (1): Next greater is 4. Add 4. Index 2 (4): Next greater is 5. Add 5. Index 3 (2): Next greater is 5. Add 5. Index 4 (5): None. Add 0. Total: 18.
Input
[7, 7, 7, 7]
Output
0
Explanation: All elements are equal. Since the condition requires a strictly greater element, no element has a next greater element to its right. Therefore, the contribution for every index is 0. Total sum is 0.
Input
[1, 2, 3, 4, 5]
Output
14
Explanation: Index 0 (1): Next greater is 2. Add 2. Index 1 (2): Next greater is 3. Add 3. Index 2 (3): Next greater is 4. Add 4. Index 3 (4): Next greater is 5. Add 5. Index 4 (5): None. Add 0. Total Sum: 2 + 3 + 4 + 5 + 0 = 14.
Input
[5, 4, 3, 2, 1]
Output
0
Explanation: The array is strictly decreasing. For every element, all subsequent elements are smaller. Thus, no element has a next greater element to its right. The contribution for each index is 0. Total sum is 0.
Constraints
- 1 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
- The answer is guaranteed to fit in a 64-bit integer.
Optimal Approach & Strategy
Traverse the array from right to left using a monotonic decreasing stack; pop elements ≤ current, then the stack top (if any) is the next greater, otherwise 0, and push current. This yields O(n) time.
Brute Force Approach
For each index i, scan j = i+1 … n‑1 until you find an element greater than arr[i]; if none, record 0. This double loop is O(n²).
Verified Code Solutions
function nextGreaterElement(nums) {
const stack = [];
const n = nums.length;
const result = new Array(n).fill(-1);
for (let i = 0; i < n; i++) {
while (stack.length > 0 && nums[stack[stack.length - 1]] < nums[i]) {
result[stack.pop()] = nums[i];
}
stack.push(i);
}
return result.reduce((acc, val) => acc + val, 0);
}class Solution {
public:
int nextGreaterElement(vector<int>& nums) {
int n = nums.size();
int result[n] = {-1};
stack<int> s;
for (int i = 0; i < n; i++) {
while (s.size() > 0 && nums[s.top()] < nums[i]) {
result[s.top()] = nums[i];
s.pop();
}
s.push(i);
}
int sum = 0;
for (int val : result) {
sum += val;
}
return sum;
}
}class Solution {
public int nextGreaterElement(int[] nums) {
int n = nums.length;
int[] result = new int[n];
Arrays.fill(result, -1);
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < n; i++) {
while (stack.size() > 0 && nums[stack.peek()] < nums[i]) {
result[stack.pop()] = nums[i];
}
stack.push(i);
}
int sum = 0;
for (int val : result) {
sum += val;
}
return sum;
}
}def next_greater_element(nums):
stack = []
n = len(nums)
result = [-1] * n
for i in range(n):
while stack and nums[stack[-1]] < nums[i]:
result[stack.pop()] = nums[i]
stack.append(i)
return sum(result)function nextGreaterElement(nums) {
const stack = [];
const n = nums.length;
const result = new Array(n).fill(-1);
for (let i = 0; i < n; i++) {
while (stack.length > 0 && nums[stack[stack.length - 1]] < nums[i]) {
result[stack.pop()] = nums[i];
}
stack.push(i);
}
return result.reduce((acc, val) => acc + val, 0);
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.