<p>Given an array <code>arr</code> that represents a permutation of numbers from <code>1</code> to <code>n</code>.</p>

<p>You have a binary string of size <code>n</code> that initially has all its bits set to zero. At each step <code>i</code> (assuming both the binary string and <code>arr</code> are 1-indexed) from <code>1</code> to <code>n</code>, the bit at position <code>arr[i]</code> is set to <code>1</code>.</p>

<p>You are also given an integer <code>m</code>. Find the latest step at which there exists a group of ones of length <code>m</code>. A group of ones is a contiguous substring of <code>1</code>&#39;s such that it cannot be extended in either direction.</p>

<p>Return <em>the latest step at which there exists a group of ones of length <strong>exactly</strong></em> <code>m</code>. <em>If no such group exists, return</em> <code>-1</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> arr = [3,5,1,2,4], m = 1
<strong>Output:</strong> 4
<strong>Explanation:</strong> 
Step 1: &quot;00<u>1</u>00&quot;, groups: [&quot;1&quot;]
Step 2: &quot;0010<u>1</u>&quot;, groups: [&quot;1&quot;, &quot;1&quot;]
Step 3: &quot;<u>1</u>0101&quot;, groups: [&quot;1&quot;, &quot;1&quot;, &quot;1&quot;]
Step 4: &quot;1<u>1</u>101&quot;, groups: [&quot;111&quot;, &quot;1&quot;]
Step 5: &quot;111<u>1</u>1&quot;, groups: [&quot;11111&quot;]
The latest step at which there exists a group of size 1 is step 4.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> arr = [3,1,5,4,2], m = 2
<strong>Output:</strong> -1
<strong>Explanation:</strong> 
Step 1: &quot;00<u>1</u>00&quot;, groups: [&quot;1&quot;]
Step 2: &quot;<u>1</u>0100&quot;, groups: [&quot;1&quot;, &quot;1&quot;]
Step 3: &quot;1010<u>1</u>&quot;, groups: [&quot;1&quot;, &quot;1&quot;, &quot;1&quot;]
Step 4: &quot;101<u>1</u>1&quot;, groups: [&quot;1&quot;, &quot;111&quot;]
Step 5: &quot;1<u>1</u>111&quot;, groups: [&quot;11111&quot;]
No group of size 2 exists during any step.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == arr.length</code></li>
	<li><code>1 &lt;= m &lt;= n &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= arr[i] &lt;= n</code></li>
	<li>All integers in <code>arr</code> are <strong>distinct</strong>.</li>
</ul>

class UnionFind:
    def __init__(self, vals):
        self.vals = vals
        self.parents = {}
        self.size = {}
        self.numComponents = 0
        for val in vals:
            self.parents[val] = val
            self.numComponents += 1

    def find(self, a):
        root = a  # root of a
        while self.parents[root] != root:
            root = self.parents[root]

        tmp = a
        while tmp != root:
            r = self.parents[tmp]
            self.parents[tmp] = root
            self.size[tmp]= self.size[root]
            tmp = r

        return root

	# directional, so b is unified with a
	# you can also write this directionally to get lower runtimes
    def union(self, a, b):
        # b gets a's parent
        if a not in self.parents:
            self.size[a] = 1
            self.parents[a] = a
            self.numComponents += 1
        if b not in self.parents:
            self.size[b] = 1
            self.parents[b] = b
            self.numComponents += 1

        root1 = self.find(a)
        root2 = self.find(b)
        if root1 != root2:  # we can only combine sizes if this is the case
            self.parents[root1] = root2
            # note: we specifically increase the size of root1 because root2 will no longer be used
            # as it has been combined with root1
            self.size[root2] += self.size[root1]
            # num components decreases by 1 on a union
            self.numComponents -= 1

class Solution:
    def findLatestStep(self, arr: List[int], m: int) -> int:
        # binary search
        # assuming we can check for the step with binary search
        # can we check if the latest step at which a group of size m
        # occurs is at step X?
        # the reason this works is because checking the exact step
        # is cheaper than checking all the steps first
        U = UnionFind([])
        lo = 1
        hi = len(arr)
        # 0 indexed
        ans = -1
        A = [0]*len(arr)
        #111110s
        # since the input is a permutation from 1 to n
        # then we know the end state is n bits 1111111 
        # use binary search to split intervals 
        from collections import defaultdict
        G = defaultdict(int) 
        S = defaultdict(int) # size at index
        i = 0

        while i < len(arr):
            left = 0
            right = 0

            v = arr[i]-1
            A[v] = 1

            if v-1 >= 0:
                left = A[v-1]
            if v+1 < len(arr):
                right = A[v+1]

            if left == 1 and right == 1:
                L = v-1
                R = v+1
                G[S[L-S[L]+1]] -= 1
                G[S[R+S[R]-1]] -= 1
                newSize = S[L-S[L]+1]+S[R+S[R]-1]+1
                S[R+S[R]-1] = newSize
                S[L-S[L]+1] = newSize
                G[newSize] += 1
            elif left == 1:
                L = v-1
                oldSize = S[L]
                newSize = S[L-oldSize+1]+1
                G[oldSize] -= 1
                S[L-oldSize+1] = newSize
                S[v] = newSize
                G[newSize] += 1
            elif right == 1:
                R = v+1
                oldSize = S[R]
                S[R+oldSize-1] += 1
                S[v] = S[R+oldSize-1]
                G[S[R+oldSize-1]] += 1
                G[oldSize] -= 1
            else:
                S[v] = 1
                G[1] += 1
            #print(i,G)

            if m in G and G[m] > 0:
                ans = i+1
            i += 1

        return ans
                
915