LeetCode [1562] Find Latest Group of Size M

 1562. Find Latest Group of Size M

Medium

Given an array arr that represents a permutation of numbers from 1 to n. You have a binary string of size n that initially has all its bits set to zero.

At each step i (assuming both the binary string and arr are 1-indexed) from 1 to n, the bit at position arr[i] is set to 1. You are given an integer m and you need to find the latest step at which there exists a group of ones of length m. A group of ones is a contiguous substring of 1s such that it cannot be extended in either direction.

Return the latest step at which there exists a group of ones of length exactly m. If no such group exists, return -1.

 

Example 1:

Input: arr = [3,5,1,2,4], m = 1
Output: 4
Explanation:
Step 1: "00100", groups: ["1"]
Step 2: "00101", groups: ["1", "1"]
Step 3: "10101", groups: ["1", "1", "1"]
Step 4: "11101", groups: ["111", "1"]
Step 5: "11111", groups: ["11111"]
The latest step at which there exists a group of size 1 is step 4.

Example 2:

Input: arr = [3,1,5,4,2], m = 2
Output: -1
Explanation:
Step 1: "00100", groups: ["1"]
Step 2: "10100", groups: ["1", "1"]
Step 3: "10101", groups: ["1", "1", "1"]
Step 4: "10111", groups: ["1", "111"]
Step 5: "11111", groups: ["11111"]
No group of size 2 exists during any step.

Example 3:

Input: arr = [1], m = 1
Output: 1

Example 4:

Input: arr = [2,1], m = 2
Output: 2

 

Constraints:

• n == arr.length
• 1 <= n <= 10^5
• 1 <= arr[i] <= n
• All integers in arr are distinct.
• 1 <= m <= arr.length

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

class Solution { public int findLatestStep(int[] arr, int m) { int n = arr.length, lastValidStep = -1; int[] cnt = new int[n+1];//cnt[i]: # of segments of length i Map<Integer, Integer> map = new HashMap<>(); for(int i=0; i<n; ++i){ int index = arr[i]-1, left = index-1, right = index+1, leftLeft = 0, rightRigth = 0, leftSegLen = 0, rightSegLen = 0; if(map.containsKey(left)){ leftLeft = map.get(left); leftSegLen = left-leftLeft+1; } if(map.containsKey(right)){ rightRigth = map.get(right); rightSegLen = rightRigth-right+1; } int newSegLen; if(map.containsKey(left) && map.containsKey(right)){ newSegLen = leftSegLen+rightSegLen+1; cnt[leftSegLen]--; cnt[rightSegLen]--; map.put(leftLeft, rightRigth); map.put(rightRigth, leftLeft); }else if(map.containsKey(left)){ newSegLen = leftSegLen+1; cnt[leftSegLen]--; map.put(index, leftLeft); map.put(leftLeft, index); }else if(map.containsKey(right)){ newSegLen = rightSegLen+1; cnt[rightSegLen]--; map.put(index, rightRigth); map.put(rightRigth, index); }else{ newSegLen = 1; map.put(index, index); } cnt[newSegLen]++; if(cnt[m]>0) lastValidStep = i+1; } return lastValidStep; } }