Problem

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 also given an integer m. Find the latest step at which there exists a group of ones of length m. A group of ones is a contiguous substring of 1’s such that it cannot be extended in either direction.

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

Examples

Example 1

1
2
3
4
5
6
7
8
9

Input: arr = [3,5,1,2,4], m = 1
Output: 4
Explanation: 
Step 1: "00 _1_ 00", groups: ["1"]
Step 2: "0010 _1_ ", groups: ["1", "1"]
Step 3: "_1_ 0101", groups: ["1", "1", "1"]
Step 4: "1 _1_ 101", groups: ["111", "1"]
Step 5: "111 _1_ 1", groups: ["11111"]
The latest step at which there exists a group of size 1 is step 4.

Example 2

1
2
3
4
5
6
7
8
9

Input: arr = [3,1,5,4,2], m = 2
Output: -1
Explanation: 
Step 1: "00 _1_ 00", groups: ["1"]
Step 2: "_1_ 0100", groups: ["1", "1"]
Step 3: "1010 _1_ ", groups: ["1", "1", "1"]
Step 4: "101 _1_ 1", groups: ["1", "111"]
Step 5: "1 _1_ 111", groups: ["11111"]
No group of size 2 exists during any step.

Constraints

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

Solution

Method 1 – Union-Find with Length Tracking

Intuition

We need to efficiently track contiguous groups of 1s and their sizes as we flip bits in the order given by arr. By using an array to track the length of each group and a counter for groups of size m, we can update group sizes in constant time per step.

Approach

  1. Initialize an array length of size n+2 to track the length of the group at each position (with sentinels at both ends).
  2. Use a counter to track how many groups of size m exist at each step.
  3. For each step, set the bit at arr[i] to 1:
    • Check the length of the group to the left and right.
    • The new group size is left + right + 1.
    • Update the length array at the boundaries.
    • Update the counter for groups of size m (decrement for old groups, increment for new group if size matches m).
  4. If at any step the counter is positive, record the step as the latest.
  5. Return the latest step found, or -1 if none.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    int findLatestStep(vector<int>& arr, int m) {
        int n = arr.size(), res = -1, cnt = 0;
        vector<int> length(n+2);
        vector<int> count(n+1);
        for (int i = 0; i < n; ++i) {
            int pos = arr[i];
            int left = length[pos-1], right = length[pos+1];
            int total = left + right + 1;
            length[pos-left] = length[pos+right] = total;
            if (left > 0) count[left]--;
            if (right > 0) count[right]--;
            count[total]++;
            if (count[m] > 0) res = i+1;
        }
        return res;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

func findLatestStep(arr []int, m int) int {
    n := len(arr)
    length := make([]int, n+2)
    count := make([]int, n+1)
    res := -1
    for i, pos := range arr {
        left, right := length[pos-1], length[pos+1]
        total := left + right + 1
        length[pos-left] = total
        length[pos+right] = total
        if left > 0 { count[left]-- }
        if right > 0 { count[right]-- }
        count[total]++
        if count[m] > 0 { res = i+1 }
    }
    return res
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    public int findLatestStep(int[] arr, int m) {
        int n = arr.length, res = -1;
        int[] length = new int[n+2];
        int[] count = new int[n+1];
        for (int i = 0; i < n; i++) {
            int pos = arr[i];
            int left = length[pos-1], right = length[pos+1];
            int total = left + right + 1;
            length[pos-left] = length[pos+right] = total;
            if (left > 0) count[left]--;
            if (right > 0) count[right]--;
            count[total]++;
            if (count[m] > 0) res = i+1;
        }
        return res;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    fun findLatestStep(arr: IntArray, m: Int): Int {
        val n = arr.size
        val length = IntArray(n+2)
        val count = IntArray(n+1)
        var res = -1
        for (i in arr.indices) {
            val pos = arr[i]
            val left = length[pos-1]
            val right = length[pos+1]
            val total = left + right + 1
            length[pos-left] = total
            length[pos+right] = total
            if (left > 0) count[left]--
            if (right > 0) count[right]--
            count[total]++
            if (count[m] > 0) res = i+1
        }
        return res
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def findLatestStep(self, arr: list[int], m: int) -> int:
        n = len(arr)
        length = [0] * (n+2)
        count = [0] * (n+1)
        res = -1
        for i, pos in enumerate(arr):
            left, right = length[pos-1], length[pos+1]
            total = left + right + 1
            length[pos-left] = length[pos+right] = total
            if left > 0:
                count[left] -= 1
            if right > 0:
                count[right] -= 1
            count[total] += 1
            if count[m] > 0:
                res = i+1
        return res
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

impl Solution {
    pub fn find_latest_step(arr: Vec<i32>, m: i32) -> i32 {
        let n = arr.len();
        let mut length = vec![0; n+2];
        let mut count = vec![0; n+1];
        let mut res = -1;
        for (i, &pos) in arr.iter().enumerate() {
            let pos = pos as usize;
            let left = length[pos-1];
            let right = length[pos+1];
            let total = left + right + 1;
            length[pos-left] = total;
            length[pos+right] = total;
            if left > 0 { count[left] -= 1; }
            if right > 0 { count[right] -= 1; }
            count[total] += 1;
            if count[m as usize] > 0 { res = (i+1) as i32; }
        }
        res
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    findLatestStep(arr: number[], m: number): number {
        const n = arr.length;
        const length = new Array(n+2).fill(0);
        const count = new Array(n+1).fill(0);
        let res = -1;
        for (let i = 0; i < n; i++) {
            const pos = arr[i];
            const left = length[pos-1], right = length[pos+1];
            const total = left + right + 1;
            length[pos-left] = total;
            length[pos+right] = total;
            if (left > 0) count[left]--;
            if (right > 0) count[right]--;
            count[total]++;
            if (count[m] > 0) res = i+1;
        }
        return res;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of arr. Each step is constant time.
  • 🧺 Space complexity: O(n), for the length and count arrays.