algoadvance

Leetcode 1640. Check Array Formation Through Concatenation

Problem Statement

You are given an array of distinct integers arr and an array of integer arrays pieces, where the integers in pieces are distinct. Arrange the arrays in pieces in any order to form arr. However, you can only take pieces that form an exact subsequence of arr.

Return true if you can form the array arr from pieces. Otherwise, return false.

Example:

Input: arr = [85], pieces = [[85]]
Output: true

Input: arr = [15,88], pieces = [[88],[15]]
Output: true

Input: arr = [49,18,16], pieces = [[16,18,49]]
Output: false

Clarifying Questions

1. Are there any constraints on the size of arr and pieces?
   • Usually, this is defined in the problem description on LeetCode, but it is safe to assume that arrays are reasonably sized such that standard algorithms can process them within time limits.
2. Are the integers in arr all distinct?
   • Yes, the problem statement specifies that integers in arr and pieces are distinct.
3. Can any piece in pieces be used more than once?
   • No, each piece can only be used once.
4. Is the order within each piece important?
   • Yes, the order within each piece is important; they must maintain their order as specified in pieces.

Strategy

1. Map Elements to their Corresponding Pieces
   • Create a hashmap (unordered_map) to quickly find the starting index of any piece by mapping the first element of each piece to its index in the pieces array.
2. Reconstruct arr Using Pieces
   • Iterate through arr using a while loop. For each element in arr, check if it is the start of any piece by consulting the hashmap.
   • If the element starts a piece, check if the subsequent elements in arr match the current piece.
   • If any element does not match or if an element does not start a piece, return false.
3. Complete the Iteration
   • If successfully complete iterating through arr and all elements are matched appropriately, return true.

Code

Here is a C++ implementation of the above strategy:

#include <iostream>
#include <unordered_map>
#include <vector>

bool canFormArray(std::vector<int>& arr, std::vector<std::vector<int>>& pieces) {
    // Create a hashmap to map the first element of each piece to the piece itself
    std::unordered_map<int, std::vector<int>> pieceMap;
    
    for (const auto& piece : pieces) {
        pieceMap[piece.front()] = piece;
    }
    
    // Iterate through the 'arr' array and verify if we can match pieces
    for (int i = 0; i < arr.size(); ) {
        if (pieceMap.find(arr[i]) == pieceMap.end()) {
            return false; // if arr[i] is not the start of any piece
        }
        
        const std::vector<int>& piece = pieceMap[arr[i]];
        for (int j = 0; j < piece.size(); ++j) {
            if (arr[i + j] != piece[j]) {
                return false; // mismatch in piece
            }
        }
        
        i += piece.size(); // move index by the size of the current piece
    }
    
    return true; // all pieces matched correctly
}

Time Complexity

• Time Complexity: O(n + m), where n is the length of arr and m is the total number of elements across all pieces in pieces, since each element in arr and every element in pieces are processed exactly once.
• Space Complexity: O(k), where k is the number of pieces since we store each piece in the map.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?