Another Casual Coder

This problem can be solved with a Prefix Sum approach. Basically we can calculate and store the partial array sum from 0..i, for each i. That way we can easily compute the average needed (just use long for the prefix sum array since the addition may go past Max.Int). This way we're trading space (O(n)) for time (also O(n)). Code is down below, cheers, ACC. K Radius Subarray Averages - LeetCode 2090. K Radius Subarray Averages Medium 111 1 Add to List Share You are given a  0-indexed  array  nums  of  n  integers, and an integer  k . The  k-radius average  for a subarray of  nums   centered  at some index  i  with the  radius   k  is the average of  all  elements in  nums  between the indices  i - k  and  i + k  ( inclusive ). If there are less than  k  elements before  or  after the index  i , then the  k-radius average  is...

A while back I posted a nice non-recursive trick for subsets generation involving bits manipulation, right here  A non-recursive trick for subsets generation (anothercasualcoder.blogspot.com) . The problem today reuses that trick. The idea is the following: 1/ Think about the same process to generate the subsets as described in the link above 2/ If the bit is one, increment the counter 3/ If the bit is zero, check if we have a counter to append, reset the counter, and append the current character 4/ Make sure to do one more check for the counter after exiting the inner loop Complexity will be O(N * 2*N), and since N = 15, we're talking about ~500K iterations (plus the cost of the string manipulation), which is passable. Code is down below, cheers, ACC. Generalized Abbreviation - LeetCode 320. Generalized Abbreviation Medium 552 191 Add to List Share A word's  generalized abbreviation  can be constructed by taking any number of non-overlapping substrings and replacing...

If you look at this problem, it can become a N^3 one with N=250, which starts to get a little slow. It will be a BFS for each gate, but the pruning will happen primarily due to this condition here . Basically we'll only proceed with the BFS while the cells being reached have a greater (or equal to) number of steps. It is easy to understand: suppose that you're performing the BFS given a certain gate and you run into a cell which has a number-of-steps-to-a-gate equal to 5 but with the current BFS that value is 6. You don't want to update OR continue in that path since the value that was there was already better than the one you're "suggesting". Code is down below, cheers, and Happy ThxGiving!!! Walls and Gates - LeetCode 286. Walls and Gates Medium 1952 27 Add to List Share You are given an  m x n  grid  rooms  initialized with these three possible values. -1  A wall or an obstacle. 0  A gate. INF  Infinity means an empty room. We use the value...

This problem requires a fast sorting implementation (QuickSort). Luckily we no longer have to memorize how that wonderful implementation works (for more fun historical information about QuickSort, take a look at my interview with its creator, right here  My Quickshort interview with Sir Tony Hoare, the inventor of Quicksort (anothercasualcoder.blogspot.com) ). Instead, we can make use of the Array.Sort and the IComparer interface. Implementing IComparer is very simple, you can even make use of the .Compare() implementation for each type too. Back to this problem, it can be solved in NLogN: 1/ Sort the items (using IComparer): NLogN 2/ For each item determine the max beauty: N 3/ For each query perform a binary search: NLogN Code is down below, cheers, ACC. Most Beautiful Item for Each Query - LeetCode 2070. Most Beautiful Item for Each Query Medium 71 0 Add to List Share You are given a 2D integer array  items  where  items[i] = [price i , beauty i ]  denot...

This problem exemplifies a standard implementation of a Finite State Machine (FSM), non-recursively. It simply follows the instructions of the robot until it finds a visited state. The only caveat is that a visited state is not only a given cell, but rather a given cell and the direction . Some basic math to create a key that identifies this state. The standard FSM then becomes: check for end condition, process, based on current state, either move or change state. Code is down below, cheers, ACC. Number of Spaces Cleaning Robot Cleaned - LeetCode 2061. Number of Spaces Cleaning Robot Cleaned Medium 10 0 Add to List Share A room is represented by a  0-indexed  2D binary matrix  room  where a  0  represents an  empty  space and a  1  represents a space with an  object . The top left corner of the room will be empty in all test cases. A cleaning robot starts at the top left corner of the room and is facing right. The robot will co...