Form Array by Concatenating Subarrays: Greedy Matching Pattern

Given a list of groups (each group is a list of integers) and an array nums, determine whether you can find each group as a contiguous subarray of nums, in order, without overlapping.

This is LeetCode 1764: Form Array by Concatenating Subarrays of Another Array, a medium problem that tests your ability to greedily match patterns inside a larger array. At first glance you might think about dynamic programming or backtracking, but the greedy approach is clean and optimal.

Why this problem matters

This problem teaches you the greedy sequential matching pattern. You have a sequence of "targets" (the groups), and you need to locate each one inside nums in order, making sure they do not overlap. The greedy choice is always to match each group as early as possible. If the earliest match works, any later match would also work but with less room left for future groups.

This same pattern appears whenever you need to verify that a sequence of patterns or subsequences can be found within a larger structure. Think of it as a generalization of the "is subsequence" problem, but instead of matching individual elements, you are matching contiguous blocks.

Understanding this greedy matching approach also builds intuition for problems like interval scheduling, where taking the earliest available option leaves the most room for future choices.

The key insight

The greedy strategy is: for each group, scan forward through nums starting from where the previous group ended, and take the first contiguous match you find. If you find it, jump past it. If you reach the end of nums without finding a match, return False.

Why is the greedy choice correct? Suppose group k can be matched at two positions: an early one and a late one. Choosing the early position leaves more of nums available for the remaining groups. Choosing the late position can only make things harder. So the earliest match is always at least as good as any later match.

This means you never need to backtrack. A single left-to-right scan handles everything.

The solution

def can_choose(groups, nums):
    i = 0
    for group in groups:
        g_len = len(group)
        found = False
        while i + g_len <= len(nums):
            if nums[i:i + g_len] == group:
                i += g_len
                found = True
                break
            i += 1
        if not found:
            return False
    return True

Here is what each piece does:

1. i is your position in nums. It starts at 0 and only moves forward, never backward.
2. For each group, you slide a window of size g_len across nums starting from i.
3. When you find a match (nums[i:i + g_len] == group), you advance i past the matched subarray by adding g_len. This ensures no overlap with future groups.
4. If the inner while loop finishes without finding a match, you return False immediately.
5. If all groups are matched, you return True.

The key detail is that i never resets. It only moves forward. This is what prevents groups from overlapping and what makes the algorithm greedy.

Visual walkthrough

Let's trace through the example groups = [[1,2,3],[3,4]], nums = [1,2,3,3,4]:

The algorithm finds [1,2,3] at the very start of nums, jumps i to index 3, then immediately finds [3,4] starting at index 3. Both groups are matched without overlap, so the answer is True.

Complexity analysis

In the worst case, each position in nums is compared against the current group's elements. The outer pointer i traverses nums at most once (it never goes backward), and at each position the comparison costs up to the length of the current group. Since the total length of all groups is bounded by n, the practical runtime is close to O(n) for most inputs.

The building blocks

This problem is built on two reusable patterns that CodeBricks drills independently.

1. Greedy forward scan

The pattern of scanning through an array with a pointer that only moves forward, greedily matching the first valid occurrence:

i = 0
for target in targets:
    while i < len(arr):
        if matches(arr, i, target):
            i += len(target)
            break
        i += 1

This skeleton shows up in "is subsequence" problems, pattern matching, and interval packing. The pointer never backtracks, which is what keeps the time complexity linear in the size of the array. The greedy choice (take the first match) is correct whenever earlier matches leave at least as much room for future targets as later matches would.

2. Sliding window comparison

The inner check compares a slice of nums against the current group. This is essentially a fixed-size sliding window:

while i + window_size <= len(arr):
    if arr[i:i + window_size] == pattern:
        return i
    i += 1

This is the same idea behind naive string matching. You slide a window of size len(pattern) across the array and check for equality at each position. For this problem the pattern changes with each group, but the sliding logic stays the same.

Edge cases

Before submitting, make sure your solution handles these:

• Single group that equals all of nums: groups = [[1,2,3]], nums = [1,2,3]. The entire array is one match. Return True.
• Group not found at all: groups = [[5]], nums = [1,2,3]. The value 5 does not appear in nums. Return False.
• Groups consume all of nums exactly: groups = [[1],[2],[3]], nums = [1,2,3]. Each single-element group matches exactly one element, and i ends at the very end of nums. Return True.
• Overlapping would be needed: groups = [[1,2],[2,3]], nums = [1,2,3]. The first group matches at index 0 and advances i to 2. Now nums[2:4] is [3] (out of bounds for length 2), so the second group cannot be found. Return False. The groups overlap at element 2, but overlapping is not allowed.
• Empty groups list: groups = [], nums = [1,2,3]. No groups to match, so return True trivially.

The greedy solution handles all of these without special-case logic.

From understanding to recall

You have read through the greedy matching solution and it clicks. One pointer, one forward scan per group, no backtracking. But can you write it from memory in an interview?

The details matter: initializing i to 0 outside the loop, checking i + g_len <= len(nums) (not i < len(nums)), advancing by g_len on match (not by 1), and using a found flag to detect when a group has no match. These are small but critical details that are easy to fumble under pressure.

Spaced repetition closes that gap. You write the greedy forward scan from scratch at increasing intervals until the pattern is automatic. After a few rounds, you see "match groups in order without overlap" and the code flows out without hesitation.

The greedy forward scan pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping the patterns stick.

Related posts

• Group Anagrams - Another array pattern problem where organizing and comparing groups of elements is the core skill
• Find First and Last Position of Element in Sorted Array - Searching for contiguous regions within an array, a related scanning technique
• Subsets - Understanding how to enumerate and match substructures within a collection

CodeBricks breaks the form array by concatenating subarrays problem into its greedy forward scan and sliding window comparison building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a greedy matching question shows up in your interview, you do not think about it. You just write it.