Boris Coding Blog

Here is the problem:  Number of Distinct Substrings in a String - LeetCode 1698. Number of Distinct Substrings in a String Hard 4 0 Add to List Share Given a string  s , return  the number of  distinct  substrings of   s . A  substring  of a string is obtained by deleting any number of characters (possibly zero) from the front of the string and any number (possibly zero) from the back of the string.   Example 1: Input: s = "aabbaba" Output: 21 Explanation: The set of distinct strings is ["a","b","aa","bb","ab","ba","aab","abb","bba","aba","aabb","abba","bbab","baba","aabba","abbab","bbaba","aabbab","abbaba","aabbaba"] Example 2: Input: s = "abcdefg" Output: 28   Constraints: 1 <= s.length <= 500 s  consists of lowercase English letters. Accepted 118 Submissio

I've written before about  two-pointers techniques  before. In this particular case (Medium LC), you'll need to use some sort of hash or memo to keep track of all the unique values, but the two-pointers solution remains standard. Here it is:  Maximum Erasure Value - LeetCode You are given an array of positive integers  nums  and want to erase a subarray containing  unique elements . The  score  you get by erasing the subarray is equal to the  sum  of its elements. Return  the  maximum score  you can get by erasing  exactly one  subarray. An array  b  is called to be a  subarray  of  a  if it forms a contiguous subsequence of  a , that is, if it is equal to  a[l],a[l+1],...,a[r]  for some  (l,r) .   Example 1: Input: nums = [4,2,4,5,6] Output: 17 Explanation: The optimal subarray here is [2,4,5,6]. Example 2: Input: nums = [5,2,1,2,5,2,1,2,5] Output: 8 Explanation: The optimal subarray here is [5,2,1] or [1,2,5].   Constraints: 1 <= nums.length <= 10 5 1 <= nums[i

Howdy Everyone,   Catching up on the Advent of Code, I got to day 10 today, here it is:  Day 10 - Advent of Code 2020 .  Description is a little long and tedious but in the end you get the gist of it. Part 1 is looking for a simple path from 0 to max. I looked at the input size and it did not seem that large, so I thought backtracking would do the trick. Indeed a simple straightforward DFS backtracking from 0 to max works. Part 2 asks for the count of ALL paths. That's a little tricky, especially after reading this part of the description: You glance back down at your bag and try to remember why you brought so many adapters; there must be  more than a trillion  valid ways to arrange them! Surely, there must be  an efficient way  to count the arrangements. That should give you the hint that the "adventers" are looking for a Dynamic Programming (DP) solution. Luckily, this DP is super simple, and the way that I like to implement DP is by construction from 0..max. Basically

Tricky one, resembling more like a medium LC problem. Here it is:  Day 8 - Advent of Code 2020 Especially the second part of the problem: --- Part Two --- After some careful analysis, you believe that  exactly one instruction is corrupted . Somewhere in the program,  either  a  jmp  is supposed to be a  nop ,  or  a  nop  is supposed to be a  jmp . (No  acc  instructions were harmed in the corruption of this boot code.) The program is supposed to terminate by  attempting to execute an instruction immediately after the last instruction in the file . By changing exactly one  jmp  or  nop , you can repair the boot code and make it terminate correctly. For example, consider the same program from above: nop +0 acc +1 jmp +4 acc +3 jmp -3 acc -99 acc +1 jmp -4 acc +6 If you change the first instruction from  nop +0  to  jmp +0 , it would create a single-instruction infinite loop, never leaving that instruction. If you change almost any of the  jmp  instructions, the program will still eventu

I've written before about two-pointers techniques  before. Usually this technique works well with sorted array: have the first pointer in the very left, second pointer in the very right, and do the processing until the pointers cross each other. If the array is already sorted, the solution is linear, otherwise you'll end up with an NLogN. This problem exemplifies the technique:  Max Number of K-Sum Pairs - LeetCode 1679. Max Number of K-Sum Pairs Medium 46 4 Add to List Share You are given an integer array  nums  and an integer  k . In one operation, you can pick two numbers from the array whose sum equals  k  and remove them from the array. Return  the maximum number of operations you can perform on the array .   Example 1: Input: nums = [1,2,3,4], k = 5 Output: 2 Explanation: Starting with nums = [1,2,3,4]: - Remove numbers 1 and 4, then nums = [2,3] - Remove numbers 2 and 3, then nums = [] There are no more pairs that sum up to 5, hence a total of 2 operations. Example 2:

This was an interesting one, but still comparable to an "easy" Leetcode problem (I'm sure this will get tougher as the days go by):  Day 5 - Advent of Code 2020 The analysis of each seat is a variation of a Binary Search . What I did is one function that given a string returns the number associated with it. That way you can call it for the 0-6 and 7-9 parts of the string. After that, the first part is easy, just getting the max. The second part is also relatively easy: sort the entries, and then go one by one from the very beginning looking for the first gap. Once found, that's your solution. Code is down below, cheers, ACC. static void Main(string[] args) { FileInfo fi = new FileInfo(args[0]); StreamReader sr = fi.OpenText(); List list = new List (); int max = 0; while (!sr.EndOfStream) { string str = sr.ReadLine().Trim(); if (!String.IsNullOrEmpty(str)) { int val = SeatNumber(str.Substring(0, 7)) * 8 + Sea

Super cool the Advent of Code - something fun to do in the last 30+ days of the year. Check it out. Two challenges every night for a little over a month:  Day 3 - Advent of Code 2020 For day #3, best is to push the input to a list of strings, and then create a function that takes that list, the col and the row, looking for the trees. Some modular math in the middle to account for the infinite cols. First submission failed due to the fact that the product will be larger than Int.Max. Switch to long, and it works. Fun idea. Code is below, no spoillers (won't give away the result). Cheers, ACC. using System; using System.IO; using System.Collections; using System.Collections.Generic; using System.Text; namespace AdventOfCode { class Program { static void Main(string[] args) { FileInfo fi = new FileInfo(args[0]); StreamReader sr = fi.OpenText(); List input = new List (); while (!sr.EndOfStream) {

Students at the University of Buenos Aires have published a very-short paper this month (November, 2020) providing an astonishing formula to generate all primes - in sequence. This has been the Holy Grail in Number Theory: is there a way to generate all the prime numbers one by one with a deterministic formula? The students have proved that there is. Their paper is here:  2010.15882.pdf (arxiv.org) The formula is actually very simple. Here it is: And F1 should be a constant which "magically" is F1 = 2.9200509773161350318170795639 This constant is being called now the "Buenos Aires Prime Constant". The only problem is how to find this constant without knowing a priori all the primes. This is the current open problem. If someone can extend this constant to a very-very-very large number of decimal points, the problem of primes generation will be solved. With the current one, though, it is good enough to generate few primes, in order. The code below (using Miller-Rabin

If you work with graphics and eventually you want to pivot a binary tree using a different node as the root, this might be interesting to you. Here is the problem:  Change the Root of a Binary Tree - LeetCode 1666. Change the Root of a Binary Tree Medium 6 14 Add to List Share Given the  root  of a binary tree and a  leaf  node, reroot the tree so that the  leaf  is the new root. You can reroot the tree with the following steps for each node  cur  on the path  starting from the  leaf  up to the  root ​​​  excluding the root : If  cur  has a left child, then that child becomes  cur 's right child. Note that it is guaranteed that  cur  will have at most one child. cur 's original parent becomes  cur 's left child. Return  the new root  of the rerooted tree. Note:  Ensure that your solution sets the  Node.parent  pointers correctly after rerooting or you will receive "Wrong Answer".   Example 1: Input: root = [3,5,1,6,2,0,8,null,null,7,4], leaf = 7 Output: [7,2,nul

Problem is here:  Minimum Operations to Reduce X to Zero - LeetCode From the get-go, the main technique to be used here will be a BFS (Breadth-First-Search). No need to use weights, Dijkstra. Simple BFS should do it. The one, and very important point to bare in mind: when the bug lands on a position P, it does not mean that the bug can never land on P again. Remember that the bug might have come from a forward move, or might have come from a backwards move, and these are distinct, hence when you determine the key to mark P as visited, you actually have two distinct keys: P + ForwardMove P + BackwardsMove Doing so is the key to solving it. Code is down below, cheers, ACC. public class QueueItem { public int position; public bool forwardMove; public int steps; public int key; public QueueItem(int position, bool forwardMove, int steps) { this.position = position; this.forwardMove = forwardMove; this.steps = steps; this.key = positio

This is my post number #400. I think I have this idea that when I retire I'm going to read all this shit... Illusion...  In any case, here is the problem:  Correct a Binary Tree - LeetCode 1660. Correct a Binary Tree Medium 13 2 Add to List Share You have a binary tree with a small defect. There is  exactly one  invalid node where its right child incorrectly points to another node at the  same depth  but to the  invalid node's right . Given the root of the binary tree with this defect,  root , return  the root of the binary tree after  removing  this invalid node  and every node underneath it  (minus the node it incorrectly points to). Custom testing: The test input is read as 3 lines: TreeNode root int fromNode  ( not available to  correctBinaryTree ) int toNode  ( not available to  correctBinaryTree ) After the binary tree rooted at  root  is parsed, the  TreeNode  with value of  fromNode  will have its right child pointer pointing to the  TreeNode  with a value of  toNode .

I thought this problem was very tricky - I had to read the hints and even spy at some comments to see how to tackle it:  https://leetcode.com/problems/minimum-operations-to-reduce-x-to-zero/ My first attempt was to do exactly what the problem suggests: try all the possibilities. Of course I ran into TLE (Time Limit Exceeded) since we're talking about O(2^100000).  Reading the hints and some comments, it was clear that the strategy should be a little inverse of what the problem is asking: instead of looking for the extremes summing up to X, we should be looking for the longest sub-array adding up to Sum(Array) - X . Basically if you find that array, the answer will be straightforward (len of the array - len of the longest sub-array adding up to Sum(Array) - X). Now to find the longest sub-array adding up to a certain number N, one can use the two pointers approach (left and right) in a sliding window. That's actually linear time and space. But to be honest I'd have never had