Another Casual Coder
by Marcelo De Barros
19h ago
This is an interesting example to study the performance characteristics of Golang compared to C# for a very particular case (not generalized though).  The same code was written in C# and Golang (literally translated from one to the other). Below you'll be able to see the source code for both. The problem is a simple post-order DFS in a tree-like graph. The code in C# times out (TLE = Time Limited Exceeded). The code in Golang not only works but beats 100% of the other Golang submissions. Take a look the image below: Some potential reasons for the performance gains from Go in this partic ..read more
Another Casual Coder
by Marcelo M De Barros
1M ago
The concept of invariants is very powerful in computer science. Basically, an invariant is something that has certain immutable properties. For example, in the solution to the problem down below, the string current has the invariant property that it is always a "valid string", ready to be added to the retVal collection as soon as the length constraint is met. As we progress throughout the code, we need to assume and enforce the invariant property. Hence, since current is always valid, we can either append a "1" any time (remains valid), or append a "0" only if current is em ..read more
Another Casual Coder
by Marcelo M De Barros
1M ago
You can think of the solution to this problem in two ways: either a prefix sum, or a Dynamic Programming where you're solving the problem for the {r-1, c}, {r, c-1} and {r-1,c-1} and using those solutions to solve the problem for {r,c}. Code is down below, cheers, ACC. Count Submatrices With Equal Frequency of X and Y - LeetCode 3212. Count Submatrices With Equal Frequency of X and Y Medium 8918Add to ListShare Given a 2D character matrix grid, where grid[i][j] is either 'X', 'Y', or '.', return the number of submatrices that contains: grid[0 ..read more
Another Casual Coder
by Marcelo M De Barros
2M ago
IComparer is particularly interesting when dealing with multi-dimensional arrays. In this case, sorting a set of intervals can be tricky if done using standard merge sort or quick sort algorithms. IComparer makes the task super simple (sure behind the scenes it is using qSort, but the sorting function is very simplified in this case with IComparer). The merge of the intervals afterwards becomes a linear pass, and so is the calculation of the days without meetings. Code is down below, cheers, ACC. Count Days Without Meetings - LeetCode 3169. Count Days Without Meetings Medium 411Add to L ..read more
Another Casual Coder
by Marcelo M De Barros
2M ago
Binary Search is a powerful technique in algorithms, used to cut down search space in pretty much constant time. A binary search against a space of 2^100 items takes a mere 100 iterations, again near constant time. When the breakthrough paper "Primes is in P" came out in 2003, it allowed primality test in logN time, exactly the calculation I showed above. Problem below exemplifies the use of binary search. Find the indexes of the words, and perform binary search. Some calculation is needed to take into account the surrounding indexes, but other than that, straightforward. Code is down below, c ..read more
Another Casual Coder
by Marcelo M De Barros
2M ago
Another example where string concatenation leads to TLE while the StringBuilder approach gets to the expected solution. A lot of concatenations using Strings in C# will lead to many objects being created all the time, which not only wastes memory but also time in the process (including GC). This article from SO discusses this theme well: c# - benefits of using a stringbuilder - Stack Overflow Code is down below, cheers, ACC String Compression III - LeetCode 3163. String Compression III Medium 453Add to ListShare Given a string word, compress it using the following algorithm ..read more
Another Casual Coder
by Marcelo M De Barros
3M ago
An interesting problem (which I guarantee you'll never see in real life) to turn a tree upside down (yeah, guaranteed). Three steps taken here: 1. A pre-order approach to find the new root (just a loop going thru the left nodes) 2. A post-order approach to turn every node upside down using the given rules 3. Make the original root a leaf node Code is down below, cheers, ACC. Binary Tree Upside Down - LeetCode 156. Binary Tree Upside Down Medium 258346Add to ListShare Given the root of a binary tree, turn the tree upside down and return the new root. You can turn a binar ..read more
Another Casual Coder
by Marcelo M De Barros
3M ago
This is problem 11 on LeetCode, and the solution is a 2-pointer one, always moving the pointer pointing to the lower wall. The reason can be explained mathematically. Suppose that the current area is: Min(L,R) * N You want to maximize the first term (Min(L,R)) since the second one (N) will always decrease as you move the pointers. Therefore, move the one pointing to minimum height in order to guarantee that the next Min(L,R) will be greater than the previous one. The code is down below, but more interesting is to play with Copilot to debug the code. Purposedly, I introduced a bug where I forgo ..read more
Another Casual Coder
by Marcelo M De Barros
3M ago
This one was a straightforward DP, usually problems related to Min/Max with a constraint can be solved efficiently with DP. To make this post more interesting and to celebrate Mother's Day, here is a poem for all Mothers using Dynamic Programming (thanks to GAI): Mom's Dynamic Love Mom's love, like an algorithm refined, Dynamic and recursive, forever entwined. Her hugs are the base case, warm and secure, While her laughter loops infinitely, that's for sure. In the matrix of memories, she's the constant term, Guiding us through life's loops, each twist and turn. Her kisses, a recursive functio ..read more
Another Casual Coder
by Marcelo M De Barros
3M ago
Polynomial solutions are of course exponentially better than non-polynomial solutions (pun-intended). Comparing an N^2 with a 2^N is a no brainer, same for LogN with a SQRT(N) (the former is way better than the latter). The value of N clearly matters, though. The problem below is solved with an N^4 solution, where N=100. Now it is pushing the limits of LC, which won't ever accept a 10^9 solution (billion), but in some cases 100M is tractable. That's the case here. Best way to solve it IMO is to have a function to check whether the boundaries of the sub-matrix form a valid square. That one is t ..read more

OR