Check Array Formation Through Concatenation

Easy

#1506Time: O(M^2 + N), where N is the length of `arr` and M is the number of pieces. The main `while` loop runs M times in total (once for each piece that forms `arr`). In each iteration of the `while` loop, we might iterate through all M pieces to find the one that starts with `arr[i]`. This search contributes O(M^2) to the complexity. The element-wise comparisons across all successful matches sum up to N comparisons in total. Thus, the overall complexity is O(M^2 + N).Space: O(1), as no additional data structures are used. The space required is limited to a few variables to keep track of the current index and state, which does not depend on the input size.

Data structures

Array Hash Table

Prompt

You are given an array of distinct integers arr and an array of integer arrays pieces, where the integers in pieces are distinct. Your goal is to form arr by concatenating the arrays in pieces in any order. However, you are not allowed to reorder the integers in each array pieces[i].

Return true if it is possible to form the array arr from pieces. Otherwise, return false.

Example 1:

Input: arr = [15,88], pieces = [[88],[15]]
Output: true
Explanation: Concatenate [15] then [88]

Example 2:

Input: arr = [49,18,16], pieces = [[16,18,49]]
Output: false
Explanation: Even though the numbers match, we cannot reorder pieces[0].

Example 3:

Input: arr = [91,4,64,78], pieces = [[78],[4,64],[91]]
Output: true
Explanation: Concatenate [91] then [4,64] then [78]

Constraints:

1 <= pieces.length <= arr.length <= 100
sum(pieces[i].length) == arr.length
1 <= pieces[i].length <= arr.length
1 <= arr[i], pieces[i][j] <= 100
The integers in arr are distinct.
The integers in pieces are distinct (i.e., If we flatten pieces in a 1D array, all the integers in this array are distinct).

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves a straightforward, brute-force search. We iterate through the target array arr with a pointer. At each position, we search through the entire pieces array to find a piece that can start at the current position. If a potential piece is found, we verify if it perfectly matches the corresponding segment in arr. If it does, we advance our pointer and repeat the process. If no matching piece is found at any point, we conclude that arr cannot be formed.

Algorithm

Initialize a pointer i to 0, which will track the current position in arr.
Loop as long as i is less than the length of arr.
Inside the loop, initialize a boolean flag foundMatch to false.
Iterate through each piece in the pieces array.
- If the first element of the current piece matches arr[i]:
  - Set foundMatch to true.
  - Verify that the entire piece matches the corresponding segment in arr starting from i.
  - If any element does not match, it's impossible to form arr, so return false.
  - If the entire piece matches, advance i by the length of the piece and break the inner loop to move to the next segment of arr.
After the inner loop, if foundMatch is still false, it means no piece starts with arr[i]. Return false.
If the outer loop completes, it means i has reached the end of arr, and the array has been successfully formed. Return true.

Walkthrough

The core idea is to build the arr from left to right. We use an index i to keep track of our progress in arr. While i hasn't reached the end of arr, we look for a piece that can be placed at arr[i]. We do this by iterating through all the arrays in pieces. If we find a piece whose first element is arr[i], we then check if the rest of that piece's elements match the subsequent elements in arr. Because all numbers are distinct, there can be at most one such starting piece. If the piece doesn't fully match the segment in arr, we can immediately return false. If it does match, we advance our index i by the length of the matched piece and continue our search for the next piece. If we ever fail to find a piece that starts with arr[i], we also return false. If we successfully reach the end of arr, we return true.

