Skip to content

1640. Check Array Formation Through Concatenation 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
 public:
  bool canFormArray(vector<int>& arr, vector<vector<int>>& pieces) {
    vector<int> concatenated;
    unordered_map<int, vector<int>> startToPiece;

    for (const vector<int>& piece : pieces)
      startToPiece[piece[0]] = piece;

    for (const int a : arr)
      if (startToPiece.contains(a))
        for (const int num : startToPiece[a])
          concatenated.push_back(num);

    return concatenated == arr;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
  public boolean canFormArray(int[] arr, int[][] pieces) {
    List<Integer> concatenated = new ArrayList<>();
    Map<Integer, int[]> startToPiece = new HashMap<>();

    for (int[] piece : pieces)
      startToPiece.put(piece[0], piece);

    for (final int a : arr)
      for (final int num : startToPiece.getOrDefault(a, new int[]))
        concatenated.add(num);

    return Arrays.equals(concatenated.stream().mapToInt(Integer::intValue).toArray(), arr);
  }
}

1
2
3
4
5
6
7
8
9
class Solution:
  def canFormArray(self, arr: list[int], pieces: list[list[int]]) -> bool:
    concatenated = []
    startToPiece = {piece[0]: piece for piece in pieces}

    for a in arr:
      concatenated += startToPiece.get(a, [])

    return concatenated == arr