LeetCode-in-TypeScript · javadev · Apr 5, 2025 · Apr 5, 2025 · Apr 5, 2025
diff --git a/README.md b/README.md
@@ -50,6 +50,7 @@ TypeScript-based LeetCode algorithm problem solutions, regularly updated.
 
 | <!-- --> | <!-- --> | <!-- --> | <!-- --> | <!-- --> | <!-- -->
 |-|-|-|-|-|-
+| 0069 |[Sqrt(x)](src/main/ts/g0001_0100/s0069_sqrtx/solution.ts)| Hard | Array, String, Simulation | 0 | 100.00
 
 #### Day 5
 
@@ -418,6 +419,7 @@ TypeScript-based LeetCode algorithm problem solutions, regularly updated.
 
 | <!-- --> | <!-- --> | <!-- --> | <!-- --> | <!-- --> | <!-- -->
 |-|-|-|-|-|-
+| 0067 |[Add Binary](src/main/ts/g0001_0100/s0067_add_binary/solution.ts)| Easy | String, Math, Bit_Manipulation, Simulation | 0 | 100.00
 
 #### Day 6
 
@@ -1018,6 +1020,7 @@ TypeScript-based LeetCode algorithm problem solutions, regularly updated.
 | 0014 |[Longest Common Prefix](src/main/ts/g0001_0100/s0014_longest_common_prefix/solution.ts)| Easy | Top_100_Liked_Questions, Top_Interview_Questions, String | 0 | 100.00
 | 0006 |[Zigzag Conversion](src/main/ts/g0001_0100/s0006_zigzag_conversion/solution.ts)| Medium | String | 2 | 99.08
 | 0028 |[Implement strStr()](src/main/ts/g0001_0100/s0028_find_the_index_of_the_first_occurrence_in_a_string/solution.ts)| Easy | Top_Interview_Questions, String, Two_Pointers, String_Matching | 0 | 100.00
+| 0068 |[Text Justification](src/main/ts/g0001_0100/s0068_text_justification/solution.ts)| Hard | Array, String, Simulation | 0 | 100.00
 
 #### Top Interview 150 Two Pointers
 
@@ -1063,6 +1066,7 @@ TypeScript-based LeetCode algorithm problem solutions, regularly updated.
 | <!-- --> | <!-- --> | <!-- --> | <!-- --> | <!-- --> | <!-- -->
 |-|-|-|-|-|-
 | 0020 |[Valid Parentheses](src/main/ts/g0001_0100/s0020_valid_parentheses/solution.ts)| Easy | Top_100_Liked_Questions, Top_Interview_Questions, String, Stack, Big_O_Time_O(n)_Space_O(n) | 1 | 86.85
+| 0071 |[Simplify Path](src/main/ts/g0001_0100/s0071_simplify_path/solution.ts)| Medium | String, Stack | 0 | 100.00
 | 0155 |[Min Stack](src/main/ts/g0101_0200/s0155_min_stack/solution.ts)| Medium | Top_100_Liked_Questions, Top_Interview_Questions, Stack, Design, Big_O_Time_O(1)_Space_O(N) | 5 | 99.10
 
 #### Top Interview 150 Linked List
@@ -1126,6 +1130,7 @@ TypeScript-based LeetCode algorithm problem solutions, regularly updated.
 | <!-- --> | <!-- --> | <!-- --> | <!-- --> | <!-- --> | <!-- -->
 |-|-|-|-|-|-
 | 0017 |[Letter Combinations of a Phone Number](src/main/ts/g0001_0100/s0017_letter_combinations_of_a_phone_number/solution.ts)| Medium | Top_100_Liked_Questions, Top_Interview_Questions, String, Hash_Table, Backtracking, Big_O_Time_O(4^n)_Space_O(n) | 0 | 100.00
