Max Chunks To Make Sorted II LeetCode solution in Java

1
/*
2

3
1. Generate Right min
4
2. Generate Left Max
5
3. Count chunks
6

7
Pos -->. 0 1 2 3 4 5 6 7
8

9
Input --> 30 , 10 , 20 , 40 , 60 , 50 , 75 , 70
10
             <------------> <--> <-------> <------->
11
Left Max --> 30 , 30 , 30 , 40 , 60 , 60 , 75 , 75
12

13
Right Min --> 10 , 10 , 20 , 40 , 50 , 50 , 70 , 70 , Integer.max
14

15
1. At pos 2 , left_max 30 is smaller than right_min 40 at pos 3
16
2. That means , all the elements in the right side of 30 are bigger than all the elements of left side of 30 , including 30
17
3. Hence we can break it at pos 2 into a chunk and sort this whole sub-array( 0 - 2 )
18

19
*/
20

21
class Solution {
22

23
  public int maxChunksToSorted(int[] arr) {
24

25
    // 1. Generate Right min
26

27
    int[] min_from_right = new int[arr.length + 1];
28
    min_from_right[arr.length] = Integer.MAX_VALUE;
29

30
    for (int i = arr.length - 1; i >= 0; i--) {
31
      min_from_right[i] = Math.min(arr[i], min_from_right[i + 1]);
32
    }
33

34
    // 2. Generate Left Max and Count chunks
35
    int chunk_count = 0;
36
    int max_cur = Integer.MIN_VALUE;
37

38
    for (int i = 0; i < arr.length; i++) {
39
      max_cur = Math.max(max_cur, arr[i]);
40
      if (max_cur <= min_from_right[i + 1]) {
41
        chunk_count++;
42
      }
43
    }
44

45
    return chunk_count;
46
  }
47
}