1640. Check Array Formation Through Concatenation

EasyArrayHash Table
Leetcode Link

Problem Description

The problem presents a scenario where you have two arrays: arr is a single list of distinct integers, and pieces is a list of lists with each sublist also containing distinct integers. The goal is to determine if it is possible to form the arr array by concatenating the subarrays in pieces in any order. However, it is important to note that you cannot reorder the elements within the subarrays in pieces. You must use the subarrays in pieces as they are.

For example, if arr = [1,2,3,4] and pieces = [[2,3], [4], [1]], you could form arr by concatenating [1], [2,3], and [4] in order. However, if pieces were [[2,3], [1,4]], you could not form arr because that would require reordering the integers within a piece, which is not allowed.

The task is to return true if you can form arr by such concatenations or false otherwise.

Intuition

The intuition for solving this problem is to use a hash map to easily find the location of the subarrays in pieces that can potentially be concatenated to match arr. The first element of each subarray in pieces can be used as a unique key in the hash map because we are given that all integers are distinct. This way, you can quickly look up the starting element of each piece to see if you can continue building arr from the current position.

To arrive at the solution, we can follow these steps:

  1. Create a hash map (d) where each key is the first integer of a subarray in pieces, and the value is the subarray itself.

  2. Iterate over arr, and at each step:

    • Check if the current element exists in our hash map (d). If it doesn’t, it means there's a number in arr that isn't the start of any piece, and thus we cannot form arr fully. Return false.
    • If the present element is in d, fetch the corresponding subarray and check if the subsequent elements in arr match this subarray exactly. If they don’t, return false because the ordering within a piece cannot be altered.
    • If they do match, increment the index (i) by the length of the piece, effectively 'skipping' over these elements in arr.
  3. If you reach the end of arr without returning false, it means you've been able to build all of arr using the pieces in the correct order, and hence return true.

The solution demonstrates a greedy approach, building arr incrementally from the start by mapping each element to a potential subarray from pieces, ensuring the order within both arr and pieces remains unchanged.

Solution Approach

The solution approach to this problem uses a hash table (in Python, a dictionary) and array slicing.

  1. Creating a hash table: A hash table (d) is created where for every subarray (p) in pieces, there's an entry with the key being the first element of the subarray and the value being the subarray itself. This allows us to quickly look up the piece that could potentially match a segment of arr starting from a given position.

    1d = {p[0]: p for p in pieces}

    This is very efficient because finding an item in a hash table has an average-case time complexity of O(1).

  2. Iterating over the target array (arr): We then start walking through arr from the first element, intending to find a match in d.

    1i, n = 0, len(arr)
    2while i < n:
  3. Checking existence in the hash table: For each element in arr, we first check whether this element is a key in our hash table d.

    1if arr[i] not in d:
    2    return False

    If it's not present, it means we cannot find a subarray in pieces to continue our concatenation, and the function should return false.

  4. Comparing subarrays: If we find the element in d, we fetch the corresponding subarray (p). Then we slice arr starting from the current index i up to the length of the p and compare it with the p.

    1p = d[arr[i]]
    2if arr[i : i + len(p)] != p:
    3    return False

    If the sliced portion of arr and the subarray p do not match, it means the current segment cannot be formed with the pieces provided, and we return false.

  5. Incrementing the index: If a match is found, we increment our current index (i) by the length of the p to move past the part of arr we just confirmed.

    1i += len(p)
  6. Returning the result: After the loop, if we haven't returned false, it means arr has been successfully formed by concatenating the subarrays in pieces, we return true.

    1return True

This algorithm's overall time complexity is O(n), where n is the number of elements in arr, as we are iterating through each element once and hash map operations are O(1) on average. It's an efficient and effective way to solve the problem provided.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's illustrate the solution approach with a small example:

Say we have arr = [5, 6, 7] and pieces = [[7], [5, 6]]. According to the problem, we can only concatenate subarrays from pieces to form arr and cannot change the order within each subarray.

Step 1: Creating a hash table

Firstly, we create a hash table where each key is the first element of the subarray from pieces, and the value is the subarray itself.

