All code for challenges I am doing here:

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

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

Analysis

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.