LeetCode 768. Max Chunks to Make Sorted (ver. 2) - Weekly Contest 68

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

	class Solution {
	/**
	* @param arr an array of Integer
	* @return an integer
	*/
	public int maxChunksToSorted(int[] arr) {
	// filter abnormal cases
	if (arr == null || arr.length == 0) {
	return 1;
	}
	// core logic
	int max = arr[0];
	int cutCounter = 1;
	int[] copy = Arrays.copyOf(arr, arr.length);
	Arrays.sort(copy);
	// System.out.println(Arrays.toString(copy));
	// System.out.println(Arrays.toString(arr));
	HashMap<Integer, Integer> map = new HashMap<>();
	for (int i = 0; i < arr.length - 1; i++) {
	// System.out.println("i = " + i);
	// System.out.println("map = " + map);
	if (stepAndIsEmpty(copy[i], arr[i], map)) {
	// System.out.println("Got a cut! i = " + i);
	// System.out.println("copy[i] = " + copy[i]);
	// System.out.println("arr[i] = " + arr[i]);
	cutCounter++;
	}
	}
	// return the final result
	return cutCounter;
	}
	private boolean stepAndIsEmpty(int keyToAdd, int keyToKill, HashMap<Integer, Integer> map) {
	if (keyToAdd != keyToKill) {
	if (map.containsKey(keyToAdd)) {
	if (map.get(keyToAdd) + 1 == 0) {
	map.remove(keyToAdd);
	} else {
	map.put(keyToAdd, map.get(keyToAdd) + 1);
	}
	} else {
	map.put(keyToAdd, 1);
	}
	if (map.containsKey(keyToKill)) {
	if (map.get(keyToKill) - 1 == 0) {
	map.remove(keyToKill);
	} else {
	map.put(keyToKill, map.get(keyToKill) - 1);
	}
	} else {
	map.put(keyToKill, -1);
	}
	}
	return map.isEmpty();
	}
	}

view raw LC 768. Max Chunks to Make Sorted (ver. 2) - Weekly Contest 68 - LeetCode.java hosted with ❤ by GitHub