## Posts

Showing posts from May, 2020

### Sliding Window Technique - Part 2 Crossing the 650 problems solved milestone today (weekends in covid-filled era are great for practicing algorithms) Here is the 650th problem:  https://leetcode.com/problems/check-if-a-string-contains-all-binary-codes-of-size-k/ 1461. Check If a String Contains All Binary Codes of Size K Medium 34 20 Add to List Share Given a binary string  s  and an integer  k . Return  True  if any binary code of length  k  is a substring of  s . Otherwise, return  False .   Example 1: Input: s = "00110110", k = 2 Output: true Explanation: The binary codes of length 2 are "00", "01", "10" and "11". They can be all found as substrings at indicies 0, 1, 3 and 2 respectively. Example 2: Input: s = "00110", k = 2 Output: true Example 3: Input: s = "0110", k = 1 Output: true Explanation: The binary codes of length 1 are "0" and "1", it is clear that both exist as a substring. Example 4: Input: s = "011

### Trees, Palindromes and C# Great problem covering all three aspects - tree, palindromes and peculiarities of the C# language:  https://leetcode.com/problems/pseudo-palindromic-paths-in-a-binary-tree/ 1457. Pseudo-Palindromic Paths in a Binary Tree Medium 62 2 Add to List Share Given a binary tree where node values are digits from 1 to 9. A path in the binary tree is said to be  pseudo-palindromic  if at least one permutation of the node values in the path is a palindrome. Return the number of  pseudo-palindromic  paths going from the root node to leaf nodes.   Example 1: Input: root = [2,3,1,3,1,null,1] Output: 2 Explanation: The figure above represents the given binary tree. There are three paths going from the root node to leaf nodes: the red path [2,3,3], the green path [2,1,1], and the path [2,3,1]. Among these paths only red path and green path are pseudo-palindromic paths since the red path [2,3,3] can be rearranged in [3,2,3] (palindrome) and the green path [2,1,1] can be rearranged in [1,2,1] (palind

### Sliding Window Technique Great problem to describe the sliding window technique:  https://leetcode.com/problems/maximum-number-of-vowels-in-a-substring-of-given-length/ 1456. Maximum Number of Vowels in a Substring of Given Length Medium 67 1 Add to List Share Given a string  s  and an integer  k . Return  the maximum number of vowel letters  in any substring of  s  with length  k . Vowel letters  in English are (a, e, i, o, u).   Example 1: Input: s = "abciiidef", k = 3 Output: 3 Explanation: The substring "iii" contains 3 vowel letters. Example 2: Input: s = "aeiou", k = 2 Output: 2 Explanation: Any substring of length 2 contains 2 vowels. Example 3: Input: s = "leetcode", k = 3 Output: 2 Explanation: "lee", "eet" and "ode" contain 2 vowels. Example 4: Input: s = "rhythms", k = 4 Output: 0 Explanation: We can see that s doesn't have any vowel letters. Example 5: Input: s = "tryhard", k = 4 Output: 1

### 300 Medium LC Problems This is my 300th Medium LC Problem solved:  https://leetcode.com/problems/people-whose-list-of-favorite-companies-is-not-a-subset-of-another-list/ 1452. People Whose List of Favorite Companies Is Not a Subset of Another List Medium 76 98 Add to List Share Given the array  favoriteCompanies  where  favoriteCompanies[i]  is the list of favorites companies for the  ith  person ( indexed from 0 ). Return the indices of people whose list of favorite companies is not a  subset  of any other list of favorites companies . You must return the indices in increasing order.   Example 1: Input: favoriteCompanies = [["leetcode","google","facebook"],["google","microsoft"],["google","facebook"],["google"],["amazon"]] Output: [0,1,4] Explanation: Person with index=2 has favoriteCompanies=["google","facebook"] which is a subset of favoriteCompanies=["leetcode","google&q

### Greatest Common Divisor: recursion from 300 BC Look at this problem:  https://leetcode.com/problems/simplified-fractions/ Given the small N (100), the brute-force solution works just fine: go thru all the possible divisors and numerators (100x100 = 10000), and for each one check whether the Greatest Common Divisor between them is 1. If so, add to the return val. GCD can be calculated in LogN. Hence total execution time becomes N*N*LogN, or around 140,000, which runs very fast. Code is down below. The Greatest Common Divisor algorithm was proposed by Euclid, back few years ago, in 300 BC. It is a clever and the best algorithm ever devised to determine the GCD of two numbers, running in LogN. You can find it here:  https://en.wikipedia.org/wiki/Euclidean_algorithm .  Cheers, ACC.   public class Solution {     public IList<string> SimplifiedFractions(int n)     {         List<string> retVal = new List<string>();         for (int d = 1; d <= n; d++)         {             for (int nu = 1; nu < d; nu++)

### Consecutive Chars, O(n)-time, O(1)-space Problem is here:  https://leetcode.com/problems/consecutive-characters/ Explanation: Base case when the string is empty - zero From that point on, max is at least 1 Start from the second char Look to the previous one, if the same, increment the current count (you still have a candidate) Otherwise, the current becomes 1 Always make max = Max( max, current ) Code is below, cheers, ACC. public class Solution {     public int MaxPower(string s)     {         if (String.IsNullOrEmpty(s)) return 0;         int max = 1;         int current = 1;         for (int i = 1; i < s.Length; i++)         {             if (s[i] == s[i - 1]) current++;             else current = 1;             max = Math.Max(max, current);         }         return max;     } }

### Binary, Binary Search Problem:  https://leetcode.com/problems/leftmost-column-with-at-least-a-one/ 1428. Leftmost Column with at Least a One Medium 6 0 Add to List Share (This problem is an  interactive problem .) A binary matrix means that all elements are  0  or  1 . For each  individual  row of the matrix, this row is sorted in non-decreasing order. Given a row-sorted binary matrix binaryMatrix, return leftmost column index(0-indexed) with at least a  1  in it. If such index doesn't exist, return  -1 . You can't access the Binary Matrix directly.   You may only access the matrix using a  BinaryMatrix  interface: BinaryMatrix.get(row, col)  returns the element of the matrix at index  (row, col)  (0-indexed). BinaryMatrix.dimensions()  returns a list of 2 elements  [rows, cols] , which means the matrix is  rows * cols . Submissions making more than  1000  calls to  BinaryMatrix.get  will be judged  Wrong Answer .  Also, any solutions that attempt to circumvent the judge wil

### First Unique Number: priority queue, hash tables and math Tough problem:  https://leetcode.com/problems/first-unique-number/ 1429. First Unique Number Medium 2 0 Add to List Share You have a queue of integers, you need to retrieve the first unique integer in the queue. Implement the  FirstUnique  class: FirstUnique(int[] nums)  Initializes the object with the numbers in the queue. int showFirstUnique()  returns the value of  the first unique  integer of the queue, and returns  -1  if there is no such integer. void add(int value)  insert value to the queue. Example 1: Input: ["FirstUnique","showFirstUnique","add","showFirstUnique","add","showFirstUnique","add","showFirstUnique"] [[[2,3,5]],[],,[],,[],,[]] Output: [null,2,null,2,null,3,null,-1] Explanation: FirstUnique firstUnique = new FirstUnique([2,3,5]); firstUnique.showFirstUnique(); // return 2 firstUnique.add(5); // the queue is now [2,3,5,5] firstUnique.showFir