Understanding the next closest occurrence pattern

Some problems require us to find, for each item in a sequence, the next closest occurrence of a data item that is greater than or smaller than it (that is, the nearest item to its right in the sequence that is greater than or smaller than it). One way to solve this problem would be to use nested loops to traverse forward from each item in the sequence until the required greater or smaller item is found. Consider the example below where we need to find the next greater item for each item in the array.

Even though the solution is correct, it requires expensive nested loops that make the overall performance poor. We can leverage the LIFO (Last in, first out) property of a stack to solve this problem in a single pass without any nested loops using the next closest occurrence technique.

Using the previous closest occurrence technique

Consider we are given an array of unique integers arr and we need to find the next greater integer for all items in the array. It is important to note that not all items in the array may have a next greater integer (for instance, the last item never does, and any item that is larger than every item to its right has none).