Sequence Diagram and Pseudocode - Next Greater Element II

Here is solutions for Sequence Diagram and Pseudocode - Next Greater Element II.

1. Sequence Diagram

sequenceDiagram
    actor User
    participant S as Solution
    participant A as nums[]
    participant St as Stack
    participant Ans as answer[]

    User->>S: nextGreaterElements(nums)

    Note over S: IDEA 1: We need to find the first greater element<br/>to the right of every element.

    S->>S: n = len(nums)
    S->>Ans: answer = [-1] * n
    S->>St: stack = []

    Note over S,Ans: Why initialize answer with -1?<br/>-1 means "no greater element found yet".

    Note over S,St: IDEA 2: A normal array ends at n-1,<br/>but this problem is CIRCULAR.<br/>After the last element, we continue from index 0.

    S->>S: Iterate i = 2n-1 down to 0

    Note over S: Why iterate 2n times?<br/>Imagine nums is duplicated:<br/>[1,2,1] → [1,2,1,1,2,1]<br/>This lets elements near the end see elements at the beginning.

    loop i = 2n-1 down to 0

        S->>A: current = nums[i % n]
        A-->>S: current

        Note over A,S: Why i % n?<br/>i can be >= n, but nums only has n elements.<br/>Modulo maps the "virtual doubled array"<br/>back to the real circular array.

        loop while stack not empty AND nums[stack.top] <= current

            Note over S,St: IDEA 3: Remove elements that CANNOT be the answer.<br/>If stack.top <= current,<br/>current is already greater than it.<br/>So stack.top will never help any earlier element.

            S->>St: pop()
            St-->>S: discard smaller/equal element
        end

        Note over S,St: After popping,<br/>the stack top is the FIRST candidate<br/>to the right that is greater than current.

        alt i < n

            Note over S: Why only i < n?<br/>The second traversal exists only to provide<br/>future candidates for the original elements.<br/>We don't want to overwrite answers twice.

            alt stack is not empty

                S->>St: peek()
                St-->>S: index of next greater element

                S->>Ans: answer[i] = nums[stack.top]

                Note over Ans: The remaining stack top is the nearest<br/>greater element to the right.

            else stack is empty

                S->>Ans: answer[i] = -1

                Note over Ans: No greater element exists<br/>in the circular array.
            end
        end

        Note over S,St: IDEA 4: Push current index.<br/>Current can become the next greater candidate<br/>for elements processed later.

        S->>St: push(i % n)
    end

    S->>User: return answer

2. Pseudocode

FUNCTION nextGreaterElements(nums):

    n = length(nums)

    // IDEA 1:
    // Initially assume every element has no greater element.
    answer = array of size n filled with -1

    // Stack stores indices of elements that can still
    // become the "next greater element" for something.
    stack = empty stack


    // IDEA 2:
    // The array is circular.
    // Instead of physically duplicating nums,
    // simulate [nums + nums] by using i % n.
    //
    // Example:
    // nums = [1, 2, 1]
    // virtual = [1, 2, 1, 1, 2, 1]
    //
    // We go from right → left because when processing
    // an element, we want to already know about elements
    // to its right.
    FOR i = 2*n - 1 DOWN TO 0:

        current = nums[i % n]


        // IDEA 3:
        // Remove elements that cannot be the next greater
        // element for the current element.
        //
        // If stack.top <= current:
        //     current is already greater than stack.top.
        //
        // Therefore stack.top will never be useful as
        // a greater element for the current or earlier elements.
        WHILE stack is not empty
              AND nums[stack.top] <= current:

            stack.pop()


        // After removing smaller/equal elements:
        //
        //     stack.top
        //
        // is the nearest element to the right that is
        // greater than current, if one exists.

        IF i < n:

            IF stack is not empty:

                answer[i] = nums[stack.top]

            ELSE:

                answer[i] = -1


        // IDEA 4:
        // Current element can become a candidate for
        // elements that will be processed later.
        //
        // Store its real circular index, not i,
        // because nums only has indices [0 ... n-1].
        stack.push(i % n)


    RETURN answer

3. Implementation Python

def next_greater_elements(nums):
    n = len(nums)

    # IDEA 1:
    # Initially assume every element has no greater element.
    answer = [-1] * n

    # Stack stores indices of useful candidates.
    stack = []

    # IDEA 2:
    # Simulate a circular array by traversing 2n elements.
    #
    # Instead of creating:
    # [nums + nums]
    #
    # use nums[i % n].
    for i in range(2 * n - 1, -1, -1):

        current = nums[i % n]

        # IDEA 3:
        # Remove elements that cannot be the next greater element.
        #
        # If stack.top <= current, current is already
        # greater than stack.top, so stack.top is useless.
        while stack and nums[stack[-1]] <= current:
            stack.pop()

        # Only fill the answer for the original n elements.
        #
        # The second traversal (i >= n) is only used to
        # provide candidates for the circular part.
        if i < n:

            if stack:
                answer[i] = nums[stack[-1]]
            else:
                answer[i] = -1

        # IDEA 4:
        # Current element can become a candidate for
        # elements processed later.
        stack.append(i % n)

    return answer
August 16, 2026