[Notes] Leetcode Codebooks

Posted on October 30, 2022 in Coding Job Hunting

This is the notebook for Leetcode problems. The problems are categorized into different types, and tricks are summarized for each type so that they can be looked up quickly like in a toolbox. The primary language is C++ or rust, as I am practicing system programming.

Basic Data Structure

Basic structure:
- Core: continuous array, linked list (pointers to pointers)
- Operations: exhaustive traversal (tree, dynamic programming, back tracing) + insert/delete/update.
Tree problems:
- Option 1: traversal (recursive while updating global status)
- Option 2: divide and conquer (still recursive, but with return value)
- Generalization and traversal orders:
  - DFS/BFS are graph-level search/traversal. DFS can produce same result as pre-order. BFS is level-order traversal
  - pre-order/in-order/post-order traversal (is special case of DFS in BT)
  - DFS can be used to calc DAG topological order

// traversal template
void traverse(TreeNode* root) {
	if (root == nullptr) return;
	// pre-order ...
	traverse(root->left);
	// in-order ...
	traverse(root->right);
	// post-order ...
}


// sub-problem template (divide and conquer)
int tree_max_depth(TreeNode* root) {
	if (root == nullptr) return 0;
	int left = tree_max_depth(root->left);
	int right = tree_max_depth(root->right);
	return max(left, right) + 1;
}

Priority Queue (PQ): a generate interface which is usually implemented as a binary heap (i.e., a binary tree structure where every node’s value is greater/equal to its subtree node’s value)
- Not getting confused with the stack/heap memory (e.g., function call stack, dynamically allocated memory regions) versus the stack/heap data structures.

#include <queue>

// Max priority queue (popping the max in O(logN))
std::priority_queue<int> q1; 
for (int i = 0; i < 10; i++) q1.push(i);
while (!pq.empty()) {
    std::cout << pq.top() << ' ';
    pq.pop();
}

// Min priority queue
std::priority_queue<int, std::vector<int>, std::greater<int>> q2; 
std::priority_queue q3(data.begin(), data.end(), std::greater<int>());  

// Max PQ with custom object container
auto custom_comparator = [](const custom_obj& a, const custom_obj& b) {
	return a.val < b.val;
};
std::proirity_queue<obj, std::vector<obj>, decltype(custom_comparator)> q4;

Double Pointers

Linked List Double Pointers

[LC21] Merging two ascending ordered linked list.
- Insert a dummy initial node, as we always deciding on the next pointer
- [LC86] Decomposing a linked list into two lists based on a threshold value.
- [LC23] Merging K lists: use a priority queue to keep track of the smallest node in each list.

struct ListNode {
	int val;
	ListNode* next;
	ListNode(int x) : val(x), next(nullptr) {}
};

ListNode* listMerger(ListNode* p1, ListNode* p2) {
	ListNode dummy(0);
	ListNode* tail = &dummy;
	while (p1 != nullptr && p2 != nullptr) {
		if (p1->val < p2->val) {
			tail->next = p1;
			p1 = p1->next; // move p1 forward
		} else {
			tail->next = p2;
			p2 = p2->next; // move p2 forward
		}
		tail = tail->next;
	}
	tail->next = p1 != nullptr ? p1 : p2;
	return dummy.next;
}

Use two forward moving pointers
- [LC19] Delete K-th element in the linked list from end: two pointers are spaced out with a distance of K nodes. When the first pointer reaches the end, the second pointer is at the K-th node from end (N-K)
- [LC876] Find the middle node of a linked list: two pointers are spaced out with different speeds
- [LC141] Find the cycle in a linked list: two pointers are spaced out with different speeds. If there is a cycle, the two pointers will meet at some point.


void FindCycleStartPoint(LinkedList* head) {
	LinkedList* slow = head;
	LinkedList* fast = head;
	while (fast != nullptr && fast->next != nullptr) {
		slow = slow->next;
		fast = fast->next->next;
		if (slow == fast) break;
	}
	if (fast == nullptr || fast->next == nullptr) return nullptr; // no cycle

	// find the start point of the cycle. assume distance between start and meeting point is m
	// it only takes another (k-m) steps for the slow pointer to reach the start point
	slow = head;
	while (slow != fast) {
		slow = slow->next;
		fast = fast->next;
	}
	return slow;
}

Array Double Pointers

Fast-Slow pointers
- [LC26] In-place remove duplicates in a sorted array: fast pointer is always ahead of slow pointer, and only moves when the value is different from the slow pointer.
- [LC27] In-place remove all instances of a value in an array
- [LC283] In-place move zeros to the end of the array


void removeDuplicates(vector<int>& nums) {
	if (nums.empty()) return 0;
	int slow = 0;
	while (fast < nums.size()) {
		fast++;
		if (nums[fast] != nums[slow]) {
			slow++;
			nums[slow] = nums[fast];
		}
	}
	return slow + 1;
}

Left-Right pointers
- Binary search in a sorted array
- [LC167] Two sum in a sorted array
- [LC344] Reverse a string
- [LC5] Longest palindromic substring

// pointers from middle to both ends
string PalindromeAt(string s, int left, int right) {
	while (left >= 0 && right < s.size() && s[left] == s[right]) {
		left--;
		right++;
	}
	return s.substr(left + 1, right - left - 1);
}

// Scan palindromes from start to end
string longestPalindrome(string s) {
	if (s.empty()) return "";
	string res = s.substr(0, 1);
	for (int i = 0; i < s.size() - 1; i++) {
		string p1 = PalindromeAt(s, i, i);
		string p2 = PalindromeAt(s, i, i + 1);
		if (p1.size() > res.size()) res = p1;
		if (p2.size() > res.size()) res = p2;
	}
	return res;
}

C++ Basics

struct and class: pretty much the same except that struct has default public access modifier, while class has default private access modifier, and only class can be used as a typename to declare a template parameter.

// NB: typedef a template not allowed: https://stackoverflow.com/a/2448307
template <typename T> // only class can be used as typename
struct array { 
  size_t x; 
  T *ary; 
};