Check Array Formation Through Concatenation

🏠 ⬅️ ➡️

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.

Example 1:

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

Example 2:

Input: arr = [49,18,16], pieces = [[16,18,49]] Output: false Explanation: Even though the numbers match, we cannot reorder pieces[0].

Example 3:

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

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 (i.e., If we flatten pieces in a 1D array, all the integers in this array are distinct).
Note: This problem is from LeetCode.
✅ Compiled
✅ Executed
✅ Correct 
program main
    implicit none

    integer, parameter :: n = 2
    integer, parameter :: m = 3
    integer, parameter :: arr(n) = [15, 88]
    integer, parameter :: pieces(m, n) = reshape([88, 15, 49, 16, 18, 49], shape(pieces))
    logical :: result

    print '(L1)', canFormArray(arr, pieces)

contains

    function canFormArray(arr, pieces) result(res)
        implicit none
        integer, intent(in) :: arr(:), pieces(:, :)
        logical :: res
        integer :: i, j, k

        res = .false.

        do i = 1, size(pieces, 2)
            do j = 1, size(pieces, 1)
                if (any(arr /= pieces(j, :))) cycle
                res = .true.
                exit
            end do
            if (res) exit
        end do

    end function canFormArray

end program main
❌ Compiled
❌ Executed
❌ Correct 
program canFormArray
      implicit none

      integer, parameter :: int64 = selected_int_kind(13)

      integer, dimension(:), allocatable :: arr
      integer, dimension(:, :), allocatable :: pieces

      logical :: canFormArray

      integer :: i, j, k

      read(*, *) arr
      read(*, *) pieces

      canFormArray = .true.

      ! Iterate over the arrays in pieces
      do i = 1, size(pieces, 1)
          ! Iterate over the elements in the current array
          do j = 1, size(pieces, 2)
              ! Check if the current element is in arr
              do k = 1, size(arr)
                  if (pieces(i, j) == arr(k)) then
                      ! If it is, remove it from arr
                      arr(k) = arr(size(arr))
                      exit
                  end if
              end do
          end do

          ! If any element was not found in arr, return false
          if (.not. all(pieces(i, :) == arr)) then
              canFormArray = .false.
              exit
          end if
      end do

      ! If all elements were found in arr, return true
      if (canFormArray) then
          write (*, *) "True"
      else
          write (*, *) "False"
      end if

      end program canFormArray
🌐 Data from online sources 
def canFormArray(arr, pieces):
    map = {piece[0]: piece for piece in pieces}

    i = 0
    while i < len(arr):
        if arr[i] not in map:
            return False
        piece = map[arr[i]]
        for num in piece:
            if num != arr[i]:
                return False
            i += 1
    return True

1. First, create a hash map (or, in Python, a dictionary) to store each `piece` in `pieces`, indexed by its first element.
  1. Initialize a variable i to iterate through the arr array.
  2. Use a while loop to check each element in arr with the help of the hash map. If the element is not in the hash map, return false because it means we can't form the array.
  3. If the element is found in the hash map, get the associated piece in pieces.
  4. Use a nested loop (or iterator) to iterate through the elements of the found piece, comparing them with the corresponding elements in arr. If they don't match, return false. Otherwise, increment the index i.
  5. If we successfully iterate through the entire arr array, return true.
🌐 Data from online sources 
#include <vector>
#include <unordered_map>

bool canFormArray(std::vector<int>& arr, std::vector<std::vector<int>>& pieces) {
    std::unordered_map<int, std::vector<int>> map;
    for (auto& piece : pieces) {
        map[piece[0]] = piece;
    }

    int i = 0;
    while (i < arr.size()) {
        if (map.find(arr[i]) == map.end()) {
            return false;
        }
        std::vector<int>& piece = map[arr[i]];
        for (int j = 0; j < piece.size(); ++j) {
            if (piece[j] != arr[i]) {
                return false;
            }
            ++i;
        }
    }
    return true;
}

1. First, create a hash map (or, in Python, a dictionary) to store each `piece` in `pieces`, indexed by its first element.
  1. Initialize a variable i to iterate through the arr array.
  2. Use a while loop to check each element in arr with the help of the hash map. If the element is not in the hash map, return false because it means we can't form the array.
  3. If the element is found in the hash map, get the associated piece in pieces.
  4. Use a nested loop (or iterator) to iterate through the elements of the found piece, comparing them with the corresponding elements in arr. If they don't match, return false. Otherwise, increment the index i.
  5. If we successfully iterate through the entire arr array, return true.