# Monotonicity: Find Largest Subarrays for Each Array Element

Given an array of numbers $A$, for each number $A[i]$, find the largest subarray that contains $A[i]$ and $A[i]$ is the minimum of the subarray. For example, for $A=[2, 0, 3, 5, 1, 1, 0, 2 1]$, the largest subarray for $A[4]$ is $[3,5,1,1]$. Let's represent the subarray for $A[i]$ as the left boundary $l[i]$ and right boundary $r[i]$. $$l[i] = \min_{j \le i }\lbrace \forall_{j \le k \le i} A[k] \ge A[i] \rbrace $$ $$r[i] = \max_{j \ge i }\lbrace \forall_{i \le k \le j} A[k] \ge A[i] \rbrace $$

It is obvious that calculating $l$ and $r$ are symmetric. Therefore we will focus on $l$. Consider two adjacent numbers, $A[i-1]$ and $A[i]$. If $A[i-1] < A[i]$, then $l[i]=i$. Otherwise, look back from from $A[i-1]$ to find the first element less than $A[i]$. The time complexity of this algorithm is $O(n^2)$.

## The monotonic function

Can we do better than $O(n^2)$? Let's start with case analysis.

- Case 1. $A[i] > A[i-1]$, then $l[i]=i$.
- Case 2. $A[i] \le A[i-1]$. According to definition of $l$, $\forall_{l[i-1] \le j \le i-1 } A[j] \ge A[i-1]$. Put the two inequalities together, $\forall_{l[i-1] \le j \le i-1} A[j] \ge A[i]$. In a more succinct form, $$A[i] \le A[i-1] \Rightarrow l[i] \le l[i-1] $$

```
1func leftBoundaryV1(nums []int) []int {
2 n := len(nums)
3 l := make([]int, n)
4 for i := 0; i < n; i++ {
5 for j := i; j >= 0; {
6 if j == 0 {
7 l[i] = 0
8 break
9 }
10 if nums[i] > nums[j-1] {
11 l[i] = j
12 break
13 } else if nums[i] == nums[j-1] {
14 l[i] = l[j-1]
15 break
16 } else {
17 j = l[j-1] // follow left boundaries recursively.
18 }
19 }
20 }
21 return l
22}
```

What is the time complexity? It is not immediately obvious due to the nested loop. My intuition suggests it is $O(n)$. For any $\lbrace j, l[i-1] \le j \lt i\rbrace$ that is skipped for $l[i]$, the same $j$ will be skipped for any $l[k]$ where $k \lt i$. So an element will be compared (i.e., not skipped) in a constant number of times. Can we prove the intuition?

Yes. The intuition suggests that if we skipped $l[j]$, we will always skip it in the future. So, we can keep a collection of $l$ that is still worth comparing. When a $l[i]$ is calculated, we add it to the collection. When a $l[j]$ is skipped, we remove it from the collection. Taking a closer look, both the adding and removal happen at the end of the collection. Therefore, the collection is a stack. The following is the corresponding Go code.

```
1func leftBoundaryV2(nums []int) []int {
2 n := len(nums)
3 l := make([]int, n)
4 stack := make([]int, 0, n)
5 for i := 0; i < n; i++ {
6 for {
7 if len(stack) == 0 {
8 break
9 }
10 top := stack[len(stack)-1]
11 if nums[i] > nums[top] {
12 break
13 }
14 stack = stack[:len(stack)-1] // removal
15 }
16 if len(stack) == 0 {
17 l[i] = 0
18 } else {
19 l[i] = stack[len(stack)-1] + 1
20 }
21 stack = append(stack, i) // add
22 }
23 return l
24}
```

Now, it is clear that any element is added to the stack and removed from the stack once. Thus,
the total time complexity of the inner for loop is $O(n)$. The outer for loop is also $O(n)$. Therefore,
the overall time complexity is $O(n)$. At any point in time, the values in the stack is monotonically increasing
from bottom to top. Consequently, the algorithm is often referred to as *monotonic stacks*.

## Find left boundary and right boundary in one scan

Calculate $r$ is symmetric to calculating $l$; just scan from right to left. However, this requires a second scan of the array. Can we compute both $l$ and $r$ in a single scan?

Yes. The stack is monotonic increasing. A number is popped from the stack when $A[i] \le Stack[top]$. Assume all numbers in $A$ are unique, then $A[i] \lt Stack[top]$ and we can assert $r[top]=i$. We already demonstrated that every number is pushed onto the stack once and popped from the stack once. Therefore, we can be certain that $r$ is set for every number. Do you see the beautiful symmetry? We set $l$ on pushing and set $r$ on popping.

What we can do when there are duplicate values in $A$? We can no longer set $r[top]=i$ when popping from the stack. Consider the example $A=[1, 1, 2]$. $A[0]$ is popped when $A[1]$ is pushed to the stack. However, in this case, $r[0]=2$, we should delay setting $r[0]$ till setting $r[1]$, because $A[0]=A[1]$. To address this scenario in the monotonic stack algorithm, we introduce $prev[i]=j$ where we delay setting $r[j]$ until we set $r[i]$. Upon popping $A[j]$, we set all previous $r$ that were delayed. The following is the modified algorithm in Go.

```
1func leftLeftAndRightBoundaries(nums []int) ([]int, []int) {
2 n := len(nums)
3 if n == 0 {
4 return nil, nil
5 }
6 l, r := make([]int, n), make([]int, n)
7 stack := make([]int, 0, n)
8
9 prev := make(map[int]int)
10 setRightBoundary := func(i int) {
11 j := i
12 for {
13 if _, ok := prev[j]; ok {
14 r[prev[j]] = r[i] // follow the prev recursively to set all delayed right boundaries.
15 j = prev[j]
16 continue
17 }
18 break
19 }
20 }
21
22 for i := 0; i < n; i++ {
23 for {
24 if len(stack) == 0 {
25 break
26 }
27 top := stack[len(stack)-1]
28 if nums[i] > nums[top] {
29 break
30 }
31 stack = stack[:len(stack)-1]
32 if nums[i] < nums[top] {
33 r[top] = i - 1
34 setRightBoundary(top)
35 } else { // nums[i] == nums[top]. record prev
36 prev[i] = top
37 }
38 }
39 if len(stack) == 0 {
40 l[i] = 0
41 } else {
42 l[i] = stack[len(stack)-1] + 1
43 }
44 stack = append(stack, i)
45 }
46 for _, idx := range stack {
47 r[idx] = n - 1
48 setRightBoundary(idx)
49 }
50 return l, r
51}
```

Does the scan-once algorithm always result in fewer operations than the scan-twice algorithm? Not necessarily. In the worst case, where all numbers are the same, the $prev$ stores all numbers.

### Appendix A. A series of posts on monotonicity.

- Monotonicity: Find the K-th number in two sorted arrays
- Monotonicity: Sliding Window
- Monotonic Stack: Steps to Make Array Non-decreasing

## Appendix B. Online coding problems to practice

Problem 1. 84. Largest Rectangle in Histogram