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 ofdistinct integersarr and an array of integer arrayspieces, where the integers inpieces aredistinct. Your goal is to formarr by concatenating the arrays inpiecesin any order. However, you arenot allowed to reorder the integers in each arraypieces[i].

Returntrue if it is possible to form the arrayarr frompieces. Otherwise, returnfalse.

My Tests

importpytestfrom.Day1importSolutions=Solution()@pytest.mark.parametrize("arr,pieces",[([49,18,16],[[16,18,49]]),([1,3,5,7],[[2,4,6,8]])])deftest_cannot_form_array(arr,pieces):assertnots.canFormArray(arr,pieces)@pytest.mark.parametrize("arr,pieces",[([],[]),([85],[[85]]),([15,88],[[88],[15]]),([91,4,64,78],[[78],[4,64],[91]]),],)deftest_can_form_array(arr,pieces):asserts.canFormArray(arr,pieces)

My Solution

fromtypingimportListclassSolution:defcanFormArray(self,arr:List[int],pieces:List[List[int]])->bool:index=0new_index=indexpieces_m=pieceswhileindex<len(arr):curr=arr[index]forainpieces_m:ifa[0]==curranda==arr[index:index+len(a)]:new_index+=len(a)pieces_m.remove(a)ifnew_index==index:returnFalseelse:index=new_indexreturnTrue

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 wasarr[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 adict (HashMap). Might give that a shot after the challenge is over.