## Posts

Showing posts from September, 2020

### Space is cheap. Time, isn't As the say goes: " Space is cheap. Time, isn't ". In today's world it is almost always the case that you can spare an extra few bytes here and there, but rest assure that your customer won't spare few extra milliseconds to wait for your site to load. Always err on the side of optimizing for speed. Mem is cheap. Here is the problem (LC, medium):  https://leetcode.com/problems/iterator-for-combination/ 1286. Iterator for Combination Medium 485 41 Add to List Share Design an Iterator class, which has: A constructor that takes a string  characters  of  sorted distinct  lowercase English letters and a number  combinationLength  as arguments. A function  next()  that returns the next combination of length  combinationLength  in  lexicographical order . A function  hasNext()  that returns  True  if and only if there exists a next combination.   Example: CombinationIterator iterator = new CombinationIterator("abc", 2); // creates the iterator. iterator.next();

### Backtracking to maximize the split of a string Here is the problem (medium difficulty, LC):  https://leetcode.com/problems/split-a-string-into-the-max-number-of-unique-substrings/ 1593. Split a String Into the Max Number of Unique Substrings Medium 32 4 Add to List Share Given a string  s ,  return  the maximum number of unique substrings that the given string can be split into . You can split string  s  into any list of  non-empty substrings , where the concatenation of the substrings forms the original string. However, you must split the substrings such that all of them are  unique . A  substring  is a contiguous sequence of characters within a string.   Example 1: Input: s = "ababccc" Output: 5 Explanation : One way to split maximally is ['a', 'b', 'ab', 'c', 'cc']. Splitting like ['a', 'b', 'a', 'b', 'c', 'cc'] is not valid as you have 'a' and 'b' multiple times. Example 2: Input: s = "aba" Output: 2

### Iterator for a Binary Tree (in C#) For more that I'm falling in love with Python, C# still has a special place in my heart :) This problem (LC, medium) asks to create an iterator for a Binary Tree, here it is:  https://leetcode.com/problems/binary-search-tree-iterator-ii/ 1586. Binary Search Tree Iterator II Medium 14 2 Add to List Share Implement the  BSTIterator  class that represents an iterator over the  in-order traversal  of a binary search tree (BST): BSTIterator(TreeNode root)  Initializes an object of the  BSTIterator  class. The  root  of the BST is given as part of the constructor. The pointer should be initialized to a non-existent number smaller than any element in the BST. boolean hasNext()  Returns  true  if there exists a number in the traversal to the right of the pointer, otherwise returns  false . int next()  Moves the pointer to the right, then returns the number at the pointer. boolean hasPrev()  Returns  true  if there exists a number in the traversal to the left of the pointer, otherwise retur

### Special positions in Matrix (linear-time) Here is a problem that can be solved in linear-time:  https://leetcode.com/problems/special-positions-in-a-binary-matrix/ 1582. Special Positions in a Binary Matrix Easy 26 3 Add to List Share Given a  rows x cols  matrix  mat , where  mat[i][j]  is either  0  or  1 , return  the number of special positions in  mat . A position  (i,j)  is called  special  if  mat[i][j] == 1  and all other elements in row  i  and column  j  are  0  (rows and columns are  0-indexed ).   Example 1: Input: mat = [[1,0,0],   [0,0, 1 ],   [1,0,0]] Output: 1 Explanation: (1,2) is a special position because mat == 1 and all other elements in row 1 and column 2 are 0. Example 2: Input: mat = [[ 1 ,0,0],   [0, 1 ,0],   [0,0, 1 ]] Output: 3 Explanation: (0,0), (1,1) and (2,2) are special positions. Example 3: Input: mat = [[0,0,0, 1 ],   [ 1 ,0,0,0],   [0,1,1,0],   [0,0,0,0]] Output: 2 Example 4: Input: mat = [[0,

### Falling in love with Python... Looks like the Python "snake" bit me pretty good. I get the same vibe when I first learned C#, that feeling of simplicity, readability and completeness. Not everything is perfect though, IMO: the indentation structure reminds me of Fortran (wow), I still lack to properly define variables instead of them appearing out of the blue (with no explicit type), and I must say that the support from VS to Python is not as good as the support to C# for example (it ain't bad but not optimal). Here is a medium-level LC problem that can be solved in O(n)-time:  https://leetcode.com/problems/minimum-deletion-cost-to-avoid-repeating-letters/ 1578. Minimum Deletion Cost to Avoid Repeating Letters Medium 149 9 Add to List Share Given a string  s  and an array of integers  cost  where  cost[i]  is the cost of deleting the  i th  character in  s . Return the minimum cost of deletions such that there are no two identical letters next to each other. Notice that you will delete the chosen chara

### Dictionary in Python As a big fan of Hash table in general, the usage of Hash tables in Python, or Dictionary, is also pretty straightforward. This problem illustrates it well: https://leetcode.com/problems/number-of-ways-where-square-of-number-is-equal-to-product-of-two-numbers/ 1577. Number of Ways Where Square of Number Is Equal to Product of Two Numbers Medium 74 18 Add to List Share Given two arrays of integers  nums1  and  nums2 , return the number of triplets formed (type 1 and type 2) under the following rules: Type 1: Triplet (i, j, k) if  nums1[i] 2  == nums2[j] * nums2[k]  where  0 <= i < nums1.length  and  0 <= j < k < nums2.length . Type 2: Triplet (i, j, k) if  nums2[i] 2  == nums1[j] * nums1[k]  where  0 <= i < nums2.length  and  0 <= j < k < nums1.length .   Example 1: Input: nums1 = [7,4], nums2 = [5,2,8,9] Output: 1 Explanation: Type 1: (1,1,2), nums1^2 = nums2 * nums2. (4^2 = 2 * 8). Example 2: Input: nums1 = [1,1], nums2 = [1,1,1] Output: 9

### Medium LC Problem in Python This is my first medium-difficulty LC problem in Python (learning the language). It still does not require any deep understand of the language (only simple data structures), just the basics loops and conditions. Here is the problem:  https://leetcode.com/problems/number-of-ways-to-split-a-string/ 1573. Number of Ways to Split a String Medium 88 12 Add to List Share Given a binary string  s  (a string consisting only of '0's and '1's), we can split  s  into 3  non-empty  strings s1, s2, s3 (s1+ s2+ s3 = s). Return the number of ways  s  can be split such that the number of characters '1' is the same in s1, s2, and s3. Since the answer may be too large, return it modulo 10^9 + 7.   Example 1: Input: s = "10101" Output: 4 Explanation: There are four ways to split s in 3 parts where each part contain the same number of letters '1'. "1|010|1" "1|01|01" "10|10|1" "10|1|01" Example 2: Input: s = "1001&q