1764. Form Array by Concatenating Subarrays of Another Array

MediumGreedyArrayString Matching
Leetcode Link

Problem Description

In this problem, we are provided with a two-dimensional integer array called groups, with a length of n. Also, we have another one-dimensional integer array named nums. The objective of the problem is to check whether it's possible to find n disjoint (non-overlapping) subarrays within nums that match the subarrays described in groups in the exact same order.

A few key points to understand the problem:

  • The subarray groups[i] should match exactly with a contiguous portion of nums.
  • If i > 0, the subarray groups[i - 1] must be found in nums before the subarray groups[i]. This enforces the order of the subarrays to be the same as their respective order in groups.
  • Disjoint subarrays mean no element in nums can be part of more than one subarray that matches the groups.

To summarize, the task is to verify if we can find matching sequences in nums for each of the subarrays in groups, following the sequence order and ensuring that the matching sequences in nums do not overlap.

Intuition

When approaching the solution, it is crucial to sequentially search through the nums array and check for a subarray that matches the current groups subarray. If we find a matching subsequence, we move on to the next subarray in groups while also advancing our position in nums past the matched sequence.

Here's a step-by-step approach to the solution:

  1. Initialize two pointers - i to iterate over groups and j to iterate over nums.
  2. Iterate over both arrays using the pointers until either of them reaches the end.
  3. In each iteration, check if the subarray of nums starting from the current position j matches the groups[i] subarray. This can be done by comparing slices of nums.
  4. If a match is found, increment the pointer i to the next subarray in groups and increment the pointer j by the length of the matched group. This ensures the subarrays are disjoint and follows the correct sequence.
  5. If a match is not found, only increment the pointer j to check the next possible starting position in nums.
  6. Continue this process until all groups are matched or we reach the end of nums.

The key to the solution is realizing that all elements in each subarray in groups must appear in the same order and without interruption within nums. This means that the whole subarray must match a contiguous slice of nums. By updating pointers accordingly and ensuring we only progress in groups when a complete match is found, we can determine if there's a way to choose the disjoint subarrays that satisfy the conditions laid out in the problem description.

Ultimately, the goal is to check if the pointer i equals the length of groups, which would indicate all subarrays from groups have been matched in nums. If this is the case, we return true; otherwise, false.

Solution Approach

The problem can be solved using a straightforward two-pointer approach without requiring any additional data structures or complex algorithms. Let's delve into the implementation details of the solution provided:

  1. Initialize Pointers: We start by initializing two pointers i and j to 0. Pointer i will traverse the groups array to check each group one by one, whereas j will traverse the nums array to find the matching subarrays.

  2. Main Loop: We run a while loop where it continues as long as i is less than n (length of groups) and j is less than m (length of nums). This ensures we do not go out of bounds of either array.

  3. Matching Subarrays: Inside the loop, we compare the subarray from nums starting at index j and having the same length as the current group we are checking (represented by groups[i]). If nums[j:j+len(groups[i])] equals groups[i], we have found a matching subarray.

  4. Advance Pointers: When a match is found, we increment i by 1 to move to the next group in groups and j by the length of the matched group (len(g)), ensuring that the next search in nums starts right after the end of the current matched group. This ensures the subarrays are disjoint, as the elements in nums used for the current match no longer participate in future matches.

  5. No Match, Increment j: If there is no match, we just increment j by 1. This is because we are trying to find the next possible starting point for the current group within nums.

  6. Termination: The loop will terminate in one of two cases: We have either found all the groups within nums (success case), or we've reached the end of nums without matching all groups (failure case).

  7. Return Result: After exiting the loop, we check if i == n, which would mean all groups have been matched correctly. If this is true, we return true, indicating that it is possible to choose n disjoint subarrays from nums that match groups in order. If not, we return false.

The simplicity of the two-pointer approach lies in its linear traversal of the nums array and the incremental checking process against groups. It allows us to verify the presence and correct sequencing of subarrays within an array using constant additional space and O(m) time complexity, where m is the length of nums.

Example Walkthrough

To illustrate the solution approach, let's work through a small example. Suppose groups = [[1, 2], [2, 3]] and nums = [1, 2, 3, 2, 3]. We need to check if we can find two disjoint subarrays within nums that match the subarrays described in groups in the exact same order.

