Posts

Analysis: multiple for-loops still in constant time

Image
This is an interesting problem: the key here is to keep track of the frequency within the Y, frequency outside of the Y, and then at this point we can try "all possibilities". But all possibilities here means actually a constant time. In the code below, you have 3*3*3 = 27 iterations. Just be careful when you see nested loops, they may still be cnstant time. Code is down below, cheers, ACC. Minimum Operations to Write the Letter Y on a Grid - LeetCode You are given a  0-indexed   n x n  grid where  n  is odd, and  grid[r][c]  is  0 ,  1 , or  2 . We say that a cell belongs to the Letter  Y  if it belongs to one of the following: The diagonal starting at the top-left cell and ending at the center cell of the grid. The diagonal starting at the top-right cell and ending at the center cell of the grid. The vertical line starting at the center cell and ending at the bottom border of the grid. The Letter  Y  is written on the grid if and only if: All values at cells belonging to th

Two liners using LINQ

Image
You can use LINQ to get the count of instances in one line. Call it N. Then a bit of math: you're looking for combination of N, 2 by 2, which would be the formula N! / (2! * (N-2)!) and if you simplify you get N*(N-1)/2. You also have to add N to account for single-letters strings. Code is down below, cheers, ACC. Count Substrings Starting and Ending with Given Character - LeetCode You are given a string s and a character c. Return the total number of substrings of s that start and end with c. public long CountSubstrings(string s, char c) { long n = s.Where(k => k == c).Count(); return n + (n * (n - 1) / 2); }

Sorting and Math

Image
In this problem we need to be careful to not fall into the trap of decrementing each element after each step, otherwise you'll get into an N^2 state (and N=10^5, hence intractable). What can be done is sorting, and then use a decrement variable to keep track of the amount to decrement the happiness to. Leads to nLogn. code is down below, cheers, ACC. Maximize Happiness of Selected Children - LeetCode You are given an array  happiness  of length  n , and a  positive  integer  k . There are  n  children standing in a queue, where the  i th  child has  happiness value   happiness[i] . You want to select  k  children from these  n  children in  k  turns. In each turn, when you select a child, the  happiness value  of all the children that have  not  been selected till now decreases by  1 . Note that the happiness value  cannot  become negative and gets decremented  only  if it is positive. Return  the  maximum  sum of the happiness values of the selected children you can achieve by sel

Grid and Hashes - Part 2

Image
Another problem involving grid and hash tables. Relatively simple, just keeping track of the numbers already used, and the mapping letter --> number. Complexity-wise, O(|board| * |pattern|) or in other words, 50^4, or ~6M, which is very tractable. Code is down below, cheers, ACC. Match Alphanumerical Pattern in Matrix I - LeetCode You are given a 2D integer matrix  board  and a 2D character matrix  pattern . Where  0 <= board[r][c] <= 9  and each element of  pattern  is either a digit or a lowercase English letter. Your task is to find a  submatrix  of  board  that  matches   pattern . An integer matrix  part  matches  pattern  if we can replace cells containing letters in  pattern  with some digits (each  distinct  letter with a  unique  digit) in such a way that the resulting matrix becomes identical to the integer matrix  part . In other words, The matrices have identical dimensions. If  pattern[r][c]  is a digit, then  part[r][c]  must be the  same  digit. If  pattern[r][c