Understanding the previous closest occurrence pattern

Some problems require us to find, for each item in a sequence, the previous closest occurrence of a greater or smaller item (that is, the nearest item to its left 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 backward from each item in the sequence until the required greater or smaller item is found. Consider the example below, where we must find the previous greater item for each item in the array.

Finding the previous greater item for all items in a sequence.

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 previous closest occurrence technique.

The previous closest occurrence pattern is a classification of problems that can be solved using the previous closest occurrence technique using a stack.

The previous closest occurrence technique

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

Find the previous greater item for all items in an array arr.

We can solve the problem by traversing the array from start to end and maintaining a chain of previous greater items starting from the previous item. We will learn more about the proof of correctness of this technique later in this lesson.