1class Solution {2    public boolean canFormArray(int[] arr, int[][] pieces) {3        int i = 0;4        while (i < arr.length) {5            boolean foundPiece = false;6            for (int[] piece : pieces) {7                if (piece[0] == arr[i]) {8                    foundPiece = true;9                    // Check if the rest of the piece matches10                    for (int j = 0; j < piece.length; j++) {11                        if (i + j >= arr.length || arr[i + j] != piece[j]) {12                            return false;13                        }14                    }15                    i += piece.length;16                    break; // Move to the next segment of arr17                }18            }19            if (!foundPiece) {20                return false; // No piece starts with arr[i]21            }22        }23        return true;24    }25}

Complexity

Time

O(M^2 + N), where N is the length of `arr` and M is the number of pieces. The main `while` loop runs M times in total (once for each piece that forms `arr`). In each iteration of the `while` loop, we might iterate through all M pieces to find the one that starts with `arr[i]`. This search contributes O(M^2) to the complexity. The element-wise comparisons across all successful matches sum up to N comparisons in total. Thus, the overall complexity is O(M^2 + N).

Space

O(1), as no additional data structures are used. The space required is limited to a few variables to keep track of the current index and state, which does not depend on the input size.

Trade-offs

Pros

It uses constant extra space, O(1), as it only requires a few variables for indexing and flags.

Cons

The time complexity is relatively high due to the nested iteration. For each segment of arr that needs to be matched, the algorithm scans the entire pieces array.

This optimized approach significantly improves the time efficiency by using a hash map. Instead of repeatedly searching the pieces array, we first pre-process it by storing all pieces in a hash map. The key for each piece is its first element. This allows us to find the correct piece for any given starting number in constant time on average. We then iterate through arr, and for each segment, we use the map to instantly find the corresponding piece and verify the match.

Algorithm

Create a HashMap to map the starting number of each piece to the piece itself.
Iterate through the pieces array. For each piece, add an entry to the map: map.put(piece[0], piece).
Initialize an index i = 0 to traverse arr.
While i is less than arr.length:
- Look for arr[i] as a key in the map. If it's not present, return false.
- Retrieve the corresponding piece from the map.
- Compare the elements of the piece with the elements of arr starting from index i.
- If there is any mismatch, return false.
- If they match, advance i by the length of the piece.
If the loop completes, it means the entire arr has been successfully constructed. Return true.

Walkthrough

The bottleneck in the brute-force approach is the linear scan to find the right piece. We can eliminate this by using a hash map. We create a map where keys are the first elements of the pieces and values are the piece arrays themselves. This map can be built by iterating through pieces once.

After building the map, we iterate through arr using an index i. For each arr[i], we check if it exists as a key in our map. If not, no piece starts with this number, and we can't form arr, so we return false. If it does exist, we retrieve the piece and verify that it matches the subarray in arr starting at i. If it matches, we advance i by the length of that piece. If it doesn't match, we return false. If we successfully process the entire arr, we return true.

1import java.util.HashMap;2import java.util.Map;3 4class Solution {5    public boolean canFormArray(int[] arr, int[][] pieces) {6        Map<Integer, int[]> map = new HashMap<>();7        for (int[] piece : pieces) {8            map.put(piece[0], piece);9        }10 11        int i = 0;12        while (i < arr.length) {13            if (!map.containsKey(arr[i])) {14                return false;15            }16            17            int[] piece = map.get(arr[i]);18            for (int val : piece) {19                if (i >= arr.length || arr[i] != val) {20                    return false;21                }22                i++;23            }24        }25        26        return true;27    }28}

Complexity

Time

O(N + M), where N is the length of `arr` and M is the number of pieces. Building the map takes O(M) time. The subsequent traversal of `arr` involves one lookup and one comparison for each element of `arr`. Since the total number of elements is N, this part takes O(N) time. Therefore, the total time complexity is O(N + M). Given that M <= N, this can be simplified to O(N).

Space

O(N), where N is the total number of elements in `pieces` (which equals `arr.length`). The hash map stores M key-value pairs, where M is the number of pieces. The keys and references take O(M) space, and the pieces themselves (which the map values refer to) contain N elements in total.

Trade-offs

Pros

Very efficient time complexity, as finding the correct piece is an O(1) operation on average.
The logic is straightforward once the hash map is built.

Cons

This approach requires extra space to store the hash map. The space complexity is proportional to the number of pieces and their total length.

Solutions

Solution

1class Solution {2public3  boolean canFormArray(int[] arr, int[][] pieces) {4    for (int i = 0; i < arr.length;) {5      int k = 0;6      while (k < pieces.length && pieces[k][0] != arr[i]) {7        ++k;8      }9      if (k == pieces.length) {10        return false;11      }12      int j = 0;13      while (j < pieces[k].length && arr[i] == pieces[k][j]) {14        ++i;15        ++j;16      }17    }18    return true;19  }20}

1/** * @param {number[]} arr * @param {number[][]} pieces * @return {boolean} */ var canFormArray =2  function (arr, pieces) {3    const d = new Map();4    for (const p of pieces) {5      d.set(p[0], p);6    }7    for (let i = 0; i < arr.length; ) {8      if (!d.has(arr[i])) {9        return false;10      }11      const p = d.get(arr[i]);12      for (const v of p) {13        if (arr[i++] != v) {14          return false;15        }16      }17    }18    return true;19  };

1class Solution {2public:3  bool canFormArray(vector<int> &arr, vector<vector<int>> &pieces) {4    for (int i = 0; i < arr.size();) {5      int k = 0;6      while (k < pieces.size() && pieces[k][0] != arr[i]) {7        ++k;8      }9      if (k == pieces.size()) {10        return false;11      }12      int j = 0;13      while (j < pieces[k].size() && arr[i] == pieces[k][j]) {14        ++i;15        ++j;16      }17    }18    return true;19  }20};

1class Solution:2    def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool: i = 0 while i < len(arr): k = 0 while k < len(pieces) and pieces[k][0] != arr[i]: k += 1 if k == len(pieces): return False j = 0 while j < len(pieces[k]) and arr[i] == pieces[k][j]: i, j = i + 1, j + 1 return True

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem