Watch 7 video solutions for Form Array by Concatenating Subarrays of Another Array, a medium level problem involving Array, Two Pointers, Greedy. This walkthrough by Cherry Coding [IIT-G] has 651 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a 2D integer array groups of length n. You are also given an integer array nums.
You are asked if you can choose n disjoint subarrays from the array nums such that the ith subarray is equal to groups[i] (0-indexed), and if i > 0, the (i-1)th subarray appears before the ith subarray in nums (i.e. the subarrays must be in the same order as groups).
Return true if you can do this task, and false otherwise.
Note that the subarrays are disjoint if and only if there is no index k such that nums[k] belongs to more than one subarray. A subarray is a contiguous sequence of elements within an array.
Example 1:
Input: groups = [[1,-1,-1],[3,-2,0]], nums = [1,-1,0,1,-1,-1,3,-2,0] Output: true Explanation: 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 Explanation: 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 Explanation: 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 == n1 <= n <= 1031 <= groups[i].length, sum(groups[i].length) <= 1031 <= nums.length <= 103-107 <= groups[i][j], nums[k] <= 107Problem Overview: You are given a list of integer subarrays called groups and a main array nums. The task is to determine whether you can form the sequence of groups by concatenating them in order using subarrays from nums. Each group must appear exactly in order and cannot overlap with another matched group.
Approach 1: Greedy Matching Approach (O(n * k) time, O(1) space)
This approach scans nums from left to right and greedily tries to match each group in order. For the current group, compare its elements with the current segment in nums. If all elements match sequentially, move the pointer forward by the length of the group and start matching the next group. If the match fails, advance the pointer in nums by one and try again. The key insight is that once a group matches, skipping exactly its length prevents overlap and preserves order.
The algorithm performs repeated sequential comparisons similar to string matching. Although each attempt compares multiple elements, the pointer only moves forward, so the scan remains efficient. This method relies on simple iteration over the array and works well for interview scenarios because it is straightforward and easy to reason about.
Approach 2: Two Pointer Approach (O(n * k) time, O(1) space)
The two pointer strategy maintains one pointer for nums and another for the current group. As you iterate through nums, check whether the current value matches the first element of the active group. If it does, advance both pointers and continue verifying the rest of that group. If any mismatch occurs, reset the group pointer and continue scanning the main array.
This technique uses the classic two pointers pattern to synchronize traversal between the main array and the current group. Once an entire group matches, increment the group index and continue scanning from the next position in nums. Because groups must appear in order and cannot overlap, pointer movement naturally enforces the constraint.
Recommended for interviews: The greedy matching solution is typically expected. It clearly demonstrates your understanding of sequential matching and pointer control while keeping the implementation simple. A brute-force mindset helps initially, but the greedy scan shows stronger algorithmic clarity and avoids unnecessary backtracking.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Matching | O(n * k) | O(1) | Best general solution. Simple sequential scan with minimal memory. |
| Two Pointer | O(n * k) | O(1) | Useful when explicitly tracking positions in both arrays during matching. |