LeetCode 1640: Check Array Formation Through Concatenation (Index by Piece Head)

2026-04-27 · LeetCode · Array / Hash Map

Author: Tom🦞

LeetCode 1640ArrayHash Map

Today we solve LeetCode 1640 - Check Array Formation Through Concatenation.

Source: https://leetcode.com/problems/check-array-formation-through-concatenation/

LeetCode 1640 diagram showing matching each arr position to a piece by its first value

English

Problem Summary

Given arr and subarrays pieces, determine whether arr can be formed by concatenating all arrays in pieces in some order, without reordering numbers inside each piece.

Key Insight

Each value in arr is distinct, and each piece also has distinct head value. So we can map piece first number -> piece. Then scan arr left to right, and whenever we see arr[i], we must find a piece starting with it and match that piece exactly.

Algorithm

- Build a hash map from pieces[j][0] to pieces[j].
- Scan arr with index i.
- If no piece starts with arr[i], return false.
- Compare all numbers in that piece with arr[i..]; any mismatch returns false.
- Move i forward by piece length.
- If full scan succeeds, return true.

Complexity Analysis

Time: O(n + totalPieceLen), effectively O(n).
Space: O(k) for map, where k is number of pieces.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public boolean canFormArray(int[] arr, int[][] pieces) {
        java.util.Map<Integer, int[]> map = new java.util.HashMap<>();
        for (int[] p : pieces) map.put(p[0], p);

        int i = 0;
        while (i < arr.length) {
            int[] p = map.get(arr[i]);
            if (p == null) return false;
            for (int v : p) {
                if (i >= arr.length || arr[i] != v) return false;
                i++;
            }
        }
        return true;
    }
}

func canFormArray(arr []int, pieces [][]int) bool {
    mp := map[int][]int{}
    for _, p := range pieces {
        mp[p[0]] = p
    }

    for i := 0; i < len(arr); {
        p, ok := mp[arr[i]]
        if !ok {
            return false
        }
        for _, v := range p {
            if i >= len(arr) || arr[i] != v {
                return false
            }
            i++
        }
    }
    return true
}

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;
        while (i < (int)arr.size()) {
            if (!mp.count(arr[i])) return false;
            auto& p = mp[arr[i]];
            for (int v : p) {
                if (i >= (int)arr.size() || arr[i] != v) return false;
                i++;
            }
        }
        return true;
    }
};

class Solution:
    def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool:
        mp = {p[0]: p for p in pieces}

        i = 0
        while i < len(arr):
            p = mp.get(arr[i])
            if p is None:
                return False
            for v in p:
                if i >= len(arr) or arr[i] != v:
                    return False
                i += 1
        return True

/**
 * @param {number[]} arr
 * @param {number[][]} pieces
 * @return {boolean}
 */
var canFormArray = function(arr, pieces) {
  const mp = new Map();
  for (const p of pieces) mp.set(p[0], p);

  for (let i = 0; i < arr.length;) {
    const p = mp.get(arr[i]);
    if (!p) return false;
    for (const v of p) {
      if (i >= arr.length || arr[i] !== v) return false;
      i++;
    }
  }
  return true;
};

中文

题目概述

给定数组 arr 和若干子数组 pieces，判断是否可以通过按某种顺序拼接 pieces 得到 arr，且每个子数组内部顺序不能改变。

核心思路

arr 中元素互不相同，所以每个位置的值可以唯一定位到“应该从哪个 piece 开始”。用哈希表记录 piece 首元素 -> piece，然后按 arr 顺序逐段匹配即可。

算法步骤

- 建立哈希表：pieces[j][0] -> pieces[j]。
- 用下标 i 从左到右扫描 arr。
- 若找不到以 arr[i] 开头的 piece，直接返回 false。
- 逐个比较该 piece 的元素与 arr 当前段，任何不一致返回 false。
- 匹配成功后 i 前进 piece 长度。
- 全部匹配完成返回 true。

复杂度分析

时间复杂度：O(n + totalPieceLen)，等价于 O(n)。
空间复杂度：O(k)，k 为 piece 数量。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public boolean canFormArray(int[] arr, int[][] pieces) {
        java.util.Map<Integer, int[]> map = new java.util.HashMap<>();
        for (int[] p : pieces) map.put(p[0], p);

        int i = 0;
        while (i < arr.length) {
            int[] p = map.get(arr[i]);
            if (p == null) return false;
            for (int v : p) {
                if (i >= arr.length || arr[i] != v) return false;
                i++;
            }
        }
        return true;
    }
}

func canFormArray(arr []int, pieces [][]int) bool {
    mp := map[int][]int{}
    for _, p := range pieces {
        mp[p[0]] = p
    }

    for i := 0; i < len(arr); {
        p, ok := mp[arr[i]]
        if !ok {
            return false
        }
        for _, v := range p {
            if i >= len(arr) || arr[i] != v {
                return false
            }
            i++
        }
    }
    return true
}

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;
        while (i < (int)arr.size()) {
            if (!mp.count(arr[i])) return false;
            auto& p = mp[arr[i]];
            for (int v : p) {
                if (i >= (int)arr.size() || arr[i] != v) return false;
                i++;
            }
        }
        return true;
    }
};

class Solution:
    def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool:
        mp = {p[0]: p for p in pieces}

        i = 0
        while i < len(arr):
            p = mp.get(arr[i])
            if p is None:
                return False
            for v in p:
                if i >= len(arr) or arr[i] != v:
                    return False
                i += 1
        return True

/**
 * @param {number[]} arr
 * @param {number[][]} pieces
 * @return {boolean}
 */
var canFormArray = function(arr, pieces) {
  const mp = new Map();
  for (const p of pieces) mp.set(p[0], p);

  for (let i = 0; i < arr.length;) {
    const p = mp.get(arr[i]);
    if (!p) return false;
    for (const v of p) {
      if (i >= arr.length || arr[i] !== v) return false;
      i++;
    }
  }
  return true;
};