LeetCode 1764 - Form Array by Concatenating Subarrays of Another Array

The problem asks us to determine whether we can select disjoint subarrays from a given array nums such that each subarray matches exactly one of the subarrays in the groups array, in order.

leetcodemediumarraytwo-pointersgreedystring-matching

LeetCode Problem 1764

Difficulty: 🟡 Medium
Topics: Array, Two Pointers, Greedy, String Matching

Solution

Problem Understanding

The problem asks us to determine whether we can select disjoint subarrays from a given array nums such that each subarray matches exactly one of the subarrays in the groups array, in order. A subarray is contiguous, and "disjoint" means no element in nums is part of more than one selected subarray. The order constraint requires that for every i > 0, the subarray corresponding to groups[i-1] must appear before the subarray corresponding to groups[i] in nums.

The input consists of two main components: groups, a list of lists of integers, and nums, a flat list of integers. The goal is to determine whether all groups can be matched in order without overlap. Constraints tell us that nums and the total length of all groups are small (up to 1000 elements), so an approach with roughly O(n*m) complexity is feasible. Important edge cases include:

  1. A group cannot be matched because its sequence does not exist in nums.
  2. Groups appear in the wrong order in nums.
  3. Groups overlap if naive matching is used.

Approaches

The brute-force approach is to try every possible starting index in nums for each group. For each group, you iterate over nums and check if the subarray starting at that index matches the current group. Once a match is found, you continue with the next group from the index immediately after the matched subarray. This approach is correct but can be inefficient, as each check can require scanning up to the length of the group repeatedly, leading to a potential O(n * m * k) complexity, where n is the number of groups, m is the length of nums, and k is the average length of a group.

The optimal approach leverages a greedy linear scan with subarray matching. Instead of testing every start index, we scan through nums sequentially and try to match the current group at each position. If the current element matches the start of the group, we check if the next few elements also match the group entirely. If so, we move the pointer in nums past this matched subarray and proceed to the next group. This guarantees both order and disjoint constraints without excessive redundant scanning.

Approach Time Complexity Space Complexity Notes
Brute Force O(n * m * k) O(1) Checks all possible start positions for each group in nums
Optimal O(m * k) O(1) Sequentially scans nums, matching each group greedily without overlap

Algorithm Walkthrough

  1. Initialize a pointer i to traverse nums and a pointer g to track the current group in groups.

  2. While i is less than the length of nums and g is less than the number of groups, do the following:

  3. Check if the subarray nums[i:i+len(groups[g])] matches groups[g].

  4. If it matches, move i forward by the length of groups[g] and increment g to check the next group.

  5. If it does not match, increment i by 1 to try matching the group at the next index.

  6. If all groups (g == len(groups)) have been matched, return True.

  7. If the end of nums is reached before matching all groups, return False.

Why it works: This algorithm guarantees that groups are matched in order and are disjoint because once a group is matched, we move past its subarray in nums. Each group is attempted at every valid start position, ensuring no potential match is missed.

Python Solution

from typing import List

class Solution:
    def canChoose(self, groups: List[List[int]], nums: List[int]) -> bool:
        i = 0  # pointer in nums
        for group in groups:
            found = False
            while i + len(group) <= len(nums):
                if nums[i:i + len(group)] == group:
                    found = True
                    i += len(group)  # move past the matched subarray
                    break
                i += 1  # try next position
            if not found:
                return False
        return True

This implementation iterates through each group and tries to match it in nums. It maintains a pointer i to ensure matches are disjoint. If a group is not found, it immediately returns False. Otherwise, after all groups are matched, it returns True.

Go Solution

func canChoose(groups [][]int, nums []int) bool {
    i := 0
    for _, group := range groups {
        found := false
        for i+len(group) <= len(nums) {
            match := true
            for j := 0; j < len(group); j++ {
                if nums[i+j] != group[j] {
                    match = false
                    break
                }
            }
            if match {
                found = true
                i += len(group)
                break
            }
            i++
        }
        if !found {
            return false
        }
    }
    return true
}

In Go, we explicitly check each element of nums against the current group because Go slices do not support direct slice equality. Otherwise, the logic mirrors the Python implementation.

Worked Examples

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

Step i group nums[i:i+len(group)] Action
1 0 [1,-1,-1] [1,-1,0] Not equal, i -> 1
2 1 [1,-1,-1] [-1,0,1] Not equal, i -> 2
3 2 [1,-1,-1] [0,1,-1] Not equal, i -> 3
4 3 [1,-1,-1] [1,-1,-1] Match, i -> 6, move to next group
5 6 [3,-2,0] [3,-2,0] Match, i -> 9, all groups matched

Return True.

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

No matching sequence is found for the first group [10,-2] at the start. After scanning, return False.

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

The first group [1,2,3] matches starting at i=2. Then [3,4] would require overlap at i=4 (nums[4:6] = [3,4]), but the algorithm moves i past the first group, ensuring disjointness. Return False.

Complexity Analysis

Measure Complexity Explanation
Time O(m * k) We scan nums once for each group, and for each position, we may compare up to length of the group.
Space O(1) Only pointers and loop variables are used; no extra space proportional to input size is needed.

The complexity is manageable due to the constraints: nums.length and total groups size are ≤ 1000.

Test Cases

# Provided examples
assert Solution().canChoose([[1,-1,-1],[3,-2,0]], [1,-1,0,1,-1,-1,3,-2,0]) == True
assert Solution().canChoose([[10,-2],[1,2,3,4]], [1,2,3,4,10,-2]) == False
assert Solution().canChoose([[1,2,3],[3,4]], [7,7,1,2,3,4,7,7]) == False

# Edge and boundary cases
assert Solution().canChoose([[1]], [1]) == True  # single element match
assert Solution().canChoose([[1]], [2]) == False  # single element no match
assert Solution().canChoose([[1,2,3]], [1,2,3,1,2,3]) == True  # multiple occurrences
assert Solution().canChoose([[1,2,3],[1,2,3]], [1,2,3,1,2,3]) == True  # sequential matching
assert Solution().canChoose([[1,2,3],[1,2,3]], [1,2,3,1,2]) == False  # second group incomplete
Test Why
[[1,-1,-1],[3,-2,0]] Standard matching with disjoint subarrays
[[10,-2],[1,2,3,4]] Groups appear in wrong order
[[1,2,3],[3,4]] Overlapping groups
[[1]]