#1562
Find Latest Group of Size M
specialist · 980 · lc medium +32 · verified · 43.8% accepted · 679 likes · top 25%
Description
You have a binary string of length n initialized to all zeros and an array arr that is a permutation of integers 1 through n. At step i, you set the bit at position arr[i] to 1. You are also given an integer m. A group of ones is a maximal contiguous block of 1s. Return the latest step at which a group of exactly m ones exists. If no such step 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.
Code
1
2
3