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.

[@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 !!!

[@ruiqimao1078]

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

[@sidazhong2019]

Not similar, exactly the same.

[@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.

[@TheElementFive]

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

[@fa11en1ce]

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

[@kagekami-gaming]

By 4:24 i knew what i have to write. Thanks a lot.

[@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.

[@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]

[@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

[@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); } };

[@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.

[@huaminwang4748]

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

[@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.

[@prempeacefulchannel]

Good explanation of the approach!

[@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

[@anjaliyadav9360]

Nice Explaination

[@shantanukumar4081]

Great Explanation !!!

[@chasehelton2581]

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

[@NeetCode]

I use Paint3D

[@Sulerhy]

This problem is too difficult to imagine

[@usungyang4934]

special case of 698 Partition to K Equal Sum Subsets.

[@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.

[@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.

[@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

[@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

[@vinayakgupta1]

Partition to k equal sum where k is 4.

[@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.

[@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.

[@sathyanarayanankulasekaran5928]

this is exactly partition to k equal sum

[@kwaminaessuahmensah8920]

Mans a god.

[@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

[@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

[@aishwaryaranghar3385]

informative vid!

[@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]

[@anuragtiwari3032]

first comment!!!!