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.
Practice online at Leetcode 84. Largest Rectangle in Histogram