+| 0077 |[Combinations](src/main/ts/g0001_0100/s0077_combinations/solution.ts)| Medium | Backtracking | 46 | 96.14
 | 0046 |[Permutations](src/main/ts/g0001_0100/s0046_permutations/solution.ts)| Medium | Top_100_Liked_Questions, Top_Interview_Questions, Array, Backtracking, Big_O_Time_O(n\*n!)_Space_O(n+n!) | 1 | 84.44
 | 0039 |[Combination Sum](src/main/ts/g0001_0100/s0039_combination_sum/solution.ts)| Medium | Top_100_Liked_Questions, Array, Backtracking, Big_O_Time_O(2^n)_Space_O(n+2^n) | 1 | 98.17
 | 0052 |[N-Queens II](src/main/ts/g0001_0100/s0052_n_queens_ii/solution.ts)| Hard | Backtracking | 1 | 96.89
@@ -1167,6 +1172,7 @@ TypeScript-based LeetCode algorithm problem solutions, regularly updated.
 
 | <!-- --> | <!-- --> | <!-- --> | <!-- --> | <!-- --> | <!-- -->
 |-|-|-|-|-|-
+| 0067 |[Add Binary](src/main/ts/g0001_0100/s0067_add_binary/solution.ts)| Easy | String, Math, Bit_Manipulation, Simulation | 0 | 100.00
 | 0136 |[Single Number](src/main/ts/g0101_0200/s0136_single_number/solution.ts)| Easy | Top_100_Liked_Questions, Top_Interview_Questions, Array, Bit_Manipulation, Big_O_Time_O(N)_Space_O(1) | 1 | 78.27
 
 #### Top Interview 150 Math
@@ -1175,6 +1181,7 @@ TypeScript-based LeetCode algorithm problem solutions, regularly updated.
 |-|-|-|-|-|-
 | 0009 |[Palindrome Number](src/main/ts/g0001_0100/s0009_palindrome_number/solution.ts)| Easy | Math | 3 | 99.14
 | 0066 |[Plus One](src/main/ts/g0001_0100/s0066_plus_one/solution.ts)| Easy | Top_Interview_Questions, Array, Math | 0 | 100.00
+| 0069 |[Sqrt(x)](src/main/ts/g0001_0100/s0069_sqrtx/solution.ts)| Hard | Array, String, Simulation | 0 | 100.00
 | 0050 |[Pow(x, n)](src/main/ts/g0001_0100/s0050_powx_n/solution.ts)| Medium | Top_Interview_Questions, Math, Recursion | 0 | 100.00
 
 #### Top Interview 150 1D DP
@@ -1477,6 +1484,7 @@ TypeScript-based LeetCode algorithm problem solutions, regularly updated.
 
 | <!-- --> | <!-- --> | <!-- --> | <!-- --> | <!-- --> | <!-- -->
 |-|-|-|-|-|-
+| 0077 |[Combinations](src/main/ts/g0001_0100/s0077_combinations/solution.ts)| Medium | Backtracking | 46 | 96.14
 | 0046 |[Permutations](src/main/ts/g0001_0100/s0046_permutations/solution.ts)| Medium | Top_100_Liked_Questions, Top_Interview_Questions, Array, Backtracking, Big_O_Time_O(n\*n!)_Space_O(n+n!) | 1 | 84.44
 
 #### Day 12 Dynamic Programming
@@ -1690,12 +1698,17 @@ TypeScript-based LeetCode algorithm problem solutions, regularly updated.
 | 0084 |[Largest Rectangle in Histogram](src/main/ts/g0001_0100/s0084_largest_rectangle_in_histogram/solution.ts)| Hard | Top_100_Liked_Questions, Top_Interview_Questions, Array, Stack, Monotonic_Stack, Big_O_Time_O(n_log_n)_Space_O(log_n) | 15 | 72.81
 | 0079 |[Word Search](src/main/ts/g0001_0100/s0079_word_search/solution.ts)| Medium | Top_100_Liked_Questions, Top_Interview_Questions, Array, Matrix, Backtracking, Algorithm_II_Day_11_Recursion_Backtracking, Top_Interview_150_Backtracking, Big_O_Time_O(4^(m\*n))_Space_O(m\*n) | 243 | 85.30
 | 0078 |[Subsets](src/main/ts/g0001_0100/s0078_subsets/solution.ts)| Medium | Top_100_Liked_Questions, Top_Interview_Questions, Array, Bit_Manipulation, Backtracking, Algorithm_II_Day_9_Recursion_Backtracking, Udemy_Backtracking/Recursion, Big_O_Time_O(2^n)_Space_O(n\*2^n) | 0 | 100.00