1d = {7: [7], 5: [5, 6]}

The hash table d is now {5: [5, 6], 7: [7]}.

Step 2: Iterating over the target array (arr)

We aim to match elements in arr to keys in d:

1i, n = 0, len(arr)  # i - current index, n - length of arr
2while i < n:

Step 3: Checking existence in the hash table

For each element arr[i], check if it is a key in d.

  • For i = 0, arr[i] is 5. Since 5 is a key in d, we can continue to the next step.
  • If arr[i] were not in d, for example, 8, we would return False.

Step 4: Comparing subarrays

Now, we need to check if the segment of arr starting at index i matches the subarray in d.

  • For i = 0, d[arr[i]] is [5, 6]. We compare arr[0:2] ([5, 6]) with [5, 6], and they match.

If they didn't match or if arr had fewer elements than the subarray p, we would return False.

Step 5: Incrementing the index

After finding a match, we skip over the matched part of arr:

  • Since the length of [5, 6] is 2, we increment i by 2: i += len([5, 6]).

We then continue to the next iteration of the loop with i = 2.

Step 6: Iterating continues

  • Now i = 2 and arr[i] is 7. We look up 7 in the hash table and get [7].
  • We compare arr[2:3] ([7]) with [7] and they match.

Step 7: Returning the result

Having reached the end of arr without returning False, we can conclude that arr can be formed by concatenating subarrays in pieces. Therefore, the final result is True.

By following these steps, we demonstrated that arr can be formed from pieces. This approach efficiently utilizes the hash table for quick lookups and array slicing for comparison, resulting in an efficient solution.

Solution Implementation

1class Solution:
2    def can_form_array(self, arr: List[int], pieces: List[List[int]]) -> bool:
3        # Create a dictionary that maps the first element of each piece to the piece itself
4        index_dict = {piece[0]: piece for piece in pieces}
5      
6        i = 0  # Initialize a pointer to iterate through 'arr'
7        n = len(arr)  # The length of 'arr'
8      
9        # Loop through 'arr' using the pointer 'i'
10        while i < n:
11            # If the current element in 'arr' does not start any piece, return False
12            if arr[i] not in index_dict:
13                return False
14          
15            # Retrieve the piece that starts with 'arr[i]'
16            current_piece = index_dict[arr[i]]
17          
18            # Check if the next elements in 'arr' match this piece
19            if arr[i: i + len(current_piece)] != current_piece:
20                return False
21          
22            # Move the pointer 'i' forward by the length of the matched piece
23            i += len(current_piece)
24      
25        # If all pieces are matched without any issues, return True
26        return True
27
1class Solution {
2    public boolean canFormArray(int[] arr, int[][] pieces) {
3        // Create a hashmap to easily look up if a piece can be placed.
4        Map<Integer, int[]> piecesMap = new HashMap<>();
5      
6        // Iterate over pieces and map the first element of each piece to the piece itself.
7        for (int[] piece : pieces) {
8            piecesMap.put(piece[0], piece);
9        }
10      
11        // Use 'i' to traverse the arr array.
12        for (int i = 0; i < arr.length;) {
13            // Check if there is a starting piece for the current element in arr.
14            if (!piecesMap.containsKey(arr[i])) {
15                return false; // No piece starts with this element, return false.
16            }
17
18            // Get the piece that starts with arr[i].
19            for (int val : piecesMap.get(arr[i])) {
20                // Check if the element in arr matches the element in the piece.
21                if (arr[i++] != val) {
22                    return false; // Element doesn't match, array can't be formed.
23                }
24            }
25        }
26      
27        // All elements matched correctly, array can be formed.
28        return true;
29    }
30}
31
1#include <unordered_map>
2#include <vector>
3
4class Solution {
5public:
6    // Returns true if the arr can be formed by concatenating subarrays from pieces
7    bool canFormArray(std::vector<int>& arr, std::vector<std::vector<int>>& pieces) {
8        // Creating a hashmap to map the first element of each piece to its corresponding vector
9        std::unordered_map<int, std::vector<int>> piece_map;
10        for (auto& piece : pieces) {
11            piece_map[piece[0]] = piece;
12        }
13
14        // Iterate over the elements of arr
15        for (int i = 0; i < arr.size();) {
16            // If the current element of arr is not the first element of any piece, return false
17            if (piece_map.count(arr[i]) == 0) {
18                return false;
19            }
20            // Retrieve the piece that starts with the current element of arr
21            for (int& value : piece_map[arr[i]]) {
22                // Check if the current subsequence of arr matches the piece
23                // Increment index i for each match
24                if (arr[i++] != value) {
25                    return false; // If there's a mismatch, return false
26                }
27            }
28        }
29
30        // If all elements of arr are matched with a piece correctly, return true
31        return true;
32    }
33};
34
1/**
2 * Checks if it's possible to form an array by concatenating subarrays in 'pieces' to match 'arr'.
3 * Each subarray in 'pieces' will appear at most once in 'arr'.
4 * The concatenation of all subarrays in 'pieces' is allowed to be in any order.
5 *
6 * @param {number[]} arr - The target array that we want to form.
7 * @param {number[][]} pieces - The subarrays that can be concatenated to form 'arr'.
8 * @returns {boolean} true if the 'arr' can be formed from 'pieces', otherwise false.
9 */
10function canFormArray(arr: number[], pieces: number[][]): boolean {
11    // The length of the target array.
12    const targetLength = arr.length;
13
14    let currentIndex = 0; // A pointer to track the current index in 'arr'
15
16    // While there are unprocessed elements in 'arr'
17    while (currentIndex < targetLength) {
18        // The current element we want to find in 'pieces'
19        const currentTargetValue = arr[currentIndex];
20
21        // Find the subarray in 'pieces' that starts with 'currentTargetValue'
22        const currentPiece = pieces.find(piece => piece[0] === currentTargetValue);
23
24        // If no such subarray exists, we cannot form 'arr'
25        if (!currentPiece) {
26            return false;
27        }
28
29        // Iterate through the elements of the found subarray
30        for (const item of currentPiece) {
31            // If any element doesn't match the corresponding element in 'arr', we cannot form 'arr'
32            if (item !== arr[currentIndex]) {
33                return false;
34            }
35            // Move the index in 'arr' forward
36            currentIndex++;
37        }
38    }
39
40    // If we processed all elements without issues, we can form 'arr'
41    return true;
42}
43

