Form Array by Concatenating Subarrays of Another Array solution and explanation
6 more videos on this problem
LeetCode 1764. Form Array by Concatenating Subarrays of Another Array | BiWeekly Contest 228 | C++Cherry Coding [IIT-G] · 9:44 · 659 views
LeetCode 1764. Form Array by Concatenating Subarrays of Another ArrayHappy Coding · 20:02 · 439 views
【每日一题】1764. Form Array by Concatenating Subarrays of Another Array, 2/22/2021Huifeng Guan · 36:01 · 288 views
1764. Form Array by Concatenating Subarrays of Another Array (Leetcode Medium)Programming Live with Larry · 10:32 · 210 views
LeetCode 1764. Form Array by Concatenating Subarrays of Another Array宰相小甘罗 · 2:41 · 71 views
Leetcode 1764. Form Array by Concatenating Subarrays of Another ArrayFearless Learner · 6:13 · 46 views
LeetCode 1764. Form Array by Concatenating Subarrays of Another Array 中文宰相小甘罗 · 2:52 · 23 views
The problem
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] <= 107
Approach overview
Problem 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 1: Greedy Matching Approach
This approach involves a greedy search through the `nums` array to find each subarray from `groups` in sequence. Starting from the first position, for each subarray in `groups`, check if it aligns with the current sequence in `nums`. If it does, move the index forward by the length of the current subarray in `nums`, ensuring no overlaps or reuse of elements.
def canChoose(groups, nums):
pos = 0
for group in groups:
found = False
while pos <= len(nums) - len(group):
if nums[pos:pos+len(group)] == group:
found = True
pos += len(group)
break
pos += 1
if not found:
return False
return Trueclass Solution {
public boolean canChoose(int[][] groups, int[] nums) {
int pos = 0;
for (int[] group : groups) {
boolean found = false;
for (; pos <= nums.length - group.length; pos++) {
int j;
for (j = 0; j < group.length; j++) {
if (nums[pos + j] != group[j]) break;
}
if (j == group.length) {
found = true;
pos += group.length;
break;
}
}
if (!found) return false;
}
return true;
}
}#include <vector>
#include <cstring>
using namespace std;
class Solution {
public:
bool canChoose(vector<vector<int>>& groups, vector<int>& nums) {
int pos = 0;
for (const auto& group : groups) {
int gLength = group.size();
bool found = false;
while (pos <= nums.size() - gLength) {
if (equal(group.begin(), group.end(), nums.begin() + pos)) {
found = true;
pos += gLength;
break;
}
++pos;
}
if (!found) return false;
}
return true;
}
};var canChoose = function(groups, nums) {
let pos = 0;
for (let group of groups) {
let found = false;
while (pos <= nums.length - group.length) {
if (nums.slice(pos, pos + group.length).every((val, index) => val === group[index])) {
found = true;
pos += group.length;
break;
}
pos++;
}
if (!found) return false;
}
return true;
};#include <stdbool.h>
#include <string.h>
bool canChoose(int** groups, int groupsSize, int* groupsColSize, int* nums, int numsSize) {
int pos = 0;
for (int i = 0; i < groupsSize; ++i) {
int gLength = groupsColSize[i];
bool found = false;
while (pos <= numsSize - gLength) {
if (memcmp(nums + pos, groups[i], gLength * sizeof(int)) == 0) {
found = true;
pos += gLength;
break;
}
++pos;
}
if (!found) return false;
}
return true;
}public class Solution {
public bool CanChoose(int[][] groups, int[] nums) {
int pos = 0;
foreach (var group in groups) {
bool found = false;
while (pos <= nums.Length - group.Length) {
if (Enumerable.Range(0, group.Length).All(j => nums[pos + j] == group[j])) {
found = true;
pos += group.Length;
break;
}
pos++;
}
if (!found) return false;
}
return true;
}
}This Python solution slices the `nums` list to match each `group` list. If a match is found, it updates the position to skip over the matched section, maintaining disjoint subarrays.
Time Complexity: O(numsLength * summation of lengths of groups)
Space Complexity: O(1)
Approach 2: Two Pointer Approach
The two-pointer approach employs two indices to track positions within the `nums` and `groups` arrays. As the main pointer iterates through `nums`, the second pointer verifies each subarray in `groups`. When a full subarray match is identified, the main pointer advances to bypass these elements, ensuring subarrays remain disjoint and ordered.
def canChoose(groups, nums):
def valid_group(group, nums, start):
return all(group[i] == nums[start + i] for i in range(len(group)))
pos = 0
for group in groups:
while pos <= len(nums) - len(group):
if valid_group(group, nums, pos):
pos += len(group)
break
pos += 1
else:
return False
return Trueclass Solution {
private boolean validGroup(int[] group, int[] nums, int start) {
for (int i = 0; i < group.length; i++) {
if (group[i] != nums[start + i]) return false;
}
return true;
}
public boolean canChoose(int[][] groups, int[] nums) {
int pos = 0;
for (int[] group : groups) {
boolean found = false;
while (pos <= nums.length - group.length) {
if (validGroup(group, nums, pos)) {
pos += group.length;
found = true;
break;
}
pos++;
}
if (!found) return false;
}
return true;
}
}#include <vector>
using namespace std;
bool validGroup(vector<int>& target, vector<int>& nums, int start) {
for (int i = 0; i < target.size(); ++i) {
if (target[i] != nums[start + i]) return false;
}
return true;
}
class Solution {
public:
bool canChoose(vector<vector<int>>& groups, vector<int>& nums) {
int pos = 0;
for (auto& group : groups) {
bool found = false;
while (pos <= nums.size() - group.size()) {
if (validGroup(group, nums, pos)) {
pos += group.size();
found = true;
break;
}
pos++;
}
if (!found) return false;
}
return true;
}
};var canChoose = function(groups, nums) {
const validGroup = (group, nums, start) => {
for (let i = 0; i < group.length; i++) {
if (group[i] !== nums[start + i]) return false;
}
return true;
};
let pos = 0;
for (let group of groups) {
let found = false;
while (pos <= nums.length - group.length) {
if (validGroup(group, nums, pos)) {
pos += group.length;
found = true;
break;
}
pos++;
}
if (!found) return false;
}
return true;
};#include <stdbool.h>
bool validGroup(int* target, int* nums, int start, int length) {
for (int i = 0; i < length; i++) {
if (target[i] != nums[start + i]) return false;
}
return true;
}
bool canChoose(int** groups, int groupsSize, int* groupsColSize, int* nums, int numsSize) {
int pos = 0;
for (int i = 0; i < groupsSize && pos < numsSize; i++) {
while (pos <= numsSize - groupsColSize[i]) {
if (validGroup(groups[i], nums, pos, groupsColSize[i])) {
pos += groupsColSize[i];
break;
}
pos++;
}
if (pos > numsSize - groupsColSize[i]) {
return false;
}
}
return true;
}public class Solution {
private bool ValidGroup(int[] group, int[] nums, int start) {
for (int i = 0; i < group.Length; i++) {
if (group[i] != nums[start + i]) return false;
}
return true;
}
public bool CanChoose(int[][] groups, int[] nums) {
int pos = 0;
foreach (var group in groups) {
bool found = false;
while (pos <= nums.Length - group.Length) {
if (ValidGroup(group, nums, pos)) {
pos += group.Length;
found = true;
break;
}
pos++;
}
if (!found) return false;
}
return true;
}
}The Python solution uses a `valid_group` function to conduct subarray matches. It iterates through `nums`, confirming matches using the `all` function to align elements into methodically verified subarrays.
Time Complexity: O(numsLength * summation of lengths of groups)
Space Complexity: O(1)
Approach 3: Default Approach
func canChoose(groups [][]int, nums []int) bool {
check := func(a, b []int, j int) bool {
m, n := len(a), len(b)
i := 0
for ; i < m && j < n; i, j = i+1, j+1 {
if a[i] != b[j] {
return false
}
}
return i == m
}
n, m := len(groups), len(nums)
i := 0
for j := 0; i < n && j < m; {
if check(groups[i], nums, j) {
j += len(groups[i])
i++
} else {
j++
}
}
return i == n
}Complexity comparison
| Approach | Complexity |
|---|---|
| Greedy Matching Approach | Time Complexity: O(numsLength * summation of lengths of groups) |
| Two Pointer Approach | Time Complexity: O(numsLength * summation of lengths of groups) |
| Default Approach | – |
Complexity analysis
| 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. |
Frequently asked questions
Is Form Array by Concatenating Subarrays of Another Array easy or hard?
The problem is rated Medium on LeetCode with an acceptance rate around 54%. The difficulty comes from correctly handling sequential matching and avoiding overlap between groups. Once the greedy scanning idea is clear, the implementation becomes relatively straightforward.
Form Array by Concatenating Subarrays of Another Array Python/Java solution
Most implementations follow the same greedy structure across languages. Iterate through nums, check whether the current position matches the start of the next group, and verify all elements of that group. If they match, advance the pointer by the group length. This logic translates directly into Python, Java, C++, and JavaScript with similar complexity.
How to solve Form Array by Concatenating Subarrays of Another Array in O(n)?
A near-linear scan is achieved using a greedy pointer technique. Iterate through nums and try to match the current group starting at each position. When the full group matches, move the pointer forward by the group's length and switch to the next group. Because the pointer never moves backward, the overall scan behaves close to O(n) in practice.
What is the best approach for Form Array by Concatenating Subarrays of Another Array?
The greedy matching approach is the most common solution. Scan the main array and attempt to match each group sequentially. If a group matches completely, skip ahead by its length and start matching the next group. This method runs in O(n * k) time and O(1) space, where n is the size of nums and k is the maximum group length.
Is Form Array by Concatenating Subarrays of Another Array asked at Google/Amazon/Meta?
Problems involving sequential matching and greedy array traversal appear frequently in interviews at companies like Amazon and Google. Variations of subarray matching, string-style comparisons, and pointer-based scanning are common technical interview topics.
What data structure is used in Form Array by Concatenating Subarrays of Another Array?
The solution primarily uses arrays with pointer-based traversal. No advanced data structures are required. The algorithm relies on sequential comparison, pointer movement, and greedy matching to ensure groups appear in order without overlap.
What is the time complexity of Form Array by Concatenating Subarrays of Another Array?
The typical solution runs in O(n * k) time. The algorithm scans the main array while comparing elements with the current group. In the worst case, each position may attempt a comparison with a group of length k. Space complexity remains O(1) because the algorithm uses only a few pointers.