## DEV Community is a community of 618,434 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# Day1 - Check Array Formation Through Concatenation

Ruairí O'Brien Updated on ・2 min read

All code for challenges I am doing here:

# leetcode-jan-2021

Just a quick note to say, I am doing this series in the hope this habit of writing about the problems will help me finish the 30 days. I am also improving my Python knowledge while doing this so I am sorry if the code looks terrible! I limit my time each day so the solutions are just my best effort and not the best (or even particularly good) solutions.

## The 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`.

## My Tests

``````import pytest
from .Day1 import Solution

s = Solution()

@pytest.mark.parametrize(
"arr,pieces", [([49, 18, 16], [[16, 18, 49]]), ([1, 3, 5, 7], [[2, 4, 6, 8]])]
)
def test_cannot_form_array(arr, pieces):
assert not s.canFormArray(arr, pieces)

@pytest.mark.parametrize(
"arr,pieces",
[
([], []),
([85], [[85]]),
([15, 88], [[88], [15]]),
([91, 4, 64, 78], [[78], [4, 64], [91]]),
],
)
def test_can_form_array(arr, pieces):
assert s.canFormArray(arr, pieces)
``````

## My Solution

``````from typing import List

class Solution:
def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool:
index = 0
new_index = index
pieces_m = pieces
while index < len(arr):
curr = arr[index]
for a in pieces_m:
if a[0] == curr and a == arr[index : index + len(a)]:
new_index += len(a)
pieces_m.remove(a)
if new_index == index:
return False
else:
index = new_index
return True
``````

## My Commentary

The performance wasn't terrible I guess but memory usage was pretty bad.

The way I thought about it was, if you loop over the array, look to see if any of the pieces start with that value. If it does, check the next segment for a match. If there's a match, bump the index to the end of the segment. If ever there is not a match just short circuit out.

I am a bit new to python but I think one place where I may have paid a price in memory was `arr[index : index + len(a)]`. I need to research and see if that creates a new list each time.

I stopped at the easiest solution that day as I actually ended up doing 2 solutions (the bonus one for that week also) and I went over my allocated time for the evening. Thinking about it after writing here, like most other problems, I could have made this faster with a dict (HashMap). Might give that a shot after the challenge is over.