Improved tasks 104-215

javadev · web-flow · commit acd621543358 · 2025-03-26T05:45:59.000+02:00
diff --git a/README.md b/README.md
diff --git a/src/main/ts/g0101_0200/s0104_maximum_depth_of_binary_tree/solution.ts b/src/main/ts/g0101_0200/s0104_maximum_depth_of_binary_tree/solution.ts
@@ -2,7 +2,7 @@
 // #Tree #Binary_Tree #Data_Structure_I_Day_11_Tree
 // #Programming_Skills_I_Day_10_Linked_List_and_Tree #Udemy_Tree_Stack_Queue
 // #Top_Interview_150_Binary_Tree_General #Big_O_Time_O(N)_Space_O(H)
-// #2023_10_04_Time_51_ms_(97.14%)_Space_46.1_MB_(68.29%)
+// #2025_03_26_Time_0_ms_(100.00%)_Space_59.10_MB_(43.48%)
 
 import { TreeNode } from '../../com_github_leetcode/treenode'
 
diff --git a/src/main/ts/g0101_0200/s0105_construct_binary_tree_from_preorder_and_inorder_traversal/solution.ts b/src/main/ts/g0101_0200/s0105_construct_binary_tree_from_preorder_and_inorder_traversal/solution.ts
@@ -1,6 +1,6 @@
 // #Medium #Top_100_Liked_Questions #Top_Interview_Questions #Array #Hash_Table #Tree #Binary_Tree
 // #Divide_and_Conquer #Data_Structure_II_Day_15_Tree #Top_Interview_150_Binary_Tree_General
-// #Big_O_Time_O(N)_Space_O(N) #2023_10_04_Time_65_ms_(96.47%)_Space_45.9_MB_(80.00%)
+// #Big_O_Time_O(N)_Space_O(N) #2025_03_26_Time_2_ms_(93.38%)_Space_60.17_MB_(76.57%)
 
 import { TreeNode } from '../../com_github_leetcode/treenode'
 
diff --git a/src/main/ts/g0101_0200/s0114_flatten_binary_tree_to_linked_list/solution.ts b/src/main/ts/g0101_0200/s0114_flatten_binary_tree_to_linked_list/solution.ts
@@ -1,6 +1,6 @@
 // #Medium #Top_100_Liked_Questions #Depth_First_Search #Tree #Binary_Tree #Stack #Linked_List
 // #Udemy_Linked_List #Top_Interview_150_Binary_Tree_General #Big_O_Time_O(N)_Space_O(N)
-// #2023_10_04_Time_55_ms_(90.66%)_Space_45.8_MB_(12.11%)
+// #2025_03_26_Time_0_ms_(100.00%)_Space_58.93_MB_(15.60%)
 
 import { TreeNode } from '../../com_github_leetcode/treenode'
 
diff --git a/src/main/ts/g0101_0200/s0121_best_time_to_buy_and_sell_stock/solution.ts b/src/main/ts/g0101_0200/s0121_best_time_to_buy_and_sell_stock/solution.ts
@@ -1,7 +1,7 @@
 // #Easy #Top_100_Liked_Questions #Top_Interview_Questions #Array #Dynamic_Programming
 // #Data_Structure_I_Day_3_Array #Dynamic_Programming_I_Day_7 #Level_1_Day_5_Greedy #Udemy_Arrays
 // #Top_Interview_150_Array/String #Big_O_Time_O(N)_Space_O(1)
