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.
You are given an array of distinct integers
arrand an array of integer arrays
pieces, where the integers in
piecesare distinct. Your goal is to form
arrby concatenating the arrays in
piecesin any order. However, you are not allowed to reorder the integers in each array
trueif it is possible to form the array
pieces. Otherwise, return
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", [ (, ), (, []), ([15, 88], [, ]), ([91, 4, 64, 78], [, [4, 64], ]), ], ) def test_can_form_array(arr, pieces): assert s.canFormArray(arr, pieces)
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 == 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
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.