LeetCode Solution

This is powered by CodeXplore

Table of contents
Part A: Data Structure
1. Primitive Types
2. Arrays
- 2.1. Keynotes
- 2.2. Array Problems
3. Linked List
- 3.1. Keynotes
- 3.2. Linked List Problems
4. Hash Map
- 4.1. Keynotes
5. Queue
Part B: Algorithms
1. Recursion
2. Dynamic Programming
3. BFS & DFS
- 3.1. BFS
- 3.2. DFS
4. Graph Theory
Searching
LeetCode Solutions
Resources
License

Part A: Data Structure

1. Primitive Types

1.1. KeyNotes

[Number] Infinity: float('inf') and float('-inf')
[Number] Math Operator: %10 modulus 10 to extract last digit in a number, //10 to remove the last digit in a number
[Number > String] 9 to "9": char(ord('0') + 9)
[String > Number] "9" to 9: ord('9') - ord('0') = 9, for s="123" to 123: res = res*10 + ord(s[i]) - ord('0')
[String] Palindromic all(s[i] == s[~i] for i in range(len(s//2)) where s[~i] = s[-(i+1)]
[Set] Create a set of digits ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9'] => nums = set('0123456789')
[Circular Array] to circular the array index index = (index + 1) % array_size

External Library:

help(): to understand the function usage. For ex: help(math.log)
dir(): See all the names in module or to understand an un-known object, using the built-in function dir()
help(): to understand the function usage. For ex: help(math.log)
dir(): See all the names in module or to understand an un-known object, using the built-in function dir()

import math
print(dir(math))

['__doc__', '__file__',....]

1.2. Bitwise Operation:

n-bitbinary numbers can re-present 2^(n) distinct integers. For example: 4-bit binary numbers can represent 16 distinct integers.
x << y: x is Left shifted by 2**y same as multiplying x by 2**y (and new bits on the right-hand-side are zeros).
x >> y: x is Right shifted by 2**y same as dividing x by 2**y (and new bits on the left-hand-side are zeros).
n-bitbinary numbers can re-present 2^(n) distinct integers. For example: 4-bit binary numbers can represent 16 distinct integers.
x << y: x is Left shifted by 2**y same as multiplying x by 2**y (and new bits on the right-hand-side are zeros).
x >> y: x is Right shifted by 2**y same as dividing x by 2**y (and new bits on the left-hand-side are zeros).
x & 1 : compares LSB of X with 1 (For ex: x=1010, then x & 0001 = 0)
x | 1 : add the LSB of X with 1 (For ex: x=1010, then x | 0001 = 1011)
⭐ x ^ 1 : XOR (0 0 -> 0, 0 1 -> 1, 1 0 -> 1, 1 1 -> 0)
⭐ x&(x-1): to erase lowest set bit of x. (For ex: x=00101100, x-1= 00101011 then x&(x-1)=00101000)

1.2.1. Bitwise Example

Question #1: Write a program to count number of bits set to 1 in a positive integer, say x = 69

num_bits = 0
while x:
    num_bits += x & 1 #Compare LSB of X with 1, if LSB = 1, then increase num_bits by 1
    x >>= 1 #Shift Right x by 1 bit

Question #2: Computing Parity of Binary Word (parity = 1 when # of 1s in the word is odd (1011), parity = 1 when # of 1s in the word is even (1010))

result = 0
while x:
    result ^= x & 1 #XOR
    x >> = 1

Explain result ^= x & 1
- If res is even (0) and x-bit is 1, res evaluates to odd (1).
- If res is odd (1) and x-bit is 1, res evaluates to even (0).
- If res is even (0) and x-bit is 1, res evaluates to odd (1).
- If res is odd (1) and x-bit is 1, res evaluates to even (0).

1.2.2. LeetCode Questions:

Convert Binary Number to Integer For ex: LinkedList of Binary: 1 -> 0 -> 1 = 5 in decimal
- Tips: Bitwise operation
  - initialise an integer variable num to 0
  - num << 1 left shift num by 1 position to make way for the val in the next node in linked list. This is same as multiplying num by 2
  - num << 1 | head.val Add (|) next bit to num at least significant position
- Tips: Bitwise operation
  - initialise an integer variable num to 0
  - num << 1 left shift num by 1 position to make way for the val in the next node in linked list. This is same as multiplying num by 2
  - num << 1 | head.val Add (|) next bit to num at least significant position

1.3. Strings and Numbers

1.3.1. find() and rfind()

.find(): find the starting index of the first occurrence of a substring as specified

s = 'machine learning'

s.find('n') #return = 5 > find the first occurance 'n'
s.find('n', 6) #return = 12 >  find the occurance from 6th index
s.find('n', 6, 10) #return = -1 > represents not found, not a negative index here

.rfind(): find the starting index in the reverse direction

s.rfind('n') #return = 5 > find the first occurance 'n'
s.rfind('n', 15) #return = -1 >  If a second argument is provided, it is where the search ends in the reverse direction, inclusive of this index itself
s.rfind('n', 0, 12) #return = 5 > represents not found, not a negative index here

String Format

Padding 0: For example, convert integer month = 2 to "02": f"{month:02d}"

1.3.3. String and Number LeetCode Questions

Problems	Difficulty	Solutions	Description
1. Two Sum	`Easy`	Code	Using Hash Map
2. Add Two Number	`Medium`	Code
5. Longest Palindromic Substring	`Medium`	Code	Need to check if odd pal `cabac` and even pal `abba` and keep track on the maximum
6. ZigZag Conversion	`Medium`	Code	to identify the pattern
8. String to Integer (atoi)	`Medium`	Code	to solve one by one, starting with `whitespace`, then `-/+` then `numbers` by iterating through the string with O(n)
15. 3Sum	`Medium`	Code
17. Letter Combinations of a Phone Number	`Medium`	Code	Using the recursion
20. Valid Parentheses	`Easy`	Code	Using Stack
50. Pow(x, n)	`Medium`	Code	Using Recursive Approach, divide `power n` by `//2`, remember to take care of negative power i.e `n < 0`
125. Valid Palindrome		Code	Check if original & reverse string are the same (ie: return result == result[ : : -1])
167. Two Sum II - Input array is sorted		Code	Using 2 pointers
344. Reverse String		Code	2-pointer approach to reverse the string without creating extra memory (i.e: Space Complexity O(1)
441. Arranging Coins		Code	Using Mathematics Formula
454. 4Sum II		Code	Using Hash Map
1446. Consecutive Characters		Code	2-pointer approach
1539. Kth Missing Positive Number	`Easy`	Code

728. Self Dividing Numbers

Learn #1: Splitting A Number (169) into Digit (9, 6, 1)

 while n > 0:
   d = n%10
   #Do somthing here with each digit d
   n //=10

Learn #1: Splitting A Number (169) into Digit (9, 6, 1)

 while n > 0:
   d = n%10
   #Do somthing here with each digit d
   n //=10

1304. Find N Unique Integers Sum up to Zero
- Learn #1: Do not be misleading by Examples, find the general rule
- Learn #2: Python to append multiple items into list: result+=[i, -i]
- Learn #1: Do not be misleading by Examples, find the general rule
- Learn #2: Python to append multiple items into list: result+=[i, -i]
1370. Increasing Decreasing String
- Learn #1: Hash Table + Sorted + Flag desc to toggle the sort direction sorted(dict, reverse = desc)
- Learn #2: To flipping between True/False in Python, we can use ~ i.e `desc = ~desc
- Learn #1: Hash Table + Sorted + Flag desc to toggle the sort direction sorted(dict, reverse = desc)
- Learn #2: To flipping between True/False in Python, we can use ~ i.e `desc = ~desc
1436. Destination City
- Learn: using Hash Table to check for existing of elements instead of looping through
- Learn: using Hash Table to check for existing of elements instead of looping through
1464. Maximum Product of Two Elements in an Array Given the array of integers nums, you will choose two different indices i and j of that array. Return the maximum value of (nums[i]-1)*(nums[j]-1). - Learn: Find the 2 largest elements in nums Given the array of integers nums, you will choose two different indices i and j of that array. Return the maximum value of (nums[i]-1)*(nums[j]-1). - Learn: Find the 2 largest elements in nums

1748. Sum of Unique Elements

Learn: Using Hash Table to calculate Unique Element (like below code), we can use collections.Counter(nums)

      for num in nums:
        if num in dict:
            dict[num]+=1
        else:
            dict[num]=1

Learn: Using Hash Table to calculate Unique Element (like below code), we can use collections.Counter(nums)

      for num in nums:
        if num in dict:
            dict[num]+=1
        else:
            dict[num]=1

2. Arrays

2.1. Keynotes

To reverse List: list[::-1]
To sort a list: list.sort(reverse = True)
To insert First Element to Array: list.insert(0,new_element) (Exercise: 66)
To insert @ Tail: list.append(element)
To insert Many @ Tail: list.append([1,2,3])
To remove:

l = [1, 2, 3, 5, 7, 9, 11, 13, 15, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49]

#.remove(): remove a specific value
# l.remove(4) # error if remove 4 as 4 not in l
l.remove(9)   # l = [1, 2, 3, 5, 7, 11, 13, 15, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49]

#.pop(): remove at an index and return
l.pop()  # return 49 and l = [1, 2, 3, 5, 7, 11, 13, 15, 17, 19, 23, 29, 31, 37, 41, 43, 47]
l.pop(1) # return 2 and  l = [1, 3, 5, 7, 11, 13, 15, 17, 19, 23, 29, 31, 37, 41, 43, 47]

#.clear(): remove all
l.clear # l = []

To iterate both index and value in List: enumerate

for index, value in enumerate(arr):
  print(index, value)
0 a
1 b
2 c

Operation	Complexity	Description
Retrieve	`O(1)`
Update	`O(1)`
Append	`O(1)`	Append (Inserrt to full array) can be handled by `resizing`, i.e: allocating a new array with addtional memory and copying over the entries from the original array. However, the average time for insertion is constant as `resizing` is very infrequent.
Insert @ ith index	`O(n-i)`	Use to insert First Element to array `list.insert(0,new_element)`
Delete @ ith index	`O(n-i)`	Delete an element @ ith from an array requires moving all successive elements on over to the left to fill the vacated @ ith
Operation	Complexity	Description
------------------	:--------:	-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Retrieve	`O(1)`
Update	`O(1)`
Append	`O(1)`	Append (Inserrt to full array) can be handled by `resizing`, i.e: allocating a new array with addtional memory and copying over the entries from the original array. However, the average time for insertion is constant as `resizing` is very infrequent.
Insert @ ith index	`O(n-i)`	Use to insert First Element to array `list.insert(0,new_element)`
Delete @ ith index	`O(n-i)`	Delete an element @ ith from an array requires moving all successive elements on over to the left to fill the vacated @ ith

2.2. Array Problems

2.2.1. 1D Array

Problems	Difficulty	Solutions	Description
11. Container With Most Water	`Medium`	Code	Need to start from both 2 end and go inwards
66. Plus One	`Easy`	Code	Using `list.insert(0,new_element)` for first element insert to array
Problems	Difficulty	Solutions	Description
-------------------------------------------------------	:--------:	:------------------------------------------------:	:-------------------------------------------------------------------
11. Container With Most Water	`Medium`	Code	Need to start from both 2 end and go inwards
66. Plus One	`Easy`	Code	Using `list.insert(0,new_element)` for first element insert to array

75. Sort Colors (Dutch National Flag Problem)
- Learn #1: to sort an array with (3 type of element) in Time Complexity O(n), use Dutch National Flag algo.
  - Select pivot as a middle number, say array contains [0,1,2], choose pivot=1
  - First iteration: go Left to right, move element < pivot to left
  - Second iteration: go Right to left, move element > pivot to right, stop when meeting element < pivot.
- Learn #1: to sort an array with (3 type of element) in Time Complexity O(n), use Dutch National Flag algo.
  - Select pivot as a middle number, say array contains [0,1,2], choose pivot=1
  - First iteration: go Left to right, move element < pivot to left
  - Second iteration: go Right to left, move element > pivot to right, stop when meeting element < pivot.

1299. Replace Elements with Greatest Element on Right Side

Learn #1: Look at the problem from Right to Left

Tradition: arr = [17,18,5,4,6,1] > [18, , , , , , ]          > [18,6, , , , , ]
Optimal  : arr = [17,18,5,4,6,1] > [, , , , , , -1] curMax=1 > [, , , , , 1,-1] curMax=6

Learn #1: Look at the problem from Right to Left

Tradition: arr = [17,18,5,4,6,1] > [18, , , , , , ]          > [18,6, , , , , ]
Optimal  : arr = [17,18,5,4,6,1] > [, , , , , , -1] curMax=1 > [, , , , , 1,-1] curMax=6

2.2.2. 2D Matrix

1351. Count Negative Numbers in a Sorted Matrix

Learn #1: O(n+m) 2D Array => Using 2-Pointer Approach => "trace" the outline of the staircase
Learn #2: Q(m*log(n)) Sorted Array => Binary Search Tree: to search to position of First Negative Number in the Array

 def binarySearch(row):
        start = 0
        end = len(row) - 1
        while (start <= end):
            # Mid post
            mid = start + (end - start)//2
            if (row[mid] < 0):
                end = mid - 1
            else:
                start = mid + 1
        return len(row) - start

Learn #1: O(n+m) 2D Array => Using 2-Pointer Approach => "trace" the outline of the staircase
Learn #2: Q(m*log(n)) Sorted Array => Binary Search Tree: to search to position of First Negative Number in the Array

 def binarySearch(row):
        start = 0
        end = len(row) - 1
        while (start <= end):
            # Mid post
            mid = start + (end - start)//2
            if (row[mid] < 0):
                end = mid - 1
            else:
                start = mid + 1
        return len(row) - start

3. Linked List

3.1. Keynotes

Create a linked list with dummy_head and tail: dummy_head = tail = ListNode() using tail to move (Exercise: 21)
Create a dummy_head = None for the case do NOT require extra node.

3.2. Linked List Problems

Problems	Difficulty	Solutions	Description
19. Remove Nth Node From End of Lists	`Medium`	Code
92. Reverse Linked List II	`Medium`	Code
142. Linked List Cycle II	`Medium`	Code	⭐ Good Algo to do Need to calculate the distance to reach
206. Reverse Linked List	`Easy`	Code
Problems	Difficulty	Solutions	Description
-----------------------------------------------------------------------------------	:--------:	:-------------------------------------------------------:	:-----------------------------------------------------------------
19. Remove Nth Node From End of Lists	`Medium`	Code
92. Reverse Linked List II	`Medium`	Code
142. Linked List Cycle II	`Medium`	Code	⭐ Good Algo to do Need to calculate the distance to reach
206. Reverse Linked List	`Easy`	Code

4. Hash Map

4.1. Keynotes

len(d): return numbers of items in dictionary
d[key] or d.get(key, default_value): return corresponding value with specific key, return default_value when key is not found
in or not in: membership operators
d.pop(key) or del d[key]: remove an item from the dictionary To access keys, values, and items
d[key] or d.get(key, default_value): return corresponding value with specific key, return default_value when key is not found
in or not in: membership operators
d.pop(key) or del d[key]: remove an item from the dictionary To access keys, values, and items
d.keys() return the set of all keys in dictionary d
d.values() return the set of all values in dictionary d
d.items() return the set of all items (pair of keys and values) in dictionary d

#to access both keys and values
for k, v in d.items():
    print(k, v)

5. Queue

Queue will be used for BFS
Queue in Python: using list with dequeue list.pop(0) (But requiring O(n) as need to shift all elements) time and enqueue list.append(item)
Queue with Built-in Function:

from collections import deque
q = deque() # Initializing a queue
q.append('a') # Adding elements to a queue
# Removing elements from a queue - only O(1) in compare with using List to implement Queue
q.popleft()

Problems	Difficulty	Solutions	Description
622. Design Circular Queue	`Medium`	Code	To circular the array: `self.tail = (self.tail + 1)%self.size` For enqueue, need to take care only the tail, for dequeue, need to take care only the head. Please refer the link for the circular queue example https://leetcode.com/explore/learn/card/queue-stack/228/first-in-first-out-data-structure/1396/

Problems	Difficulty	Solutions	Description
622. Design Circular Queue	`Medium`	Code	To circular the array: `self.tail = (self.tail + 1)%self.size` For enqueue, need to take care only the tail, for dequeue, need to take care only the head. Please refer the link for the circular queue example https://leetcode.com/explore/learn/card/queue-stack/228/first-in-first-out-data-structure/1396/

Part B: Algorithms

1. Recursion

Key Points: Change Large Input → Smaller Input
- Ex1 - Fibonacci: The next number is found by adding up the two numbers before it
  - fib(1) = fib(2) = 1
  - fib(n) = fib(n-1) + fib(n-2)

Problems	Solutions	Difficulty	Description
24. Swap Nodes in Pairs	Code	`Medium`	Refer to the code comments
Problems	Solutions	Difficulty	Description
-----------------------	:------------------------------------------:	----------	--------------------------
24. Swap Nodes in Pairs	Code	`Medium`	Refer to the code comments

2. Dynamic Programming

Tips: For Dynamic Programming, it s very important to write down the recurrence relationship like below
- d(i,j) cell = relationship with its neighbors: d(i, j+1), d(i+1, j), d(i+1, j+1)
Key Points: DP can be done either by Recursive (Top-Down) or Iterative (Bottom-Up) Approach
Key Points: Cache memo can be passed into the function as an input param

    def climbStairs(self, n: int, memo = {1: 1, 2:2}) -> int:
        if n not in memo: #T(n) = T(n-1) + T(n-2)
            memo[n] = self.climbStairs(n-1, memo) + self.climbStairs(n-2, memo)
        return memo[n]

Problems	Solutions	Difficulty	Description
53. Maximum Subarray	Code	`Easy`	`T(i) = max(T(i-1) + nums[i] , nums[i])` where T(i) is maximum sum at that particular position
62. Unique Paths	Code	`Medium`
64. Minimum Path Sum	Code	`Medium`	`dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i-1][j-1]`
70. Climbing Stairs	Code	`Easy`	At T(n): first step = 1, remaining steps = T(n-1) or first step = 2, remaing steps = T(n-2). This recurrence relationship is similar to Fibonacci number
72. Edit Distance	Code	`Hard`
198. House Robber	Code	`Medium`
322. Coin Change	Code	`Medium`	1D - DP Table
518. Coin Change 2	Code	`Medium`	0/1 Knapsacks Problem
1143. Longest Common Subsequence	Code	`Medium`

3. BFS and DFS

3.1. BFS

BFS for Graph: need to keep track on visited = set() vertices
BFS to find shortest path for un-weighted graph or weighted graph if all costs are equal, we can use BFS (Level Traversal) instead of Dijkstra's algorithm.

Find Neighbors:

2D Matrix:

direction = [(0,-1), (0,1), (-1,0), (1,0)] #Top, Down, Left, Right
while(queue):
    i, j = queue.pop(0)
    for d_i, d_j in direction:
        new_i, new_j = i + d_i, j + d_j
        if (new_i >= 0 and new_i < row) and (new_j >= 0 and new_j < col):
        #For valid new_i, new_j, do something

Problems	Type	Solutions	Difficulty	Description
200. Number of Islands	Graph	Code	`Medium`	Need to search the adjacent location (top, down, left, right) of the "1" cell to find the maximum size of an island, then can continue
429. N-ary Tree Level Order Traversal	Tree	Code	`Medium`
542. 01 Matrix	Tree	Code	`Medium`	Using BFS for multiple nodes at the same time Land-Sea Strategy
752. Open the Lock	Graph	Code	`Medium`	from start, add the next possible turn into the queue and then continue to search with Target
2039. The Time When the Network Becomes Idle	Graph	Code	`Medium`	We can use DFS to calculate the travel time from master server to remain data servers like Level Traversal

3.2. DFS

Problems	Type	Solutions	Difficulty	Description
797. All Paths From Source to Target	DAG	Code	`Medium`	DFS without the color flag
Problems	Type	Solutions	Difficulty	Description
------------------------------------	:-----:	:-------------------------------------------------------:	:--------:	--------------------------
797. All Paths From Source to Target	DAG	Code	`Medium`	DFS without the color flag

4. Graph Theory

4.1. Topological Sort

Problems	Solutions	Difficulty	Description
210. Course Schedule II	Code	`Medium`	Step 1: Conver into a graph, then apply Topological Sort, remember to add the flag for Cycle Detection

4.2. Minimum Spanning Tree - Kruskal Algorithm

Problems	Solutions	Difficulty	Description
1584. Min Cost to Connect All Points	Code	`Medium`	Using Kruskal Algorithm
Problems	Solutions	Difficulty	Description
------------------------------------	:-------------------------------------------------------:	----------	-----------------------
1584. Min Cost to Connect All Points	Code	`Medium`	Using Kruskal Algorithm

4.3. Minimum Spanning Tree - Prim Algorithm

Problems	Solutions	Difficulty	Description
1584. Min Cost to Connect All Points	Code	`Medium`	Using Prim Algorithm

Problems	Solutions	Difficulty	Description
1584. Min Cost to Connect All Points	Code	`Medium`	Using Prim Algorithm

4.4. Shortest Path for Weighted Graph - Dijkstra Algorithm

Dijkstra's algorithm: find the shortest path like BFS, but for weighted graphs.
- If all costs are equal, we can use BFS (Level Traversal) instead of Dijkstra's algorithm.

Problems	Solutions	Difficulty	Description
743. Network Delay Time	Code	`Medium`	This is Dijkstra for the directed Graph - Need to take care the adj_list

Searching

Algo Name	Note
Breadth First Search (BFS)	Shortest Path; Closer Nodes
Algo Name	Note
------------------------------------------------------------------------	:-------------------------:
Breadth First Search (BFS)	Shortest Path; Closer Nodes

LeetCode Solutions

Binary Tree

General Tips for Tree:

Learn #1: Search Types
- BFS : While ? Because using Recursion costs additional Space Complexity due to Recusive call in Stack
- DFS : Recursion
- BFS : While ? Because using Recursion costs additional Space Complexity due to Recusive call in Stack
- DFS : Recursion
BFS Pseudo Code:

def bfs(root):
    res = []
    queue = [root]
    while(queue):
        node = queue.pop(0) #pop(0) = dequeue
        if node:
            res.append(node.val)
            queue.append(node.left)
            queue.append(node.right)

DFS Pseudo Code:

def dfs_postOrder(root, res):
    if (root):
        dfs_postOrder(root.left)
        dfs_postOrder(root.right)
        res.append(root.val)

dfs_postOrder(root, [])

Problems	Solutions	Difficulty	Description
98. Validate Binary Search Tree	Code	`Medium`	Recursion: check one by one node to ensure that low < node.val < hight. Why low & high ? because we need to ensure the left and right child to be within the range
100. Same Tree	Code	`Easy`	Recursion: Compare 2 root, then recusively compare both left with left and right with right sub-tree
101. Symmetric Tree	Code	`Easy`	Recursion: Call a recursive function on left and right Sub-trees
104. Maximum Depth of Binary Tree	Code		DFS
107. Binary Tree Level Order Traversal II	Code		BFS + Each Tree Level Traversal
112. Path Sum	Code	`Easy`	Need to check at leaf node, what is the remaining sum
116. Populating Next Right Pointers in Each Node	Code	`Medium`	BFS
543. Diameter of Binary Tree	Code	`Easy`	Need to calculate the left and the right height of the tree, then compare left_height + right_height with the max diameter
700. Search in a Binary Search Tree	Code	`Easy`
701. Insert into a Binary Search Tree	Code	`Medium`	Same concept as Search in BST
Problems	Solutions	Difficulty	Description
------------------------------------------------------------------------------------------	:-------------------------------------------------------------------:	----------	-------------------------------------------------------------------------------------------------------------------------------------------------------------------
98. Validate Binary Search Tree	Code	`Medium`	Recursion: check one by one node to ensure that low < node.val < hight. Why low & high ? because we need to ensure the left and right child to be within the range
100. Same Tree	Code	`Easy`	Recursion: Compare 2 root, then recusively compare both left with left and right with right sub-tree
101. Symmetric Tree	Code	`Easy`	Recursion: Call a recursive function on left and right Sub-trees
104. Maximum Depth of Binary Tree	Code		DFS
107. Binary Tree Level Order Traversal II	Code		BFS + Each Tree Level Traversal
112. Path Sum	Code	`Easy`	Need to check at leaf node, what is the remaining sum
116. Populating Next Right Pointers in Each Node	Code	`Medium`	BFS
543. Diameter of Binary Tree	Code	`Easy`	Need to calculate the left and the right height of the tree, then compare left_height + right_height with the max diameter
700. Search in a Binary Search Tree	Code	`Easy`
701. Insert into a Binary Search Tree	Code	`Medium`	Same concept as Search in BST

617. Merge Two Binary Trees

Learn #1: Using Recursion. Identify the base cases

897. Increasing Order Search Tree

Learn #1: Tracing through the entire tree using Current Node: curr = tree

tree = TreeNode(val = val_list.pop(0))
curr = tree

for i in range(0, len(val_list)):
    val = val_list[i]
    curr.right = TreeNode(val=val)
    curr = curr.right

938. Range Sum of BST

Learn #1: Using the property of BST

if node.val < low:
   queue.append(node.right)
elif node.val > high:
   queue.append(node.left)

1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree

BFS Implementation in Python: using pop(0) for dequeue and append for enqueue

queue = [cloned]
while(queue):
    node = queue.pop(0) #pop(0) = dequeue
    if node:
        if node.val == t:
            return node
        queue.append(node.left)
        queue.append(node.right)

(Back to top)

N ary Tree

590. N-ary Tree Postorder Traversal

Learn #1: DFS expansion for N-ary tree

def dfs_postOrder(root, result):
    if (root):
        for child in root.children:
            dfs_postOrder(child, result)
        result.append(root.val)

Class Design

1603. Design Parking System

Learn #1: How to use Hash Table to look up the value

def __init__(self, big: int, medium: int, small: int):
        self.lots = {3: small, 2: medium, 1: big}

    def addCar(self, carType: int) -> bool:
        lot = self.lots[carType]

Others

(Back to top)

Resources

Data Structure & Algo - TypeScript

(Back to top)

FilesExpand file tree

README_detailed.md

Latest commit

History

README_detailed.md

File metadata and controls

LeetCode Solution

Table of contents

Part A: Data Structure

1. Primitive Types

1.1. KeyNotes

External Library:

1.2. Bitwise Operation:

1.2.1. Bitwise Example

1.2.2. LeetCode Questions:

1.3. Strings and Numbers

1.3.1. find() and rfind()

String Format

1.3.3. String and Number LeetCode Questions

2. Arrays

2.1. Keynotes

2.2. Array Problems

2.2.1. 1D Array

2.2.2. 2D Matrix

3. Linked List

3.1. Keynotes

3.2. Linked List Problems

4. Hash Map

4.1. Keynotes

5. Queue

Part B: Algorithms

1. Recursion

2. Dynamic Programming

3. BFS and DFS

3.1. BFS

3.2. DFS

4. Graph Theory

4.1. Topological Sort

4.2. Minimum Spanning Tree - Kruskal Algorithm

4.3. Minimum Spanning Tree - Prim Algorithm

4.4. Shortest Path for Weighted Graph - Dijkstra Algorithm

Searching

LeetCode Solutions

Binary Tree

General Tips for Tree:

N ary Tree

Class Design

Others

Resources

License