+| 0077 |[Combinations](src/main/ts/g0001_0100/s0077_combinations/solution.ts)| Medium | Backtracking, Algorithm_I_Day_11_Recursion_Backtracking, Top_Interview_150_Backtracking | 46 | 96.14
 | 0076 |[Minimum Window Substring](src/main/ts/g0001_0100/s0076_minimum_window_substring/solution.ts)| Hard | Top_100_Liked_Questions, Top_Interview_Questions, String, Hash_Table, Sliding_Window, Level_2_Day_14_Sliding_Window/Two_Pointer, Top_Interview_150_Sliding_Window, Big_O_Time_O(s.length())_Space_O(1) | 20 | 90.35
 | 0075 |[Sort Colors](src/main/ts/g0001_0100/s0075_sort_colors/solution.ts)| Medium | Top_100_Liked_Questions, Top_Interview_Questions, Array, Sorting, Two_Pointers, Data_Structure_II_Day_2_Array, Udemy_Arrays, Big_O_Time_O(n)_Space_O(1) | 0 | 100.00
 | 0074 |[Search a 2D Matrix](src/main/ts/g0001_0100/s0074_search_a_2d_matrix/solution.ts)| Medium | Top_100_Liked_Questions, Array, Binary_Search, Matrix, Data_Structure_I_Day_5_Array, Algorithm_II_Day_1_Binary_Search, Binary_Search_I_Day_8, Level_2_Day_8_Binary_Search, Udemy_2D_Arrays/Matrix, Top_Interview_150_Binary_Search, Big_O_Time_O(endRow+endCol)_Space_O(1) | 0 | 100.00
 | 0073 |[Set Matrix Zeroes](src/main/ts/g0001_0100/s0073_set_matrix_zeroes/solution.ts)| Medium | Top_100_Liked_Questions, Top_Interview_Questions, Array, Hash_Table, Matrix, Udemy_2D_Arrays/Matrix, Top_Interview_150_Matrix, Big_O_Time_O(m\*n)_Space_O(1) | 4 | 50.63
 | 0072 |[Edit Distance](src/main/ts/g0001_0100/s0072_edit_distance/solution.ts)| Medium | Top_100_Liked_Questions, String, Dynamic_Programming, Algorithm_II_Day_18_Dynamic_Programming, Dynamic_Programming_I_Day_19, Udemy_Dynamic_Programming, Top_Interview_150_Multidimensional_DP, Big_O_Time_O(n^2)_Space_O(n2) | 6 | 93.83
+| 0071 |[Simplify Path](src/main/ts/g0001_0100/s0071_simplify_path/solution.ts)| Medium | String, Stack, Top_Interview_150_Stack | 0 | 100.00
 | 0070 |[Climbing Stairs](src/main/ts/g0001_0100/s0070_climbing_stairs/solution.ts)| Easy | Top_100_Liked_Questions, Top_Interview_Questions, Dynamic_Programming, Math, Memoization, Algorithm_I_Day_12_Dynamic_Programming, Dynamic_Programming_I_Day_2, Level_1_Day_10_Dynamic_Programming, Udemy_Dynamic_Programming, Top_Interview_150_1D_DP, Big_O_Time_O(n)_Space_O(n) | 0 | 100.00
