<p>You are given the <code>head</code> of a linked list.</p>

<p>Remove every node which has a node with a greater value anywhere to the right side of it.</p>

<p>Return <em>the </em><code>head</code><em> of the modified linked list.</em></p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2022/10/02/drawio.png" style="width: 631px; height: 51px;" />
<pre>
<strong>Input:</strong> head = [5,2,13,3,8]
<strong>Output:</strong> [13,8]
<strong>Explanation:</strong> The nodes that should be removed are 5, 2 and 3.
- Node 13 is to the right of node 5.
- Node 13 is to the right of node 2.
- Node 8 is to the right of node 3.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> head = [1,1,1,1]
<strong>Output:</strong> [1,1,1,1]
<strong>Explanation:</strong> Every node has value 1, so no nodes are removed.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li>The number of the nodes in the given list is in the range <code>[1, 10<sup>5</sup>]</code>.</li>
	<li><code>1 &lt;= Node.val &lt;= 10<sup>5</sup></code></li>
</ul>

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:
        """
        how to determine if a node needs to be removed/has a node to the right side of it that is greater
        
        
        Approach 1
        O(n^2)
        sum of first n-1 integers:
        at each node,
            scan through rest of arr and see if there is a val greater than
            
            
        Approach 2
        Do some preprocessing
        
        convert the LL to an arr O(n) time and space
        create a set with indices of nodes that need to be removed
        
        iterate through the array from right to left keeping track of the maximum value seen so far
            if max value greater than curr value, mark the corresponding node to be removed
            
        
        create a dummy node that points to head
        init curr ptr at dummy node
        
        while curr
        
        while next nodes index is in the set, remove the next node
        
        the reason why im adding the index instead of the value of the node to the hashset is that there can be duplicate values and not all of the nodes wiht that value may need to be removed, the index however is a uniquely identifying attribute
        """
        
        # convert LL to array
        nodeValues = []
        curr = head
        while curr:
            nodeValues.append(curr.val)
            curr = curr.next
            
        # find out which nodes need to be removed (have a value to the right that is greater)
        maxValue = 0
        nodesToBeRemoved = set()
        for i in range(len(nodeValues) - 1, -1, -1):
            if maxValue > nodeValues[i]:
                nodesToBeRemoved.add(i) # has a value to the right which is greater 
                
            maxValue = max(maxValue, nodeValues[i])
            
        dummyHead = ListNode(val=0, next=head)
        curr = dummyHead
        index = -1
        while curr:
            # while we can/need to remove the next node
            while curr.next and index+1 in nodesToBeRemoved:
                curr.next = curr.next.next
                index += 1 # increment index so that we can accurately compute the index of the next node
                
            # advance curr and update index
            curr = curr.next
            index += 1
            
        return dummyHead.next
        
522