Check Array Formation Through Concatenation

Problem

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 arrayarr frompieces. Otherwise, return false.

Examples

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

Solution

Method 1 – Hash Map for Fast Lookup

Intuition

We want to check if we can reconstruct arr by concatenating the subarrays in pieces in any order, but the order within each subarray must be preserved. Since all numbers are distinct, we can map the first element of each piece to the piece itself for fast lookup.

Approach

1. Build a hash map from the first element of each piece to the piece.
2. Iterate through arr, and for each position, check if the current number is the start of a piece. If so, check if the next elements in arr match the piece.
3. If at any point the mapping fails, return false. If we finish, return true.

Code

C++

class Solution {
public:
    bool canFormArray(vector<int>& arr, vector<vector<int>>& pieces) {
        unordered_map<int, vector<int>> mp;
        for (auto& p : pieces) mp[p[0]] = p;
        int i = 0, n = arr.size();
        while (i < n) {
            if (!mp.count(arr[i])) return false;
            auto& v = mp[arr[i]];
            for (int x : v) {
                if (i >= n || arr[i] != x) return false;
                i++;
            }
        }
        return true;
    }
};

Go

func canFormArray(arr []int, pieces [][]int) bool {
    mp := map[int][]int{}
    for _, p := range pieces {
        mp[p[0]] = p
    }
    i := 0
    for i < len(arr) {
        v, ok := mp[arr[i]]
        if !ok {
            return false
        }
        for _, x := range v {
            if i >= len(arr) || arr[i] != x {
                return false
            }
            i++
        }
    }
    return true
}

Java

class Solution {
    public boolean canFormArray(int[] arr, int[][] pieces) {
        Map<Integer, int[]> mp = new HashMap<>();
        for (int[] p : pieces) mp.put(p[0], p);
        int i = 0, n = arr.length;
        while (i < n) {
            if (!mp.containsKey(arr[i])) return false;
            int[] v = mp.get(arr[i]);
            for (int x : v) {
                if (i >= n || arr[i] != x) return false;
                i++;
            }
        }
        return true;
    }
}

Kotlin

class Solution {
    fun canFormArray(arr: IntArray, pieces: Array<IntArray>): Boolean {
        val mp = mutableMapOf<Int, IntArray>()
        for (p in pieces) mp[p[0]] = p
        var i = 0
        while (i < arr.size) {
            val v = mp[arr[i]] ?: return false
            for (x in v) {
                if (i >= arr.size || arr[i] != x) return false
                i++
            }
        }
        return true
    }
}

Python

class Solution:
    def canFormArray(self, arr: list[int], pieces: list[list[int]]) -> bool:
        mp = {p[0]: p for p in pieces}
        i, n = 0, len(arr)
        while i < n:
            if arr[i] not in mp:
                return False
            v = mp[arr[i]]
            for x in v:
                if i >= n or arr[i] != x:
                    return False
                i += 1
        return True

Rust

impl Solution {
    pub fn can_form_array(arr: Vec<i32>, pieces: Vec<Vec<i32>>) -> bool {
        use std::collections::HashMap;
        let mut mp = HashMap::new();
        for p in pieces.iter() {
            mp.insert(p[0], p);
        }
        let mut i = 0;
        while i < arr.len() {
            if let Some(v) = mp.get(&arr[i]) {
                for &x in *v {
                    if i >= arr.len() || arr[i] != x {
                        return false;
                    }
                    i += 1;
                }
            } else {
                return false;
            }
        }
        true
    }
}

Complexity

• ⏰ Time complexity: O(n), where n is the length of arr.
• 🧺 Space complexity: O(n)