Another Casual Coder

Interesting problem combining post-order traversal and sorted lists: 1/ Perform a post-order traversal 2/ On each step, return a sorted list with the smallest K elements in the subtree 3/ Insertion operation and merge of sorted lists done in a custom way for speed Time complexity around O(number of nodes * k). Code is down below, cheers, ACC. Count Nodes That Are Great Enough - LeetCode 2792. Count Nodes That Are Great Enough Medium 7 0 Add to List Share You are given a  root  to a binary tree and an integer  k . A node of this tree is called  great enough  if the followings hold: Its subtree has  at least   k  nodes. Its value is  greater  than the value of  at least   k  nodes in its subtree. Return  the number of nodes in this tree that are great enough. The node  u  is in the  subtree  of the node  v , if  u == v  or  v  is an ancestor of  u .   Exam...

Crossing the 1300 mark with a problem for which I was stuck in 2020. I was trying it before using sorted native data structures but it was too slow. This time I switched to my own Priority Queue implementation, and it barely worked. Code is down below, cheers, ACC. K-th Smallest Prime Fraction - LeetCode 786. K-th Smallest Prime Fraction Medium 1164 48 Add to List Share You are given a sorted integer array  arr  containing  1  and  prime  numbers, where all the integers of  arr  are unique. You are also given an integer  k . For every  i  and  j  where  0 <= i < j < arr.length , we consider the fraction  arr[i] / arr[j] . Return  the   k th   smallest fraction considered . Return your answer as an array of integers of size  2 , where  answer[0] == arr[i]  and  answer[1] == arr[j] .   Example 1: Input: arr = [1,2,3,5], k = 3 Output: [2,5] Explanation: The fr...

Very often if you're getting stuck into TLE due to string manipulation, especially concatenation, switch to StringBuilder and your problems will be gone. This is an example of such switch. The TLE came from my initial implementation using String manipulation. Code is down below, cheers, ACC. Sort Vowels in a String - LeetCode 2785. Sort Vowels in a String Medium 82 1 Add to List Share Given a  0-indexed  string  s ,  permute   s  to get a new string  t  such that: All consonants remain in their original places. More formally, if there is an index  i  with  0 <= i < s.length  such that  s[i]  is a consonant, then  t[i] = s[i] . The vowels must be sorted in the  nondecreasing  order of their  ASCII  values. More formally, for pairs of indices  i ,  j  with  0 <= i < j < s.length  such that  s[i]  and  s[j]  are vowels, then  t...

This problem requires  Boyer–Moore Majority Vote algorithm , described here:  Boyer–Moore majority vote algorithm - Wikipedia . The variation needed is the following: in standard Boyer-Moore, you need a second pass to determine whether the majoritarian candidate is indeed the majoritarian. However, if we perform the second pass here, we'll end up with an N^2 solution (since N=10^5, this will lead to TLE). The variation requires space utilization: keep track of the frequency of each element. When it is time to perform the check (what would have been the second pass), look up in the frequency table. That keeps the execution in O(N), but with an O(N)-space. Do the right-to-left first, store the majoritarian per index (you'll need another O(N)-space). Then perform the same from left-to-right, the moment you find a match, you have your answer. Code is down below, cheers, ACC. Minimum Index of a Valid Split - LeetCode 2780. Minimum Index of a Valid Split Medium 140 5 Add to Lis...

Another approach to use sliding window technique is the following: 1/ Still have right and left pointers 2/ First loop is controlled by the right one, meaning it runs thru all the way to the length of the string 3/ The second loop is controlled by the left pointer (left over) In all it is still O(2n). The problem below keeps track of K distinct chars in the sliding window. Code is down below, cheers, ACC Longest Substring with At Most K Distinct Characters - LeetCode 340. Longest Substring with At Most K Distinct Characters Medium 2687 77 Add to List Share Given a string  s  and an integer  k , return  the length of the longest  substring  of   s   that contains at most   k   distinct  characters .   Example 1: Input: s = "eceba", k = 2 Output: 3 Explanation: The substring is "ece" with length 3. Example 2: Input: s = "aa", k = 1 Output: 2 Explanation: The substring is "aa" with length 2.   Constraints: 1 <= ...

Another DP, this time doing a simple N^2 traversal storing the maximum jumps per index. N=10^3 so it is very tractable. Code is down below, ACC. Maximum Number of Jumps to Reach the Last Index - LeetCode 2770. Maximum Number of Jumps to Reach the Last Index Medium 95 6 Add to List Share You are given a  0-indexed  array  nums  of  n  integers and an integer  target . You are initially positioned at index  0 . In one step, you can jump from index  i  to any index  j  such that: 0 <= i < j < n -target <= nums[j] - nums[i] <= target Return  the  maximum number of jumps  you can make to reach index   n - 1 . If there is no way to reach index  n - 1 , return  -1 .   Example 1: Input: nums = [1,3,6,4,1,2], target = 2 Output: 3 Explanation: To go from index 0 to index n - 1 with the maximum number of jumps, you can perform the following jumping sequence: - Jump from index 0 to ...