Another Casual Coder

I had tried solving this problem few years back, failed. Took a look at the hint, and if you follow the hint, you'll solve it too. Here is the problem:  Monotone Increasing Digits - LeetCode 738. Monotone Increasing Digits Medium 771 81 Add to List Share An integer has  monotone increasing digits  if and only if each pair of adjacent digits  x  and  y  satisfy  x <= y . Given an integer  n , return  the largest number that is less than or equal to  n  with  monotone increasing digits .   Example 1: Input: n = 10 Output: 9 Example 2: Input: n = 1234 Output: 1234 Example 3: Input: n = 332 Output: 299   Constraints: 0 <= n <= 10 9 Accepted 34,146 Submissions 73,531 And here was the hint: " Build the answer digit by digit, adding the largest possible one that would make the number still less than or equal to N. " This is exactly how the solution was implemented. Since we're looking at the increasi...

Sliding window is a great technique to solve problems in linear time. It usually involves an input of size N, and a window of size K, and thus the problem can be solved in O(N)-time with O(K)-space. This is an example whereby such technique can be applied: Number of Unique Flavors After Sharing K Candies - LeetCode 2107. Number of Unique Flavors After Sharing K Candies Medium 5 0 Add to List Share You are given a  0-indexed  integer array  candies , where  candies[i]  represents the flavor of the  i th  candy. Your mom wants you to share these candies with your little sister by giving her  k   consecutive  candies, but you want to keep as many flavors of candies as possible. Return  the  maximum  number of  unique  flavors of candy you can keep after sharing  with your sister.   Example 1: Input: candies = [1, 2,2,3 ,4,3], k = 3 Output: 3 Explanation: Give the candies in the range [1, 3] (inclus...

Another problem where we trade space for time. The idea is to calculate the max decreasing sequence per element from the right and from the left, for a total of O(2n) space, in linear time. During the second loop, we also check if the element meets the "time" criteria. Space is cheap, time, isn't. Code is down below. To honor the 80th anniversary of the Pearl Harbor attack, here is a picture that I took on the Battleship Missouri, in Pearl Harbor, this year (2021). Cheers, ACC. Find Good Days to Rob the Bank - LeetCode 2100. Find Good Days to Rob the Bank Medium 64 6 Add to List Share You and a gang of thieves are planning on robbing a bank. You are given a  0-indexed  integer array  security , where  security[i]  is the number of guards on duty on the  i th  day. The days are numbered starting from  0 . You are also given an integer  time . The  i th  day is a good day to rob the bank if: There are at least  time  da...

Advent of Code is back and this particular problem was fairly interesting: Day 6 - Advent of Code 2021 The first part of the puzzle can certainly be solved with simulation. Not the second one, though. Since the second one is in the trillions, simulation will run forever. A better approach is to do the following: 1/ Use a bucket approach, where you count the instance of all numbers from 0..8 2/ Each day, save off the number of elements in bucket[0] 3/ Every bucket will receive the value from the subsequent one (j <- j+1) 4/ At the end, use the value from #2 to update bucket[6] and bucket[8] 5/ Count them all and return The time complexity is O(9 * NDays). Since NDays is 256, this becomes ridiculously fast. Code is below, but not the answer to avoid spoilers. Cheers, ACC. using System; using System.Numerics; using System.IO; using System.Collections; using System.Collections.Generic; using System.Text; namespace AdventOfCode2021 { class Day6 { public BigInteger Puzzle...

Covid days (and nights) are still amongst us, especially now with the sucky Omicron Variant . Stuck at home, yet again, we resort to our dear friend Dijkstra: In this latest problem on Leetcode (959th solved), we see another by-the-book invitation to solve a problem using Dijkstra's Algorithm. There is a graph, with weights, and you want to minimize the cost (I'm sure there is a DP algorithm for that too, but I'm not that good in DP as I mentioned many times before). The problem adds a "tweak" since now you have a max of N discounts that you can apply. This really doesn't change the problem that much: in each interaction, you should assume (a) adding a new connection with the discount (if allowed) and (b) adding a new connection without. So max of two potential enqueue calls for each connection. Recapping what Dijkstra's is: 1/ It is a BFS algorithm 2/ But it uses a Priority Queue, rather than just a Queue 3/ You only mark as "visited" during the...

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