Taro Logo

Form Array by Concatenating Subarrays of Another Array

#709 Most AskedMedium
15 views
Topics:
Arrays

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


Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

  1. What are the possible ranges and data types for the numbers within both the main array and the subarrays?
  2. Can the input array or the subarrays be empty or null?
  3. If it's impossible to form the target array by concatenating the subarrays, what should I return (e.g., null, empty array, or a specific error code)?
  4. Are the subarrays guaranteed to be distinct, or can there be overlapping or identical subarrays in the input?
  5. Is the order of the subarrays in the concatenated array significant, or can I rearrange them to form the target array?

Brute Force Solution

Approach

The goal is to build a final arrangement by sticking together smaller blocks from a source arrangement. The brute force strategy tries every possible combination of these blocks to see if we can build the desired final arrangement. It's like trying every puzzle piece, in every orientation and position, until we find a solution.

Here's how the algorithm would work step-by-step:

  1. Consider all possible starting positions for the first block within the source arrangement.
  2. For each starting position, check if that block perfectly matches the beginning of the final arrangement we're trying to build.
  3. If it matches, move on to finding the next block. If it doesn't, try the next starting position.
  4. Now, try all possible starting positions for the second block, keeping in mind the second block needs to follow right after the first block.
  5. Check if this second block matches the part of the final arrangement that comes after the first block we already matched.
  6. Keep repeating this process, finding the next block and checking if it fits, until we've used up all the blocks or we've completely matched the entire final arrangement.
  7. If we manage to match the entire final arrangement using the blocks, we've found a solution. If we exhaust all the possibilities, then it can't be done.

Code Implementation

def can_form_array_brute_force(arrangement, blocks):
    number_of_blocks = len(blocks)
    arrangement_length = len(arrangement)

    def solve(current_arrangement, blocks_used):
        if not current_arrangement:
            return True

        for block_index in range(number_of_blocks):
            # Skip already used blocks
            if blocks_used[block_index]:
                continue

            block = blocks[block_index]
            block_length = len(block)

            # Check all possible start positions of this block
            if current_arrangement[:block_length] == block:
                new_blocks_used = blocks_used[:]
                new_blocks_used[block_index] = True

                # Recursive call for the remaining arrangement
                if solve(current_arrangement[block_length:], new_blocks_used):
                    return True

        return False

    # Convert main arr to list of lists to handle base cases
    blocks_used = [False] * number_of_blocks
    return solve(arrangement, blocks_used)

Big(O) Analysis

Time Complexity
O(n^k) – Let n be the length of the target array and k be the number of blocks to concatenate. For each block, we iterate through the target array to find a potential starting position, resulting in O(n) operations per block. Since we have k blocks, and for each block, we potentially need to explore all previous block combinations, the time complexity becomes O(n^k), where in the worst case, we explore all n possible starting positions for each of the k blocks.
Space Complexity
O(K) – The described brute force approach explores different combinations of blocks recursively. The maximum depth of this recursion corresponds to the number of blocks, denoted as K, as each recursive call potentially selects a block. At each level of recursion, we need to store function call information including local variables and the return address, adding to the auxiliary space. Therefore, the recursion stack grows proportionally to K, resulting in O(K) space complexity.

Optimal Solution

Approach

The goal is to see if you can construct a larger collection by piecing together smaller collections in order. The efficient approach involves strategically checking for matches of these smaller collections in the bigger collection, and advancing forward appropriately if a match is found.

Here's how the algorithm would work step-by-step:

  1. Go through the smaller collections one by one, looking to see if they appear in the larger collection, and trying to piece them together.
  2. When you start, begin at the beginning of the larger collection and scan to see if the current smaller collection is present there.
  3. If you find the smaller collection in the larger collection, then note that the smaller collection matches and advance your position in the larger collection past the section you just confirmed matched. Move on to the next smaller collection.
  4. If you do not find the smaller collection starting at your current position in the larger collection, then you cannot piece together the final collection and can stop looking. Return an indication that you failed.
  5. If you successfully iterate through all of the smaller collections and find each of them in the larger collection, then return an indication that you succeeded in piecing the collection together.

Code Implementation

def can_form_array(arr, pieces):
    array_index = 0

    for piece in pieces:
        # Iterate through each piece
        piece_index = 0
        while array_index < len(arr) and piece_index < len(piece):
            # Check if the current element of the piece matches
            if arr[array_index] == piece[piece_index]:
                array_index += 1
                piece_index += 1
            else:
                # If mismatch, reset the piece and advance array index
                array_index -= (piece_index - 0)
                # force exit of piece loop
                piece_index = len(piece)
                break

        # Current piece must be found in array
        # piece not exhausted
        if piece_index != len(piece):
            return False

    # Check if we have exhausted the array
    if array_index != len(arr):
        return False

    return True

Big(O) Analysis

Time Complexity
O(m*n) – Let n be the length of the main array arr and m be the total number of elements across all subarrays in pieces. The algorithm iterates through each subarray in pieces and searches for it within arr. In the worst case, for each subarray, the algorithm might need to scan through almost the entire main array arr to find a match or determine that a match does not exist. This results in a time complexity of O(m*n) because we are comparing each element of subarrays of pieces against sections of the main array arr in the worst case.
Space Complexity
O(1) – The provided algorithm primarily relies on iterative checks and index manipulations within the input arrays. It doesn't create any auxiliary data structures like temporary lists, hash maps, or recursion stacks whose size depends on the input. The space used is limited to a few index variables or pointers to track positions within the arrays, and this number of variables remains constant regardless of the input size, N, where N represents the total number of elements in the input arrays. Therefore, the auxiliary space complexity is O(1).

Edge Cases

Empty 'nums' array.
How to Handle:
Return true if 'groups' is also empty, otherwise return false.
Empty 'groups' array.
How to Handle:
Return true, as no groups need to be found.
A group in 'groups' is empty.
How to Handle:
Throw an exception, or treat the empty group as always matchable and continue to find matches for other groups.
The sum of lengths of all groups exceeds the length of 'nums'.
How to Handle:
Return false, as it is impossible to form the array.
A group in 'groups' cannot be found as a subarray in 'nums'.
How to Handle:
Return false after attempting all groups.
Multiple overlapping occurrences of the same group exist within 'nums'.
How to Handle:
The algorithm should correctly select the earliest occurrence or any valid occurrence without considering overlapping scenarios.
Groups can be reordered to find a solution, but original order yields no solution.
How to Handle:
Return false, as the problem specifies to maintain the order of the groups.
Large input arrays for 'nums' and 'groups', leading to potential performance issues.
How to Handle:
Optimize search for group occurrences in 'nums' using efficient string matching algorithms like KMP.
0/1718 completed