Scale Engineer

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
ArrayHash 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.

class Solution {    public boolean canFormArray(int[] arr, int[][] pieces) {        int i = 0;        while (i < arr.length) {            boolean foundPiece = false;            for (int[] piece : pieces) {                if (piece[0] == arr[i]) {                    foundPiece = true;                    // Check if the rest of the piece matches                    for (int j = 0; j < piece.length; j++) {                        if (i + j >= arr.length || arr[i + j] != piece[j]) {                            return false;                        }                    }                    i += piece.length;                    break; // Move to the next segment of arr                }            }            if (!foundPiece) {                return false; // No piece starts with arr[i]            }        }        return true;    }}

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.

Solutions

class Solution {public  boolean canFormArray(int[] arr, int[][] pieces) {    for (int i = 0; i < arr.length;) {      int k = 0;      while (k < pieces.length && pieces[k][0] != arr[i]) {        ++k;      }      if (k == pieces.length) {        return false;      }      int j = 0;      while (j < pieces[k].length && arr[i] == pieces[k][j]) {        ++i;        ++j;      }    }    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 →

Next problem