FilesExpand file tree

 master

/

MaxChunksToMakeSorted769.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

43 lines (42 loc) · 1.26 KB

 master

/

MaxChunksToMakeSorted769.java

Copy path

Top

File metadata and controls

• Code
• Blame

43 lines (42 loc) · 1.26 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

/**

* Given an array arr that is a permutation of [0, 1, ..., arr.length - 1], we

* split the array into some number of "chunks" (partitions), and individually

* sort each chunk. After concatenating them, the result equals the sorted

* array.

*

* What is the most number of chunks we could have made?

*

* Example 1:

* Input: arr = [4,3,2,1,0]

* Output: 1

* Explanation:

* Splitting into two or more chunks will not return the required result.

* For example, splitting into [4, 3], [2, 1, 0] will result in [3, 4, 0, 1, 2],

* which isn't sorted.

*

* Example 2:

* Input: arr = [1,0,2,3,4]

* Output: 4

* Explanation:

* We can split into two chunks, such as [1, 0], [2, 3, 4].

* However, splitting into [1, 0], [2], [3], [4] is the highest number of

* chunks possible.

*

* Note:

* arr will have length in range [1, 10].

* arr[i] will be a permutation of [0, 1, ..., arr.length - 1].

*/

public class MaxChunksToMakeSorted769 {

public int maxChunksToSorted(int[] arr) {

if (arr == null || arr.length == 0) return 0;

int res = 0;

int max = arr[0];

for (int i=0; i<arr.length; i++) {

max = Math.max(max, arr[i]);

if (max == i) {

res++;

}

}

return res;

}

}