+| 0069 |[Sqrt(x)](src/main/ts/g0001_0100/s0069_sqrtx/solution.ts)| Hard | Array, String, Simulation, Top_Interview_150_Array/String | 0 | 100.00
+| 0068 |[Text Justification](src/main/ts/g0001_0100/s0068_text_justification/solution.ts)| Hard | Array, String, Simulation, Top_Interview_150_Array/String | 0 | 100.00
+| 0067 |[Add Binary](src/main/ts/g0001_0100/s0067_add_binary/solution.ts)| Easy | String, Math, Bit_Manipulation, Simulation, Programming_Skills_II_Day_5, Top_Interview_150_Bit_Manipulation | 0 | 100.00
 | 0066 |[Plus One](src/main/ts/g0001_0100/s0066_plus_one/solution.ts)| Easy | Top_Interview_Questions, Array, Math, Programming_Skills_II_Day_3, Udemy_Arrays, Top_Interview_150_Math | 0 | 100.00
 | 0064 |[Minimum Path Sum](src/main/ts/g0001_0100/s0064_minimum_path_sum/solution.ts)| Medium | Top_100_Liked_Questions, Array, Dynamic_Programming, Matrix, Dynamic_Programming_I_Day_16, Udemy_Dynamic_Programming, Top_Interview_150_Multidimensional_DP, Big_O_Time_O(m\*n)_Space_O(m\*n) | 4 | 70.73
 | 0063 |[Unique Paths II](src/main/ts/g0001_0100/s0063_unique_paths_ii/solution.ts)| Medium | Array, Dynamic_Programming, Matrix, Dynamic_Programming_I_Day_15, Top_Interview_150_Multidimensional_DP | 0 | 100.00

