Posts

Classic Dynamic Programming VII

This is a simple one where you don't even need to allocate extra memory - use the grid itself as the DP storage, assuming that you don't need to keep the elements of grid intact. Code is down below, cheers, ACC. Count Submatrices with Top-Left Element and Sum Less Than k - LeetCode You are given a  0-indexed  integer matrix  grid  and an integer  k . Return  the  number  of  submatrices  that contain the top-left element of the   grid ,  and have a sum less than or equal to  k .   Example 1: Input: grid = [[7,6,3],[6,6,1]], k = 18 Output: 4 Explanation: There are only 4 submatrices, shown in the image above, that contain the top-left element of grid, and have a sum less than or equal to 18. Example 2: Input: grid = [[7,2,9],[1,5,0],[2,6,6]], k = 20 Output: 6 Explanation: There are only 6 submatrices, shown in the image above, that contain the top-left element of grid, and have a sum less than or equal to 20. ...

Sliding Window Technique - Part 12

The control pointer here is the left (slow) pointer. There is probably some optimization that can be done to jump the left pointer far ahead if needed, but even with the slow movement one can achieve O(N) (in 2*N). Code is down below, cheers, ACC. Count Subarrays Where Max Element Appears at Least K Times - LeetCode 2962. Count Subarrays Where Max Element Appears at Least K Times Medium 257 13 Add to List Share You are given an integer array  nums  and a  positive  integer  k . Return  the number of subarrays where the  maximum  element of  nums  appears  at least   k  times in that subarray. A  subarray  is a contiguous sequence of elements within an array.   Example 1: Input: nums = [1,3,2,3,3], k = 2 Output: 6 Explanation: The subarrays that contain the element 3 at least 2 times are: [1,3,2,3], [1,3,2,3,3], [3,2,3], [3,2,3,3], [2,3,3] and [3,3]. Example 2: Input: nums = [1,4,2,1], k = 3 Output: ...

Trie-Trie-Trie!!! - Part 4

A super simple implementation of a Trie: a class with just a hash table as the children. The code for the prefix len becomes super easy (two lines). A little slow probably because of the conversion to strings, can be sped up by using just numerical manipulation. Code is down below, cheers, ACC. Find the Length of the Longest Common Prefix - LeetCode 3043. Find the Length of the Longest Common Prefix Medium 94 5 Add to List Share You are given two arrays with  positive  integers  arr1  and  arr2 . A  prefix  of a positive integer is an integer formed by one or more of its digits, starting from its  leftmost  digit. For example,  123  is a prefix of the integer  12345 , while  234  is  not . A  common prefix  of two integers  a  and  b  is an integer  c , such that  c  is a prefix of both  a  and  b . For example,  5655359  and  56554 ...