#116

Next Larger Element

medium

arraystackmonotonic-stack

Given an integer array nums, return an array answer of the same length where answer[i] is the next larger element to the right of nums[i].

The next larger element of nums[i] is the first value that appears after index i and is strictly greater than nums[i]. If no such value exists, answer[i] is -1.

Example

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

Output: [4,2,4,-1,-1]

2 is answered by the later 4; 1 by the 2 to its right; 4 and the trailing 3 have nothing larger ahead.

Constraints

0 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9

Intuition

The obvious approach: for each index, walk forward until you hit a strictly larger value, and record it (or -1 if you fall off the end).

function nextLargerToRight(nums) {
  const answer = new Array(nums.length).fill(-1);
  for (let i = 0; i < nums.length; i++) {
    // Look rightward for the first value that beats nums[i].
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[j] > nums[i]) { answer[i] = nums[j]; break; }
    }
  }
  return answer;
}

Brute force — scan the suffix for each element: O(n²).

On a sorted-descending input every suffix scan runs to the end, so this is O(n²). Can we do better?

The key observation: when we reach a value, it can immediately answer every earlier value it exceeds — and those earlier values are exactly the ones still waiting, in decreasing order. Holding “elements still waiting for a larger neighbour, most-recent on top” is a [monotonic stack](/study-guide/algos/topic/stacks).

Keep a stack of indices whose values decrease down the stack. For each new value, pop every waiting index whose value it beats — the current value is their next-larger — then push the current index. Anything still on the stack at the end never met anything larger and keeps -1.

Walking it through (the stack below holds the waiting indices):

nums = [2, 1, 2, 4, 3]

i↓

1 < 2 → push 1

Index 0 (value 2) is already waiting. Value 1 doesn't beat it, so it waits too. Stack: [0, 1].

i↓

2 > 1 → pop 1, answer[1]=2; 2 == 2 → stop

Value 2 beats the waiting 1 (answer[1]=2) but not the equal 2 at index 0 (strictly greater only). Push 2. Stack: [0, 2].

i↓

4 > 2 and 4 > 2 → pop 2 and 0, answer[2]=4, answer[0]=4

Value 4 clears both waiting 2's at once. Push 3. Stack: [3].

i↓

3 < 4 → push 4

Value 3 can't beat the waiting 4, so it joins the queue. Stack: [3, 4].

scan ends → indices 3, 4 keep -1

Values 4 and 3 never met anything larger to their right. answer = [4, 2, 4, -1, -1].

Optimization

Monotonic decreasing stack

Keep a stack of indices whose values are still waiting for a larger element to their right, ordered so their values strictly decrease down the stack. Walk left to right: while the current value is greater than the value at the index on top of the stack, that index has just found its next-larger element — pop it and record the current value. Then push the current index.

Each index is pushed and popped at most once, so the scan is O(n). Any indices left on the stack at the end never found a larger element and keep their -1.

O(n) time, O(n) space.

function nextLargerToRight(nums) {
  const answer = new Array(nums.length).fill(-1);
  const stack = []; // indices whose next-larger is still unknown
  for (let i = 0; i < nums.length; i++) {
    // Current value resolves every smaller value waiting on the stack.
    while (stack.length > 0 && nums[i] > nums[stack[stack.length - 1]]) {
      answer[stack.pop()] = nums[i];
    }
    stack.push(i);
  }
  return answer;
}

Complexity analysis

Time complexity: O(n). Here's why:

The outer loop visits each index once.
The inner while pops indices, but each index is pushed once and popped at most once across the whole run.

So the total push/pop work is bounded by n, making the scan O(n) — even though the nested while reads like it could be quadratic. The brute force's per-element suffix scan is the O(n²) it replaces.

Space complexity: O(n). Here's why:

The stack holds indices still waiting for a larger value.
A strictly decreasing input (e.g. [5, 4, 3, 2, 1]) never pops until the end, so every index is on the stack at once.

So the stack reaches n entries in the worst case — O(n). The output array is the required result, not counted as auxiliary space.

Test cases

Beyond the example above, these are worth thinking through before you submit.

Input	Expected output	Description
nums = []	[]	Empty input — empty result, returned before the loop runs.
nums = [9]	[-1]	Single element — nothing to its right, so -1.
nums = [3,3,3]	[-1,-1,-1]	All equal — strictly greater is never satisfied, so all -1.
nums = [1,2,3]	[2,3,-1]	Strictly increasing — each value's answer is its right neighbor.
nums = [5,4,3,2,1]	[-1,-1,-1,-1,-1]	Strictly decreasing — the stack never pops; everything stays -1.
nums = [2,1,2,4,3]	[4,2,4,-1,-1]	Mixed — one large value resolves several waiting smaller ones at once.

Try it yourself

Write your solution against the real judge before checking the reference.

Open in editor