Another Casual Coder

Let's talk about untying the knot... You're given a fully-connected, undirected graph that contains at most one knot. A knot is defined as a loop. The graph contains only unique positive integers as the edges, and if an edge (a,b) is in the graph, then it is guaranteed that a!=b. The graph may have up to 10^5 nodes. In order to untie the knot, you need to first find the loop (if it exists) in the graph, and then find the smallest element in that loop. In the example below, the graph does have one loop, and the smallest element (the weak link) is node 3. That's what you should return. Otherwise, if there is no loop, return -1. Here is how I solved it: 1/ Created the graph (from the edges) using a hash table (that's my favorite way to handle a graph) 2/ Perform a DFS recursively looking for a loop 3/ As you do the DFS, store the current node and the parent node 4/ Once you find a loop, then backtrack non-recursively in order to find the smallest element 5/ Notice that bec

This problem can certainly be solved with DP, but a simple brute-force approach works. Notice that we have 12 sections, and Bob can choose to win a section, or ignore it. Hence for each one we have 2 options. Or, if we were to try them all, 2^12, which is 4096, which is a tiny number. So I tried it all and it worked. The way to try it all is by doing a tail-end recursion. There is just a small caveat which is that we need to ensure that the number of arrows used by Bob is the same as the number of arrows used by Alice, so you're going to see some calculations here to accomplish that goal. Cheers, ACC. Maximum Points in an Archery Competition - LeetCode 2212. Maximum Points in an Archery Competition Medium 135 12 Add to List Share Alice and Bob are opponents in an archery competition. The competition has set the following rules: Alice first shoots  numArrows  arrows and then Bob shoots  numArrows  arrows. The points are then calculated as follows: The target has integer scoring sect

Medium LeetCode problem:  Count Collisions on a Road - LeetCode One approach that worked for me was to treat this problem as a Finite-State-Machine (FSM) problem. Basically the states are defined by the different vehicles (R, L and S), and the state transitions take place depending on the previous rightmost car. That leads to a linear solution without the use of extra space. Code is down below, cheers, ACC. There are  n  cars on an infinitely long road. The cars are numbered from  0  to  n - 1  from left to right and each car is present at a  unique  point. You are given a  0-indexed  string  directions  of length  n .  directions[i]  can be either  'L' ,  'R' , or  'S'  denoting whether the  i th  car is moving towards the  left , towards the  right , or  staying  at its current point respectively. Each moving car has the  same speed . The number of collisions can be calculated as follows: When two cars moving in  opposite  directions collide with each other, t

This problem is a simple parser of the input data structure, placing it in a hashtable (the "graph") followed by a tail recursion. Tail recursion happens when the recursive call is the last statement in the function. It can easily be modified by using a stack, de-recursifying a function, this is usually well done by functional languages. In my case, I kept the recursive calls. Code is down below, cheers, ACC. Create Binary Tree From Descriptions - LeetCode 2196. Create Binary Tree From Descriptions Medium 224 7 Add to List Share You are given a 2D integer array  descriptions  where  descriptions[i] = [parent i , child i , isLeft i ]  indicates that  parent i  is the  parent  of  child i  in a  binary  tree of  unique  values. Furthermore, If  isLeft i  == 1 , then  child i  is the left child of  parent i . If  isLeft i  == 0 , then  child i  is the right child of  parent i . Construct the binary tree described by  descriptions  and return  its  root . The test cases will be g

This is going to be a recursive solution using DFS, but the difference is that we'll use two hash tables: the first one will be a shallow connection which we'll populate based on the edges input. The second one will contain the full deep connections of all ancestors. This is the one that we want to populate thoroughly throughout the recursive calls. Once we have the deep connections fully populated, then it is just a matter of parsing it and creating the return value. Code is down below, cheers, ACC. All Ancestors of a Node in a Directed Acyclic Graph - LeetCode 2192. All Ancestors of a Node in a Directed Acyclic Graph Medium 202 1 Add to List Share You are given a positive integer  n  representing the number of nodes of a  Directed Acyclic Graph  (DAG). The nodes are numbered from  0  to  n - 1  ( inclusive ). You are also given a 2D integer array  edges , where  edges[i] = [from i , to i ]  denotes that there is a  unidirectional  edge from  from i  to  to i  in the graph. Re

I tried solving this problem with a bubble-sort, but it led to TLE. Then the solution again is to implement an IComparer interface. The only caveat here is that we need to have a hash table mapping available to the IComparer, which can be done with a static variable inside the Solution class. Code is down below, cheers, ACC. Sort the Jumbled Numbers - LeetCode 2191. Sort the Jumbled Numbers Medium 148 16 Add to List Share You are given a  0-indexed  integer array  mapping  which represents the mapping rule of a shuffled decimal system.  mapping[i] = j  means digit  i  should be mapped to digit  j  in this system. The  mapped value  of an integer is the new integer obtained by replacing each occurrence of digit  i  in the integer with  mapping[i]  for all  0 <= i <= 9 . You are also given another integer array  nums . Return  the array  nums  sorted in  non-decreasing  order based on the  mapped values  of its elements. Notes: Elements with the same mapped values should appear in