Showing posts from October, 2020

Friday Night Dijkstra's Algorithm

Covid-times Friday Night - Dijkstra's Algorithm.  Check out this problem: You are a hiker preparing for an upcoming hike. You are given  heights , a 2D array of size  rows x columns , where  heights[row][col]  represents the height of cell  (row, col) . You are situated in the top-left cell,  (0, 0) , and you hope to travel to the bottom-right cell,  (rows-1, columns-1)  (i.e.,  0-indexed ). You can move  up ,  down ,  left , or  right , and you wish to find a route that requires the minimum  effort . A route's  effort  is the  maximum absolute difference   in heights between two consecutive cells of the route. Return  the minimum  effort  required to travel from the top-left cell to the bottom-right cell.   Example 1: Input: heights = [[1,2,2],[3,8,2],[5,3,5]] Output: 2 Explanation: The route of [1,3,5,3,5] has a maximum absolute difference of 2 in consecutive cells. This is better than the route of [1,2,2,2,5], where

Polynomials Addition

This is a classic problem, usually solved with either two-pointers (merge-sort style), or a simple recursion. In the case below, I have opted for a recursive solution. Here is the problem: The recursion will have one base case followed by four induction steps. Base case is straightforward. The four induction steps are: head of poly1 greater than head of poly2, head of poly2 greater than head of poly1, both being the same but the addition leading to a zero coefficient, or finally both being the same and the sum not leading to a zero coefficient. Works well, code is below, cheers! ACC public PolyNode AddPoly(PolyNode poly1, PolyNode poly2) { if (poly1 == null) return poly2; if (poly2 == null) return poly1; if (poly1.power > poly2.power) return new PolyNode(poly1.coefficient, poly1.power, AddPoly(, poly2)); else if (poly1.power < poly2.power) return new PolyNode

Post-fix tree evaluation

A fun problem from LC involving post-fix tree evaluation. Solution is actually very simple, in spite of the long problem description. Linearly scan the post-fix. If it is a number, push to the stack. Otherwise, pop, pop, evaluate, and push it back. Return the last element in the stack. That's it. Cheers! ACC public abstract class Node { public abstract int evaluate(); }; public class MyNode : Node { private int result = 0; private string val; private Node left; private Node right; public override int evaluate() { return result; } public MyNode(string val, int result) { this.result = result; this.val = val; this.left = null; this.right = null; } public MyNode(string val, int result, Node left, Node right) { this.result = result; this.val = val; this.left = left; this.right = rig

A linear approach to find largest substring between characters

 Problem is here: 1624. Largest Substring Between Two Equal Characters Easy 39 2 Add to List Share Given a string  s , return  the length of the longest substring between two equal characters, excluding the two characters.  If there is no such substring return  -1 . A  substring  is a contiguous sequence of characters within a string.   Example 1: Input: s = "aa" Output: 0 Explanation: The optimal substring here is an empty substring between the two 'a's . Example 2: Input: s = "abca" Output: 2 Explanation: The optimal substring here is "bc". Example 3: Input: s = "cbzxy" Output: -1 Explanation: There are no characters that appear twice in s. Example 4: Input: s = "cabbac" Output: 4 Explanation: The optimal substring here is "abba". Other non-optimal substrings include "bb" and "".   Constraints: 1 <= s.len

Brute-force based on hints

 I looked at the hints for this one: 1625. Lexicographically Smallest String After Applying Operations Medium 28 76 Add to List Share You are given a string  s  of  even length  consisting of digits from  0  to  9 , and two integers  a  and  b . You can apply either of the following two operations any number of times and in any order on  s : Add  a  to all odd indices of  s   (0-indexed) . Digits post  9  are cycled back to  0 . For example, if  s = "3456"  and  a = 5 ,  s  becomes  "3951" . Rotate  s  to the right by  b  positions. For example, if  s = "3456"  and  b = 1 ,  s  becomes  "6345" . Return  the  lexicographically smallest  string you can obtain by applying the above operations any number of times on   s . A string  a  is lexicographically smaller than a string  b  (of the same length) if in the first position where  a  and  b  differ, string 

A problem worthy of attack, proves its worth by fighting back

These are the famous words by Paul Erdos: “A problem worthy of attack, proves its  worth by fighting back !” –  Paul Erdos  One of the greatest mathematicians of the 20th Century, Paul Erdos , is often associated with the following rhyme: “A problem worthy of attack, proves its worth by fighting back!” I'm sure that he was thinking beyond a LeetCode problem :D But this one was worth an attack: 1604. Alert Using Same Key-Card Three or More Times in a One Hour Period Medium 23 51 Add to List Share Leetcode company workers use key-cards to unlock office doors. Each time a worker uses their key-card, the security system saves the worker's name and the time when it was used. The system emits an  alert  if any worker uses the key-card  three or more times  in a one-hour period. You are given a list of strings  keyName  and  keyTime  where  [keyName[i], keyTime[i]]  corresponds to a pers