Let's start with the initial setup:

  • i (pointer for groups) is at position 0, meaning we are looking for [1, 2].
  • j (pointer for nums) is at position 0.

Now, let's step through the algorithm:

  1. At j = 0, we find that nums[0:2] is [1, 2], which matches groups[0]. So now we increment i by 1 (moving to the next group, which is [2, 3]) and j by 2 (the length of the matched group).

    Current pointers: i = 1, j = 2.

  2. Now looking at nums starting from j = 2, we have nums[2:4] is [3, 2], which does not match groups[1]. So we just increment j by 1 and keep i the same.

    Current pointers: i = 1, j = 3.

  3. From j = 3, we see that nums[3:5] is [2, 3], which matches groups[1]. Now we've matched both subarrays in groups, so we increment i by 1 signaling we've found all group subarrays.

    Current pointers: i = 2 (which equals the length of groups), j = 5 (end of nums).

At the end of the steps, we've matched all subarrays in groups with disjoint subarrays in nums following the correct order. Since i equals the length of groups, we can return true.

So, applying this solution approach to our example, it indicates we can choose disjoint subarrays from nums ([1, 2] and [2, 3]) that exactly match the groups in order.

Python Solution

1from typing import List
2
3class Solution:
4    def canChoose(self, groups: List[List[int]], nums: List[int]) -> bool:
5        # Initialize variables
6        # Total number of groups
7        total_groups = len(groups)
8        # Total number of numbers in 'nums'
9        total_nums = len(nums)
10      
11        # Pointers for the current group and current number in 'nums'
12        group_idx = num_idx = 0
13      
14        # Loop through the groups and 'nums' list
15        while group_idx < total_groups and num_idx < total_nums:
16            # Current group
17            current_group = groups[group_idx]
18            # If current group matches a subsequence in 'nums' starting from current num_idx
19            if current_group == nums[num_idx : num_idx + len(current_group)]:
20                # Move num_idx ahead by the length of the current group since we found a match
21                num_idx += len(current_group)
22                # Move to the next group after a successful match
23                group_idx += 1
24            else:
25                # If no match, move to the next number in 'nums'
26                num_idx += 1
27      
28        # Return True if all groups have been successfully matched, False otherwise
29        return group_idx == total_groups
30

Java Solution

1class Solution {
2
3    // Method to determine if all groups can be found as subsequences in 'nums' array in the given order
4    public boolean canChoose(int[][] groups, int[] nums) {
5        int groupCount = groups.length; // Number of groups
6        int numLength = nums.length; // Length of 'nums' array
7        int currentGroupIndex = 0; // Current index of groups being searched for in 'nums'
8
9        // Loop through 'nums' array looking for each group
10        for (int currentIndexInNums = 0; currentGroupIndex < groupCount && currentIndexInNums < numLength;) {
11            // If current group is found in 'nums' starting from currentIndexInNums
12            if (isGroupMatch(groups[currentGroupIndex], nums, currentIndexInNums)) {
13                // Move currentIndexInNums ahead by the length of the found group
14                currentIndexInNums += groups[currentGroupIndex].length;
15                // Move to the next group
16                ++currentGroupIndex;
17            } else {
18                // If not found, increment the 'nums' index to check the next subsequence
19                ++currentIndexInNums;
20            }
21        }
22        // Return true if all groups have been found, false otherwise
23        return currentGroupIndex == groupCount;
24    }
25
26    // Helper method to check if a group is found at a specific starting index in 'nums'
27    private boolean isGroupMatch(int[] group, int[] nums, int startIndex) {
28        int groupLength = group.length; // Length of the current group
29        int numLength = nums.length; // Length of 'nums' array
30        int groupIndex = 0; // Index for iterating over the group elements
31
32        // Loop over the group and 'nums' starting from startIndex
33        for (; groupIndex < groupLength && startIndex < numLength; ++groupIndex, ++startIndex) {
34            // If any element does not match, return false
35            if (group[groupIndex] != nums[startIndex]) {
36                return false;
37            }
38        }
39        // Return true if all elements matched, meaning the whole group is found
40        return groupIndex == groupLength;
41    }
42}
43

C++ Solution

