Another Casual Coder

85 FOLLOWERS

This is what I do after the kids go to bed and before Forensic Files.
I casually write code.

Another Casual Coder

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

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

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

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

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

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

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

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

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

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