Check Array Formation Through Concatenation

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 array arr from pieces. Otherwise, return false.

Input & Output

Example 1 — Basic Case

$ Input: arr = [85], pieces = [[85]]

› Output: true

💡 Note: Single piece [85] exactly matches the target array [85]

Example 2 — Multiple Pieces

$ Input: arr = [15,88], pieces = [[88],[15]]

› Output: true

💡 Note: Can rearrange pieces: [15] + [88] = [15,88] matches target

Example 3 — Impossible Case

$ Input: arr = [49,18,16], pieces = [[16,18,49]]

› Output: false

💡 Note: Piece [16,18,49] cannot be reordered to match [49,18,16]

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

Visualization

Tap to expand

Understanding the Visualization

Input

Target array [15,88] and pieces [[88],[15]]

Process

Find valid arrangement of pieces

Output

Return true if formation is possible

Key Takeaway

🎯 Key Insight: Use the first element of each piece as a unique key for fast lookup and matching

Asked in

a Amazon 15 G Google 8

The key insight is to use the first element of each piece as a unique identifier. Since all integers are distinct, we can create a hash map mapping first elements to their pieces. Best approach is hash map lookup with Time: O(n), Space: O(p).

Common Approaches

Approach	Time	Space	Notes
✓ Hash Map Lookup	O(n)	O(p)	Use hash map to quickly find where each piece belongs in the target array
Brute Force - Try All Permutations	O(n! × m)	O(m)	Generate all possible permutations of pieces and check if any matches arr

Hash Map Lookup — Algorithm Steps

Build hash map: first element → piece
Traverse target array
For each position, lookup piece and verify it matches

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Hash Map

Map first element to piece: 85→[85], 15→[15]

Traverse Array

For each element, lookup piece and verify match

Success

All elements matched with pieces

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define MAX_VAL 10000

bool solution(int* arr, int arrSize, int** pieces, int* pieceSizes, int piecesSize) {
    // Simple hash table using array (assuming values are small)
    int pieceIndex[MAX_VAL];
    memset(pieceIndex, -1, sizeof(pieceIndex));
    
    // Build hash table: first element -> piece index
    for (int i = 0; i < piecesSize; i++) {
        if (pieceSizes[i] > 0) {
            pieceIndex[pieces[i][0]] = i;
        }
    }
    
    int i = 0;
    while (i < arrSize) {
        // Look for a piece that starts with arr[i]
        int idx = pieceIndex[arr[i]];
        if (idx == -1) {
            return false;
        }
        
        // Verify the entire piece matches
        for (int j = 0; j < pieceSizes[idx]; j++) {
            if (i + j >= arrSize || arr[i + j] != pieces[idx][j]) {
                return false;
            }
        }
        
        // Move to next unmatched position
        i += pieceSizes[idx];
    }
    
    return true;
}

int main() {
    // Simplified example
    int arr[] = {85, 15};
    int arrSize = 2;
    int piece1[] = {85};
    int piece2[] = {15};
    int* pieces[] = {piece1, piece2};
    int pieceSizes[] = {1, 1};
    int piecesSize = 2;
    
    bool result = solution(arr, arrSize, pieces, pieceSizes, piecesSize);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through target array, each element checked once

✓ Linear Growth

Space Complexity

O(p)

Hash map stores p pieces where p is number of pieces

✓ Linear Space

28.0K Views

Medium Frequency

~15 min Avg. Time

920 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Hash Map Lookup — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler