# Monotonic Stack

## Next greater element

This is the archetype of monotonic stack problems.

You are given two integer arrays `nums1`

and `nums2`

both of unique elements, where `nums1`

is a subset of `nums2`

.

Find all the next greater numbers for `nums1`

’s elements in the corresponding places of `nums2`

.

The *Next Greater Number* of a number $x$ in `nums1`

is the first greater number to its right in `nums2`

. If it does not exist, return -1 for this number.

Example:

```
Input: nums1 = [4,1,2], nums2 = [1,3,4,2]
Output: [-1,3,-1]
```

***

The problem implies that `nums2`

is the source data, and we should process this array in some way
so that we can iterate over `nums1`

and return the answer for each element.

To answer these *next greater element* questions, we can use a *monotonic stack*.
It is just a regular stack we maintain in such a way that the elements inside
at any given time are monotonically increasing or decreasing.

## Intuition

Say we have an element $3$.

- If the next element is $2$, we don’t know the
*next greater element*of $3$ yet. So we need tothis $2$, and wait for its next greater element to appear.*stash* - If the next element is $4$, we have found the
*next greater element*of $3$, as well as any previously stashed element $x$ before $3$ such that $3 < x < 4$.

```
fun nextGreaterElement(nums1: IntArray, nums2: IntArray): IntArray {
val dict = hashMapOf<Int, Int>()
val stack = Stack<Int>()
for (n in nums2) {
while (!stack.isEmpty() && stack.peek() < n) { dict[stack.pop()] = n } stack.push(n) }
val ret = IntArray(nums1.size)
for (i in ret.indices) {
ret[i] = dict.getOrDefault(nums1[i], -1)
}
return ret
}
```

The highlighted part of the code is the idiom for maintaining a monotonic stack.

## Variations

№ 503. Next Greater Element II

Given a circular integer array `nums`

(i.e., the next element of `nums[nums.length - 1]`

is `nums[0]`

),
return the next greater number for every element in nums.

***

To handle circularity, we can concatenate two copies of the `nums`

array.
The modulo operation `%`

helps us achieve this without allocating extra space.
Then the code is almost the same as *Next Greater Element I*.

Notice we store the array index rather than array item in the monotonic stack.

```
fun nextGreaterElements(nums: IntArray): IntArray {
val stack = Stack<Int>()
val ret = IntArray(nums.size) { -1 }
// i in [0, 2 * nums.size)
for (i in 0 until (2 * nums.size - 1)) {
// adjusted index
val ii = i % nums.size
while (!stack.isEmpty() && nums[stack.peek()] < nums[ii]) { ret[stack.pop()] = nums[ii] } stack.push(ii) }
return ret
}
```

Write a class `StockSpanner`

which collects daily price quotes for some stock, and returns the span of that stock’s price for the current day.

The span of the stock’s price today is defined as the maximum number of consecutive days (starting from today and going backwards) for which the price of the stock was less than or equal to today’s price.

```
Example:
stock quotes: [100, 80, 60, 70, 60, 75, 85]
stock spans: [1, 1, 1, 2, 1, 4, 6]
```

Skeleton:

```
class StockSpanner {
fun next(price: Int): Int {/**/}
}
```

***

Solution:

```
class StockSpanner() {
data class Data(val price: Int, val span: Int)
val stack: Deque<Data> = ArrayDeque()
fun next(price: Int): Int {
var n = 1
while (!stack.isEmpty() && stack.peek().price <= price) { n += stack.pop().span } stack.push(Data(price, n))
return n
}
}
```

Intuition:

The question asks for the maximum number of consecutive days before for which the price is $\leq$ today’s price. In other words, if we find the previous greater element, we’ve got the answer.

When the top of the stack is $\leq$ today’s price, we are effectively merging previous records into today’s record,
since we only care about previous *greater* element when new quotes come in.
If the element on top of the stack is smaller, it doesn’t matter anymore.

Given a list of daily temperatures `T`

, return a list such that,
for each day in the input, tells you how many days you would have to wait until a warmer temperature.
If there is no future day for which this is possible, put $0$ instead.

***

```
fun dailyTemperatures(T: IntArray): IntArray {
val stack: Deque<Int> = ArrayDeque()
val ret = IntArray(T.size)
for (i in T.indices) {
while (!stack.isEmpty() && T[stack.peek()] < T[i]) { val j = stack.pop() ret[j] = i - j } stack.push(i)
}
return ret
}
```

This section is WIP.

Given an array of n integers `nums`

, a *132 pattern* is a subsequence of three integers `nums[i]`

, `nums[j]`

and `nums[k]`

such that

Return `true`

if there is a 132 pattern in nums, otherwise, return `false`

.

Example 1:

```
Input: nums = [3,1,4,2]
Output: true
Explanation: There is a 132 pattern in the sequence: [1, 4, 2].
```

Example 2:

```
Input: nums = [1,2,3,4]
Output: false
Explanation: There is no 132 pattern in the sequence.
```

***

Iterate through the numbers and presume the current element is the $3$ in the pattern.

- The
`1`

is to the left of the current element. The best candidate is*the smallest item to the left*. - the
`2`

is to the right of the current element. The best candidate is*the next greater element to the right*

Compare these three numbers and if they match the pattern we can return `true`

.

We can solve the first part by dynamic programming, and the second part by a monotonic stack.

## Reference

- StackOverflow: Intuition behind using a monotonic stack
- [JAVA Solution] With visualization and easy explained!