Check Array Formation Through Concatenation

Language Options

Solution Code


class Solution {
  public boolean canFormArray(int[] arr, int[][] pieces) {
    List concatenated = new ArrayList<>();
    Map 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);
  }
}

Problem Description

So, you think you can just take a bunch of pieces of an array and magically form a complete array? Well, welcome to the world of “Check Array Formation Through Concatenation!” Imagine you have a jigsaw puzzle, but instead of pieces shaped like dinosaurs or flowers, you have integer arrays. Your task is to figure out if you can piece them together to form a complete array.

Let’s say you have a collection of pieces that represent different parts of a delicious pizza. If you have a slice with pepperoni (1, 2) and another slice with mushrooms (3, 4), can you combine them to recreate the whole pizza (1, 2, 3, 4)? Spoiler alert: If you can’t, you might just end up with a sad, incomplete pizza!

Approach Explanation

The code uses a HashMap to map the starting element of each piece to the piece itself. Then, it iterates through the arr, checking if each element can be found in the map. If it can, it adds the corresponding piece to a new list. Finally, it checks if the newly formed list matches the original array. If they match, congratulations! You’ve successfully formed your array. If not, well, better luck next time!

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n + m)
Space Complexity	O(m)

Real-World Example

Imagine you’re at a buffet, and you have a plate (the arr) that you want to fill with different food items (the pieces). Each food item can only be placed on your plate if it’s available at the buffet. If you can successfully fill your plate with the available food items, you’ve formed a complete meal! If not, you might end up with a plate that’s missing your favorite dish.