Another Casual Coder

Another medium problem requiring a DP solution (more and more I'm seeing Medium-LC problems needing an DP solution). It follows a similar pattern of the previous ones, except that it doesn't look for min/max, but you can see the structure being the same: suppose you know the solution on whether you can do a valid partition for positions 0, 1, 2, ..., N-1. In order to know whether there is a valid partition for N, just run the three checks using the info stored for the previous partitions. Code is down below, cheers, ACC. Check if There is a Valid Partition For The Array - LeetCode 2369. Check if There is a Valid Partition For The Array Medium 321 85 Add to List Share You are given a  0-indexed  integer array  nums . You have to partition the array into one or more  contiguous  subarrays. We call a partition of the array  valid  if each of the obtained subarrays satisfies  one  of the following conditions: The subarray consists of  e...

Ideal problem for Dynamic Programming: max/min problem, with an exponential complexity if executed thru brute-force. Given the number k and the string s, what you're going to do is keep track of the longest strings thus far ending on 'a', and 'b', and 'c', and, ..., and 'z'. Knowing the longest for the step i, it is easy to compute the best for the step i+1 by scanning the k previous solutions. Execution time becomes O(k*|s|) and space O(k). Since k is very small and finite, the practical execution time is linear and space is constant. Code is down below, cheers, ACC. Longest Ideal Subsequence - LeetCode 2370. Longest Ideal Subsequence Medium 305 11 Add to List Share You are given a string  s  consisting of lowercase letters and an integer  k . We call a string  t   ideal  if the following conditions are satisfied: t  is a  subsequence  of the string  s . The absolute difference in the alphabet order of every two  adjacent ...

I've been trying to solve this problem for a while, and most of the time running into TLE. On the surface it seems a simple BFS. And it is. With the following problem: each BFS takes 10^5. There might be 10^5 test cases. So in total the solution was hitting TLE.  The epiphany is that you can run the BFS once and store all the possible solutions for later test cases. You can store using a static (class variable) data structure, such as a static Hashtable. Hence only the first test case takes 10^5. All others take O(1). Code is down below, cheers, ACC. Minimum Knight Moves - LeetCode 1197. Minimum Knight Moves Medium 1260 359 Add to List Share In an  infinite  chess board with coordinates from  -infinity  to  +infinity , you have a  knight  at square  [0, 0] . A knight has 8 possible moves it can make, as illustrated below. Each move is two squares in a cardinal direction, then one square in an orthogonal direction. Return  the minimu...

Hard Leetcode problems often require a DP solution. This one is no different. The DP min formula is actually fairly simple, the complication is: do we simulate the train going thru the regular path first, or going thru the expression path first? Answer: try both, pick the min from them. Code is down below, cheers, ACC. Minimum Costs Using the Train Line - LeetCode 2361. Minimum Costs Using the Train Line Hard 9 0 Add to List Share A train line going through a city has two routes, the regular route and the express route. Both routes go through the  same   n + 1  stops labeled from  0  to  n . Initially, you start on the regular route at stop  0 . You are given two  1-indexed  integer arrays  regular  and  express , both of length  n .  regular[i]  describes the cost it takes to go from stop  i - 1  to stop  i  using the regular route, and  express[i]  describes the cost it takes ...

I find the strategy to solving this problem an instance of the famous programming pattern "Map-Reduce", where you use step one to map a sparse subset of potential solutions to your problem, followed by a reduction of that subset into the actual solution. The map in this case calculates the distance from a node to all the other nodes using a queue and BFS. The reduce simply goes to the two calculated distance arrays and retrieves the solution in linear time. Code is down below, cheers, ACC. Find Closest Node to Given Two Nodes - LeetCode 2359. Find Closest Node to Given Two Nodes Medium 147 44 Add to List Share You are given a  directed  graph of  n  nodes numbered from  0  to  n - 1 , where each node has  at most one  outgoing edge. The graph is represented with a given  0-indexed  array  edges  of size  n , indicating that there is a directed edge from node  i  to node  edges[i] . If there is no o...

This actually is a simpler problem then it looks. Given the limit for N is O(10^2), an N^3 solution brings us to O(10^6), which is very tractable. Three nested loops (and a hash table) would do it. Code is down below, cheers, ACC. Equal Row and Column Pairs - LeetCode 2352. Equal Row and Column Pairs Medium 205 3 Add to List Share Given a  0-indexed   n x n  integer matrix  grid ,  return the number of pairs  (R i , C j )  such that row  R i  and column  C j  are equal . A row and column pair is considered equal if they contain the same elements in the same order (i.e. an equal array).   Example 1: Input: grid = [[3,2,1],[1,7,6],[2,7,7]] Output: 1 Explanation: There is 1 equal row and column pair: - (Row 2, Column 1): [2,7,7] Example 2: Input: grid = [[3,1,2,2],[1,4,4,5],[2,4,2,2],[2,4,2,2]] Output: 3 Explanation: There are 3 equal row and column pairs: - (Row 0, Column 0): [3,1,2,2] - (Row 2, Column 2): [2,4,2,2] - ...

Gauss is one the most brilliant mathematicians to have ever lived. The formula for the summation that he discovered when he was only 10y old is used everyday today but hundreds of thousands of people, sometimes not even aware that they are using the formula discovered by a 10y old kid. Problem below requires this formula. Count the number of consecutive zeroes (use a simple finite-state-machine technique) and then apply Gauss' formula. Watch out for overflows (use long instead of int). Code is down below, cheers, ACC. Number of Zero-Filled Subarrays - LeetCode 2348. Number of Zero-Filled Subarrays Medium 31 2 Add to List Share Given an integer array  nums , return  the number of  subarrays  filled with  0 . A  subarray  is a contiguous non-empty sequence of elements within an array.   Example 1: Input: nums = [1,3,0,0,2,0,0,4] Output: 6 Explanation: There are 4 occurrences of [0] as a subarray. There are 2 occurrences of [0,0] as a subarr...