Next Greater Element I
Next Greater Element I is a easy monotonic stack problem solved with the monotonic stack pattern.
The best approach, optimal (monotonic stack + map), runs in O(m + n) time and O(n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force up.
Problem
For each value x in nums1, find where x appears in nums2 and return the first larger value to its right in nums2, or -1 if there is none. All values are distinct and nums1 is a subset of nums2.
Examples
Example 1
- Input
nums1 = [2, 5], nums2 = [3, 2, 7, 5]- Output
[7, -1]- Why
- After 2 in nums2 comes 7. Nothing greater follows 5.
Example 2
- Input
nums1 = [1], nums2 = [1, 4]- Output
[4]
Constraints
1 <= nums1.length <= nums2.length <= 1000- All values are distinct; nums1 is a subset of nums2.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 10 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Animated walkthrough
A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.
Concepts first, then the problem and every approach, step by step.
Space to play or pause · ← → to jump a step · click or drag the bar to seek
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force | O(m · n) | O(1) |
| Optimal (monotonic stack + map) | O(m + n) | O(n) |
1Brute force
O(m · n)O(1)For each value of nums1, find it in nums2 and scan right for the first larger value.
- Locate x in nums2.
- Scan to the right for the first value > x.
class Solution {
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
int[] out = new int[nums1.length];
for (int i = 0; i < nums1.length; i++) {
out[i] = -1;
int j = 0;
while (nums2[j] != nums1[i]) j++;
for (j++; j < nums2.length; j++)
if (nums2[j] > nums1[i]) { out[i] = nums2[j]; break; }
}
return out;
}
}class Solution:
def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
out = [0] * len(nums1)
for i in range(len(nums1)):
out[i] = -1
j = 0
while nums2[j] != nums1[i]:
j += 1
for j in range(j + 1, len(nums2)):
if nums2[j] > nums1[i]:
out[i] = nums2[j]
break
return outclass Solution {
public:
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
vector<int> out(nums1.size());
for (int i = 0; i < (int)nums1.size(); i++) {
out[i] = -1;
int j = 0;
while (nums2[j] != nums1[i]) j++;
for (j++; j < (int)nums2.size(); j++)
if (nums2[j] > nums1[i]) { out[i] = nums2[j]; break; }
}
return out;
}
};function nextGreaterElement(nums1, nums2) {
const out = new Array(nums1.length);
for (let i = 0; i < nums1.length; i++) {
out[i] = -1;
let j = 0;
while (nums2[j] !== nums1[i]) j++;
for (j++; j < nums2.length; j++)
if (nums2[j] > nums1[i]) { out[i] = nums2[j]; break; }
}
return out;
}2Optimal (monotonic stack + map)
O(m + n)Each value is pushed and popped once.O(n)Scan nums2 keeping a stack of values still waiting for a greater element; it stays decreasing. When a larger value arrives, it is the answer for every smaller value it pops. Store answers in a map and look up nums1.
- For each x in nums2: while stack top < x, map[pop()] = x. Push x.
- out[i] = map.getOrDefault(nums1[i], -1).
class Solution {
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
Map<Integer, Integer> next = new HashMap<>();
Deque<Integer> st = new ArrayDeque<>();
for (int x : nums2) {
while (!st.isEmpty() && st.peek() < x) next.put(st.pop(), x);
st.push(x);
}
int[] out = new int[nums1.length];
for (int i = 0; i < nums1.length; i++) out[i] = next.getOrDefault(nums1[i], -1);
return out;
}
}class Solution:
def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
next = {}
st = []
for x in nums2:
while st and st[-1] < x:
next[st.pop()] = x
st.append(x)
out = [0] * len(nums1)
for i in range(len(nums1)):
out[i] = next.get(nums1[i], -1)
return outclass Solution {
public:
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
unordered_map<int, int> next;
vector<int> st;
for (int x : nums2) {
while (!st.empty() && st.back() < x) { next[st.back()] = x; st.pop_back(); }
st.push_back(x);
}
vector<int> out(nums1.size());
for (int i = 0; i < (int)nums1.size(); i++) {
auto it = next.find(nums1[i]);
out[i] = it != next.end() ? it->second : -1;
}
return out;
}
};function nextGreaterElement(nums1, nums2) {
const next = new Map();
const st = [];
for (const x of nums2) {
while (st.length > 0 && st[st.length - 1] < x) next.set(st.pop(), x);
st.push(x);
}
const out = new Array(nums1.length);
for (let i = 0; i < nums1.length; i++) out[i] = next.has(nums1[i]) ? next.get(nums1[i]) : -1;
return out;
}Edge cases to test
- The last element of nums2 (always -1)
- A decreasing nums2 (all -1)
Hints
Hint 1
Compute the next greater element for every value of nums2 once, then look them up.
FAQ
What is the best time complexity for Next Greater Element I?
Optimal (monotonic stack + map) runs in O(m + n) time and O(n) extra space. Each value is pushed and popped once.
Which pattern does Next Greater Element I use?
It is a monotonic stack problem that uses the monotonic stack pattern. Other problems with the same pattern: Daily Temperatures, Next Greater Element II, Largest Rectangle in Histogram.
Is there a brute force solution for Next Greater Element I?
Yes. Brute force takes O(m · n) time and O(1) space. For each value of nums1, find it in nums2 and scan right for the first larger value.
Which edge cases should I test for Next Greater Element I?
The last element of nums2 (always -1); A decreasing nums2 (all -1).