Matchsticks to Square - Leetcode 473 - Python

[@MonsterhunterFTWWTF]

I managed to pass my Google SWE intern interviews thanks to your videos Neetcode! I talked through all my solutions and applied a lot of the thinking patterns from your videos. Finally after 200+ LC and 5 months of interviewing I’m done.

[@NeetCode]

That's awesome!!! Good luck at Google!

[@hp1612]

Over the last 2 months, I've been following the way you walk through the problems and apply that to my daily practice. Last week I got an offer from Amazon. Thank you so much man. Keep it up. You're changing people's lives.

[@vinayak186f3]

congrats 🎊🎊🎊

[@hp1612]

@@vinayak186f3 thanks

[@NeetCode]

Congrats on the Amazon offer and good luck in your future! Happy I could help :)

[@fsteve6443]

amazon offer in just 2 months?

[@hp1612]

FBA Steven yessir

[@zactamzhermin1434]

For those of y'all getting TLE, I'll just paste what I wrote to another guy on how to fix it. TLDR, you need to memoize. Hi met the same problem as it's today's daily. It's not enough to backtrack blindly. For me it TLE all the time with naive backtracking, even after optimizing by sorting first. So to avoid TLE, you need to memoize the sides array, kind of like the state (memoizing the index i is useless because it does not prevent any recalculation so using python's caching decorator shortcut @cache wouldn't help). Finally of course, you have to transform the sides array into a tuple before memoizing because arrays are immutable and hence not hashable into a set or dict. ``` # add extra base case in the backtracking function if tuple(sides) in memo: return memo[tuple(sides)] ... # outside of the sides backtracking for loop memo[tuple(sides)] = False # we only need to memoize the False case because if it's ever True, we've finished the problem return memo[tuple(sides)] ```

[@aishwaryaranghar3385]

waaao!!!!! thankyouuuuuu

[@LiuGang]

Thank for your valuable comments, it is extremely helpful. BTW, using frozenset or tuple(sorted(sides))) instead of tuple(sides) can even further speed-up.

[@techandmore12]

even that gives me a memory exceed error....

[@Ragdoll333-q5l]

Thanks for your amazing video! I made some optimization: I added a if statement at the end of for loop which means we do not need to loop through all four sides as a starting side. If it does not work from one side at the very beginning, just return False. for j in range(4): if cur[j] + matchsticks[i]

[@techpowercoders8009]

@Qiaoqiao your optimization works !!!

[@dheepthaaanand3214]

So this would be helpful for cases like 3,2,2,1 where each side is supposed to be 2, but 3 overshoots and we can immediately return false instead of trying it in other sides And this works because we are sorting the array in reverse right

[@dheepthaaanand3214]

As another comment mentioned, we can also achieve this by adding if not sides[j]: break, after line 18 Because if matchsticks[i] couldn't build a side, then it can't be used in any other side as well

[@ruiqimao1078]

Similar to leetcode: 698. Partition to K Equal Sum Subsets

[@sidazhong2019]

Not similar, exactly the same.

[@fa11en1ce]

The matches are on fire! What a reckless leetcode problem.

[@Deschuttes]

I've a question. By about the 2:00 mark you've already figured out the "has to be divisible by 4" piece. However, initially figuring out what the problem is even for a brute-force solution isn't always clear, especially if trying to apply a dozen previously seen paradigms to the question. Any tips there on what to do for the very start? It's obvious when you explain it but not as obvious in the heat of the battle.

[@akhma102]

Very interesting solution, Thanks Neet!

[@TheElementFive]

The dual screen format would be especially helpful for recursive problems such as this!

[@jasdn93bsad992]

The backtracking function should return `sides[0] == sides[1] && sides[1] == sides[2] && sides[2] == sides[3];` instead of true. This would prevent false positives.

[@abhishekpawar8458]

