LeetCode Summary

Table of Contents

• LeetCode Summary
  • bebo1010 – python
    • Sorting
    • Graph
    • Tree
    • Stack
    • Heap Queue
    • Miscellany
  • bebo1010 – C++
    • Circular Deque
  • bebo1010 – C
    • Array
    • Bit-wise Operation
  • sushake – c
    • String
    • Graph
    • Sort
    • Top Interview 150

bebo1010 – python

Sorting

One Line Sorting

Sort by another Dictionary

sorted(nums, key = lambda element: key_dict[element])

Sort by Height

[name for name, height in sorted(zip(names, heights), key=lambda item: item[1], reverse=True)]

Sort by Most Profit

difficulty, profit = zip(*sorted(zip(difficulty, profit), key=lambda i: i[1], reverse=True))

Sort by Occurrences then Elements

1636. Sort Array by Increasing Frequency
Sort by occurences in ascending order, then sort by elements themself in descending order

from collections import Counter

occurrences = Counter(nums) # a dict that stores occurrences, {element: occurrence}
sorted(nums, key=lambda element: (occurrences[element], -element))

Radix Sort

912. Sort an Array

2-Based Radix Sort

def counting_sort(arr, exp, min_value):
    n = len(arr)
    output = [0] * n  # Output array
    count = [0] * 2  # Counting array for base 2 (0 and 1)

    # Store count of occurrences in count[]
    for i in range(n):
        index = ((arr[i] - min_value) >> exp) & 1
        count[index] += 1

    # Change count[i] so that count[i] now contains actual
    # position of this digit in output[]
    count[1] += count[0]

    # Build the output array
    i = n - 1
    while i >= 0:
        index = ((arr[i] - min_value) >> exp) & 1
        output[count[index] - 1] = arr[i]
        count[index] -= 1
        i -= 1

    # Copy the output array to arr[], so that arr now
    # contains sorted numbers according to current digit
    for i in range(n):
        arr[i] = output[i]

def radix_sort(arr):
    # Find the minimum and maximum number to know the range
    min_value = min(arr)
    max_num = max(arr) - min_value
    exp = 0
    while (max_num >> exp) > 0:
        counting_sort(arr, exp, min_value)
        exp += 1

Graph

Dijkstra's Algorithm

1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance
Dijkstra's Algorithm Reference

Dijkstra's Algorithm for Directed Graph Implementation

def dijkstra_algorithm(n: int, starting_point: int, edges: List[List[int]]) -> list[int]:
        visited = [False] * n
        cost = [float('inf')] * n
        prev_node = [-1] * n

        cost[starting_point] = 0
        current_point = starting_point

        while not all(visited):
            for edge in edges:
                start, end, edge_cost = edge
                if current_point == start and not visited[end]:
                    new_cost = cost[current_point] + edge_cost
                    if new_cost < cost[end]:
                        cost[end] = new_cost
                        prev_node[end] = start

            visited[current_point] = True

            min_cost = float('inf')
            next_point = -1
            for i in range(n):
                if not visited[i] and cost[i] < min_cost:
                    min_cost = cost[i]
                    next_point = i
            
            if next_point == -1:
                break
            
            current_point = next_point

        return cost

Dijkstra's Algorithm for Undirected Graph Implementation

def dijkstra_algorithm(n: int, starting_point: int, edges: List[List[int]]) -> list[int]:
        visited = [False] * n
        cost = [float('inf')] * n
        prev_node = [-1] * n

        cost[starting_point] = 0
        current_point = starting_point

        bidirectional_edges = edges + [[end, start, edge_cost] for start, end, edge_cost in edges]

        while not all(visited):
            for edge in bidirectional_edges:
                start, end, edge_cost = edge
                if current_point == start and not visited[end]:
                    new_cost = cost[current_point] + edge_cost
                    if new_cost < cost[end]:
                        cost[end] = new_cost
                        prev_node[end] = start

            visited[current_point] = True

            min_cost = float('inf')
            next_point = -1
            for i in range(n):
                if not visited[i] and cost[i] < min_cost:
                    min_cost = cost[i]
                    next_point = i
            
            if next_point == -1:
                break
            
            current_point = next_point

        return cost

