LeetCode Q.2454

[StarsExpress]

https://github.com/doocs/leetcode/blob/main/solution/2400-2499/2454.Next%20Greater%20Element%20IV/README.md

Your time complexity is O(nlogn).
Time complexity can achieve O(n) by double stacks.

class Solution: def secondGreaterElement(self, nums: List[int]) -> List[int]: total_nums = len(nums) second_next_greater = [-1] * total_nums # Decreasing monotonic stacks: (num, idx). stack_1, stack_2 = [(nums[0], 0)], [] # Increasing monotonic list to transport tuples from stack 1 to stack 2. transporter = [] for current_idx in range(1, total_nums): while stack_2 and stack_2[-1][0] < nums[current_idx]: _, past_idx = stack_2.pop(-1) second_next_greater[past_idx] = nums[current_idx] while stack_1 and stack_1[-1][0] < nums[current_idx]: transporter.append(stack_1.pop(-1)) stack_2.extend(transporter[::-1]) # Ensure decreasing monotonicity. transporter.clear() stack_1.append((nums[current_idx], current_idx)) return second_next_greater 

[HARIHARANS24]

here is the solution to solve the above problem

class Solution:
def secondGreaterElement(self, nums: List[int]) -> List[int]:
total_nums = len(nums)
second_next_greater = [-1] * total_nums

 # Stack 1: elements waiting for their first greater # Stack 2: elements waiting for their second greater stack_1, stack_2 = [(nums[0], 0)], [] transporter = [] for current_idx in range(1, total_nums): # Process second greater while stack_2 and stack_2[-1][0] < nums[current_idx]: _, past_idx = stack_2.pop() second_next_greater[past_idx] = nums[current_idx] # Process first greater and move to transporter while stack_1 and stack_1[-1][0] < nums[current_idx]: transporter.append(stack_1.pop()) # Move from transporter to stack_2 stack_2.extend(reversed(transporter)) transporter.clear() # Push current element to stack_1 stack_1.append((nums[current_idx], current_idx)) return second_next_greater