1class Solution {
2public:
3    // Function to determine if all 'groups' can be chosen in the same order they appear, as subarrays from 'nums'
4    bool canChoose(vector<vector<int>>& groups, vector<int>& nums) {
5        // Lambda function to check if subarray starting from index 'startIdx' in 'nums' matches the 'group'
6        auto isMatch = [&](vector<int>& group, vector<int>& nums, int startIdx) {
7            int groupSize = group.size(), numsSize = nums.size();
8            int i = 0;
9            // Check each element of the 'group' against 'nums' starting from 'startIdx'
10            for (; i < groupSize && startIdx < numsSize; ++i, ++startIdx) {
11                if (group[i] != nums[startIdx]) {
12                    return false; // Mismatch found, return false
13                }
14            }
15            return i == groupSize; // All elements match if we have gone through the entire 'group'
16        };
17
18        int totalGroups = groups.size(), numsSize = nums.size();
19        int currentGroupIndex = 0; // Index of the current group
20
21        // Iterate through 'nums' with index 'j'
22        for (int j = 0; currentGroupIndex < totalGroups && j < numsSize;) {
23            // Check if the current group matches a subsequence starting at 'j'th index of 'nums'
24            if (isMatch(groups[currentGroupIndex], nums, j)) {
25                j += groups[currentGroupIndex].size(); // Move 'j' past this group in 'nums'
26                ++currentGroupIndex; // Move on to the next group
27            } else {
28                ++j; // Mismatch found, move 'j' to check for the current group starting at next index
29            }
30        }
31
32        // If all groups have been matched, return true
33        return currentGroupIndex == totalGroups;
34    }
35};
36

Typescript Solution

1// Represents a group of numbers and the main array of numbers
2type NumGroup = number[];
3type MainArray = number[];
4
5// Function to determine if all 'groups' can be chosen in the same order they appear, as subarrays from 'nums'
6function canChoose(groups: NumGroup[], nums: MainArray): boolean {
7    // Helper function to check if subarray starting from index 'startIndex' in 'nums' matches the 'group'
8    const isMatch = (group: NumGroup, nums: MainArray, startIndex: number): boolean => {
9        const groupSize = group.length;
10        const numsSize = nums.length;
11        let i = 0;
12
13        // Check each element of the 'group' against 'nums' starting from 'startIndex'
14        for (; i < groupSize && startIndex < numsSize; i++, startIndex++) {
15            if (group[i] !== nums[startIndex]) {
16                return false; // Mismatch found, return false
17            }
18        }
19
20        // All elements match if we have gone through the entire 'group'
21        return i === groupSize;
22    };
23
24    const totalGroups = groups.length;
25    const numsSize = nums.length;
26    let currentGroupIndex = 0; // Index of the current group being matched
27
28    // Iterate through 'nums' with index 'j'
29    for (let j = 0; currentGroupIndex < totalGroups && j < numsSize;) {
30        // Check if the current group matches a subarray starting at 'j'-th index of 'nums'
31        if (isMatch(groups[currentGroupIndex], nums, j)) {
32            j += groups[currentGroupIndex].length; // Move 'j' past this matched group in 'nums'
33            currentGroupIndex++; // Move on to the next group
34        } else {
35            j++; // Mismatch found, move 'j' to check for the current group starting at the next index
36        }
37    }
38
39    // If all groups have been matched, return true
40    return currentGroupIndex === totalGroups;
41}
42

Time and Space Complexity

The given Python code is designed to check whether all the groups of numbers in the groups list can be chosen sequentially from the nums list.

Time Complexity:

The time complexity of the code depends on the number of elements in both groups and nums.

Let's denote:

  • n as the length of groups
  • m as the length of nums
  • k as the average length of a group in groups

In the worst-case scenario, you may have to check each element of nums against each group in groups. The worst-case time complexity will be O(n * m * k) since for each group we potentially check each element in nums, and for each comparison, we may compare up to k elements (the length of a group).

However, in practice, the pointer j advances by at least one with each outer loop iteration, so you should not always multiply n and m. The real time complexity is between O(n * k + m) and O(n * m * k) depending on the structure of groups and nums.

Space Complexity:

The space complexity of the code is O(1), which is constant. This is because the code only uses a fixed amount of extra space (a few integer variables like i, j, and g). The slices in nums[j : j + len(g)] do not count towards extra space since Python utilizes an iterator over the sublist rather than copying it. Thus, the use of space does not scale with the size of the input.


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