Abstract / Summary

Given a list of group IDs and a number m, find the largest index where a group of m consecutive identical IDs ends.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 44% (50k+ submissions).

Typical patterns to solve this problem:

• Array
• Binary Search
• Hash Table
• Simulation

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation solves the problem of determining the latest step at which a contiguous group of exactly m ones appears while progressively turning positions on a binary string from 0 to 1 according to the order given in arr. The algorithm maintains dynamic information about the lengths of groups of consecutive ones and updates this information in constant time for each insertion. By tracking the count of groups of each size, it can instantly decide whether a group of length m exists after each step and record the most recent step where this condition holds.

Core Data Structures

The solution relies on three mutable containers:

• A dictionary named left that maps the leftmost index of a group to the length of that group.
• A dictionary named right that maps the rightmost index of a group to the length of that group.
• A defaultdict called sizes that records how many groups of a particular length currently exist.

These structures together enable O(1) access to a group’s boundaries and to the global count of groups of any given size.

left  = {}                     # left end → length
right = {}                     # right end → length
sizes = defaultdict(int)      # length → count of groups

Main Iteration

The algorithm iterates over the positions in arr using their enumeration index i and the position value a. For each new position, it initially creates a group of length 1 at that index, updates the dictionaries, and increments the count for size 1.

for i, a in enumerate(arr):
    left[a]  = 1
    right[a] = 1
    sizes[1] += 1

After the singleton group is created, the code checks whether the newly added position can be merged with an existing group on its right side (i.e., a+1 is already a left boundary) and with an existing group on its left side (i.e., a-1 is already a right boundary). If either condition holds, the appropriate merge operation is invoked.

    if a + 1 in left:
        merge(a, a + 1)
    if a - 1 in right:
        merge(a - right[a - 1], a)

Finally, the algorithm inspects the sizes dictionary to see if any group of length m exists after the current step. If so, it records the step number (1-based) as the current result.

    if sizes[m] > 0:
        result = i + 1

Merge Function

The nested merge function consolidates two adjacent groups whose left boundaries are given by one and two (with one < two). It computes the combined length, updates the leftmost and rightmost entries to reflect the new group, increments the count for the new length, and decrements the counts for the two original lengths. The original boundary entries are then removed to keep the dictionaries consistent.

def merge(one, two):            # one < two
    length = left[one] + left[two]
    last   = one + length - 1
    left[one] = right[last] = length
    sizes[length] += 1

    sizes[left[two]]   -= 1
    sizes[right[two-1]] -= 1
    del left[two]
    del right[two-1]

The function’s careful bookkeeping ensures that the sizes map always reflects the true number of groups of each size, which is essential for the constant-time size check performed after each insertion.

Edge Cases Handled

The implementation gracefully handles several boundary conditions:

• When the first element of arr is processed, there are no neighboring groups, so only the singleton creation occurs. The merge checks safely evaluate to false because the neighboring indices are absent from the dictionaries.
• When a newly added position bridges two existing groups (forming a larger group that spans both sides), the first merge call joins the new position with the right neighbor, and the second merge call subsequently joins the resulting group with the left neighbor. The order of these calls guarantees that the dictionaries contain the correct boundaries for the second merge.
• If m equals 1, the algorithm correctly records the step whenever a singleton group appears, because sizes[1] is incremented for each new position and decremented only when that singleton becomes part of a larger group.
• When the final step creates a group of length m that later expands, the result is still updated because the size check occurs before any further merges in the same iteration, preserving the latest step at which the exact size existed.
• The use of defaultdict(int) for sizes prevents key-error exceptions when querying a length that has not yet been seen, returning zero automatically.

Performance Optimizations

The code achieves high efficiency through several deliberate choices:

• All dictionary operations (lookup, insertion, deletion) are O(1) on average, allowing each iteration to run in constant time regardless of the current number of groups.
• By storing only the boundary indices of each group rather than the full list of positions, the memory footprint stays proportional to the number of groups, which is at most the number of steps processed.
• The sizes counter eliminates the need to scan the groups to determine whether a group of length m exists; a single dictionary lookup suffices.
• The merge logic updates the sizes map incrementally, adjusting counts for the old lengths and the new combined length without recomputing the entire distribution.
• The nested merge function is defined inside the loop, capturing the surrounding dictionaries without requiring additional parameters, which reduces overhead in passing arguments.

Through these mechanisms, the algorithm processes the entire input in linear time relative to the length of arr while maintaining constant-time updates and queries for group sizes.

Imagine a long row of empty chairs. At the start, all the chairs are empty. This computer program is like a game where people sit down one by one, picking specific chairs that are listed in a sequence. Every time someone sits down, they might be joining a group of friends who are sitting in a row next to them.

The code keeps track of these groups of friends. It uses two boxes to remember where each line of friends begins and ends, and another box to count how many lines have a certain number of friends sitting together.

When a new person sits in a chair, the program checks if there are neighbors to their left or their right. If there are, the program joins them into one bigger group. It is like snapping together blocks to make a longer tower whenever friends are side by side.

As it builds these rows, it constantly looks to see if a row has exactly the number of friends that were requested. If it finds a row that is just the right length, it remembers the current turn number. By the time it finishes watching everyone sit down, it knows the last turn when a row of that special size existed.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++		Java	Python			TS
	WalkCCC	C++		Java	Python
	leetcode.ca	C++	JS	Java	Python		Go
	Progiez	C++		Java	Python
github	black-shadows	C++
	charles-wangkai			Java
	everthis		JS
	FelixFan1122			Java
	fsq	C++
	JoshCrozier		JS
	keineahnung2345	C++
	lkwq007				Python
	suxrobGM					C#
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, JavaScript, Python
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
FelixFan1122	Java
fsq	C++
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
suxrobGM	C#
wisdompeak	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality