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

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

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

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

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

Those of you who know me know that I'm a big fan of key;value pairs for solving problems, mainly using hash tables. But they aren't cost free. The problem below leads to a TLE if you use a hash table to store all the ones in the matrix (up to 1M ones). Interesting that all the tests pass but you still get a TLE. Solution is to replace the hash table with a simple array (a little more space being used) which does the trick. The code with the hash table that led to TLE is in the screenshot below, and the correct code written down below too. Cheers, ACC. Right Triangles - LeetCode 3128. Rig ..read more

A bit overkill to use MRP here. Also, there is probably a way to do it a little faster by scanning from left, then right, and stopping at the first prime number from each side. Code is down below, cheers, ACC. 3115. Maximum Prime Difference Medium 766Add to ListShare You are given an integer array nums. Return an integer that is the maximum distance between the indices of two (not necessarily different) prime numbers in nums.   Example 1: Input: nums = [4,2,9,5,3] Output: 3 Explanation: nums[1], nums[3], and nums[4] are ..read more

Priority Queues can be used as a standard NLogN sorting mechanism. Usually it isn't used as sorting due to the extra space required for the heap, but in terms of execution time it is as efficient as MergeSort for the worst case and even better than QuickSort on some cases. If you have a handy implementation of PQueue, don't be afraid of using it for sorting. Problem below requires a sorting of the elements based on the X-coordinate, followed by a linear scanning counting the number of rectangles. PQueue comes to the rescue here. Code is down below, cheers, ACC. Minimum Rectangles to Cover P ..read more

It has been a while since I had solved a PE problem. This one is simple, difficulty is 5%. As always I cannot share the solution or full code due to the rules of engagement with PE, but I can share the overall approach: 1/ Figure out a way to quickly find the Pisano Period. Hint: AI is your friend, so is Google or Bing 2/ Brute force it up to 1B. Takes a couple of minutes Cheers, ACC #853 Pisano Periods 1 - Project Euler ..read more

This problem requires a solution similar to the longest increasing subsequence one. Basically on each step you either reset the current streak or increments it, adding the value to the return value. Code is down below, cheers, ACC. Count Alternating Subarrays - LeetCode 3101. Count Alternating Subarrays Medium 1507Add to ListShare You are given a binary array nums. We call a subarray alternating if no two adjacent elements in the subarray have the same value. Return the number of alternating subarrays in nums.   ..read more