This problem is a variation of k subset sum problem. Here k is 4 class Solution { public: bool canForm(vector &vec, int target, int sum, int ind, int k){ if(k == 4){ return true; } if(sum > target){ return false; } if(sum == target){ return canForm(vec,target,0,0,k+1); } for(int i = ind; i < vec.size(); i++){ if(vec[i] < 0){ continue; } sum += vec[i]; vec[i] = -1*vec[i]; if(canForm(vec, target, sum, i+1, k)){ return true; } vec[i] = -1*vec[i]; sum -= vec[i]; } return false; } bool makesquare(vector& matchsticks) { int perimeter = 0; for(int i = 0; i < matchsticks.size(); i++){ perimeter += matchsticks[i]; } if(perimeter%4 != 0){ return false; } int side = perimeter/4; sort(matchsticks.begin(), matchsticks.end(), greater()); return canForm(matchsticks,side,0,0,0); } };

[@shantanukumar4081]

Great Explanation !!!

[@DhruvOberoi]

Added memoization to prevent repeated work. Trick here is to store the index and the _sorted_ sides array as the key. We sort as two different states such as [4, 2, 4, 3] at index i would ultimately do the same work as [2, 3, 4, 4] at that index given we iterate through all 4 values in the sides array. This significantly improves runtime if an interviewer potentially asks for further optimisation beyond sorting the matchsticks array in descending order: def get_hashstring(i): return f"{i}_{'_'.join([str(side) for side in sorted(sides)])}" def backtrack(i): if i == len(matchsticks): return True if get_hashstring(i) in memo: return memo[get_hashstring(i)] for j in range(4): if matchsticks[i] + sides[j] > target: continue sides[j] += matchsticks[i] if backtrack(i + 1): memo[get_hashstring(i)] = True return True sides[j] -= matchsticks[i] memo[get_hashstring(i)] = False return Fals

[@dheepthaaanand3214]

Why do we need to memorize the True scenario? If we were able to build 4 sides, we can directly return True without caching right? I guess caching would help for the False scenario

[@quirkyquester]

this is a hard one, thank you!

[@anjaliyadav9360]

Nice Explaination

[@sandeeprajsaimon8600]

awesome explanation

[@qichengma9336]

i use the same approach and the it's totally depends on luck if leetcode would accept it. 4 trials, only one not reaching time limit. Would you care to try to submit it now and possibly upload some optimize suggestion to the code pls?

[@zactamzhermin1434]

Hi met the same problem as it's today's daily. It's not enough to backtrack blindly. For me it TLE all the time with naive backtracking, even after optimizing by sorting first. So to avoid TLE, you need to memoize the sides array, kind of like the state (memoizing the index i is useless because it does not prevent any recalculation so using python's caching decorator shortcut @cache wouldn't help). Finally of course, you have to transform it into a tuple before memoizing because arrays are immutable and hence not hashable into a set or dict. ``` if tuple(sides) in memo: return memo[tuple(sides)] ... # outside of the sides backtracking for loop memo[tuple(sides)] = False # we only need to memoize the False case because if it's ever True, we've finished the problem return memo[tuple(sides)] ```

[@nihaljoshi2408]

class Solution: def makesquare(self, matchsticks: List[int]) -> bool: side_length = sum(matchsticks) // 4 square = [0] * 4 if sum(matchsticks) / 4 != side_length: return False matchsticks.sort(reverse = True) def backtrack(i): if i == len(matchsticks): return True used = set() for j in range(4): if square[j] + matchsticks[i]

[@premraja55]

Good explanation of the approach!

[@vipinamar8323]

Great explanation as always this is really a Hard problem so the difficulty is inaccurate and btw there is a more generalized version of it leetcode no.698

[@Sulerhy]

This problem is too difficult to imagine

[@huaminwang4748]

Is this the same problem as 698 with k = 4?

[@raghuvamsi4879]

Honestly, I just came to your video to see a bit more optimized solution, like using DP 😭! If you have time pls explain that approach, Thank you.

[@usungyang4934]

special case of 698 Partition to K Equal Sum Subsets.

[@anonymoussloth6687]

Is there a dp solution for this?

[@haydencordeiro]

I initially thought it was a variation of subset sum

[@hrvmhv4391]

@@haydencordeiro You can definitely use the technique provided by @neetcode in this solution kzbin.info/www/bejne/o3POZXxmjZlppas

[@haydencordeiro]

