We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Form Array by Concatenating Subarrays of Another Array

Number: 1874

Difficulty: Medium

Paid? No

Companies: Amazon

Problem Description

Given a 2D integer array groups and an integer array nums, determine whether it is possible to choose groups.length disjoint subarrays from nums such that the i-th subarray is exactly equal to groups[i] (in order) and the subarrays appear in nums in the same order as in groups.

Key Insights

  • The subarrays in nums must appear in the same sequential order as groups.
  • Each subarray match must be contiguous and disjoint, meaning indices cannot overlap.
  • A greedy approach can be used: for each group in groups, scan nums (starting from the end of the previous match) to find a contiguous segment that equals the current group.
  • Two pointers help verify if a matching subarray exists starting at a candidate index.
  • Early termination is possible if any group cannot be matched.

Space and Time Complexity

Time Complexity: O(m * n) in the worst-case, where n is the length of nums and m is the total number of elements in groups. Space Complexity: O(1) additional space (ignoring input storage).

Solution

The solution employs a greedy algorithm with the following steps:

  1. Initialize a pointer in nums (let's call it current_index) to mark where to start matching the next group.
  2. For each group in groups, iterate over nums starting from current_index.
  3. For each candidate start index in nums, check if the subsequent elements match the entire group using a helper two-pointer approach.
  4. If a match is found, update current_index to be the index right after the matched subarray so that future matches are disjoint.
  5. If any group cannot be matched, return false; otherwise, return true after all groups are found.

This approach guarantees that the subarrays are taken in order and without overlapping.

Code Solutions

# Python solution using a greedy approach and two pointers.
def canChoose(groups, nums):
    # Pointer for the current position in nums.
    current_index = 0
    # Iterate over each group.
    for group in groups:
        found = False
        
        # Iterate until there is no room for matching the group.
        while current_index + len(group) <= len(nums):
            # Check if the current segment matches the group.
            if nums[current_index:current_index + len(group)] == group:
                # Move the current_index to after the matched segment.
                current_index += len(group)
                found = True
                break
            current_index += 1
        
        # If the current group was not found, return False.
        if not found:
            return False
    # All groups have been matched.
    return True

# Example usage:
groups = [[1,-1,-1],[3,-2,0]]
nums = [1,-1,0,1,-1,-1,3,-2,0]
print(canChoose(groups, nums))  # Expected output: True
← Back to All Questions