LeetCode 1562. Find the latest group of size M

1562. Find size is M The latest group of

Medium difficulty 52 Switch to English to receive dynamic feedback

Give you an array arr , This array represents a from 1 To n Numerical arrangement of . There is a length of n Binary string of , All bits on this string are initially set to 0 .

In from 1 To n Every step of i in （ Suppose binary strings and arr from 1 Start indexing ）, Binary string at position arr[i] The bit of will be set to 1 .

Give you an integer m , Please find out that the binary string has a length of m A group of 1 The last step of . A group of 1 It's a continuous 、 from 1 Composed of substrings , And there are no longer extendable on the left and right 1 .

Return the existing length just by m Of A group of 1 The last step of . If there is no such step , Please return -1 .

Example 1：

 Input ：arr = [3,5,1,2,4], m = 1
 Output ：4
 explain ：
 step  1："00100", from  1  A group of ：["1"]
 step  2："00101", from  1  A group of ：["1", "1"]
 step  3："10101", from  1  A group of ：["1", "1", "1"]
 step  4："11101", from  1  A group of ：["111", "1"]
 step  5："11111", from  1  A group of ：["11111"]
 The length of existence is  1  A group of  1  The last step of is step  4 .

Example 2：

 Input ：arr = [3,1,5,4,2], m = 2
 Output ：-1
 explain ：
 step  1："00100", from  1  A group of ：["1"]
 step  2："10100", from  1  A group of ：["1", "1"]
 step  3："10101", from  1  A group of ：["1", "1", "1"]
 step  4："10111", from  1  A group of ：["1", "111"]
 step  5："11111", from  1  A group of ：["11111"]
 No matter which step, it cannot form a length of  2  A group of  1 .

Example 3：

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

Example 4：

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

Tips ：

• n == arr.length
• 1 <= n <= 10^5
• 1 <= arr[i] <= n
• arr All integers in Different from each other
• 1 <= m <= arr.length

Two 、 Method 1

simulation

class Solution {
    
    public int findLatestStep(int[] arr, int m) {
    
        int n = arr.length;
        int[][] endpoints = new int[n + 1][2];
        for (int i = 0; i <= n; i++) {
    
            Arrays.fill(endpoints[i], -1);
        }
        int cnt = 0;
        int ret = -1;

        for (int i = 0; i < n; i++) {
    
            int left = arr[i], right = arr[i];
            if (arr[i] > 1 && endpoints[arr[i] - 1][0] != -1) {
    
                left = endpoints[arr[i] - 1][0];
                int leftLength = endpoints[arr[i] - 1][1] - endpoints[arr[i] - 1][0] + 1;
                if (leftLength == m) {
    
                    cnt--;
                }
            }
            if (arr[i] < n && endpoints[arr[i] + 1][1] != -1) {
    
                right = endpoints[arr[i] + 1][1];
                int rightLength = endpoints[arr[i] + 1][1] - endpoints[arr[i] + 1][0] + 1;
                if (rightLength == m) {
    
                    cnt--;
                }
            }
            int length = right - left + 1;
            if (length == m) {
    
                cnt++;
            }
            if (cnt > 0) {
    
                ret = i + 1;
            }
            endpoints[left][0] = endpoints[right][0] = left;
            endpoints[left][1] = endpoints[right][1] = right;
        }
        return ret;
    }
}

Complexity analysis

• Time complexity ：O(n), among n Is the length of the array . When dealing with each step , We only visited the values of the left and right adjacent elements , Only the values at the left and right endpoints of the new group have been modified , Therefore, the time-consuming of each step is O(1) Of .

• Spatial complexity ：O(n). We need to open up an array with the same length as the original array endpoints.