diff --git a/src/main/ts/g0001_0100/s0067_add_binary/readme.md b/src/main/ts/g0001_0100/s0067_add_binary/readme.md
@@ -0,0 +1,23 @@
+67\. Add Binary
+
+Easy
+
+Given two binary strings `a` and `b`, return _their sum as a binary string_.
+
+**Example 1:**
+
+**Input:** a = "11", b = "1"
+
+**Output:** "100" 
+
+**Example 2:**
+
+**Input:** a = "1010", b = "1011"
+
+**Output:** "10101" 
+
+**Constraints:**
+
+*   <code>1 <= a.length, b.length <= 10<sup>4</sup></code>
+*   `a` and `b` consist only of `'0'` or `'1'` characters.
+*   Each string does not contain leading zeros except for the zero itself.
diff --git a/src/main/ts/g0001_0100/s0067_add_binary/solution.ts b/src/main/ts/g0001_0100/s0067_add_binary/solution.ts
@@ -0,0 +1,26 @@
+// #Easy #String #Math #Bit_Manipulation #Simulation #Programming_Skills_II_Day_5
+// #Top_Interview_150_Bit_Manipulation #2025_04_05_Time_0_ms_(100.00%)_Space_58.14_MB_(39.81%)
+
+function addBinary(a: string, b: string): string {
+    const aArray = a.split('')
+    const bArray = b.split('')
+    let sb: string[] = []
+    let i = aArray.length - 1
+    let j = bArray.length - 1
+    let carry = 0
+    while (i >= 0 || j >= 0) {
+        const digitA = i >= 0 ? parseInt(aArray[i]) : 0
+        const digitB = j >= 0 ? parseInt(bArray[j]) : 0
+        const sum = digitA + digitB + carry
+        sb.push((sum % 2).toString())
+        carry = Math.floor(sum / 2)
+        i--
+        j--
+    }
+    if (carry !== 0) {
+        sb.push(carry.toString())
+    }
+    return sb.reverse().join('')
+}
+
+export { addBinary }
diff --git a/src/main/ts/g0001_0100/s0068_text_justification/readme.md b/src/main/ts/g0001_0100/s0068_text_justification/readme.md
@@ -0,0 +1,45 @@
+68\. Text Justification
+
+Hard
+
+Given an array of strings `words` and a width `maxWidth`, format the text such that each line has exactly `maxWidth` characters and is fully (left and right) justified.
+
+You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces `' '` when necessary so that each line has exactly `maxWidth` characters.
+
+Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line does not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.
+
+For the last line of text, it should be left-justified and no extra space is inserted between words.
+
+**Note:**
+
+*   A word is defined as a character sequence consisting of non-space characters only.
+*   Each word's length is guaranteed to be greater than 0 and not exceed maxWidth.
+*   The input array `words` contains at least one word.
+
+**Example 1:**
+
+**Input:** words = ["This", "is", "an", "example", "of", "text", "justification."], maxWidth = 16
+
+**Output:** [ "This is an", "example of text", "justification. " ]
+
+**Example 2:**
+
+**Input:** words = ["What","must","be","acknowledgment","shall","be"], maxWidth = 16
+
+**Output:** [ "What must be", "acknowledgment ", "shall be " ]
+
+**Explanation:** Note that the last line is "shall be " instead of "shall be", because the last line must be left-justified instead of fully-justified. Note that the second line is also left-justified becase it contains only one word.
+
+**Example 3:**
+
+**Input:** words = ["Science","is","what","we","understand","well","enough","to","explain","to","a","computer.","Art","is","everything","else","we","do"], maxWidth = 20
+
+**Output:** [ "Science is what we", "understand well", "enough to explain to", "a computer. Art is", "everything else we", "do " ]
+
+**Constraints:**
+
+*   `1 <= words.length <= 300`
+*   `1 <= words[i].length <= 20`
+*   `words[i]` consists of only English letters and symbols.
+*   `1 <= maxWidth <= 100`
+*   `words[i].length <= maxWidth`
diff --git a/src/main/ts/g0001_0100/s0068_text_justification/solution.ts b/src/main/ts/g0001_0100/s0068_text_justification/solution.ts
@@ -0,0 +1,56 @@
+// #Hard #Array #String #Simulation #Top_Interview_150_Array/String
+// #2025_04_05_Time_0_ms_(100.00%)_Space_55.70_MB_(38.14%)
+
+function fullJustify(words: string[], maxWidth: number): string[] {
+    const output: string[] = []
+    let sb: string[] = []
+    let lineTotal = 0
+    let numWordsOnLine = 0
+    let startWord = 0
+    for (let i = 0; i < words.length - 1; i++) {
+        lineTotal += words[i].length
+        numWordsOnLine++
+        if (lineTotal + numWordsOnLine + words[i + 1].length > maxWidth) {
+            sb = []
+            if (numWordsOnLine === 1) {
+                sb.push(words[i])
+                while (lineTotal++ < maxWidth) {
+                    sb.push(' ')
+                }
+            } else {
+                const spaces = Math.floor((maxWidth - lineTotal) / (numWordsOnLine - 1))
+                let extraSp = (maxWidth - lineTotal) % (numWordsOnLine - 1)
+
+                for (let j = startWord; j < startWord + numWordsOnLine - 1; j++) {
+                    sb.push(words[j])
+                    sb.push(' '.repeat(spaces + (extraSp-- > 0 ? 1 : 0)))
+                }
+                sb.push(words[startWord + numWordsOnLine - 1])
+            }
+            output.push(sb.join(''))
+            startWord = i + 1
+            numWordsOnLine = lineTotal = 0
+        }
+    }
+
+    // Handle last line
+    sb = []
+    lineTotal = 0
+    for (let i = startWord; i < words.length; i++) {
+        lineTotal += words[i].length
+        sb.push(words[i])
+        if (lineTotal < maxWidth) {
+            sb.push(' ')
+            lineTotal++
+        }
+    }
+    while (lineTotal < maxWidth) {
+        sb.push(' ')
+        lineTotal++
+    }
+    output.push(sb.join(''))
+
+    return output
+}
+
+export { fullJustify }
diff --git a/src/main/ts/g0001_0100/s0069_sqrtx/readme.md b/src/main/ts/g0001_0100/s0069_sqrtx/readme.md
@@ -0,0 +1,28 @@
+69\. Sqrt(x)
+
+Easy
+
+Given a non-negative integer `x`, compute and return _the square root of_ `x`.
+
+Since the return type is an integer, the decimal digits are **truncated**, and only **the integer part** of the result is returned.
+
+**Note:** You are not allowed to use any built-in exponent function or operator, such as `pow(x, 0.5)` or `x ** 0.5`.
+
+**Example 1:**
+
+**Input:** x = 4
+
+**Output:** 2 
+
+**Example 2:**
+
+**Input:** x = 8
+
+**Output:** 2
+
+**Explanation:** The square root of 8 is 2.82842..., and since the decimal part is truncated, 2 is returned.
+
+**Constraints:**
+
+*   <code>0 <= x <= 2<sup>31</sup> - 1</code>
+
diff --git a/src/main/ts/g0001_0100/s0069_sqrtx/solution.ts b/src/main/ts/g0001_0100/s0069_sqrtx/solution.ts
@@ -0,0 +1,23 @@
+// #Hard #Array #String #Simulation #Top_Interview_150_Array/String
+// #2025_04_05_Time_0_ms_(100.00%)_Space_55.70_MB_(38.14%)
+
+function mySqrt(x: number): number {
+    let low = 1
+    let high = x
+    let lowest = 0
+    while (low <= high) {
+        const mid = Math.floor((low + high) / 2)
+        const pow = mid * mid
+        if(pow > x) {
+            high = mid - 1
+        } else if(pow < x) {
+            low = mid + 1
+            lowest = mid
+        } else {
+            return mid
+        }
+    }
+    return lowest
+}
+
+export { mySqrt }
diff --git a/src/main/ts/g0001_0100/s0071_simplify_path/readme.md b/src/main/ts/g0001_0100/s0071_simplify_path/readme.md
@@ -0,0 +1,52 @@
+71\. Simplify Path
+
+Medium
+
+Given a string `path`, which is an **absolute path** (starting with a slash `'/'`) to a file or directory in a Unix-style file system, convert it to the simplified **canonical path**.
+
+In a Unix-style file system, a period `'.'` refers to the current directory, a double period `'..'` refers to the directory up a level, and any multiple consecutive slashes (i.e. `'//'`) are treated as a single slash `'/'`. For this problem, any other format of periods such as `'...'` are treated as file/directory names.
+
+The **canonical path** should have the following format:
+
+*   The path starts with a single slash `'/'`.
+*   Any two directories are separated by a single slash `'/'`.
+*   The path does not end with a trailing `'/'`.
+*   The path only contains the directories on the path from the root directory to the target file or directory (i.e., no period `'.'` or double period `'..'`)
+
+Return _the simplified **canonical path**_.
+
+**Example 1:**
+
+**Input:** path = "/home/"
+
+**Output:** "/home"
+
+**Explanation:** Note that there is no trailing slash after the last directory name. 
+
+**Example 2:**
+
+**Input:** path = "/../"
+
+**Output:** "/"
+
+**Explanation:** Going one level up from the root directory is a no-op, as the root level is the highest level you can go. 
+
+**Example 3:**
+
+**Input:** path = "/home//foo/"
+
+**Output:** "/home/foo"
+
+**Explanation:** In the canonical path, multiple consecutive slashes are replaced by a single one. 
+
+**Example 4:**
+
+**Input:** path = "/a/./b/../../c/"
+
+**Output:** "/c" 
+
+**Constraints:**
+
+*   `1 <= path.length <= 3000`
+*   `path` consists of English letters, digits, period `'.'`, slash `'/'` or `'_'`.
+*   `path` is a valid absolute Unix path.
diff --git a/src/main/ts/g0001_0100/s0071_simplify_path/solution.ts b/src/main/ts/g0001_0100/s0071_simplify_path/solution.ts
@@ -0,0 +1,19 @@
+// #Medium #String #Stack #Top_Interview_150_Stack
+// #2025_04_05_Time_0_ms_(100.00%)_Space_58.31_MB_(30.21%)
+
+function simplifyPath(path: string): string {
+    const stack = []
+    const mod = path.split('/').filter((element) => element.length)
+    for (const element of mod) {
+        if (element === '..') {
+            stack.pop()
+        } else if (element === '.') {
+            continue
+        } else {
+            stack.push(element)
+        }
+    }
+    return '/'.concat(stack.join('/'))
+}
+
+export { simplifyPath }
diff --git a/src/main/ts/g0001_0100/s0077_combinations/readme.md b/src/main/ts/g0001_0100/s0077_combinations/readme.md
@@ -0,0 +1,24 @@
+77\. Combinations
+
+Medium
+
+Given two integers `n` and `k`, return _all possible combinations of_ `k` _numbers out of the range_ `[1, n]`.
+
+You may return the answer in **any order**.
+
+**Example 1:**
+
+**Input:** n = 4, k = 2
+
+**Output:** [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ] 
+
+**Example 2:**
+
+**Input:** n = 1, k = 1
+
+**Output:** [[1]] 
+
+**Constraints:**
+
+*   `1 <= n <= 20`
+*   `1 <= k <= n`