@@hrvmhv4391 hey thanks man . I appreciate it

[@vivekshaw2095]

if you are getting TLE , add if not sides[j]: break after s[j]-=matchsticks[i]

[@ningzedai9052]

This line of optimization is so brilliant !!!

[@orellavie6233]

How is that helpful?

[@vivekshaw2095]

@@orellavie6233 you will not get tle after this

[@orellavie6233]

@@vivekshaw2095 sorry, I am not sure I got ya Any chance for example?

[@pratiksingh9953]

@@orellavie6233 it's an optimization, doesn't changes the TC. Example, length_per_side = 2, and we have already put matchsticks equaling size 2 at, say, top portion, in that case there is no need to make further recursive calls trying to put more matchstick on the top portion.

[@chasehelton2581]

Hey @Neetcode, can you tell me what software you use to draw your solutions?

[@NeetCode]

I use Paint3D

[@melarryify]

Didnt understand solution completely, one line 10, you only match "i == len(matchsticks),", Shoudnt you also make sure that its a square, for eg: sides[0] == sides[1] && sides[1] == sides[2] && sides[2] == sides[3] ?

[@TheRealEz1ck]

@pranav what if the array is [1,2,2,3]? It will still be 8 and divisible by 4, coming out as an integer, but it won't work right?

[@MIHIRHUNDIWALA]

@@TheRealEz1ck Yes you will get length of side of square = integer 2, but look at the for loop closely, before another call we check if the matchstick fits the sidelength of square, and matchstick with length 3 wont fit in any of the sides, so ultimately we will come out of the for loop and return false

[@serhattural3168]

I couldnt figure out how this works without checking lenght of sides at the base case of dfs.

[@dheepthaaanand3214]

​@@serhattural3168we are proceeding for backtracking only if the total can be divided into 4 equal parts. We are storing that unique part length as "length". And in the backtrack call we are filling the sides array without each overshooting this length. If we were able to reach the end of the matchsticks array, that means we were able to fill all 4 sides with this correct length. This is also because we return False if we weren't able to use matchsticks[i] in any of the 4 sides

[@qahoushh]

I've tried this code Time Limit Exceeded

[@nihaljoshi2408]

class Solution: def makesquare(self, matchsticks: List[int]) -> bool: side_length = sum(matchsticks) // 4 square = [0] * 4 if sum(matchsticks) / 4 != side_length: return False matchsticks.sort(reverse = True) def backtrack(i): if i == len(matchsticks): return True used = set() for j in range(4): if square[j] + matchsticks[i]

[@eslammaher5946]

Make sure the array is sorted desc

[@kwaminaessuahmensah8920]

Mans a god.

[@minaFbeshay]

Why don't we start solving this problem by trying to fill the four sides, side by side? If any side failed to be fulfilled, then we are done. This will reduce the time complexity to O(2^n+2): as we have to traverse the matchsticks array 4 times and in each iteration, we check if the current stick fits in the current subset or not. Edit: My proposed solution is not correct. Assuming 1 set is correct and final and should only consider the other 3 sets is in correct, as 1 set could be filled correctly with more than one way.

[@VarunMittal-viralmutant]

