Check Array Formation Through Concatenation Leetcode Solution

The problem Check Array Formation Through Concatenation Leetcode Solution provided us with an array of arrays. Along with that we are also given a sequence. We are then told to find if we can somehow construct the given sequence using array of arrays. We can arrange the arrays in any order we want. But we cannot rearrange the elements inside the array. We are also told that the integers are unique in the array of arrays. So before taking a look at the solution, we must take a look at a few examples.

arr = [15,88], pieces = [[88],[15]]

true

Explanation: We can arrange the elements in reverse order. Thus the last array that is 15 will come in front. Similarly, the first element will go in back. This way we can form the given array.

arr = [91,4,64,78], pieces = [[78],[4,64],[91]]

true

Explanation: If we concatenate the last element first, then the middle array, and in the end the first array. This way we can get the required sequence.

Approach for Check Array Formation Through Concatenation Leetcode Solution

The problem Check Array Formation Through Concatenation Leetcode Solution asked us to check whether we can get the required sequence from the array of arrays. The problem seems to be a recursive one, where we need to check all the possibilities. In a recursive manner, we first try to pick an array and then check if the current array is suitable then perform the same operation until we exhaust the sequence. But the advantage that we have here is unique elements. So, we simply check only the first element with the first element of arrays. Even checking this will make sure that we can go ahead with the picked array.

After picking an array, we traverse all the elements in it checking if the array has all the elements of the sequence until we exhaust it. After the exhaustion, the same process is repeated. If there is some mismatch in the element of the array and the sequence, we return false. In the end, when we do not find any mismatch we return true.

Code for Check Array Formation Through Concatenation Leetcode Solution

C++ code

#include <bits/stdc++.h>
using namespace std;

bool canFormArray(vector<int>& arr, vector<vector<int>>& pieces) {
    unordered_map<int,int> entry;
    for(int i=0;i<pieces.size();i++)
        entry[pieces[i][0]] = i;
    int i =  0;
    while(i < arr.size()){
        if(entry.count(arr[i])){
            vector<int> &piece  = pieces[entry[arr[i]]];
            for(auto x: piece)
                if(x != arr[i++])
                    return false;
        } else {
            return false;
        }
    }
    return true;
}

int main(){
    vector<int> arr = {91, 4, 64, 78};
    vector<vector<int>> pieces = {{78},{4,64},{91}};
    cout<<(canFormArray(arr, pieces) ? "true" : "false");
}

true

Java code

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
  public static boolean canFormArray(int[] arr, int[][] pieces) {
        HashMap<Integer, Integer> entry = new HashMap<Integer, Integer>();
        for(int i=0;i<pieces.length;i++)
            entry.put(pieces[i][0], i);
        int i =  0;
        while(i < arr.length){
            if(entry.containsKey(arr[i])){
                int n = pieces[entry.get(arr[i])].length;
                int k = entry.get(arr[i]);
                for(int j=0;j<n;j++)
                    if(pieces[k][j] != arr[i++])
                        return false;
            } else {
                return false;
            }
        }
        return true;
    }
    
  public static void main (String[] args) throws java.lang.Exception {
    int[] arr = {91, 4, 64, 78};
      int[][] pieces = {{78},{4,64},{91}};
      System.out.print(canFormArray(arr, pieces) ? "true" : "false");
  }
}

true

Complexity Analysis

Time Complexity

O(N), where N is the total number of elements in the given sequence. The time complexity has been reduced to linear because of the usage of HashMap.

Space complexity

O(M), where M is the number of the arrays in array of arrays.