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
You are given an array of distinct integers
arr
and an array of integer arrayspieces
, where the integers inpieces
are distinct. Your goal is to formarr
by concatenating the arrays inpieces
in any order. However, you are not allowed to reorder the integers in each arraypieces[i]
.Return
true
if it is possible to form the arrayarr
frompieces
. Otherwise, returnfalse
.
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.
Top comments (0)