Tree

Character Trie

648. Replace Words

Character Trie Implementation

Path of tree is represented by the character, initialize a node per path.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str):
        node = self.root
        for char in word:
            if node.is_end_of_word:
                return
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end_of_word = True

    def search_shortest_prefix(self, word: str) -> str:
        node = self.root
        prefix = ""
        for char in word:
            if char not in node.children:
                break
            prefix += char
            node = node.children[char]
            if node.is_end_of_word:
                return prefix
        return word

Depth First Search

1038. Binary Search Tree to Greater Sum Tree

Reverse In-order Depth First Search Implementation

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
def right_first_dfs(self, current_node: TreeNode):
    if current_node is None:
        return
    self.right_first_dfs(current_node.right)

    self.current_sum += current_node.val
    current_node.val = self.current_sum

    self.right_first_dfs(current_node.left)

1110. Delete Nodes And Return Forest

Post-order Depth First Search Implementation

def depth_first_post_order(self, root: TreeNode, delete_flag: bool):
    if root is None:
        return None

    if root.val in self.to_delete_set:
        to_be_deleted = True
    else:
        to_be_deleted = False

    root.left = self.depth_first_post_order(root.left, to_be_deleted)
    root.right = self.depth_first_post_order(root.right, to_be_deleted)

    if not to_be_deleted and delete_flag:
        self.root_list.append(root)

    if to_be_deleted:
        return None
    else:
        return root

1382. Balance a Binary Search Tree

In-order Depth First Travesal Implementation

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
def in_order_traversal(self, current_node: TreeNode):
    if current_node == None:
        return None

    self.in_order_traversal(current_node.left)
    self.values.append(current_node.val)
    self.in_order_traversal(current_node.right)

Build Balanced Binary Search Tree from Array Implementation

def build_balanced_BST(self, values: list) -> TreeNode:
    if len(values) == 0:
        return None
    mid_point = int(len(values) >> 1)
    root = TreeNode(values[mid_point])

    root.left = self.build_balanced_BST(values[:mid_point])
    root.right = self.build_balanced_BST(values[mid_point+1:])

    return root

Stack

Find Score by Removing Substring

1717. Maximum Score From Removing Substrings

Remove Substring using Stack Implementation

def find_ab_scores(self, s: str, score: int) -> [str, int]:
    partial_score = 0
    stack = []

    for c in s:
        if c != 'b':
            stack.append(c)
        else:
            if len(stack) > 0:
                if stack[-1] == 'a':
                    print("added x")
                    partial_score += score
                    stack.pop()
                else:
                    stack.append(c)
            else:
                stack.append(c)

    # stack.reverse()
    return "".join(stack), partial_score

Heap Queue

703. Kth Largest Element in a Stream
Python Heap Queue Algorithm Document

Heap Queue Details

Initialize the heap with a empty list x = [] or convert a list with heapq.heapify(x)
heap[0] is the smallest item in the heap.

• heapq.heappush(heap, item)
  Push the value item onto the heap
• heapq.heappop(heap)
  Pop the smallest item from the heap
  If the heap is empty, IndexError is raised
  To access the smallest item without popping it, use heap[0]
• heapq.heappushpop(heap, item)
  Push the value item onto the heap, then pop and return the smallest item from the heap
  More efficient than heapq.heappush() then heapq.heappop()
• heapq.heapreplace(heap, item)
  Pop and return the smallest item from the heap, then push the value item onto the heap
  If the heap is empty, IndexError is raised
  More efficient than heapq.heappop() then heapq.heappush()

Heap elements can also be tuples.

