Another Casual Coder

I'm sure this problem can be solved with DP, but I don't know how to do that. Instead, a simple BFS should do it. Intuition was telling me that it could be done in 3M steps (which is very fast), but the initial implementations were leading to TLE. The problem was that I was enqueuing items outside of the [0..1000] range, which was leading to an exponential execution time. With the modification inside the traversal piece, it did the trick. Happy Halloween you all! Code is below, cheers, ACC. Minimum Operations to Convert Number - LeetCode 2059. Minimum Operations to Convert Number Medium 126 11 Add to List Share You are given a  0-indexed  integer array  nums  containing  distinct  numbers, an integer  start , and an integer  goal . There is an integer  x  that is initially set to  start , and you want to perform operations on  x  such that it is converted to  goal . You can perform the following operation repeate...

Nothing really special about problem solved 938th, as a matter of fact, this one got lots of negative votes because honestly, it isn't that cool indeed. Create a function to check whether a number is numerically balanced. Some simple calculation, and you can do it in constant time (like O(10)...). Then, keep going from n+1 to oo, until you find a balanced number. Return it. Pretty boring. Code is below fellas, cheers, ACC. Next Greater Numerically Balanced Number - LeetCode 2048. Next Greater Numerically Balanced Number Medium 40 129 Add to List Share An integer  x  is  numerically balanced  if for every digit  d  in the number  x , there are  exactly   d  occurrences of that digit in  x . Given an integer  n , return  the  smallest numerically balanced  number  strictly greater  than  n .   Example 1: Input: n = 1 Output: 22 Explanation: 22 is numerically balanced since: - The digit ...

This problem was a little more complex than the average medium problem. It can be solved in linear time (and linear space) in 3 steps: 1/ Build the graph and store in a hash table (this will be needed for the next steps). This can be done in O(n) with a linear scan 2/ Count the number of nodes in each subtree. Also O(n) (Post-Order DFS) 3/ Linear scan to calculate the score for each subtree, O(n). Warning : use LONG, since you're dealing with multiplication of 3 integers where each integer may be in the 10^5 range, it will overflow if you're not careful. Code is down below. Cheers, ACC. Count Nodes With the Highest Score - LeetCode 2049. Count Nodes With the Highest Score Medium 102 3 Add to List Share There is a  binary  tree rooted at  0  consisting of  n  nodes. The nodes are labeled from  0  to  n - 1 . You are given a  0-indexed  integer array  parents  representing the tree, where  parents[i]  is the p...

Many years ago I wrote about this simple trick to generate all subsets of a set:  A non-recursive trick for subsets generation (anothercasualcoder.blogspot.com) . The problem in this post requires the same approach. Generate all subsets, and keep track of the number of subsets satisfying a certain criteria. The code is down below, cheers, ACC. Count Number of Maximum Bitwise-OR Subsets - LeetCode 2044. Count Number of Maximum Bitwise-OR Subsets Medium 85 9 Add to List Share Given an integer array  nums , find the  maximum  possible  bitwise OR  of a subset of  nums  and return  the  number of different non-empty subsets  with the maximum bitwise OR . An array  a  is a  subset  of an array  b  if  a  can be obtained from  b  by deleting some (possibly zero) elements of  b . Two subsets are considered  different  if the indices of the elements chosen are different. ...

Gaming coding problems can always be solved thru the simulation of the game, but that usually leads to TLE (Time Limit Exceeded). Instead, it is better to found the conditions in which player A would win, and perform an algorithm (usually linear) to see if the condition can be met at the end. In the case of the problem below, the condition would be the following: as long as player A has more available moves than player B, player A would win. Write a function in linear time to determine the number of available moves given a player. That can be done in linear time. Code is below, cheers, ACC. Remove Colored Pieces if Both Neighbors are the Same Color - LeetCode 2038. Remove Colored Pieces if Both Neighbors are the Same Color Medium 41 1 Add to List Share There are  n  pieces arranged in a line, and each piece is colored either by  'A'  or by  'B' . You are given a string  colors  of length  n  where  colors[i]  is the color of th...

This was a problem that required me to literally sleep over it to come up with a solution. The way I was solving it had a time complexity of O(N*M*S) where N=50K, M=50 and S=10K, which becomes intractable. The way to speed it up then was to perform a binary search to find the next greater element given a certain number (in the case of the problem an index). Complexity reduced to O(N*M*Log(S)), which was doable. Code is down below, take a look, cheers, ACC. Number of Matching Subsequences - LeetCode 792. Number of Matching Subsequences Medium 2233 123 Add to List Share Given a string  s  and an array of strings  words , return  the number of   words[i]   that is a subsequence of   s . A  subsequence  of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters. For example,  "ace"  is a subsequence of  "abcde" . ...

Many times problems involving Min or Max can be tackled in one of the following ways: 1/ Dynamic Programming (or DP): those are the HARD problems 2/ Breadth-First Search (or BFS): those are the MEDIUM problems The following problem is an example of #2 above. Minimum Genetic Mutation - LeetCode A gene string can be represented by an 8-character long string, with choices from  'A' ,  'C' ,  'G' , and  'T' . Suppose we need to investigate a mutation from a gene string  start  to a gene string  end  where one mutation is defined as one single character changed in the gene string. For example,  "AACCGGTT" --> "AACCGGTA"  is one mutation. There is also a gene bank  bank  that records all the valid gene mutations. A gene must be in  bank  to make it a valid gene string. Given the two gene strings  start  and  end  and the gene bank  bank , return  the minimum number of mutations needed to mut...