-// #2023_10_05_Time_56_ms_(99.56%)_Space_52.3_MB_(13.22%)
+// #2025_03_26_Time_1_ms_(96.44%)_Space_65.83_MB_(26.02%)
 
 function maxProfit(prices: number[]): number {
     let buyPrice = prices[0]
diff --git a/src/main/ts/g0101_0200/s0124_binary_tree_maximum_path_sum/solution.ts b/src/main/ts/g0101_0200/s0124_binary_tree_maximum_path_sum/solution.ts
@@ -1,6 +1,6 @@
 // #Hard #Top_100_Liked_Questions #Top_Interview_Questions #Dynamic_Programming #Depth_First_Search
 // #Tree #Binary_Tree #Udemy_Tree_Stack_Queue #Top_Interview_150_Binary_Tree_General
-// #Big_O_Time_O(N)_Space_O(N) #2023_10_05_Time_61_ms_(96.73%)_Space_51.2_MB_(97.45%)
+// #Big_O_Time_O(N)_Space_O(N) #2025_03_26_Time_2_ms_(71.11%)_Space_65.59_MB_(42.96%)
 
 import { TreeNode } from '../../com_github_leetcode/treenode'
 
diff --git a/src/main/ts/g0101_0200/s0128_longest_consecutive_sequence/solution.ts b/src/main/ts/g0101_0200/s0128_longest_consecutive_sequence/solution.ts
@@ -1,18 +1,21 @@
 // #Medium #Top_100_Liked_Questions #Top_Interview_Questions #Array #Hash_Table #Union_Find
 // #Top_Interview_150_Hashmap #Big_O_Time_O(N_log_N)_Space_O(1)
-// #2023_10_05_Time_92_ms_(93.69%)_Space_64_MB_(30.13%)
+// #2025_03_26_Time_34_ms_(90.07%)_Space_82.70_MB_(18.54%)
 
 function longestConsecutive(nums: number[]): number {
-    const set = new Set(nums)
-    let max = 0
-    for (const num of nums) {
-        if (set.has(num + 1)) continue
-        let counter = 1,
-            current = num
-        while (set.has(--current)) counter++
-        max = Math.max(counter, max)
+    let sset = new Set(nums)
+    let maxLen = 0
+    for (let num of sset) {
+        // check its start of the sequence
+        if (!sset.has(num-1)) {
+            let len = 0;
+            while (sset.has(num+len)) {
+                len += 1
+            }
+            maxLen = Math.max(maxLen, len)
+        }
     }
-    return max
+    return maxLen
 }
 
 export { longestConsecutive }
diff --git a/src/main/ts/g0101_0200/s0131_palindrome_partitioning/solution.ts b/src/main/ts/g0101_0200/s0131_palindrome_partitioning/solution.ts
@@ -1,6 +1,6 @@
 // #Medium #Top_100_Liked_Questions #Top_Interview_Questions #String #Dynamic_Programming
 // #Backtracking #Big_O_Time_O(N*2^N)_Space_O(2^N*N)
-// #2023_10_05_Time_203_ms_(99.22%)_Space_81.9_MB_(42.19%)
+// #2025_03_26_Time_13_ms_(94.96%)_Space_82.19_MB_(40.76%)
 
 function partition(s: string): string[][] {
     const ans: string[][] = []
diff --git a/src/main/ts/g0101_0200/s0136_single_number/solution.ts b/src/main/ts/g0101_0200/s0136_single_number/solution.ts
@@ -1,7 +1,7 @@
 // #Easy #Top_100_Liked_Questions #Top_Interview_Questions #Array #Bit_Manipulation
 // #Data_Structure_II_Day_1_Array #Algorithm_I_Day_14_Bit_Manipulation #Udemy_Integers
 // #Top_Interview_150_Bit_Manipulation #Big_O_Time_O(N)_Space_O(1)
-// #2023_10_05_Time_56_ms_(85.48%)_Space_45.6_MB_(63.32%)
+// #2025_03_26_Time_1_ms_(78.27%)_Space_58.44_MB_(41.08%)
 
 function singleNumber(nums: number[]): number {
     let ans = 0
diff --git a/src/main/ts/g0101_0200/s0138_copy_list_with_random_pointer/solution.ts b/src/main/ts/g0101_0200/s0138_copy_list_with_random_pointer/solution.ts
@@ -1,6 +1,6 @@
 // #Medium #Top_100_Liked_Questions #Top_Interview_Questions #Hash_Table #Linked_List
 // #Programming_Skills_II_Day_14 #Udemy_Linked_List #Top_Interview_150_Linked_List
-// #Big_O_Time_O(N)_Space_O(N) #2023_10_06_Time_52_ms_(88.27%)_Space_44.7_MB_(72.42%)
+// #Big_O_Time_O(N)_Space_O(N) #2025_03_26_Time_49_ms_(72.42%)_Space_55.82_MB_(59.25%)
 
 import { Node } from '../../com_github_leetcode/node'
 
diff --git a/src/main/ts/g0101_0200/s0139_word_break/solution.ts b/src/main/ts/g0101_0200/s0139_word_break/solution.ts
@@ -1,7 +1,7 @@
 // #Medium #Top_100_Liked_Questions #Top_Interview_Questions #String #Hash_Table
 // #Dynamic_Programming #Trie #Memoization #Algorithm_II_Day_15_Dynamic_Programming
 // #Dynamic_Programming_I_Day_9 #Udemy_Dynamic_Programming #Top_Interview_150_1D_DP
-// #Big_O_Time_O(M+max*N)_Space_O(M+N+max) #2023_10_06_Time_56_ms_(88.44%)_Space_44.1_MB_(93.39%)
+// #Big_O_Time_O(M+max*N)_Space_O(M+N+max) #2025_03_26_Time_4_ms_(76.41%)_Space_58.68_MB_(22.70%)
 
 function wordBreak(s: string, wordDict: string[]): boolean {
     const dp: boolean[] = []
diff --git a/src/main/ts/g0101_0200/s0141_linked_list_cycle/solution.ts b/src/main/ts/g0101_0200/s0141_linked_list_cycle/solution.ts
@@ -1,6 +1,6 @@
 // #Easy #Top_100_Liked_Questions #Top_Interview_Questions #Hash_Table #Two_Pointers #Linked_List
 // #Data_Structure_I_Day_7_Linked_List #Udemy_Linked_List #Top_Interview_150_Linked_List
-// #Big_O_Time_O(N)_Space_O(1) #2023_10_06_Time_59_ms_(93.37%)_Space_45.2_MB_(76.28%)
+// #Big_O_Time_O(N)_Space_O(1) #2025_03_26_Time_47_ms_(89.37%)_Space_58.35_MB_(35.02%)
 
 import { ListNode } from '../../com_github_leetcode/listnode'
 
diff --git a/src/main/ts/g0101_0200/s0142_linked_list_cycle_ii/solution.ts b/src/main/ts/g0101_0200/s0142_linked_list_cycle_ii/solution.ts
@@ -1,6 +1,6 @@
 // #Medium #Top_100_Liked_Questions #Hash_Table #Two_Pointers #Linked_List
 // #Data_Structure_II_Day_10_Linked_List #Level_1_Day_4_Linked_List #Udemy_Linked_List
-// #Big_O_Time_O(N)_Space_O(1) #2023_10_06_Time_59_ms_(94.39%)_Space_45.5_MB_(60.71%)
+// #Big_O_Time_O(N)_Space_O(1) #2025_03_26_Time_51_ms_(76.99%)_Space_59.02_MB_(13.39%)
 
 import { ListNode } from '../../com_github_leetcode/listnode'
 
diff --git a/src/main/ts/g0101_0200/s0146_lru_cache/solution.ts b/src/main/ts/g0101_0200/s0146_lru_cache/solution.ts
@@ -1,6 +1,6 @@
 // #Medium #Top_100_Liked_Questions #Top_Interview_Questions #Hash_Table #Design #Linked_List
 // #Doubly_Linked_List #Udemy_Linked_List #Top_Interview_150_Linked_List
-// #Big_O_Time_O(1)_Space_O(capacity) #2023_10_06_Time_473_ms_(94.72%)_Space_125.1_MB_(69.62%)
+// #Big_O_Time_O(1)_Space_O(capacity) #2025_03_26_Time_97_ms_(81.52%)_Space_108.56_MB_(48.32%)
 
 interface ICacheNode {
     key: number
diff --git a/src/main/ts/g0101_0200/s0148_sort_list/solution.ts b/src/main/ts/g0101_0200/s0148_sort_list/solution.ts
@@ -1,6 +1,6 @@
 // #Medium #Top_100_Liked_Questions #Top_Interview_Questions #Sorting #Two_Pointers #Linked_List
 // #Divide_and_Conquer #Merge_Sort #Level_2_Day_4_Linked_List #Top_Interview_150_Divide_and_Conquer
-// #Big_O_Time_O(log(N))_Space_O(log(N)) #2023_10_08_Time_141_ms_(97.14%)_Space_71.9_MB_(47.35%)
+// #Big_O_Time_O(log(N))_Space_O(log(N)) #2025_03_26_Time_36_ms_(44.94%)_Space_86.58_MB_(5.99%)
 
 import { ListNode } from '../../com_github_leetcode/listnode'
 
diff --git a/src/main/ts/g0101_0200/s0152_maximum_product_subarray/solution.ts b/src/main/ts/g0101_0200/s0152_maximum_product_subarray/solution.ts
@@ -1,6 +1,6 @@
 // #Medium #Top_100_Liked_Questions #Top_Interview_Questions #Array #Dynamic_Programming
 // #Dynamic_Programming_I_Day_6 #Level_2_Day_13_Dynamic_Programming #Udemy_Dynamic_Programming
-// #Big_O_Time_O(N)_Space_O(1) #2023_10_08_Time_53_ms_(87.50%)_Space_44.6_MB_(63.86%)
+// #Big_O_Time_O(N)_Space_O(1) #2025_03_26_Time_0_ms_(100.00%)_Space_58.34_MB_(23.08%)
 
 function maxProduct(nums: number[]): number {
     let cMin = 1
diff --git a/src/main/ts/g0101_0200/s0153_find_minimum_in_rotated_sorted_array/solution.ts b/src/main/ts/g0101_0200/s0153_find_minimum_in_rotated_sorted_array/solution.ts
@@ -1,6 +1,6 @@
 // #Medium #Top_100_Liked_Questions #Array #Binary_Search #Algorithm_II_Day_2_Binary_Search
 // #Binary_Search_I_Day_12 #Udemy_Binary_Search #Top_Interview_150_Binary_Search
-// #Big_O_Time_O(log_N)_Space_O(log_N) #2023_10_08_Time_42_ms_(98.87%)_Space_42.9_MB_(84.75%)
+// #Big_O_Time_O(log_N)_Space_O(log_N) #2025_03_26_Time_0_ms_(100.00%)_Space_55.42_MB_(40.88%)
 
 function findMin(nums: number[]): number {
     return Math.min(...nums)
diff --git a/src/main/ts/g0101_0200/s0155_min_stack/solution.ts b/src/main/ts/g0101_0200/s0155_min_stack/solution.ts
@@ -1,7 +1,7 @@
 // #Medium #Top_100_Liked_Questions #Top_Interview_Questions #Stack #Design
 // #Data_Structure_II_Day_14_Stack_Queue #Programming_Skills_II_Day_18 #Level_2_Day_16_Design
 // #Udemy_Design #Top_Interview_150_Stack #Big_O_Time_O(1)_Space_O(N)
-// #2023_10_08_Time_84_ms_(92.72%)_Space_51.8_MB_(30.46%)
+// #2025_03_26_Time_5_ms_(99.10%)_Space_65.70_MB_(50.04%)
 
 class MinStack {
     stack: number[]
diff --git a/src/main/ts/g0101_0200/s0160_intersection_of_two_linked_lists/solution.ts b/src/main/ts/g0101_0200/s0160_intersection_of_two_linked_lists/solution.ts
@@ -1,6 +1,6 @@
 // #Easy #Top_100_Liked_Questions #Top_Interview_Questions #Hash_Table #Two_Pointers #Linked_List
 // #Data_Structure_II_Day_11_Linked_List #Udemy_Linked_List #Big_O_Time_O(M+N)_Space_O(1)
-// #2023_10_08_Time_67_ms_(93.58%)_Space_50.8_MB_(40.54%)
+// #2025_03_26_Time_65_ms_(72.36%)_Space_63.62_MB_(41.12%)
 
 import { ListNode } from '../../com_github_leetcode/listnode'
 
diff --git a/src/main/ts/g0101_0200/s0169_majority_element/solution.ts b/src/main/ts/g0101_0200/s0169_majority_element/solution.ts
@@ -1,7 +1,7 @@
 // #Easy #Top_100_Liked_Questions #Top_Interview_Questions #Array #Hash_Table #Sorting #Counting
 // #Divide_and_Conquer #Data_Structure_II_Day_1_Array #Udemy_Famous_Algorithm
 // #Top_Interview_150_Array/String #Big_O_Time_O(n)_Space_O(1)
-// #2023_10_09_Time_50_ms_(96.16%)_Space_46.1_MB_(46.90%)
+// #2025_03_26_Time_0_ms_(100.00%)_Space_60.31_MB_(17.26%)
 
 function majorityElement(arr: number[]): number {
     let count = 1
diff --git a/src/main/ts/g0101_0200/s0189_rotate_array/solution.ts b/src/main/ts/g0101_0200/s0189_rotate_array/solution.ts
@@ -1,6 +1,6 @@
 // #Medium #Top_100_Liked_Questions #Top_Interview_Questions #Array #Math #Two_Pointers
 // #Algorithm_I_Day_2_Two_Pointers #Udemy_Arrays #Top_Interview_150_Array/String
-// #Big_O_Time_O(n)_Space_O(1) #2023_10_09_Time_75_ms_(97.25%)_Space_52_MB_(63.34%)
+// #Big_O_Time_O(n)_Space_O(1) #2025_03_26_Time_1_ms_(86.17%)_Space_64.71_MB_(43.34%)
 
 /*
  Do not return anything, modify nums in-place instead.
diff --git a/src/main/ts/g0101_0200/s0198_house_robber/solution.ts b/src/main/ts/g0101_0200/s0198_house_robber/solution.ts
@@ -1,7 +1,7 @@
 // #Medium #Top_100_Liked_Questions #Top_Interview_Questions #Array #Dynamic_Programming
 // #Algorithm_I_Day_12_Dynamic_Programming #Dynamic_Programming_I_Day_3
 // #Level_2_Day_12_Dynamic_Programming #Udemy_Dynamic_Programming #Top_Interview_150_1D_DP
-// #Big_O_Time_O(n)_Space_O(n) #2023_10_09_Time_51_ms_(77.29%)_Space_42.7_MB_(62.58%)
+// #Big_O_Time_O(n)_Space_O(n) #2025_03_26_Time_0_ms_(100.00%)_Space_55.74_MB_(28.06%)
 
 function rob(nums: number[]): number {
     const n = nums.length
diff --git a/src/main/ts/g0101_0200/s0200_number_of_islands/solution.ts b/src/main/ts/g0101_0200/s0200_number_of_islands/solution.ts
@@ -3,7 +3,7 @@
 // #Algorithm_II_Day_6_Breadth_First_Search_Depth_First_Search
 // #Graph_Theory_I_Day_1_Matrix_Related_Problems #Level_1_Day_9_Graph/BFS/DFS #Udemy_Graph
 // #Top_Interview_150_Graph_General #Big_O_Time_O(M*N)_Space_O(M*N)
-// #2023_10_09_Time_61_ms_(96.71%)_Space_44.5_MB_(99.30%)
+// #2025_03_26_Time_57_ms_(93.94%)_Space_59.21_MB_(64.22%)
 
 function numIslands(grid: string[][]): number {
     let islands = 0
diff --git a/src/main/ts/g0201_0300/s0206_reverse_linked_list/solution.ts b/src/main/ts/g0201_0300/s0206_reverse_linked_list/solution.ts
@@ -1,7 +1,7 @@
 // #Easy #Top_100_Liked_Questions #Top_Interview_Questions #Linked_List #Recursion
 // #Data_Structure_I_Day_8_Linked_List #Algorithm_I_Day_10_Recursion_Backtracking
 // #Level_1_Day_3_Linked_List #Udemy_Linked_List #Big_O_Time_O(N)_Space_O(1)
-// #2023_10_09_Time_51_ms_(92.87%)_Space_44.3_MB_(96.03%)
+// #2025_03_26_Time_0_ms_(100.00%)_Space_58.92_MB_(16.01%)
 
 import { ListNode } from '../../com_github_leetcode/listnode'
 
diff --git a/src/main/ts/g0201_0300/s0207_course_schedule/solution.ts b/src/main/ts/g0201_0300/s0207_course_schedule/solution.ts
@@ -1,6 +1,6 @@
 // #Medium #Top_100_Liked_Questions #Top_Interview_Questions #Depth_First_Search
 // #Breadth_First_Search #Graph #Topological_Sort #Top_Interview_150_Graph_General
-// #Big_O_Time_O(N)_Space_O(N) #2023_10_09_Time_68_ms_(70.14%)_Space_47.7_MB_(73.55%)
+// #Big_O_Time_O(N)_Space_O(N) #2025_03_26_Time_11_ms_(81.08%)_Space_62.76_MB_(51.00%)
 
 const WHITE = 0
 const GRAY = 1
diff --git a/src/main/ts/g0201_0300/s0208_implement_trie_prefix_tree/solution.ts b/src/main/ts/g0201_0300/s0208_implement_trie_prefix_tree/solution.ts
@@ -1,7 +1,7 @@
 // #Medium #Top_100_Liked_Questions #Top_Interview_Questions #String #Hash_Table #Design #Trie
 // #Level_2_Day_16_Design #Udemy_Trie_and_Heap #Top_Interview_150_Trie
 // #Big_O_Time_O(word.length())_or_O(prefix.length())_Space_O(N)
-// #2023_10_09_Time_168_ms_(80.99%)_Space_79.5_MB_(14.46%)
+// #2025_03_26_Time_48_ms_(63.95%)_Space_81.97_MB_(12.22%)
 
 class TrieNode {
     children: TrieNode[]
diff --git a/src/main/ts/g0201_0300/s0215_kth_largest_element_in_an_array/solution.ts b/src/main/ts/g0201_0300/s0215_kth_largest_element_in_an_array/solution.ts
@@ -1,11 +1,20 @@
 // #Medium #Top_100_Liked_Questions #Top_Interview_Questions #Array #Sorting #Heap_Priority_Queue
 // #Divide_and_Conquer #Quickselect #Data_Structure_II_Day_20_Heap_Priority_Queue
 // #Top_Interview_150_Heap #Big_O_Time_O(n*log(n))_Space_O(log(n))
-// #2023_10_09_Time_148_ms_(54.45%)_Space_51.5_MB_(73.60%)
+// #2025_03_26_Time_4_ms_(99.64%)_Space_66.28_MB_(62.13%)
 
 function findKthLargest(nums: number[], k: number): number {
-    nums.sort((prev, next) => next - prev)
-    return nums[k - 1]
+    const countingLen = 2e4 + 1
+    const counting = new Int32Array(countingLen)
+    for (const num of nums) {
+        counting[num + 1e4]++;
+    }
+    for (let i = countingLen - 1; i >= 0; i--) {
+        k -= counting[i]
+        if (k <= 0) {
+            return i - 1e4
+        }
+    }
 }
 
 export { findKthLargest }