>>> h = []
>>> heappush(h, (5, 'write code'))
>>> heappush(h, (7, 'release product'))
>>> heappush(h, (1, 'write spec'))
>>> heappush(h, (3, 'create tests'))
>>> heappop(h)
(1, 'write spec')

Example for Heap Sort

def heapsort(iterable):
    h = []
    for value in iterable:
        heappush(h, value)
    return [heappop(h) for i in range(len(h))]

...

>>> heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Miscellany

Pascal Triangle

118. Pascal's Triangle

Pascal Triangle Implementation

def generate(numRows: int) -> List[List[int]]:
        full_triangle = [[1]] # base case
        for row in range(2, numRows + 1):
            prev_row = full_triangle[row - 2]
            current_row = []
            middle_point = row >> 1
            element = 1
            for index in range(middle_point):
                if index == 0:
                    current_row.insert(0, 1)
                    current_row.insert(-1, 1)
                else:
                    element = prev_row[index - 1] + prev_row[index]
                    current_row.insert(index, element)
                    current_row.insert(-index, element)
            if row & 0x01 == 1:
                element = prev_row[middle_point - 1] + prev_row[middle_point]
                current_row.insert(middle_point, element)

            full_triangle.append(current_row)

        return full_triangle

Modulo Sums

523. Continuous Subarray Sum

Modulo Sums Explanation

The sum of any array can be rewritten as follow:

$\text{sum}(:j)=\text{sum}(:i)+\text{sum}(i:j)$ for all

$i<j$

For a subarray with size greater than 1 to exist such that the sum of its elements is divisivble by k,

$\text{sum}(i:j)\mathrm{\%}k$ must equal to 0 for some

$i<j-1$, the reason for

$j-1$ is because the length of subarray must be greater than or equal to 2

If we modules both sides of the above equation:

$\text{sum}(:j)\mathrm{\%}k=[\text{sum}(:i)+\text{sum}(i:j)]\mathrm{\%}k$

$\Rightarrow \text{sum}(:j)\mathrm{\%}k=[\text{sum}(:i)\mathrm{\%}k+\text{sum}(i:j)\mathrm{\%}k]\mathrm{\%}k$

$\Rightarrow \text{sum}(:j)\mathrm{\%}k=\text{sum}(:i)\mathrm{\%}k$

Find the

$i$ and

$j$ that satisfy this condition

Sliding Window

2134. Minimum Swaps to Group All 1's Together II

Techniques for using Sliding Window on Circular Array

Assume the window size is sliding_window_size.

1. Use modulation to calculate index, quite slow

nums = [1, 2, 3]
sliding_window_size = 2

for i in range(0, len(appended_nums) - k + 1):
    subarray = [nums[(i + j) % len(nums)] for j in range(sliding_window_size)]
    ...

2. Append the first k elements to the end of array, faster

nums = [1, 2, 3]
sliding_window_size = 2
appended_nums = nums + nums[:sliding_window_size]

for i in range(0, len(appended_nums) - sliding_window_size + 1):
    subarray = appended_nums[i:i + sliding_window_size]
    ...

Split String into Chunks

273. Integer to English Words
Split the numbers from least significant digits into chunks

Spliting Implementation

def split_into_chunks(number, chunk_size=3):
        str_number = str(number)[::-1]
        chunks = [str_number[i:i+chunk_size] for i in range(0, len(str_number), chunk_size)]
        chunks = [chunk[::-1] for chunk in chunks]
        return chunks

Factorization

650. 2 Keys Keyboard

How can this problem be reduced into a factorization problem?

Factorization Implementation

The first part check if n is 1 (special case).
The second part check the multiple of 2.
The third part check other prime factors.
The last part is when the remaining of n is a prime factor, add it to the list.

def get_prime_factors(n: int) -> list:
    if n == 1:
        return [1]
    
    factors = []

    while n % 2 == 0:
        factors.append(2)
        n //= 2

    for i in range(3, int(n**0.5) + 1, 2):
        while n % i == 0:
            factors.append(i)
            n //= i

    if n > 2:
        factors.append(n)

    return factors

