Check Array Formation Through Concatenation

Easy
1105.

Check Array Formation Through Concatenation

Check Array Formation Through Concatenation is an easy coding problem on arrays and hash table, asked in Amazon and Google interviews.

arr holds distinct integers, and pieces is a list of integer arrays whose values, taken all together, are also distinct. The pieces hold exactly as many numbers as arr.

You may place the pieces one after another in any order, but you may not reorder the numbers inside a piece. Return true if some order of the pieces concatenates to exactly arr.

Example 1

Input
arr = [12,40], pieces = [[40],[12]]
Output
true
Explanation
Place [12] then [40].

Example 2

Input
arr = [7,3,9], pieces = [[9,3,7]]
Output
false
Explanation
The single piece cannot be reversed.

Example 3

Input
arr = [5,21,8,30], pieces = [[30],[21,8],[5]]
Output
true

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 (across all pieces)
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} arr
 * @param {number[][]} pieces
 * @return {boolean}
 */
var canFormArray = function(arr, pieces) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Check Array Formation Through Concatenation — Solution

Check Array Formation Through Concatenation solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Check Array Formation Through Concatenation is an easy coding problem on arrays and hash table, asked in Amazon and Google interviews.

  • Difficulty: Easy
  • Topics: Arrays, Hash Table
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

arr holds distinct integers, and pieces is a list of integer arrays whose values, taken all together, are also distinct. The pieces hold exactly as many numbers as arr.

You may place the pieces one after another in any order, but you may not reorder the numbers inside a piece. Return true if some order of the pieces concatenates to exactly arr.

Example 1

Input: arr = [12,40], pieces = [[40],[12]]
Output: true
Explanation: Place [12] then [40].

Example 2

Input: arr = [7,3,9], pieces = [[9,3,7]]
Output: false
Explanation: The single piece cannot be reversed.

Example 3

Input: arr = [5,21,8,30], pieces = [[30],[21,8],[5]]
Output: true

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 (across all pieces)

Hints for Check Array Formation Through Concatenation

  1. Hint 1

    Because all values are distinct, the first element of a piece can only go in one place.

  2. Hint 2

    Walk through arr from the left; the value at the current position must start some piece.

  3. Hint 3

    Index the pieces by their first element, then match that piece element by element and jump past it.

How to solve Check Array Formation Through Concatenation

Distinct values make the choice forced: whatever value sits at the current position of arr must be the first element of the next piece, and there is at most one piece that starts with it.

Approach

  1. Map each piece's first element to the piece.
  2. Set i = 0. While i < n: look up the piece starting with arr[i]; if there is none, return false.
  3. Compare that piece with arr[i..] element by element; on any mismatch return false; otherwise advance i by the piece's length.
  4. Return true when i reaches n.

Why it works

At every step only one piece could be placed next, so the greedy walk is the only possible arrangement — if it fails, nothing succeeds. When it succeeds, it has consumed arr exactly, and since the pieces hold exactly n distinct values, every piece was used once.

Complexity

  • Time — O(n)
  • Space — O(n)

Pitfalls

  • The order inside a piece is fixed — a piece cannot be reversed or rotated.
  • A piece can be longer than what remains of arr; check bounds while matching.
  • Values go up to 100, so a 101-slot array works as the index instead of a hash map.

Reference solution

Python

from typing import List

def canFormArray(arr: List[int], pieces: List[List[int]]) -> bool:
    first = {p[0]: p for p in pieces}
    i = 0
    while i < len(arr):
        p = first.get(arr[i])
        if p is None or arr[i:i + len(p)] != p:
            return False
        i += len(p)
    return True

Java

public static boolean canFormArray(int[] arr, int[][] pieces) {
    int[] first = new int[101];
    Arrays.fill(first, -1);
    for (int p = 0; p < pieces.length; p++) first[pieces[p][0]] = p;
    int i = 0;
    while (i < arr.length) {
        int idx = first[arr[i]];
        if (idx < 0) return false;
        int[] piece = pieces[idx];
        for (int j = 0; j < piece.length; j++) {
            if (i + j >= arr.length || arr[i + j] != piece[j]) return false;
        }
        i += piece.length;
    }
    return true;
}

C++

bool canFormArray(vector<int>& arr, vector<vector<int>>& pieces) {
    vector<int> first(101, -1);
    for (int p = 0; p < (int)pieces.size(); p++) first[pieces[p][0]] = p;
    int n = arr.size(), i = 0;
    while (i < n) {
        int idx = first[arr[i]];
        if (idx < 0) return false;
        const vector<int>& piece = pieces[idx];
        for (int j = 0; j < (int)piece.size(); j++) {
            if (i + j >= n || arr[i + j] != piece[j]) return false;
        }
        i += piece.size();
    }
    return true;
}

JavaScript

var canFormArray = function(arr, pieces) {
    var first = new Map();
    for (var p = 0; p < pieces.length; p++) first.set(pieces[p][0], pieces[p]);
    var i = 0;
    while (i < arr.length) {
        var piece = first.get(arr[i]);
        if (piece === undefined) return false;
        for (var j = 0; j < piece.length; j++) {
            if (i + j >= arr.length || arr[i + j] !== piece[j]) return false;
        }
        i += piece.length;
    }
    return true;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets