Day1 - Check Array Formation Through Concatenation
Tags: leetcode, python, challenge
Published: 2021-01-03 22:30:05

All code for challenges I am doing here:

{% github https://github.com/ruarfff/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

[LeetCode Link](https://leetcode.com/problems/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`.

## My Tests

```python
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

```python
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
```

## Analysis

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/hg70mdddcxyew3cd8cis.png)

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/04mkihcrj8arhj5djtz1.png)

## 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](https://docs.python.org/3/tutorial/datastructures.html#dictionaries) (HashMap). Might give that a shot after the challenge is over.