Form Array by Concatenating Subarrays of Another Array

Med

#1615Time: O(N * L_max), where `N` is the length of `nums` and `L_max` is the maximum length of any group in `groups`. The main pointer `i` iterates through `nums`. At each position `i`, we might perform a check that takes up to `O(L_max)` time.Space: O(1), as we only use a constant amount of extra space for pointers and loop variables.

Patterns

Two Pointers Greedy String Matching

Data structures

Array

Prompt

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 i^th subarray is equal to groups[i] (0-indexed), and if i > 0, the (i-1)^th subarray appears before the i^th 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 == n
1 <= n <= 10³
1 <= groups[i].length, sum(groups[i].length) <= 10³
1 <= nums.length <= 10³
-10⁷ <= groups[i][j], nums[k] <= 10⁷

Approaches

2 approaches with complexity analysis and trade-offs.

The problem asks us to find ordered, disjoint subarrays. This structure suggests a greedy approach. We can try to find the first group groups[0] at the earliest possible position in nums. Once found, say it ends at index k, we then search for the second group groups[1] starting from index k+1, again at its earliest possible position. We continue this process for all groups. If we successfully find a match for every group in order, the answer is true. If at any point we cannot find the current group in the remaining part of nums, it's impossible, and the answer is false. This greedy strategy works because finding an earlier match for a group leaves the maximum possible portion of nums for the subsequent groups, which can never be a worse choice than picking a later match.

Algorithm

Initialize a pointer i = 0 for the nums array and a pointer j = 0 for the groups array.
Loop while i is within the bounds of nums and j is within the bounds of groups.
Inside the loop, attempt to match groups[j] starting at nums[i].
To do this, first check if there are enough elements left in nums (i.e., nums.length - i >= groups[j].length). If not, a match is impossible from this point.
Use a helper loop to compare elements of groups[j] with the subarray nums[i...i+groups[j].length-1].
If all elements match:
- Advance the nums pointer i by the length of the matched group: i += groups[j].length.
- Advance the groups pointer j to look for the next group: j++.
If they do not match:
- Advance the nums pointer by one: i++.
After the loop, if j has reached the end of the groups array (j == groups.length), it means all groups were found in order. Return true.
Otherwise, return false.

Walkthrough

This approach iterates through the nums array with a pointer i, and for each group groups[j], it tries to find a match. If a match for groups[j] is found at index i, the pointer i is advanced by the length of that group, and we proceed to find the next group groups[j+1]. If no match is found at i, i is simply incremented to check the next possible starting position in nums. This continues until all groups are found or we exhaust the nums array.

