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. Your goal is to form arr by concatenating the arrays in pieces in any order. However, you are only allowed to concatenate whole arrays in pieces and cannot reorder the integers within any individual piece array.

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

Input: arr = [91,4,64,78], pieces = [[78],[4,64],[91]]
Output: true

Constraints:

Clarifying Questions

  1. Can each integer appear in both arr and pieces exactly once?
    • Yes, the integers in arr and pieces are distinct and each integer will appear exactly once.
  2. Is there a specific order required for concatenating the arrays in pieces?
    • Yes, when forming arr, the order must match exactly as in arr.
  3. Can pieces be concatenated in any order?
    • Yes, as long as the final concatenated array must match arr in both values and order.

Strategy

To solve this problem, follow these steps:

  1. Create a hashmap (dictionary) where the key is the first element of each subarray in pieces and the value is the entire subarray.
  2. Iterate through the arr and for each element, check if it is the starting element of any subarray in the hashmap.
  3. If a match is found, compare the sequence of numbers starting from that index in arr with the subarray.
  4. If all elements match in each corresponding position, move to the next subarray in arr.
  5. If all elements in arr are matched successfully, return True. Else, return False.

Code

import java.util.HashMap;

class Solution {
    public boolean canFormArray(int[] arr, int[][] pieces) {
        HashMap<Integer, int[]> map = new HashMap<>();

        // Store each piece's first element as key and the piece itself as value
        for (int[] piece : pieces) {
            map.put(piece[0], piece);
        }

        int i = 0;
        while (i < arr.length) {
            // If arr[i] is not a starting number of any piece, return false
            if (!map.containsKey(arr[i])) {
                return false;
            }

            // Get the piece associated with arr[i]
            int[] piece = map.get(arr[i]);
            for (int j = 0; j < piece.length; j++) {
                // Check if the current sequence in arr matches with the piece
                if (arr[i] != piece[j]) {
                    return false;
                }
                i++; // Move to the next element in arr
            }
        }

        return true; // All elements matched
    }
}

Time Complexity

Overall, the time complexity is O(n + m), which makes the solution efficient for the given constraints.

The space complexity is also minimal, mainly for the hashmap and the input array storage, which is O(n).

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