Form Array by Concatenating Subarrays of Another Array

Form Array by Concatenating Subarrays of Another Array - 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: 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.

Input & Output

Example 1 — Basic Match

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

› Output: true

💡 Note: Can choose subarrays [1,-1,-1] at indices 3-5 and [3,-2,0] at indices 6-8. Both groups found in order.

Example 2 — No Valid Arrangement

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

› Output: false

💡 Note: Cannot find both groups as disjoint subarrays in the required order.

Example 3 — Single Group

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

› Output: true

💡 Note: Single group [1,2] found at indices 0-1.

Constraints

1 ≤ groups.length ≤ 1000
1 ≤ groups[i].length ≤ 10
1 ≤ nums.length ≤ 10³
-10⁷ ≤ nums[i], groups[i][j] ≤ 10⁷

Visualization

Tap to expand

Understanding the Visualization

Input

Groups to find: [[1,3],[3,4]], Target array: [7,7,1,3,3,4,7,7]

Process

Find each group sequentially as contiguous subarrays

Output

Return true if all groups found in order

Key Takeaway

🎯 Key Insight: Use greedy sequential matching to find groups in order at first available positions

Asked in

G Google 15 M Microsoft 12 f Facebook 8

The key insight is to use greedy sequential matching - for each group, find the first occurrence starting from the current position. The greedy approach works optimally here because we only care about finding groups in order, not finding the best possible arrangement. Time: O(n×m), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Positions	O(n^m)	O(m)	Try every possible starting position for each group
Greedy Sequential Matching	O(n * m)	O(1)	Match each group at the first available position

Brute Force - Try All Positions — Algorithm Steps

Try each position in nums for first group
Recursively try remaining groups after current match
Backtrack if no valid arrangement found

Visualization

Tap to expand

Step-by-Step Walkthrough

Try Group 1

Test all possible positions for first group

Recurse

For each match, try remaining groups

Backtrack

If no solution found, try next position

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool backtrack(int** groups, int* groupSizes, int numGroups, int* nums, int numsSize, int groupIdx, int startPos) {
    if (groupIdx == numGroups) {
        return true;
    }
    
    int* currentGroup = groups[groupIdx];
    int groupLen = groupSizes[groupIdx];
    
    for (int i = startPos; i <= numsSize - groupLen; i++) {
        bool matches = true;
        for (int j = 0; j < groupLen; j++) {
            if (nums[i + j] != currentGroup[j]) {
                matches = false;
                break;
            }
        }
        
        if (matches) {
            if (backtrack(groups, groupSizes, numGroups, nums, numsSize, groupIdx + 1, i + groupLen)) {
                return true;
            }
        }
    }
    
    return false;
}

bool solution(int** groups, int* groupSizes, int numGroups, int* nums, int numsSize) {
    return backtrack(groups, groupSizes, numGroups, nums, numsSize, 0, 0);
}

int main() {
    // Simplified input parsing
    printf("false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n^m)

For each of m groups, we try up to n positions in nums

✓ Linear Growth

Space Complexity

O(m)

Recursion stack depth equals number of groups

✓ Linear Space

32.4K Views

Medium Frequency

~25 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Positions — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler