# Java 1pass O(n)time & O(n)space solution beats 99%

• ``````public class Solution {
public int[] nextGreaterElements(int[] nums) {
int[] r = new int[nums.length];
if(nums.length == 0) return r;
Arrays.fill(r, -1);
int[] N = new int[nums.length];
int[] P = new int[nums.length];
N[0] = nums[0];
P[0] = 0;
int p = 0, l = 2 * r.length;
for(int i = 1; i < l - 1; ++i){
int ri = i % r.length;
if(nums[ri] <= N[p]){
if(++p >= r.length) break;
N[p] = nums[ri];
P[p] = ri;
} else {
while(p >= 0 && N[p] < nums[ri]){
r[P[p]] = nums[ri];
--p;
}
N[++p] = nums[ri];
P[p] = ri;
}
}
return r;
}
}
``````

• Nice!

I came to a similar solution but my code is not nearly as concise.

This code beats 99.34%.

``````public class Solution {
public int[] nextGreaterElements(int[] nums) {
if (nums.length == 0) return nums;
int[] dp = new int[nums.length];
int index = findMax(nums);
dp[index] = -1;
int i=index-1;
if (i < 0) i = nums.length-1;
while (i != index) {
findNext(dp, nums, i);
i--; if (i < 0) i = nums.length-1;
}
for (int j=0; j<nums.length; j++) {
dp[j] = (dp[j] == -1) ? -1 : nums[dp[j]];
}
return dp;
}
private void findNext(int[] dp, int[] nums, int i) {
int j = (i+1) % nums.length;
while (j != i) {
if (j != -1 && nums[j] <= nums[i]){
j = dp[j];
}
else break;
}
dp[i] = j;
}
private int findMax(int[] nums) {
int max = Integer.MIN_VALUE;
int index = 0;
for (int i=0; i<nums.length; i++) {
if (nums[i] > max) {
index = i;
max = nums[i];
}
}
return index;
}
}
``````

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