#1764

Medium

auto_awesomeTwo-pointer scanning with invariant tracking

LeetCode Problem Workspace

Form Array by Concatenating Subarrays of Another Array

Determine if you can sequentially select disjoint subarrays from nums matching each group in order using two-pointer scanning.

array two pointers greedy string matching

Problem Statement

Given a 2D integer array groups and a 1D integer array nums, determine if you can choose disjoint subarrays from nums such that each subarray exactly matches the corresponding group in order. Each group[i] must appear as a consecutive subarray in nums, and all chosen subarrays must not overlap.

Return true if all groups can be matched sequentially in nums following the order of groups. Otherwise, return false. The solution must handle cases where groups have varying lengths and nums contains values not in any group.

Examples

Example 1

Input: groups = [[1,-1,-1],[3,-2,0]], nums = [1,-1,0,1,-1,-1,3,-2,0]

Output: true

You can choose the 0th subarray as [1,-1,0,1,-1,-1,3,-2,0] and the 1st one as [1,-1,0,1,-1,-1,3,-2,0]. These subarrays are disjoint as they share no common nums[k] element.

Example 2

Input: groups = [[10,-2],[1,2,3,4]], nums = [1,2,3,4,10,-2]

Output: false

Note that choosing the subarrays [1,2,3,4,10,-2] and [1,2,3,4,10,-2] is incorrect because they are not in the same order as in groups. [10,-2] must come before [1,2,3,4].

Example 3

Input: groups = [[1,2,3],[3,4]], nums = [7,7,1,2,3,4,7,7]

Output: false

Note that choosing the subarrays [7,7,1,2,3,4,7,7] and [7,7,1,2,3,4,7,7] is invalid because they are not disjoint. They share a common elements nums[4] (0-indexed).

Constraints

groups.length == n
1 <= n <= 103
1 <= groups[i].length, sum(groups[i].length) <= 103
1 <= nums.length <= 103
-107 <= groups[i][j], nums[k] <= 107

Solution Approach

Sequential Two-Pointer Matching

Use a pointer for nums and iterate over each group in order. For each group, slide the pointer through nums until a contiguous subarray matches the current group. Move the pointer past the matched subarray to prepare for the next group.

Greedy Suffix Advancement

Once a group is matched, treat the remaining part of nums as the new search space. This ensures that no subarrays overlap and respects the order of groups. If a group cannot be found in the remaining nums, return false immediately.

Early Termination and Optimization

Avoid unnecessary comparisons by checking the first and last elements of each group against potential positions in nums. This reduces redundant scanning and leverages the two-pointer invariant that the search always moves forward.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(m * n) in the worst case, where m is the total length of all groups and n is the length of nums, since each element of nums may be scanned multiple times. Space complexity is O(1) extra space beyond input arrays, as matching is done in-place with pointers and no additional structures are required.

What Interviewers Usually Probe

Focus on maintaining the current nums pointer after each matched group to avoid overlapping.
Expect you to explain why early termination is safe when a group cannot be matched in the remaining suffix.
Look for clear handling of edge cases, like groups longer than remaining nums or repeated numbers.

Common Pitfalls or Variants

Common pitfalls

Assuming groups can overlap, which violates the disjoint requirement.
Restarting scan from the beginning of nums for each group instead of advancing the pointer.
Failing to check that each group fully matches a contiguous segment of nums, not just partially.

Follow-up variants

Allow groups to appear in any order and check if nums can form them in any sequence.
Increase the constraints to larger arrays to test efficiency of two-pointer vs brute force.
Require returning the starting indices of each matched group instead of a boolean.

FAQ

What is the main pattern to solve Form Array by Concatenating Subarrays of Another Array?

The main pattern is sequential two-pointer scanning with invariant tracking to match each group in order without overlap.

Can subarrays from groups overlap in nums?

No, the problem requires selecting disjoint subarrays; overlapping would violate the constraints and return false.

How do I handle a group that doesn't appear in nums?

If a group cannot be matched in the remaining suffix of nums, you should immediately return false as no valid selection exists.

Is there an optimized way to skip unnecessary comparisons?

Yes, by checking the first and last elements of a group against nums positions, you can skip positions that cannot possibly match, reducing scans.

What is the time complexity for this approach?

The worst-case time complexity is O(m * n), where m is the total length of all groups and n is the length of nums, as each element may be scanned multiple times.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def canChoose(self, groups: List[List[int]], nums: List[int]) -> bool:
        n, m = len(groups), len(nums)
        i = j = 0
        while i < n and j < m:
            g = groups[i]
            if g == nums[j : j + len(g)]:
                j += len(g)
                i += 1
            else:
                j += 1
        return i == n

Continue Practicing

#1877 minimize maximum pair sum in array #1537 get the maximum score #2071 maximum number of tasks you can assign