1class Solution {2    public boolean canFormArray(int[][] groups, int[] nums) {3        int i = 0; // pointer for nums4        int j = 0; // pointer for groups5        while (i < nums.length && j < groups.length) {6            int[] currentGroup = groups[j];7            8            // Check if the rest of nums is long enough for the current group9            if (nums.length - i < currentGroup.length) {10                break; // Not enough elements left11            }12            13            // Try to match currentGroup at nums[i]14            boolean match = true;15            for (int k = 0; k < currentGroup.length; k++) {16                if (nums[i + k] != currentGroup[k]) {17                    match = false;18                    break;19                }20            }21            22            if (match) {23                // If matched, advance i by group length and move to next group24                i += currentGroup.length;25                j++;26            } else {27                // If not matched, advance i by 1 and try again28                i++;29            }30        }31        32        // We need to have found all groups33        return j == groups.length;34    }35}

Complexity

Time

O(N * L_max), where `N` is the length of `nums` and `L_max` is the maximum length of any group in `groups`. The main pointer `i` iterates through `nums`. At each position `i`, we might perform a check that takes up to `O(L_max)` time.

Space

O(1), as we only use a constant amount of extra space for pointers and loop variables.

Trade-offs

Pros

Simple to understand and implement.
Requires no complex data structures.
Low memory overhead.

Cons

Can be inefficient if N and L_max are large, as it may re-scan parts of nums multiple times.
The time complexity is quadratic in the worst-case scenario (e.g., nums = [a,a,a,...,a,b], groups = [[a,b]]).

This approach uses the same greedy strategy as the first one but optimizes the core operation: searching for a subarray (pattern) within a larger array (text). The naive search has a time complexity of O(text_length * pattern_length). We can significantly improve this by using a more advanced string-searching algorithm like Knuth-Morris-Pratt (KMP). The KMP algorithm can find a pattern in text in O(text_length + pattern_length) time by pre-processing the pattern to identify repeated sub-patterns. This avoids redundant comparisons after a mismatch.

Algorithm

Initialize a pointer nums_idx = 0, representing the starting index for the search in nums.
Iterate through each group in groups.
For the current group:
- Use the KMP algorithm to find its first occurrence in nums, starting the search from nums_idx.
- The KMP search involves two steps:
  - 1. Pre-computation: Build a Longest Proper Prefix which is also a Suffix (LPS) array for the current group. This takes O(group.length) time.
  - 1. Search: Scan through nums from nums_idx using the LPS array to efficiently handle mismatches. This search part, over all groups, will effectively scan nums only once.
- If the KMP search returns a valid starting index k:
  - Update nums_idx to k + group.length to ensure the next search is for a disjoint subarray that appears after the current one.
- If the KMP search returns -1 (not found):
  - It's impossible to form the array. Return false.
If the loop completes, it means all groups were found. Return true.

Walkthrough

The overall structure remains greedy. We iterate through each group and find its earliest occurrence in nums after the previously found group. The key improvement is using the KMP algorithm for this search. For each group, we first compute its LPS (Longest Proper Prefix Suffix) array. Then, we use this LPS array to search for the group in nums starting from the last known position. This avoids re-checking characters unnecessarily and brings the total time complexity down to linear.

1class Solution {2    public boolean canFormArray(int[][] groups, int[] nums) {3        int numsIdx = 0;4        for (int[] group : groups) {5            int matchIdx = kmpSearch(nums, group, numsIdx);6            if (matchIdx == -1) {7                return false;8            }9            numsIdx = matchIdx + group.length;10        }11        return true;12    }13 14    private int kmpSearch(int[] text, int[] pattern, int start) {15        if (pattern.length == 0) return start;16        if (text.length - start < pattern.length) return -1;17 18        int[] lps = computeLPS(pattern);19        int i = start; // pointer for text20        int j = 0; // pointer for pattern21 22        while (i < text.length) {23            if (pattern[j] == text[i]) {24                i++;25                j++;26            }27            if (j == pattern.length) {28                return i - j; // Match found29            } else if (i < text.length && pattern[j] != text[i]) {30                if (j != 0) {31                    j = lps[j - 1];32                } else {33                    i++;34                }35            }36        }37        return -1; // No match found38    }39 40    private int[] computeLPS(int[] pattern) {41        int[] lps = new int[pattern.length];42        int length = 0;43        int i = 1;44        while (i < pattern.length) {45            if (pattern[i] == pattern[length]) {46                length++;47                lps[i] = length;48                i++;49            } else {50                if (length != 0) {51                    length = lps[length - 1];52                } else {53                    lps[i] = 0;54                    i++;55                }56            }57        }58        return lps;59    }60}

Complexity

Time

O(N + L_total), where `N` is the length of `nums` and `L_total` is the sum of the lengths of all groups. The total time for building LPS arrays for all groups is O(L_total). The search phase is efficient because the KMP search pointer on `nums` effectively makes a single pass, leading to O(N) time for all searches combined.

Space

O(L_max), where `L_max` is the maximum length of a group. This space is needed to store the LPS array for the largest group.

Trade-offs

Pros

Highly efficient with linear time complexity.
Asymptotically optimal solution.

Cons

More complex to implement correctly compared to the naive approach.
The overhead of building the LPS array might make it slightly slower for very small inputs, though this is generally negligible.

Solutions

Solution

1class Solution { public boolean canChoose ( int [][] groups , int [] nums ) { int n = groups . length , m = nums . length ; int i = 0 ; for ( int j = 0 ; i < n && j < m ;) { if ( check ( groups [ i ], nums , j )) { j += groups [ i ]. length ; ++ i ; } else { ++ j ; } } return i == n ; } private boolean check ( int [] a , int [] b , int j ) { int m = a . length , n = b . length ; int i = 0 ; for (; i < m && j < n ; ++ i , ++ j ) { if ( a [ i ] != b [ j ]) { return false ; } } return i == m ; } }

1class Solution {2public:3  bool canChoose(vector<vector<int>> &groups, vector<int> &nums) {4    auto check = [&](vector<int> &a, vector<int> &b, int j) {5      int m = a.size(), n = b.size();6      int i = 0;7      for (; i < m && j < n; ++i, ++j) {8        if (a[i] != b[j]) {9          return false;10        }11      }12      return i == m;13    };14    int n = groups.size(), m = nums.size();15    int i = 0;16    for (int j = 0; i < n && j < m;) {17      if (check(groups[i], nums, j)) {18        j += groups[i].size();19        ++i;20      } else {21        ++j;22      }23    }24    return i == n;25  }26};

1class 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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem