Posts

Unguarded Cells: grid, hash and a linear approach

The problem this weekend asks for the number of cells that are not guarded. Since the limits of the grid are in the 10^5 range, we're then looking for a O(N) solution. First, it would be wise to add the positions of the guards and the walls in handy hash-tables. Relatively simple. After that, think this way: if you scan the grid in a left-to-right analyzing each row, you can increment the cells that are not reached by a guard in that row from left to right. Any cell that has a 1 at the end of this operation is free from guards in that row from left to right . Now apply the same approach in the other 3 directions: right to left, top down and bottoms-up. By doing so, at the very end, any cell that reaches the number 4 is free from any guard. And that's your answer. Thus, this would be a 4*m*n, and since m*n<=10^5 (as per the constraint), then the solution becomes O(4*10^5), which is very tractable and considered linear in this case. Code is down below, cheers, ACC. Count Ungua...

Lattice points inside circles

Problem looks scarier than it actually is. There is a set of circles and you need to find the integer points within them. The caveat which is what makes this problem easy is that the number of points to cover is small, in the 0-100 range. Taking into account the radius too, you might want to extrapolate to -100 to 200, covering about 300 X's, 300 Y's and 200 circles, hence a total execution time of about 18M steps, which runs in a blink of an eye. Code below, cheers, ACC. Count Lattice Points Inside a Circle - LeetCode 2249. Count Lattice Points Inside a Circle Medium 64 125 Add to List Share Given a 2D integer array  circles  where  circles[i] = [x i , y i , r i ]  represents the center  (x i , y i )  and radius  r i  of the  i th  circle drawn on a grid, return  the  number of lattice points   that are present inside  at least one  circle . Note: A  lattice point  is a point with integer coordina...

Post #500: don't assume that 2 nested loops == O(N^2)

Wow, post #500 :) This is an easy LC problem. It is interesting that the solution requires only counting the number of occurrences of each digits, storing in a small array, and then using that to create the largest value. If you can see the implementation, it shows two nested loops, but upon a closer look into the implementation, you'll notice that the outer loop executes in O(LogN) where N is the input number, and the nested loops cannot go beyond 10 steps no matter what, hence the overall Big-O time becomes O(LogN) despite the N^2-like implementation. Code is down below, cheers, ACC. Largest Number After Digit Swaps by Parity - LeetCode 2231. Largest Number After Digit Swaps by Parity Easy 122 133 Add to List Share You are given a positive integer  num . You may swap any two digits of  num  that have the same  parity  (i.e. both odd digits or both even digits). Return  the  largest  possible value of  num  after  any  nu...

Math Expression Evaluator (MEE)

I think the use of a full-fledge Math Expression Evaluator (MEE) might be too overkill for solving this particular problem, but it is always good to have an MEE in your portfolio of tools in case it is needed. The hard part of this problem is actually the parsing of the expression to create the final one - not actually hard, just a little annoying with the placement of the indexes. Once you have it, use the MEE and save the smallest val. Code is down below, cheers, ACC. Minimize Result by Adding Parentheses to Expression - LeetCode 2232. Minimize Result by Adding Parentheses to Expression Medium 86 188 Add to List Share You are given a  0-indexed  string  expression  of the form  "<num1>+<num2>"  where  <num1>  and  <num2>  represent positive integers. Add a pair of parentheses to  expression  such that after the addition of parentheses,  expression  is a  valid  mathematical exp...

Prefix Sum II: The Definition of Prefix Sum

I think a problem like this one is more like a standard definition of a prefix sum. It is asking, begging for a prefix sum solution. Take a look: Maximum Sum Score of Array - LeetCode 2219. Maximum Sum Score of Array Medium 14 6 Add to List Share You are given a  0-indexed  integer array  nums  of length  n . The  sum  score  of  nums  at an index  i  where  0 <= i < n  is the  maximum  of: The sum of the  first   i + 1  elements of  nums . The sum of the  last   n - i  elements of  nums . Return  the  maximum   sum  score  of  nums  at any index.   Example 1: Input: nums = [4,3,-2,5] Output: 10 Explanation: The sum score at index 0 is max(4, 4 + 3 + -2 + 5) = max(4, 10) = 10. The sum score at index 1 is max(4 + 3, 3 + -2 + 5) = max(7, 6) = 7. The sum score at index 2 is max(4 + 3 + -2, -2 + 5) = max(5, 3) = 5. The ...

Untying the knot

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...

2^12 is a small number

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 ...