Leetcode Editorial

class Solution:
    def minSteps(self, n: int) -> int:
        if n == 1:
            return 0
        self.n = n

        self.memo = [[0] * (n // 2 + 1) for _ in range(n + 1)]
        return 1 + self._min_steps_helper(1, 1)

    def _min_steps_helper(self, curr_len: int, paste_len: int) -> int:
        if curr_len == self.n:
            return 0
        if curr_len > self.n:
            return 1000

        # return result if it has been calculated already
        if self.memo[curr_len][paste_len] != 0:
            return self.memo[curr_len][paste_len]

        opt1 = 1 + self._min_steps_helper(curr_len + paste_len, paste_len)
        opt2 = 2 + self._min_steps_helper(curr_len * 2, curr_len)
        self.memo[curr_len][paste_len] = min(opt1, opt2)
        return self.memo[curr_len][paste_len]

Bit-Wise Complement

476. Number Complement

Bit-by-Bit Complement

1. Get the binary representation (in str) of original number num by bin().
2. Complement the bits.

The return value of bin() would contain 0b in them.
For example bin(5) returns 0b101

$O(n)$ solution where

$n$ is the number of bits used to represent the number

def findComplement(self, num: int) -> int:
    new_str = "0b"
    binary_string = bin(num)
    for bit_index in range(2, len(binary_string)):
        bit = binary_string[bit_index]
        new_str += "0" if bit == "1" else "1"

    return int(new_str, 2)

Complement with Exclusive OR

1. Get the bit length of original number num by bit_length().
2. Generate the mask.
3. Complement the number with the mask and XOR operation.

The return value of bit_length() is the number of bits used to represent the number.
For example bin(5) returns 3 (0b101 takes 3 bits to represent).

$O(log(n))$ solution where

$n$ is the number of bits used to represent the number

def findComplement(self, num: int) -> int:
    bit_length = num.bit_length()

    mask = (1 << bit_length) - 1

    return num ^ mask

Greatest Common Divisor

2807. Insert Greatest Common Divisors in Linked List
Euclidean Algorithm

Find GCD with Euclidean Algorithm Implementation

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

bebo1010 – C++

Circular Deque

641. Design Circular Deque

Circular Deque Implementation

start_index and end_index are the indices that's ready for the next insertion.
Thus having to recalculate index again when trying to getFront() and getRear().

class MyCircularDeque {
public:
    MyCircularDeque(int k) : max_length(k){
        deque.resize(k, -1);
    }
    
    bool insertFront(int value) {
        if(deque_length == max_length){
            return false;
        }

        deque[start_index] = value;
        start_index = (start_index - 1 + max_length) % max_length;
        deque_length++;
        return true;
    }
    
    bool insertLast(int value) {
        if(deque_length == max_length){
            return false;
        }

        deque[end_index] = value;
        end_index = (end_index + 1) % max_length;
        deque_length++;
        return true;
    }
    
    bool deleteFront() {
        if(deque_length == 0){
            return false;
        }

        start_index = (start_index + 1) % max_length;
        deque[start_index] = -1;
        deque_length--;
        return true;
    }
    
    bool deleteLast() {
        if(deque_length == 0){
            return false;
        }

        end_index = (end_index - 1 + max_length) % max_length;
        deque[end_index] = -1;  
        deque_length--;
        return true;
    }
    
    int getFront() {
        if(deque_length == 0){
            return -1;
        }

        int front_index = (start_index + 1) % max_length;
        return deque[front_index];
    }
    
    int getRear() {
        if(deque_length == 0){
            return -1;
        }
    
        int rear_index = (end_index - 1 + max_length) % max_length;
        return deque[rear_index];
    }
    
    bool isEmpty() {
        return deque_length == 0;
    }
    
    bool isFull() {
        return deque_length == max_length;
    }

private:
    vector<int> deque; 
    const int max_length;
    int deque_length = 0;
    int start_index = 0;
    int end_index = 1;
};

/**
 * Your MyCircularDeque object will be instantiated and called as such:
 * MyCircularDeque* obj = new MyCircularDeque(k);
 * bool param_1 = obj->insertFront(value);
 * bool param_2 = obj->insertLast(value);
 * bool param_3 = obj->deleteFront();
 * bool param_4 = obj->deleteLast();
 * int param_5 = obj->getFront();
 * int param_6 = obj->getRear();
 * bool param_7 = obj->isEmpty();
 * bool param_8 = obj->isFull();
 */

bebo1010 – C

Array

Binary Search

1331. Rank Transform of an Array
Using basic Linear Search would trigger TLE at this question.
Use Binary Search instead.

Binary Search Implementation

int binary_search(int element, int *array, int array_length){
    int left_index = 0;
    int right_index = array_length;
    int middle_index;

    while(left_index < right_index){
        middle_index = left_index + (right_index - left_index) / 2;
        if(element == array[middle_index]){
            return middle_index;
        }
        else if(element > array[middle_index]){
            left_index = middle_index;
        }
        else{
            right_index = middle_index;
        }
    }
    return -1;
}

Bit-wise Operation

Remove first set bit from least significant bit

x = x & (x - 1);

This can be used to get how many set bits are in a number, for example:

count = 0;
while(x > 0){
    count++;
    x = x & (x - 1);
}

sushake – c

String

string to array

char array1[] = source;
char* array2 = target;

//find length
int length = strlen(source);

Graph

Dijkstra's Algorithm

1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance

• Dijkstra's Algorithm Reference

Dijkstra's Algorithm for Undirected Graph Implementation

int dijkstra(int** table, int start, int n) {

    int* distance = (int*)malloc(sizeof(int) * n);
    for(int i = 0; i < n; i++) 
            distance[i] = stable[start][i];
    
    int* book = (int*)malloc(sizeof(int) * n);
    memset(book, 0, sizeof(int) * n);
    book[city] = 1;

    for(int i = 0; i < n; i++) {

        int min = INT_MAX;
        int id = -1;
        for(int j = 0; j < n; j++) {
            if(book[j] == 0 && distance[j] < min) {
                min = distance[j];
                id = j;
            }
        }

        if (id == -1)
            break;
        
        book[id] = 1;
        for(int j = 0; j < n; j++) {
            if(book[j] == 0 && table[id][j] != INT_MAX && distance[j] > distance[id] + road[id][j])
                distance[j] = distance[id] + road[id][j];
        }    
    }
}

• 2976. Minimum Cost to Convert String I
  這題會有時間限制,我的策略為將所有 distance 儲存在 26*26 表格裡，這樣就不會有重複找的問題。這題有個噁心點: 他給的 cost 有重複的，需判斷哪個比較小。

Sort

quicksort

quicksort in C library

/* The comparison function must return an integer less than, 
 * equal to, or greater than zero if the first argument is 
 * considered to be respectively less than, equal to, or greater 
 * than the second. If two members compare as equal, their 
 * order in the sorted array is undefined. */
int cmpfunc (const void * a, const void * b)
{
   return ( *(int*)a - *(int*)b );
}
int cmpstring(const void *p1, const void *p2)
{
   /* The actual arguments to this function are "pointers to
      pointers to char", but strcmp(3) arguments are "pointers
      to char", hence the following cast plus dereference */

   return strcmp(* (char * const *) p1, * (char * const *) p2);
}
qsort(array, arraySize, sizeof(int), cmpfunc);

Top Interview 150

Array / String

• 88. Merge Sorted Array
  因為答案會儲存在 array1 當中，所以節省記憶體空間的方法為從尾端開始填數字。
• 26. Remove Duplicates from Sorted Array

In-place algorithm

int removeDuplicates(int* nums, int numsSize) {
    
    int i = 0;
    int j = 0;
    while(i < numsSize) {

        int val = nums[i];
        j +=1;
        while(j < numsSize && nums[j] == val) {
            j += 1;
        }
        i +=1;
        if(j < numsSize)
            nums[i] = nums[j];  
        else
            break;  
    }
    return i;
}

• 55. Jump Game
  這題我是參照他人的解法
• 12. Integer to Roman
  這題本來很笨的用 if 迴圈慢慢把 string 找出來，chatGPT 最後整理的程式碼，供參。順便紀錄怎麼增加 string 元素(strcat)。

string add item

char* intToRoman(int num) {
    
    const char* roman_numerals[] = {
        "M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
    const int values[] = {
        1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};

    char* output = (char*)malloc(20);
    output[0] = '\0'; 

    int i = 0;
    while (num > 0) {
        while (num >= values[i]) {
            strcat(output, roman_numerals[i]);
            num -= values[i];
        }
        i++;
    }

    return output;
}

• 14. Longest Common Prefix
  紀錄如何使用 strcpy 以及 strncpy ，詳細可參考這篇文章講述差異性

string copy item

char* longestCommonPrefix(char** strs, int strsSize) {
    
    if(strsSize == 0)
        return "";

    char* output = strs[0];
    int length = strlen(output);
    for(int i = 1; i < strsSize; i++){

        char* word = strs[i];
        int len = strlen(word);
        for(int j = 0; j < length; j++){
            if(len == 0 || output[j] != word[j]){
                length = j;
                break;
            }
            len--;
        }

        if(length == 0)
            return "";   
    }

    char* final = (char*)malloc(sizeof(char) * (length + 1));
    strncpy(final, output, length);
    final[length] = '\0'; //這個要自己加!!!
    return final;
}

Two Pointers

• 15. 3Sum

這題很重要，要會!!!
這題我是看解答的，思路如下。
先從小到大排列，第一個迴圈用來固定第一個變數，這樣就是 2sum 的題目。
再來將第二個變數設為第一個變數位置加一，第三個變數位置設為佇列尾端，然後將三數相加跟零做比較 :
比零大表示第三個變數太大，往左移；比零小表示第二個變數太小，往右移。

學起來如何使用 qsort

int cmpfunc (const void * a, const void * b)
{
   return ( *(int*)a - *(int*)b );
}
int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
    
    qsort(nums, numsSize, sizeof(int), cmpfunc);

    *returnSize = 0;
    int** output = (int**)malloc(sizeof(int*) * (numsSize * numsSize));
    
    for(int i = 0; i < numsSize - 2; i++) {

        if (i > 0 && nums[i] == nums[i - 1]) continue;//skip duplicate

        int second = i + 1;
        int third = numsSize - 1;
        while(second < third) {

            int count = nums[i] + nums[second] + nums[third];
            if(count == 0) {
                output[*returnSize] = (int*)malloc(sizeof(int) * 3);
                output[*returnSize][0] = nums[i];
                output[*returnSize][1] = nums[second];
                output[*returnSize][2] = nums[third];
                (*returnSize) += 1;

                // Skip duplicate 'left' and 'right' values
                while (second < third && nums[second] == nums[second + 1]) second++;
                while (second < third && nums[third] == nums[third - 1]) third--;

                second++;
                third--;
            }else if(count > 0)
                third --;
            else   
                second++;
        }
    }
    *returnColumnSizes = (int*)malloc(sizeof(int) * (*returnSize));
    for (int i = 0; i < *returnSize; i++) {
        (*returnColumnSizes)[i] = 3;
    }
    
    return output;
}

• 3. Longest Substring Without Repeating Characters
  這題有個重點，s consists of English letters, digits, symbols and spaces.
  所以標點符號跟空白都需要包含。根據 ASCII 可顯示字元編號範圍是32-126（0x20-0x7E），共95個字元。