{x}
blog image

Form Array by Concatenating Subarrays of Another Array

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

Solution Explanation

This problem asks whether we can find a sequence of disjoint subarrays within nums that exactly match the arrays in groups, maintaining the order specified in groups.

The solution uses a two-pointer approach for efficiency. The outer loop iterates through the groups array, and the inner loop scans nums to find a matching subarray.

Algorithm:

  1. Initialization: Two pointers, i and j, are initialized to 0. i tracks the index of the current group in groups, and j tracks the index of the current element in nums.

  2. Iteration: The outer while loop continues as long as both i (groups index) and j (nums index) are within their respective array bounds.

  3. Subarray Check: Inside the loop, the check function (or equivalent inline check in Python) verifies if the current group (groups[i]) matches a subarray starting at index j in nums.

  4. Match Found: If a match is found:

    • j is advanced by the length of the matched group (groups[i].length).
    • i is incremented to move to the next group.

  5. Match Not Found: If no match is found at the current j index in nums:

    • j is incremented to check the next element in nums.

  6. Final Check: After the loop, if i equals the length of groups (n), it means all groups were successfully found in the correct order and disjointly in nums, so the function returns true. Otherwise, it returns false.

Time Complexity: O(M*K), where M is the length of nums and K is the sum of lengths of all arrays in groups. In the worst-case scenario, the inner loop might iterate through most of nums for each group.

Space Complexity: O(1). The solution uses only a few integer variables for pointers, and the check function uses constant space.

Code Explanation (Python):

The Python code is the most concise. It directly compares subarrays using slicing (nums[j : j + len(g)]). The while loop efficiently searches for the groups in nums. The final return i == n elegantly checks if all groups were found.

Code Explanation (Other Languages):

The Java, C++, and Go solutions are similar in structure to the Python code. They have a separate check function (or inline equivalent) to improve readability and maintainability. The core logic of the two-pointer approach and the final check remain the same.