1562. Find Latest Group of Size M

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: "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:

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.

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

# @lc code=start
using LeetCode

function find_latest_step(arr::Vector{Int}, m::Int)
    pos_dict = Dict{Int, Int}()
    neg_dict = Dict{Int, Int}()
    cnt = 0
    res = -1
    for (idx, num) in enumerate(arr)
        pos_dict[num] = num
        neg_dict[num] = num
        if haskey(pos_dict, num + 1)
            (pos_dict[num + 1] - num == m) && (cnt -= 1)
            tmp = pop!(pos_dict, num + 1)
            pos_dict[num] = tmp
            neg_dict[tmp] = num
        end
        if haskey(neg_dict, num - 1)
            (num - neg_dict[num - 1] == m) && (cnt -= 1)
            tmp = pop!(neg_dict, num - 1)
            neg_dict[num] = tmp
            pos_dict[tmp] = num
        end
        pos_dict[neg_dict[num]], neg_dict[pos_dict[num]] = pos_dict[num], neg_dict[num]
        (pos_dict[neg_dict[num]] - neg_dict[num] + 1 == m) && (cnt += 1)
        (cnt > 0) && (res = idx)
        if pos_dict[neg_dict[num]] != num
            pop!(pos_dict, num)
            pop!(neg_dict, num)
        end
    end
    return res
end

# @lc code=end

find_latest_step (generic function with 1 method)

This page was generated using DemoCards.jl and Literate.jl.