DEV Community

loading...

Day1 - Check Array Formation Through Concatenation

ruarfff profile image Ruairí O'Brien Updated on ・2 min read

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)
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

Analysis

Alt Text

Alt Text

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.

Discussion (0)

pic
Editor guide