Boris Coding Blog

Latest LeetCode problem deals with classical binary search, here it is:  https://leetcode.com/problems/find-smallest-letter-greater-than-target/description/ Given a list of sorted characters  letters  containing only lowercase letters, and given a target letter  target , find the smallest element in the list that is larger than the given target. Letters also wrap around. For example, if the target is  target = 'z'  and  letters = ['a', 'b'] , the answer is  'a' . Examples: Input: letters = ["c", "f", "j"] target = "a" Output: "c" Input: letters = ["c", "f", "j"] target = "c" Output: "f" Input: letters = ["c", "f", "j"] target = "d" Output: "f" Input: letters = ["c", "f", "j"] target = "g" Output: "j" Input: letters = ["c", &quo

Sometimes a solution to a problem requires the use of nested hash-tables, that is, a hash table whose values are other hash tables. This problem exemplifies this technique. It comes from Leetcode, here it is:  https://leetcode.com/problems/sentence-similarity/description/ : Given two sentences  words1, words2  (each represented as an array of strings), and a list of similar word pairs  pairs , determine if two sentences are similar. For example, "great acting skills" and "fine drama talent" are similar, if the similar word pairs are  pairs = [["great", "fine"], ["acting","drama"], ["skills","talent"]] . Note that the similarity relation is not transitive. For example, if "great" and "fine" are similar, and "fine" and "good" are similar, "great" and "good" are  not  necessarily similar. However, similarity is symmetric. For example, "g

An easy problem to finish the week, from LeetCode:  https://leetcode.com/problems/self-dividing-numbers/description/ : A  self-dividing number  is a number that is divisible by every digit it contains. For example, 128 is a self-dividing number because  128 % 1 == 0 ,  128 % 2 == 0 , and  128 % 8 == 0 . Also, a self-dividing number is not allowed to contain the digit zero. Given a lower and upper number bound, output a list of every possible self dividing number, including the bounds if possible. Example 1: Input: left = 1, right = 22 Output: [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 15, 22] Given the low ranges for the input, a simple check across all the digits for each number in the range should do it. The main logic is highlighted in green  below. Basically to check whether a given number is self-dividing, go thru its digits (that's the module ten in the code) and if the digit is zero or if it doesn't divide the number, then the number is not self-dividing. Ot

Another LeetCode, right here:  https://leetcode.com/problems/find-pivot-index/description/ Given an array of integers  nums , write a method that returns the "pivot" index of this array. We define the pivot index as the index where the sum of the numbers to the left of the index is equal to the sum of the numbers to the right of the index. If no such index exists, we should return -1. If there are multiple pivot indexes, you should return the left-most pivot index. Example 1: Input: nums = [1, 7, 3, 6, 5, 6] Output: 3 Explanation: The sum of the numbers to the left of index 3 (nums[3] = 6) is equal to the sum of numbers to the right of index 3. Also, 3 is the first index where this occurs. Example 2: Input: nums = [1, 2, 3] Output: -1 Explanation: There is no index that satisfies the conditions in the problem statement. Note: The length of nums will be in the range [0, 10000]. Each element nums[i] will be an integer in the range [-1000, 1000].

Sometimes a recursive approach to a problem might seem like a bad idea "because of the stack overhead and potential explosion of permutations and overly complicated logic"... yada, yada, yada. Sure, sometimes such arguments are right on the target, but sometimes (many times) computer science problems can mirror life problems quite accurately, where the answer to the problem can be a boring "it depends". Take a look at this problem by LeetCode: https://leetcode.com/problems/1-bit-and-2-bit-characters/description/ We have two special characters. The first character can be represented by one bit   0 . The second character can be represented by two bits ( 10   or   11 ). Now given a string represented by several bits. Return whether the last character must be a one-bit character or not. The given string will always end with a zero. Example 1: Input: bits = [1, 0, 0] Output: True Explanation: The only way to decode it is two-bit character and one-bit c

