Problem Statement:
Given a circular integer array nums (i.e., the next element of nums[nums.length - 1] is nums[0]), return the next greater number for every element in nums.
The next greater number of a number x is the first greater number to its traversing-order next in the array, which means you could search circularly to find its next greater number. If it doesn’t exist, return -1 for this number.
Examples:
Example 1:
Input:
nums = [1,2,1]
Output: [2,-1,2]
Explanation:The first 1’s next greater number is 2; The number 2 can’t find next greater number. The second 1’s next greater number needs to search circularly, which is also 2.
Example 2:
Input:
nums = [1,2,3,4,3]
Output: [2,3,4,-1,4]
Example 2:
Input:
temperatures = [30,40,50,60]
Output: [1,1,1,0]
Constraints:
1 <= nums.length <= 104-109 <= temperatures[i] <= 109
Approach:
- Initialize:
n = arr.lengthans = Array(n).fill(-1)→ To store result.stack = []→ To keep track of next greater candidates.
- Push last element into stack (start from end).
- Traverse from (2n - 2) to 0:
- Use i % n to simulate circular behavior.
- While stack is not empty:
- If current element < top of stack → that is the next greater, store it in
ans[i % n]and break. - Else pop the stack (since it’s not greater).
- If current element < top of stack → that is the next greater, store it in
- Push current element (arr[i % n]) onto the stack.
- Return
ans -
Time Complexity = O(n)
-
Space Complexity = O(n)
Visualisation:
Time Complexity:
Space Complexity:
Dry Run
Input:
arr = [73, 74, 75, 71, 69, 72, 76, 73]
State Transitions:
Initialize: n = 8 ans = [-1, -1, -1, -1, -1, -1, -1, -1] stack = [] Push last element → stack = [73] i = 14 → arr[6] = 76 → stack = [73] → arr[6] > top (76 > 73) → ans[6] = -1 (no change) → push 76 → stack = [76] i = 13 → arr[5] = 72 → top = 76 → arr[5] < top (72 < 76) → ans[5] = 76 → push 72 → stack = [76, 72] i = 12 → arr[4] = 69 → top = 72 → arr[4] < top (69 < 72) → ans[4] = 72 → push 69 → stack = [76, 72, 69] i = 11 → arr[3] = 71 → top = 69 → arr[3] > top → pop 69 → top = 72 → arr[3] < top → ans[3] = 72 → push 71 → stack = [76, 72, 71] i = 10 → arr[2] = 75 → top = 71 → arr[2] > top → pop 71 → top = 72 → arr[2] > top → pop 72 → top = 76 → arr[2] < top → ans[2] = 76 → push 75 → stack = [76, 75] i = 9 → arr[1] = 74 → top = 75 → arr[1] < top → ans[1] = 75 → push 74 → stack = [76, 75, 74] i = 8 → arr[0] = 73 → top = 74 → arr[0] < top → ans[0] = 74 → push 73 → stack = [76, 75, 74, 73] i = 7 → arr[7] = 73 → top = 73 → arr[7] == top → pop 73 → top = 74 → arr[7] < top → ans[7] = 74 → push 73 → stack = [76, 75, 74, 73] i = 6 → arr[6] = 76 → top = 73 → arr[6] > top → pop 73 → top = 74 → arr[6] > top → pop 74 → top = 75 → arr[6] > top → pop 75 → top = 76 → arr[6] == top → pop 76 → stack empty → ans[6] remains = -1 → push 76 → stack = [76] i = 5 → arr[5] = 72 → top = 76 → arr[5] < top → ans[5] already set → push 72 → stack = [76, 72] i = 4 → arr[4] = 69 → top = 72 → arr[4] < top → ans[4] already set → push 69 → stack = [76, 72, 69] i = 3 → arr[3] = 71 → top = 69 → arr[3] > top → pop 69 → top = 72 → arr[3] < top → ans[3] already set → push 71 → stack = [76, 72, 71] i = 2 → arr[2] = 75 → top = 71 → arr[2] > top → pop 71 → top = 72 → arr[2] > top → pop 72 → top = 76 → arr[2] < top → ans[2] already set → push 75 → stack = [76, 75] i = 1 → arr[1] = 74 → top = 75 → arr[1] < top → ans[1] already set → push 74 → stack = [76, 75, 74] i = 0 → arr[0] = 73 → top = 74 → arr[0] < top → ans[0] already set → push 73 → stack = [76, 75, 74, 73]
Final Output: [74, 75, 76, 72, 72, 76, -1, 74]
Final State: stack = [76, 75, 74, 73]
var nextGreaterElements = function(arr) {
let n = arr.length;
let stack = [];
let ans = Array(n).fill(-1);
stack.push(arr[n-1]);
for(let i=(2*n)-2; i >= 0; i--){
while(stack.length){
let top = stack[stack.length-1];
if(arr[i % n] < top){
ans[i % n] = top;
break;
} else{
stack.pop();
}
}
stack.push(arr[i % n]);
}
return ans.slice(0, n);
};
def nextGreaterElements(arr):
n = len(arr)
stack = []
ans = [-1] * n
stack.append(arr[n - 1])
for i in range(2 * n - 2, -1, -1):
while stack:
top = stack[-1]
if arr[i % n] < top:
ans[i % n] = top
break
else:
stack.pop()
stack.append(arr[i % n])
return ans
import java.util.Stack;
class Solution {
public int[] nextGreaterElements(int[] arr) {
int n = arr.length;
Stack stack = new Stack<>();
int[] ans = new int[n];
for(int i = 0; i < n; i++) ans[i] = -1;
stack.push(arr[n - 1]);
for(int i = 2 * n - 2; i >= 0; i--) {
while(!stack.isEmpty()) {
int top = stack.peek();
if(arr[i % n] < top) {
ans[i % n] = top;
break;
} else {
stack.pop();
}
}
stack.push(arr[i % n]);
}
return ans;
}
}
#include <vector>
#include <stack>
using namespace std;
vector nextGreaterElements(vector& arr) {
int n = arr.size();
stack s;
vector ans(n, -1);
s.push(arr[n - 1]);
for(int i = 2 * n - 2; i >= 0; i--) {
while(!s.empty()) {
int top = s.top();
if(arr[i % n] < top) {
ans[i % n] = top;
break;
} else {
s.pop();
}
}
s.push(arr[i % n]);
}
return ans;
}
#include <stdio.h>
#include <stdlib.h>
void nextGreaterElements(int* arr, int n, int* ans) {
int* stack = (int*)malloc(n * sizeof(int));
int topIndex = -1;
for(int i = 0; i < n; i++) ans[i] = -1;
stack[++topIndex] = arr[n - 1];
for(int i = 2 * n - 2; i >= 0; i--) {
while(topIndex >= 0) {
int top = stack[topIndex];
if(arr[i % n] < top) {
ans[i % n] = top;
break;
} else {
topIndex--;
}
}
stack[++topIndex] = arr[i % n];
}
free(stack);
}
using System;
using System.Collections.Generic;
public class Solution {
public int[] NextGreaterElements(int[] arr) {
int n = arr.Length;
Stack stack = new Stack();
int[] ans = new int[n];
Array.Fill(ans, -1);
stack.Push(arr[n - 1]);
for(int i = 2 * n - 2; i >= 0; i--) {
while(stack.Count > 0) {
int top = stack.Peek();
if(arr[i % n] < top) {
ans[i % n] = top;
break;
} else {
stack.Pop();
}
}
stack.Push(arr[i % n]);
}
return ans;
}
}
