LeetCode 769. Max Chunks To Make Sorted (ver. 1) - Weekly Contest 68

https://leetcode.com/contest/weekly-contest-68/problems/max-chunks-to-make-sorted-ver-1/

	class Solution {
	/**
	* @param arr
	* @return
	*/
	public int maxChunksToSorted(int[] arr) {
	// filter abnormal cases
	if (arr == null || arr.length == 0) {
	return 1;
	}
	// core logic
	int[] map = new int[arr.length];
	for (int i = 0; i < arr.length; i++) {
	map[arr[i]] = i;
	}
	int minCut = 0;
	int cutCounter = 1;
	for (int i = 0; i < arr.length - 1; i++) {
	int tmpRquire = Math.max(map[arr[i]], arr[i]);
	minCut = Math.max(minCut, tmpRquire);
	if (minCut <= i) {
	// System.out.println("Got a cut!! minCut = " + minCut);
	// System.out.println("cutCounter = " + cutCounter);
	// System.out.println("tmpRquire = " + tmpRquire);
	// System.out.println("i = " + i);
	minCut = i + 1;
	cutCounter++;
	}
	}
	// return the final result
	return cutCounter;
	}
	}

view raw LC 769. Max Chunks To Make Sorted (ver. 1) - Weekly Contest 68 - LeetCode.java hosted with ❤ by GitHub