Here is a problem: you're given a binary tree, say something like this: Now what we want to do is delete all the leaves from this tree whose value is equal to a certain target value. For this example's sake, the target value will be 5. That seems pretty straightforward: traverse down the tree, and the moment that you find a leave whose value equals to 5, chop it off: But hang on, what if the problem requires you to ensure that the remaining tree, after deleting any leaf whose value was 5, does not have any resulting leaf with value equals to five? Suppose for example that instead of "4", that node had the value "5": It would then trigger a cascading event where not only the "5" leaves would be deleted, but also their parent would be deleted too. This is because after deleting the "5"s, you'd end up with a new tree with new leaves whose values are also 5 :). Those should be deleted too. How to do that? A simple appr

Howdy!!! I had solved 203 problems on Project Euler, until it got hacked. I had solved 200+ problems on Hacker-Rank, until I ran out of easy/medium problems to solve. Now I've crossed the 200 problems mark on LeetCode. I think I can get to the 300 there, assuming they keep on posting easy/medium problems, and that my interest for TV shows continue to be zero. The 200th problem was this one:  https://leetcode.com/problems/set-mismatch/description/ : The set  S  originally contains numbers from 1 to  n . But unfortunately, due to the data error, one of the numbers in the set got duplicated to  another  number in the set, which results in repetition of one number and loss of another number. Given an array  nums  representing the data status of this set after the error. Your task is to firstly find the number occurs twice and then find the number that is missing. Return them in the form of an array. Example 1: Input: nums = [1,2,2,4] Output: [2,3] Note:

The problem is this one, new one from LeetCode:  https://leetcode.com/problems/number-of-longest-increasing-subsequence/description/ Given an unsorted array of integers, find the number of longest increasing subsequence. Example 1: Input: [1,3,5,4,7] Output: 2 Explanation: The two longest increasing subsequence are [1, 3, 4, 7] and [1, 3, 5, 7]. Example 2: Input: [2,2,2,2,2] Output: 5 Explanation: The length of longest continuous increasing subsequence is 1, and there are 5 subsequences' length is 1, so output 5. Note:  Length of the given array will be not exceed 2000 and the answer is guaranteed to be fit in 32-bit signed int. The hints that tell me that we need a Dynamic Programming (DP) solution to this problem are twofold: 1) The problem is asking for the number  of sequences, but not the sequences themselves 2) Think about a brute-force approach: at each index you'd have to binary check every other previous index. That's an 2^n approach. n=2

New problem by LeetCode:  https://leetcode.com/problems/implement-magic-dictionary/description/ Implement a magic directory with  buildDict , and  search  methods. For the method  buildDict , you'll be given a list of non-repetitive words to build a dictionary. For the method  search , you'll be given a word, and judge whether if you modify  exactly  one character into  another  character in this word, the modified word is in the dictionary you just built. Example 1: Input: buildDict(["hello", "leetcode"]), Output: Null Input: search("hello"), Output: False Input: search("hhllo"), Output: True Input: search("hell"), Output: False Input: search("leetcoded"), Output: False Note: You may assume that all the inputs are consist of lowercase letters  a-z . For contest purpose, the test data is rather small by now. You could think about highly efficient algorithm after the contest. Please remember to  RESET

So here was tonight’s problem, from our friend LeetCode: https://leetcode.com/problems/permutation-sequence/description/ The set  [1,2,3,…, n ]  contains a total of  n ! unique permutations. By listing and labeling all of the permutations in order, We get the following sequence (ie, for  n  = 3): "123" "132" "213" "231" "312" "321" Given  n  and  k , return the  k th  permutation sequence. Note:  Given  n  will be between 1 and 9 inclusive. It is an interesting one because it asks precisely for the kth permutation sequence. I’m sure there must be a clever way to generate the kth one in O(1) but I decided to generate them all (given the small n) until we get to the kth one. Here was my first implementation: a recursive depth-first search without pruning until we get to the kth sequence:               public class Solution               {                            public string GetPermutation(int n,