# Java 10 lines and C++ 12 lines linear time complexity O(n) with explanation

• The approach is same as Next Greater Element I
See explanation in my solution to the previous problem
The only difference here is that we use `stack` to keep the indexes of the decreasing subsequence

Java

``````    public int[] nextGreaterElements(int[] nums) {
int n = nums.length, next[] = new int[n];
Arrays.fill(next, -1);
Stack<Integer> stack = new Stack<>(); // index stack
for (int i = 0; i < n * 2; i++) {
int num = nums[i % n];
while (!stack.isEmpty() && nums[stack.peek()] < num)
next[stack.pop()] = num;
if (i < n) stack.push(i);
}
return next;
}
``````

C++

``````    vector<int> nextGreaterElements(vector<int>& nums) {
int n = nums.size();
vector<int> next(n, -1);
stack<int> s; // index stack
for (int i = 0; i < n * 2; i++) {
int num = nums[i % n];
while (!s.empty() && nums[s.top()] < num) {
next[s.top()] = num;
s.pop();
}
if (i < n) s.push(i);
}
return next;
}
``````

• Nice solution.
We can also iterate from back to front and maintain a decreasing stack, this will reduce the times of updating result array.

``````class Solution {
public:
vector<int> nextGreaterElement(vector<int>& findNums, vector<int>& nums) {
if (findNums.empty()) return {};
int n = nums.size();
unordered_map<int, int> ng;
stack<int> st;
for (int i = n-1; i >= 0; --i) {
while (!st.empty() && st.top() < nums[i]) st.pop();
ng[nums[i]] = st.empty() ? -1 : st.top();
st.push(nums[i]);
}

int m = findNums.size();
vector<int> res(m);
for (int i = 0; i < m; ++i) res[i] = ng[findNums[i]];
return res;
}
};
``````
``````class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
if (nums.empty()) return {};
int n = nums.size();
vector<int> res(n, -1);
stack<int> st;
for (int i = 2*n-1; i >= 0; --i) {
int num = nums[i%n];
while (!st.empty() && nums[st.top()] <= num) st.pop();
res[i%n] = st.empty() ? - 1 : nums[st.top()];
st.push(i%n);
}
return res;
}
};
``````

• @yuxiangmusic

Nice and clean.

• @yuxiangmusic Very elegant solution! Thank you!

• Brilliant solution!
BTW, we can break if stack is empty:

``````public class Solution {
public int[] nextGreaterElements(int[] nums) {
int n=nums.length, ans[]=new int[n];
Arrays.fill(ans, -1);
Stack<Integer> stack=new Stack<>();
for (int i=0;i<2*n;i++) {
while (!stack.isEmpty() && nums[stack.peek()]<nums[i%n]) ans[stack.pop()]=nums[i%n];
if (i<n) stack.push(i);
if (stack.isEmpty()) break; // break if stack is empty
}
return ans;
}
}
``````

• Here is my python version.
The same as above, you can add `break` if you like.

``````def nextGreaterElements(self, nums):
stack, res = [], [-1] * len(nums)
for i in range(len(nums)) * 2:
while stack and (nums[stack[-1]] < nums[i]):
res[stack.pop()] = nums[i]
stack.append(i)
return res``````

• Thanks very much!
It's very smart to use 2*n and i%n to deal with the rotational array.

• I did something similiar, not sure which one is a better complexity~ O(n) each on a higher level

instead of traversing the array twice (push, pop etc) i am checking the max element in first iteration & later traversing n times around the max element

https://discuss.leetcode.com/topic/83998/simple-solution-step-wise-2-iterations-of-array-o-n

• We can get rid of the stack by using the output array to do the work to reach O(1) extra space.
Of course it comes with a cost that you need to transfer the index at the end, that results in 3 passes in total.
Here is my solution:
https://discuss.leetcode.com/topic/91617/simple-c-solution-o-n-time-o-1-extra-space-no-stack-using-output-array-only

• @ckcz123 Actually the stack will not be empty, because the largest number is always in.

• @vesion Why is backward faster? Is it test case dependent? I feel backward is equivalent to working forward on next smaller element.

• This post is deleted!

• same idea, mine is from end

``````    public int[] nextGreaterElements(int[] nums) {
int len = nums.length;
int[] result = new int[len];
Stack<Integer> stack = new Stack<>();
for (int i = len * 2 - 1; i >= 0; i--) {
while (!stack.isEmpty() && stack.peek() <= nums[i % len]) stack.pop();
if (i < len) result[i] = stack.isEmpty()? -1 : stack.peek();
stack.push(nums[i % len]);
}
return result;
}
``````

• @wuyangbu same is my mind

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.