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 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.

Examples

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^3
• 1 <= groups[i].length, sum(groups[i].length) <= 10^3
• 1 <= nums.length <= 10^3
• -10^7 <= groups[i][j], nums[k] <= 10^7

Solution

Method 1 – Greedy Two-Pointer Subarray Matching

Intuition

We want to match each group in order as a contiguous subarray in nums, ensuring that the matches are disjoint and in order. We can use a pointer to scan through nums and try to match each group one by one.

Approach

1. Initialize a pointer i at the start of nums.
2. For each group in groups:
   • Scan nums from the current pointer to find a subarray that matches the group.
   • If found, move the pointer past this subarray and continue to the next group.
   • If not found, return false.
3. If all groups are matched in order, return true.

Code

C++

class Solution {
public:
    bool canChoose(vector<vector<int>>& groups, vector<int>& nums) {
        int i = 0;
        for (auto& g : groups) {
            bool found = false;
            while (i + g.size() <= nums.size()) {
                bool match = true;
                for (int j = 0; j < g.size(); ++j) {
                    if (nums[i + j] != g[j]) {
                        match = false;
                        break;
                    }
                }
                if (match) {
                    i += g.size();
                    found = true;
                    break;
                } else {
                    ++i;
                }
            }
            if (!found) return false;
        }
        return true;
    }
};

Go

type Solution struct{}
func (Solution) canChoose(groups [][]int, nums []int) bool {
    i := 0
    for _, g := range groups {
        found := false
        for i+len(g) <= len(nums) {
            match := true
            for j := 0; j < len(g); j++ {
                if nums[i+j] != g[j] {
                    match = false
                    break
                }
            }
            if match {
                i += len(g)
                found = true
                break
            } else {
                i++
            }
        }
        if !found { return false }
    }
    return true
}

Java

class Solution {
    public boolean canChoose(int[][] groups, int[] nums) {
        int i = 0;
        for (int[] g : groups) {
            boolean found = false;
            while (i + g.length <= nums.length) {
                boolean match = true;
                for (int j = 0; j < g.length; j++) {
                    if (nums[i + j] != g[j]) {
                        match = false;
                        break;
                    }
                }
                if (match) {
                    i += g.length;
                    found = true;
                    break;
                } else {
                    i++;
                }
            }
            if (!found) return false;
        }
        return true;
    }
}

Kotlin

class Solution {
    fun canChoose(groups: Array<IntArray>, nums: IntArray): Boolean {
        var i = 0
        for (g in groups) {
            var found = false
            while (i + g.size <= nums.size) {
                var match = true
                for (j in g.indices) {
                    if (nums[i + j] != g[j]) {
                        match = false
                        break
                    }
                }
                if (match) {
                    i += g.size
                    found = true
                    break
                } else {
                    i++
                }
            }
            if (!found) return false
        }
        return true
    }
}

Python

class Solution:
    def canChoose(self, groups: list[list[int]], nums: list[int]) -> bool:
        i = 0
        for g in groups:
            found = False
            while i + len(g) <= len(nums):
                if nums[i:i+len(g)] == g:
                    i += len(g)
                    found = True
                    break
                i += 1
            if not found:
                return False
        return True

Rust

impl Solution {
    pub fn can_choose(groups: Vec<Vec<i32>>, nums: Vec<i32>) -> bool {
        let mut i = 0;
        for g in groups {
            let mut found = false;
            while i + g.len() <= nums.len() {
                if nums[i..i+g.len()] == g[..] {
                    i += g.len();
                    found = true;
                    break;
                }
                i += 1;
            }
            if !found { return false; }
        }
        true
    }
}

TypeScript

class Solution {
  canChoose(groups: number[][], nums: number[]): boolean {
    let i = 0;
    for (const g of groups) {
      let found = false;
      while (i + g.length <= nums.length) {
        let match = true;
        for (let j = 0; j < g.length; j++) {
          if (nums[i + j] !== g[j]) {
            match = false;
            break;
          }
        }
        if (match) {
          i += g.length;
          found = true;
          break;
        } else {
          i++;
        }
      }
      if (!found) return false;
    }
    return true;
  }
}

Complexity

• ⏰ Time complexity: O(m + n), where m is the total length of all groups and n is the length of nums, since each element is visited at most once per group.
• 🧺 Space complexity: O(1), as only pointers and counters are used.