# Form Array by Concatenating Subarrays of Another Array
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/form-array-by-concatenating-subarrays-of-another-array)
Canonical: https://scaleengineer.com/dsa/problems/form-array-by-concatenating-subarrays-of-another-array
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers), [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [String Matching](https://scaleengineer.com/dsa/patterns/string-matching)
**Data structures:** 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 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 <= 103`
* `1 <= groups[i].length, sum(groups[i].length) <= 103`
* `1 <= nums.length <= 103`
* `-107 <= groups[i][j], nums[k] <= 107`

# Approaches
## Greedy Approach with Naive Search
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.
**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.
**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]]).
### Explanation
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.

```java
class Solution {
    public boolean canFormArray(int[][] groups, int[] nums) {
        int i = 0; // pointer for nums
        int j = 0; // pointer for groups
        while (i < nums.length && j < groups.length) {
            int[] currentGroup = groups[j];
            
            // Check if the rest of nums is long enough for the current group
            if (nums.length - i < currentGroup.length) {
                break; // Not enough elements left
            }
            
            // Try to match currentGroup at nums[i]
            boolean match = true;
            for (int k = 0; k < currentGroup.length; k++) {
                if (nums[i + k] != currentGroup[k]) {
                    match = false;
                    break;
                }
            }
            
            if (match) {
                // If matched, advance i by group length and move to next group
                i += currentGroup.length;
                j++;
            } else {
                // If not matched, advance i by 1 and try again
                i++;
            }
        }
        
        // We need to have found all groups
        return j == groups.length;
    }
}
```
### 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`.

## Optimized Greedy Approach with KMP
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.
**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.
**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.
### Explanation
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.

```java
class Solution {
    public boolean canFormArray(int[][] groups, int[] nums) {
        int numsIdx = 0;
        for (int[] group : groups) {
            int matchIdx = kmpSearch(nums, group, numsIdx);
            if (matchIdx == -1) {
                return false;
            }
            numsIdx = matchIdx + group.length;
        }
        return true;
    }

    private int kmpSearch(int[] text, int[] pattern, int start) {
        if (pattern.length == 0) return start;
        if (text.length - start < pattern.length) return -1;

        int[] lps = computeLPS(pattern);
        int i = start; // pointer for text
        int j = 0; // pointer for pattern

        while (i < text.length) {
            if (pattern[j] == text[i]) {
                i++;
                j++;
            }
            if (j == pattern.length) {
                return i - j; // Match found
            } else if (i < text.length && pattern[j] != text[i]) {
                if (j != 0) {
                    j = lps[j - 1];
                } else {
                    i++;
                }
            }
        }
        return -1; // No match found
    }

    private int[] computeLPS(int[] pattern) {
        int[] lps = new int[pattern.length];
        int length = 0;
        int i = 1;
        while (i < pattern.length) {
            if (pattern[i] == pattern[length]) {
                length++;
                lps[i] = length;
                i++;
            } else {
                if (length != 0) {
                    length = lps[length - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
        return lps;
    }
}
```
### 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.
        - 2. **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`.

# Solutions
### Java

```java
class 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 ; } }
```

### CPP

```cpp
class Solution {
public:
  bool canChoose(vector<vector<int>> &groups, vector<int> &nums) {
    auto check = [&](vector<int> &a, vector<int> &b, int j) {
      int m = a.size(), n = b.size();
      int i = 0;
      for (; i < m && j < n; ++i, ++j) {
        if (a[i] != b[j]) {
          return false;
        }
      }
      return i == m;
    };
    int n = groups.size(), m = nums.size();
    int i = 0;
    for (int j = 0; i < n && j < m;) {
      if (check(groups[i], nums, j)) {
        j += groups[i].size();
        ++i;
      } else {
        ++j;
      }
    }
    return i == n;
  }
};

```

### Python

```python
class 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
```