The weird thing is that without the .sort(reverse=True), this runs into TLE on LeetCode :( If O(4^N) is anyways the complexity, then O(N log N) should not make any difference, correct ?

[@danielginovker1984]

It's luck of the draw. NC's solution gets TLE sometimes too

[@nihaljoshi2408]

class Solution: def makesquare(self, matchsticks: List[int]) -> bool: side_length = sum(matchsticks) // 4 square = [0] * 4 if sum(matchsticks) / 4 != side_length: return False matchsticks.sort(reverse = True) def backtrack(i): if i == len(matchsticks): return True used = set() for j in range(4): if square[j] + matchsticks[i]

[@melissac4872]

@@nihaljoshi2408 I dont quite get this - for example, when we have [1,1,2,2,2], after the first two 1s square[0]+num[0]+num[1]=2, used set: 2 . And now, the next number num[2] is 2, square[1]+num[2] = 2, we can't have the 2 in the set anymore since it's already existed in the set??

[@nihaljoshi2408]

@@melissac4872 that won't happen right? Because we backtrack first, and then add it to the set.

[@vinayakgupta1]

Partition to k equal sum where k is 4.

[@sathyanarayanankulasekaran5928]

this is exactly partition to k equal sum

[@danielsun716]

This is totally a simplified leetcode 698-partition to K equal sum subsets. For this problem, k == 4. Needcode implement that by the O(k^n) algorithm. But there still be another one which has been posted in 698's video. And the time complexity is O(k * 2^n). In this algorithm, the main thing is for each side of the square, can we include the matchstick or not. Therefore, there are 2 decisions. Also, we cannot use each matchstick twice. So we have to create an array to memorize the state. def makesquare(self, matchsticks: List[int]) -> bool: # if sideSum cannot be integer, it won't be created to a square if sum(matchsticks) % 4: return False # target is each side sum target = sum(matchsticks) / 4 matchsticks.sort(reverse = True) used = [False] * len(matchsticks) def backtrack(i, k, sideSum): # base case: if we finish each side, then it works. if k == 4: return True # if one sideSum = target, then do the next side. if sideSum == target: return backtrack(0, k + 1, 0) for j in range(i, len(matchsticks)): ''' since we have sorted, so if the previous matchstick is skipped, then the next one also should be skipped. But we need to conform it is not out of bound and not be used. ''' if j > 0 and not used[j - 1] and matchsticks[j] == matchsticks[j - 1]: continue if used[j] or sideSum + matchsticks[j] > target: continue used[j] = True if backtrack(j + 1, k, sideSum + matchsticks[j]): return True used[j] = False return False return backtrack(0, 0, 0) And it is pretty efficient of 72 ms implementing time. Hope this would be helpful, if you never watched needcode's 698 solution.

[@vinayak186f3]

14:50 Can someone plz explain why we need to skip , if the if condition is false , I did the opposite way , return false if sides[j]+ matchstick[i] > sidelength and got incorrect output at 170th TC

[@chiraagpala3243]

you still need to try out the other sides

[@CS_n00b]

i never know when to do backtracking

[@jayeshnagarkar7131]

previously my java solution was getting passed through all test cases but now its showing time exceeding . please someone suggest me how to improve. class Solution { public boolean dfs(int i, int left, int top, int right, int bottom, int target, int[] sticks){ if(i == sticks.length && left == target && top == target && right == target && bottom == target){ return true; } if(i == sticks.length) return false; boolean res = false; for(int j = 0; j < 4; j++){ if(j == 0){ left = left + sticks[i]; res = res || dfs(i+1, left, top, right, bottom, target, sticks); left = left - sticks[i]; } else if(j == 1){ top = top + sticks[i]; res = res || dfs(i+1, left, top, right, bottom, target, sticks); top = top - sticks[i]; } else if(j == 2){ right = right + sticks[i]; res = res || dfs(i+1, left, top, right, bottom, target, sticks); right = right - sticks[i]; } else{ bottom = bottom + sticks[i]; res = res || dfs(i+1, left, top, right, bottom, target, sticks); bottom = bottom - sticks[i]; } if(res) return res; } return res; } public boolean makesquare(int[] matchsticks) { Arrays.sort(matchsticks); int sum = Arrays.stream(matchsticks).sum(); if(sum % 4 != 0) return false; int target = sum / 4; return dfs(0,0,0,0,0,target,matchsticks); } }

[@Sulerhy]

never ask some question like this. No one has 2 hours free to read your solution. Learn how to ask a good question!

[@jayeshnagarkar7131]

@@Sulerhy thanks that was helpful

[@hoyinli7462]

this ans seems to be TLE now

[@nihaljoshi2408]

class Solution: def makesquare(self, matchsticks: List[int]) -> bool: side_length = sum(matchsticks) // 4 square = [0] * 4 if sum(matchsticks) / 4 != side_length: return False matchsticks.sort(reverse = True) def backtrack(i): if i == len(matchsticks): return True used = set() for j in range(4): if square[j] + matchsticks[i]

[@aishwaryaranghar3385]

informative vid!

[@anuragtiwari3032]

first comment!!!!