Time and Space Complexity

The given Python code defines a method canFormArray which determines whether an array can be formed by concatenating the arrays in a given list pieces. Let's analyze the time and space complexity of the code:

Time Complexity

  • The construction of the dictionary d has a time complexity of O(m), where m is the total number of elements in pieces, since each of the k sublists in pieces is iterated over once.
  • The while loop iterates over each element of arr, which has n elements. Inside the loop, the check if arr[i] is in d is O(1) due to the hash map lookup, and the slice comparison arr[i : i + len(p)] != p is O(l) where l is the length of the current p in pieces.
  • In the worst case scenario, all n elements need to be checked, and we might have to compare against each of the k pieces with an average length of l (assuming the pieces are approximately the same size; if they vary significantly, we'd consider an average size for a more accurate analysis).

Putting it all together, the overall time complexity is O(m + n * l), where m is the total number of elements in pieces, n is the number of elements in arr, and l is the average length of the subarrays in pieces.

Space Complexity

  • The main extra space usage comes from the dictionary d, which contains at most k entries where k is the number of sublists in pieces. The space complexity for storing d is O(k).
  • There is also the space used by variable p which at maximum can hold a list of length l. However, since l is at most the length of arr, this does not exceed O(n) space.
  • Therefore, the space complexity of the code is O(k + n).

Considering that the space required for d is dependent on the number k of sublists and each list is stored entirely, whereas the space required for p and other local variables is negligible compared to the space for d, we could simplify the space complexity to O(m) because m includes both the number of sublists and their individual lengths.

Learn more about how to find time and space complexity quickly using problem constraints.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

How many times is a tree node visited in a depth first search?


Recommended Readings