Algorithm Problem Notes

· 30 min read · 6236 words

C++ Data Structure Usage

Universal header:

#include <bits/stdc++.h>

std::list::splice

In C++, the std::list and std::forward_list containers provide a member function called splice. This function transfers elements from one list to another in constant time, without copying or moving elements — it simply updates node pointers. This makes splice particularly efficient when reorganizing list elements without introducing additional performance overhead.

std::list::splice has several overloads:

  1. Transfer the entire list to another position:

    cpp
Copy code
void splice(const_iterator pos, list& other);

    Transfers all elements from other to the position before pos in the calling list. After the operation, other is empty.

  2. Transfer a single element from another list to a specified position:

    cpp
Copy code
void splice(const_iterator pos, list& other, const_iterator it);

    Transfers only the element pointed to by iterator it in other to the position before pos in the calling list.

  3. Transfer a range of elements from another list to a specified position:

    cpp
Copy code
void splice(const_iterator pos, list& other, const_iterator first, const_iterator last);

    Transfers elements in the range [first, last) from other to the position before pos in the calling list.

The C++ standard library provides several binary search functions, all defined in the <algorithm> header. These functions require the range to be sorted. The commonly used binary search functions are:

  1. std::binary_search:
    • Checks whether a given value exists in a sorted sequence.
    • Prototype: bool binary_search(ForwardIt first, ForwardIt last, const T& value)
    • Returns true if the element is found, false otherwise.
  2. std::lower_bound:
    • Finds the first element in a range that is not less than (≥) a given value.
    • Prototype: ForwardIt lower_bound(ForwardIt first, ForwardIt last, const T& value)
    • Returns an iterator to the found element. Returns last if all elements are less than the given value.
  3. std::upper_bound:
    • Finds the first element greater than a specified value.
    • Prototype: ForwardIt upper_bound(ForwardIt first, ForwardIt last, const T& value)
    • Returns an iterator to the first element greater than the specified value. Returns last if no such element exists.
  4. std::equal_range:
    • Returns both lower_bound and upper_bound results simultaneously.
    • Prototype: pair<ForwardIt, ForwardIt> equal_range(ForwardIt first, ForwardIt last, const T& value)
    • Returns a pair of iterators: the first points to the first element not less than the given value, and the second points to the first element greater than the given value.

Lambda Expressions

The basic syntax of a lambda expression is:

cppCopy code[ capture_clause ] ( parameters ) -> return_type {
    function_body
}
  • capture_clause: The capture list, defining access to variables from the enclosing scope. Variables can be captured by value or by reference.
  • parameters: The parameter list, same as for regular functions. Can be omitted or left empty () if there are no parameters.
  • return_type: The return type. In most cases, the return type of a lambda can be automatically deduced, and -> return_type can be omitted.
  • function_body: The body of the lambda expression.

Capture Modes

  • [ ]: No external variables are captured.
  • [=]: All variables in the enclosing scope are captured by value.
  • [&]: All variables in the enclosing scope are captured by reference.
  • [var]: Captures a single variable var by value.
  • [&var]: Captures a single variable var by reference.
  • [=, &var]: Captures all external variables by value, except var which is captured by reference.
  • [&, var]: Captures all external variables by reference, except var which is captured by value.

Extracting Substrings

In C++, you can use the substr member function of the std::string class to extract a substring.

substr Function Prototype

cppCopy code
string substr(size_t pos = 0, size_t len = npos) const;
  • pos: A size_t value indicating the starting position of the substring, default is 0.
  • len: A size_t value indicating the length of the substring. The default value npos means until the end of the string.

Linked Lists & Arrays

Maximum Number of Tasks You Can Assign

You have n tasks and m workers. Each task requires a certain amount of strength to complete, stored in a 0-indexed integer array tasks, where the i-th task requires tasks[i] strength. Each worker’s strength is stored in a 0-indexed integer array workers, where the j-th worker has strength workers[j]. Each worker can complete at most one task, and their strength must be greater than or equal to the task’s requirement (workers[j] >= tasks[i]).

Additionally, you have pills magic pills, each of which can increase one worker’s strength by strength. You can decide which workers to give pills to, but each worker can use at most one pill.

Given tasks, workers, pills, and strength, return the maximum number of tasks that can be completed.

Reference:

https://leetcode.cn/problems/maximum-number-of-tasks-you-can-assign/solutions/1101831/ni-ke-yi-an-pai-de-zui-duo-ren-wu-shu-mu-p7dm/?envType=study-plan-v2&envId=2024-spring-sprint-100

Binary search + greedy worker selection.

To check if k tasks can be completed: take the k smallest tasks and the k strongest workers. Iterate tasks from largest to smallest — if the strongest worker (or the weakest pill-boosted worker) can complete the task, remove that worker and continue; otherwise, it’s impossible.

Binary search for the maximum feasible k.

class Solution {
public:
    int maxTaskAssign(vector<int>& tasks, vector<int>& workers, int pills, int strength) {
        int m=tasks.size(), n=workers.size();
        sort(tasks.begin(), tasks.end());
        sort(workers.begin(), workers.end());

        int up=min(m, n), l=0, r=up;
        while(l<=r) {
            int mid=l+(r-l)/2;
            if(ifCanFinish(tasks, workers, pills, strength, mid)) {
                l=mid+1;
            }
            else {
                r=mid-1;
            }
        }

        return l-1;
    }
private:
    bool ifCanFinish(vector<int>& tasks, vector<int>& workers, int pills, int strength, int taskNum) {
        if(taskNum==0) return true;
        int m=tasks.size(), n=workers.size();
        multiset<int> ws;
        for(int i=n-1; i>=n-taskNum; --i) ws.insert(workers[i]);

        for(int i=taskNum-1; i>=0; --i) {
            int curTask=tasks[i];
            if(*prev(ws.end())>=curTask) ws.erase(prev(ws.end()));
            else {
                if(pills==0) return false;
                auto it=ws.lower_bound(curTask-strength);
                if(it==ws.end()) return false;
                --pills;
                ws.erase(it);
            }
        }
        return true;
    }
};

Optimization: use a deque to maintain pill-eligible workers instead of searching the ordered set.

Count of Smaller Numbers After Self

Given an integer array nums, return a new array counts where counts[i] is the number of elements to the right of nums[i] that are smaller than nums[i].

Data structure: Binary Indexed Tree (Fenwick Tree), supports both insertion and range query in O(log N) time.

Parent of node i: i + LowestBit(i)

Left sibling of node i: i - LowestBit(i)

References:

https://leetcode.cn/problems/count-of-smaller-numbers-after-self/solutions/324892/ji-suan-you-ce-xiao-yu-dang-qian-yuan-su-de-ge-s-7/?envType=study-plan-v2&envId=2024-spring-sprint-100

https://blog.csdn.net/TheWayForDream/article/details/118436732

class Solution {
public:
    vector<int> countSmaller(vector<int>& nums) {
        vector<int> ans(nums.size());
        vector<int> a;

        a.assign(nums.begin(), nums.end());
        sort(a.begin(), a.end());
        a.erase(unique(a.begin(), a.end()), a.end());

        vector<int> c(a.size()+1, 0);
        for(int i=(int)nums.size()-1; i>=0; --i) {
            int id = lower_bound(a.begin(), a.end(), nums[i]) - a.begin() + 1;
            int curAns=0, curId=id-1;
            while(curId>0) {
                curAns += c[curId];
                curId -= lowestBit(curId);
            }
            ans[i] = curAns;

            curId = id;
            while(curId<c.size()) {
                c[curId] += 1;
                curId += lowestBit(curId);
            }
        }

        return ans;
    }
private:
    int lowestBit(int num) {
        return num & (-num);
    }
};

Alternative: merge sort.

Deduplication trick: sort by index.

Smallest Range Covering Elements from K Lists

You have k non-decreasing sorted integer lists. Find the smallest range [a, b] such that each of the k lists contains at least one number within the range.

A range [a, b] is considered smaller than [c, d] if b - a < d - c, or if b - a == d - c and a < c.

Greedy + min-heap: for the minimum of the selected k elements, the other k-1 values are the first elements in their respective lists that are greater than this minimum (greedy choice).

class Solution {
public:
    vector<int> smallestRange(vector<vector<int>>& nums) {
        int k=nums.size();
        vector<int> ans(2, 0);
        if(k==0) return ans;

        vector<int> ptrs(k, 0);
        priority_queue<int, vector<int>, greater<int>> pq;
        int maxNum=INT_MIN;
        for(int i=0; i<k; ++i) {
            maxNum = max(maxNum, nums[i][ptrs[i]]);
            pq.push(nums[i][ptrs[i]]);
        }
        ans[0]=pq.top();
        ans[1]=maxNum;

        while(true) {
            int tmp=pq.top();
            while(!pq.empty() && pq.top()==tmp) pq.pop();
            
            bool endC=false;
            for(int i=0; i<k; ++i) {
                if(nums[i][ptrs[i]]==tmp) {
                    ptrs[i]++;
                    if(ptrs[i]>=nums[i].size()) {
                        endC=true;
                        break;
                    }
                    maxNum = max(maxNum, nums[i][ptrs[i]]);
                    pq.push(nums[i][ptrs[i]]);
                }
            }
            if(endC) break;

            int minNum=pq.top();
            if(maxNum-minNum<ans[1]-ans[0]) {
                ans={minNum, maxNum};
            }
        }

        return ans;
    }
};

Improvement: store array indices in the min-heap to eliminate the inner loop:

class Solution {
public:
    vector<int> smallestRange(vector<vector<int>>& nums) {
        int rangeLeft = 0, rangeRight = INT_MAX;
        int size = nums.size();
        vector<int> next(size);
        
        auto cmp = [&](const int& u, const int& v) {
            return nums[u][next[u]] > nums[v][next[v]];
        };
        priority_queue<int, vector<int>, decltype(cmp)> pq(cmp);
        int minValue = 0, maxValue = INT_MIN;
        for (int i = 0; i < size; ++i) {
            pq.emplace(i);
            maxValue = max(maxValue, nums[i][0]);
        }

        while (true) {
            int row = pq.top();
            pq.pop();
            minValue = nums[row][next[row]];
            if (maxValue - minValue < rangeRight - rangeLeft) {
                rangeLeft = minValue;
                rangeRight = maxValue;
            }
            if (next[row] == nums[row].size() - 1) {
                break;
            }
            ++next[row];
            maxValue = max(maxValue, nums[row][next[row]]);
            pq.emplace(row);
        }

        return {rangeLeft, rangeRight};
    }
};

Contains Duplicate II

Given an integer array nums and an integer k, return true if there exist two distinct indices i and j such that nums[i] == nums[j] and abs(i - j) <= k.

Sliding window + hash set — an elegant solution.

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_map<int, int> um;
        for(int i=0; i<nums.size(); ++i) {
            if(um.find(nums[i])!=um.end() && i-um[nums[i]]<=k) return true;
            um[nums[i]]=i;
        }

        return false;
    }
};

Minimum Size Subarray Sum

Given an array of n positive integers and a positive integer target, find the minimal length contiguous subarray

[numsl, numsl+1, ..., numsr-1, numsr] whose sum is greater than or equal to target, and return its length. Return 0 if no such subarray exists.

Sliding window approach:

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int n = nums.size();
        if (n == 0) {
            return 0;
        }
        int ans = INT_MAX;
        int start = 0, end = 0;
        int sum = 0;
        while (end < n) {
            sum += nums[end];
            while (sum >= s) {
                ans = min(ans, end - start + 1);
                sum -= nums[start];
                start++;
            }
            end++;
        }
        return ans == INT_MAX ? 0 : ans;
    }
};

Intersection of Two Linked Lists

Given the heads of two singly linked lists headA and headB, return the node at which they intersect. Return null if no intersection exists.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *p1=headA, *p2=headB;
        while(p1!=p2) {
            p1 = p1? p1->next : headB;
            p2 = p2? p2->next : headA;
        }
        return p1;
    }
};

Rotate String

class Solution {
public:
    string dynamicPassword(string password, int target) {
        return password.substr(target, password.size()) + password.substr(0, target);
    }
};

Three-reversal method:

class Solution {
public:
    void reverse(vector<int>& nums, int start, int end) {
        while (start < end) {
            swap(nums[start], nums[end]);
            start += 1;
            end -= 1;
        }
    }

    void rotate(vector<int>& nums, int k) {
        k %= nums.size();
        reverse(nums, 0, nums.size() - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.size() - 1);
    }
};

String to Integer (atoi)

Implement the myAtoi(string s) function that converts a string to a 32-bit signed integer (similar to C/C++’s atoi function).

The algorithm for myAtoi(string s) is:

  1. Read and discard leading whitespace.
  2. Check whether the next character (if not at the end) is '+' or '-', and read it if present to determine the sign. Assume positive if neither is present.
  3. Read the next characters until a non-digit character or end of input is reached. The rest of the string is ignored.
  4. Convert the digits read in the previous steps to an integer (e.g., "123" → 123, "0032" → 32). Return 0 if no digits were read. Apply the sign from step 2.
  5. If the integer is out of the 32-bit signed integer range [−2^31, 2^31 − 1], clamp it: values less than −2^31 become −2^31, values greater than 2^31 − 1 become 2^31 − 1.
  6. Return the integer.

Note:

  • Only the space character ' ' is considered whitespace in this problem.
  • Do not ignore any characters other than leading whitespace or characters after the digits.
class Solution {
public:
    int myAtoi(string str) {
        int len=str.size(), i=0;
        int symbol = 1;
        long long ans=0;
        while(str[i]==' ') ++i;
        if(str[i]=='-'){
            symbol = -1;
            ++i;
        }
        else if(str[i]=='+') ++i;
        while(isdigit(str[i])){
            ans = ans*10 + (str[i]-'0');
            if(symbol==1 && ans>INT_MAX) return INT_MAX;
            if(symbol==-1 && -ans<INT_MIN) return INT_MIN;
            ++i;
        }

        return symbol*ans;
    }
};

Copy List with Random Pointer

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(!head) return nullptr;
        Node *cur=head;
        while(cur) {
            Node *copyNode = new Node(cur->val);
            copyNode->next = cur->next;
            cur->next = copyNode;
            cur = copyNode->next;
        }

        Node *ans=head->next;
        cur = head;
        while(cur) {
            cur->next->random = cur->random? cur->random->next : nullptr;
            cur = cur->next->next;
        }

        cur = head;
        Node *copyNode;
        while(cur) {
            copyNode = cur->next;
            cur->next = copyNode->next;
            copyNode->next = copyNode->next? copyNode->next->next:nullptr;
            cur = cur->next;
        }

        return ans;
    }
};

Count Occurrences of a Target Score

Binary search using lower and upper bounds.

class Solution {
public:
    int binarySearch(vector<int>& nums, int target, bool lower) {
        int left = 0, right = (int)nums.size() - 1, ans = (int)nums.size();
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] > target || (lower && nums[mid] >= target)) {
                right = mid - 1;
                ans = mid;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }

    int countTarget(vector<int>& scores, int target) {
        int leftIdx = binarySearch(scores, target, true);
        int rightIdx = binarySearch(scores, target, false) - 1;
        if (leftIdx <= rightIdx && rightIdx < scores.size() && scores[leftIdx] == target && scores[rightIdx] == target) {
            return rightIdx - leftIdx + 1;
        }
        return 0;
    }
};

Roll Call (Missing Number)

A class of n students has IDs ranging from 0 to n-1. The roll call results are recorded in a sorted ascending array records. Exactly one student is absent. Return their ID.

Binary search.

Edge case: the last student is absent.

class Solution {
public:
    int takeAttendance(vector<int>& records) {
        int i = 0, j = records.size() - 1;
        while(i <= j) {
            int m = (i + j) / 2;
            if(records[m] == m) i = m + 1;
            else j = m - 1;
        }
        return i;
    }
};

Minimum cnt Items by Inventory Count

The warehouse manager records inventory in array stock, where stock[i] is the remaining quantity of the i-th item. Return the cnt items with the least inventory (order does not matter).

Quick select + sentinel partitioning:

class Solution {
public:
    vector<int> inventoryManagement(vector<int>& stock, int cnt) {
        if (cnt >= stock.size()) return stock;
        return quickSort(stock, cnt, 0, stock.size() - 1);
    }
private:
    vector<int> quickSort(vector<int>& stock, int cnt, int l, int r) {
        int i = l, j = r;
        while (i < j) {
            while (i < j && stock[j] >= stock[l]) j--;
            while (i < j && stock[i] <= stock[l]) i++;
            swap(stock[i], stock[j]);
        }
        swap(stock[i], stock[l]);
        if (i > cnt) return quickSort(stock, cnt, l, i - 1);
        if (i < cnt) return quickSort(stock, cnt, i + 1, r);
        vector<int> res;
        res.assign(stock.begin(), stock.begin() + cnt);
        return res;
    }
};

Find Median from Data Stream

Using a max-heap and a min-heap.

Pitfall: container.size() returns an unsigned long.

class MedianFinder {
public:
    /** initialize your data structure here. */
    MedianFinder() {
        maxH.push(INT_MIN);
        minH.push(INT_MAX);
    }
    
    void addNum(int num) {
        if(num<=maxH.top()) {
            maxH.push(num);
        }
        else {
            minH.push(num);
        }
        if(maxH.size()>minH.size()+1) {
            minH.push(maxH.top());
            maxH.pop();
        }
        if(minH.size()>maxH.size()+1) {
            maxH.push(minH.top());
            minH.pop();
        }

        return;
    }
    
    double findMedian() {
        if(maxH.size()!=minH.size()) return maxH.size()>minH.size()? maxH.top() : minH.top();
        return (minH.top()+maxH.top())/2.0;

    }
private:
    priority_queue<int> maxH;
    priority_queue<int, vector<int>, greater<int>> minH;
};

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder* obj = new MedianFinder();
 * obj->addNum(num);
 * double param_2 = obj->findMedian();
 */

Artifact Dynasty Validation

An exhibition displays artifacts from 13 dynasties, with each row containing 5 artifacts. The placement in a row is recorded in array places, where places[i] indicates the dynasty number of the i-th artifact. Dynasty 0 represents an unknown dynasty. Determine whether the dynasty numbers in this row are consecutive (unknown dynasties can be treated as any dynasty).

Conditions: no duplicates, and max dynasty − min dynasty < 5.

Using a hash set:

class Solution {
public:
    bool checkDynasty(vector<int>& places) {
        unordered_set<int> repeat;
        int ma = 0, mi = 14;
        for(int place : places) {
            if(place == 0) continue; // skip unknown dynasty
            ma = max(ma, place); // max dynasty number
            mi = min(mi, place); // min dynasty number
            if(repeat.find(place) != repeat.end()) return false; // duplicate found, return false early
            repeat.insert(place); // add dynasty to set
        }
        return ma - mi < 5; // consecutive if max - min < 5
    }
};

File Combination

A file is split into parts and labeled with consecutive positive integers (at least two parts). The transmission requirement is: return all combinations of consecutive file numbers whose sum equals a given target.

Note: each combination must be in ascending order by file number, and combinations must be sorted by their first file number in ascending order.

class Solution {
public:
    vector<vector<int>> fileCombination(int target) {
        int left=1, right=2, tmp=3;
        vector<vector<int>> ans;
        while(left<right) {
            if(tmp<target) tmp+=(++right);
            else if(tmp>target) tmp-=(left++);
            else {
                vector<int> line;
                for(int i=left; i<=right; ++i) {
                    line.push_back(i);
                }
                ans.push_back(line);
                tmp+=(++right);
            }
        }

        return ans;
    }
};

Find K Pairs with Smallest Sums

Custom priority queue:

class Solution {
public:
    vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
        auto cmp = [&nums1, &nums2](const pair<int, int> & a, const pair<int, int> & b) {
            return nums1[a.first] + nums2[a.second] > nums1[b.first] + nums2[b.second];
        };

        int m = nums1.size();
        int n = nums2.size();
        vector<vector<int>> ans;   
        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pq(cmp);
        for (int i = 0; i < min(k, m); i++) {
            pq.emplace(i, 0);
        }
        while (k-- > 0 && !pq.empty()) {
            auto [x, y] = pq.top(); 
            pq.pop();
            ans.emplace_back(initializer_list<int>{nums1[x], nums2[y]});
            if (y + 1 < n) {
                pq.emplace(x, y + 1);
            }
        }

        return ans;
    }
};

Remove Duplicates from Sorted Array II

Given a sorted array nums, remove duplicates in-place such that each element appears at most twice. Return the new length.

Two-pointer approach: the fast pointer may be overwritten by the slow pointer, so a separate variable is needed to track the current duplicate value.

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int cur=0, select=0, count=0, curnum;
        while(cur<nums.size()) {
            if(count==0) {
                nums[select] = nums[cur];
                curnum = nums[cur];
                ++cur;
                ++select;
                ++count;
            }
            else if(count==1) {
                nums[select] = nums[cur];
                if(nums[cur] == curnum) {
                    count++;
                }
                else {
                    curnum = nums[cur];
                }
                ++cur;
                ++select;
            }
            else if(count==2) {
                while(cur<nums.size() && nums[cur]==curnum) ++cur;
                count = 0;
            }
        }
        return select;
    }
};

Sort List

Given the head of a linked list, sort it in ascending order and return the sorted list.

Requirement: O(n log n) time complexity, O(1) space complexity.

Approach: bottom-up merge sort.

Personal implementation:

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if(!head) return nullptr;
        int len = 0;
        ListNode* cur = head;
        while(cur) {
            cur = cur->next;
            ++len;
        }

        int subLen = 1;
        ListNode* dummyHead = new ListNode(-1, head);
        for(;subLen<=len-1; subLen<<=1) {
            ListNode *pre=dummyHead, *a, *b;
            while(pre->next) {
                a = pre->next;
                b = pre->next;
                for(int i=0; i<subLen; ++i) {
                    if(!b) break;
                    b = b->next;
                }
                ListNode *nextN = b;
                for(int i=0; i<subLen; ++i) {
                    if(!nextN) break;
                    nextN = nextN->next;
                }

                int cntA=0, cntB=0;
                for(int i=0; i<2*subLen; ++i) {
                    if(!a && !b || cntA==subLen && !b) break;
                    if(cntA==subLen || (cntB<subLen && b && b->val<a->val)) {
                        pre->next = b;
                        pre = pre->next;
                        b = b->next;
                        cntB++;
                    }
                    else {
                        pre->next = a;
                        pre = pre->next;
                        a = a->next;
                        cntA++;
                    }
                }
                pre->next = nextN;
            }
        }

        return dummyHead->next;
    }
};

Cleaner version using split function:

#include <iostream>

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

// Merge two sublists
ListNode* merge(ListNode* l1, ListNode* l2) {
    ListNode dummyHead(0);
    ListNode* ptr = &dummyHead;
    while (l1 && l2) {
        if (l1->val < l2->val) {
            ptr->next = l1;
            l1 = l1->next;
        } else {
            ptr->next = l2;
            l2 = l2->next;
        }
        ptr = ptr->next;
    }
    ptr->next = l1 ? l1 : l2;
    return dummyHead.next;
}

// Bottom-up merge sort
ListNode* sortList(ListNode* head) {
    if (!head || !head->next) return head;

    // Compute list length
    ListNode* cur = head;
    int length = 0;
    while (cur) {
        length++;
        cur = cur->next;
    }

    ListNode dummyHead(0);
    dummyHead.next = head;
    ListNode *left, *right, *tail;
    for (int size = 1; size < length; size <<= 1) {
        cur = dummyHead.next; // restart from the head each outer iteration
        tail = &dummyHead;
        while (cur) {
            left = cur;
            right = split(left, size); // get the start of the right half
            cur = split(right, size); // update cur to the next pair to merge
            tail = merge(left, right, tail); // merge and update tail
        }
    }
    return dummyHead.next;
}

// Split function: returns the head of the second part
ListNode* split(ListNode* head, int n) {
    while (--n && head) {
        head = head->next;
    }
    ListNode* rest = head ? head->next : nullptr;
    if (head) head->next = nullptr;
    return rest;
}

// Updated merge function: returns the tail of the merged list
ListNode* merge(ListNode* l1, ListNode* l2, ListNode* head) {
    ListNode* cur = head;
    while (l1 && l2) {
        if (l1->val < l2->val) {
            cur->next = l1;
            l1 = l1->next;
        } else {
            cur->next = l2;
            l2 = l2->next;
        }
        cur = cur->next;
    }
    cur->next = l1 ? l1 : l2;
    while (cur->next) cur = cur->next; // advance to the tail
    return cur;
}

// Main function for demonstration
int main() {
    // Example: create and sort a linked list
    // (list creation omitted; assumes a linked list head exists)
    ListNode* sorted = sortList(head);
    // Print sorted list...
    return 0;
}

Remove K Digits

Given a string representation of a non-negative integer num and an integer k, remove k digits from the number so that the remaining number is the smallest possible. Return the result as a string.

Maintain a monotonically non-decreasing stack storing the digits to keep:

class Solution {
public:
    string removeKdigits(string num, int k) {
        deque<char> dq;
        dq.push_back(num[0]);
        int delCnt=0, curIndex=1;
        while(curIndex<num.size()) {
            while(!dq.empty() && num[curIndex]<dq.back() && delCnt<k) {
                delCnt++;
                dq.pop_back();
            }
            dq.push_back(num[curIndex]);
            curIndex++;
        }
        while(delCnt<k) {
            delCnt++;
            dq.pop_back();
        }

        string ans;
        while(!dq.empty() && dq.front()=='0') dq.pop_front();
        while(!dq.empty()) {
            ans += dq.front();
            dq.pop_front();
        }

        return ans.size()==0? "0":ans;
    }
};

Binary Trees

Maximum Width of Binary Tree

Given the root of a binary tree, return the maximum width of the tree.

The width of one level is defined as the length between the leftmost and rightmost non-null nodes (inclusive), treating the tree as a complete binary tree structure — null nodes between the two endpoints also count toward the width.

Binary tree array indexing + BFS level-order traversal.

Detail: use unsigned integer types to store index values, avoiding overflow issues.

class Solution {
public:
    int widthOfBinaryTree(TreeNode* root) {
        unsigned long long res = 1;
        vector<pair<TreeNode *, unsigned long long>> arr;
        arr.emplace_back(root, 1L);
        while (!arr.empty()) {
            vector<pair<TreeNode *, unsigned long long>> tmp;
            for (auto &[node, index] : arr) {
                if (node->left) {
                    tmp.emplace_back(node->left, index * 2);
                }
                if (node->right) {
                    tmp.emplace_back(node->right, index * 2 + 1);
                }
            }
            res = max(res, arr.back().second - arr[0].second + 1);
            arr = move(tmp);
        }
        return res;
    }
};

Validate Binary Search Tree

Given the root of a binary tree, determine if it is a valid BST.

Recursive approach:

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        return recur(root, LONG_MIN, LONG_MAX);
    }
private:
    bool recur(TreeNode *node, long leftRoot, long rightRoot) {
        if(node==nullptr) return true;
        if(node->val>=rightRoot || node->val<=leftRoot) return false;
        return recur(node->left, leftRoot, node->val) && recur(node->right, node->val, rightRoot);
    }
};

In-order traversal: the in-order traversal of a valid BST must produce a strictly ascending sequence.

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        stack<TreeNode*> stack;
        long long inorder = (long long)INT_MIN - 1;

        while (!stack.empty() || root != nullptr) {
            while (root != nullptr) {
                stack.push(root);
                root = root -> left;
            }
            root = stack.top();
            stack.pop();
            // If the current node's value is <= the previous inorder value, it's not a valid BST
            if (root -> val <= inorder) {
                return false;
            }
            inorder = root -> val;
            root = root -> right;
        }
        return true;
    }
};

Level Order Traversal (One Row Per Level)

class Solution {
public:
    vector<vector<int>> decorateRecord(TreeNode* root) {
        queue<TreeNode*> que;
        vector<vector<int>> res;
        if(root != NULL) que.push(root);
        while(!que.empty()) {
            vector<int> tmp;
            for(int i = que.size(); i > 0; --i) {
                root = que.front();
                que.pop();
                tmp.push_back(root->val);
                if(root->left != NULL) que.push(root->left);
                if(root->right != NULL) que.push(root->right);
            }
            res.push_back(tmp);
        }
        return res;
    }
};

Invert Binary Tree

Recursive approach:

class Solution {
public:
    TreeNode* mirrorTree(TreeNode* root) {
        if(!root) return root;
        TreeNode *tmp=root->left;
        root->left=mirrorTree(root->right);
        root->right=mirrorTree(tmp);

        return root;
    }
};

Auxiliary stack:

class Solution {
public:
    TreeNode* mirrorTree(TreeNode* root) {
        if(root == nullptr) return nullptr;
        stack<TreeNode*> stack;
        stack.push(root);
        while (!stack.empty())
        {
            TreeNode* node = stack.top();
            stack.pop();
            if (node->left != nullptr) stack.push(node->left);
            if (node->right != nullptr) stack.push(node->right);
            TreeNode* tmp = node->left;
            node->left = node->right;
            node->right = tmp;
        }
        return root;
    }
};

Lowest Common Ancestor of a Binary Tree

DFS + backtracking:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root==nullptr || root==p || root==q) {
            return root;
        }
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);

        if(left && right) return root;
        if(left==nullptr) return right;
        if(right==nullptr) return left;
        return nullptr;
    }
};

Construct Binary Tree from Preorder and Inorder Traversal

Personal approach:

class Solution {
public:
    TreeNode* deduceTree(vector<int>& preorder, vector<int>& inorder) {
        int p=0, i1=0, i2=inorder.size();
        return recur(preorder, inorder, p, i1, i2);
    }
private:
    TreeNode* recur(vector<int>& preorder, vector<int>& inorder, int &p, int i1, int i2) {
        if(i1>=i2 || p>=preorder.size()) return nullptr;
        TreeNode* cur = new TreeNode(preorder[p]);
        int mid=0;
        for(int j=i1; j<i2; ++j) {
            if(preorder[p]==inorder[j]) {
                mid=j;
                break;
            }
        }
        ++p;
        cur->left=recur(preorder, inorder, p, i1, mid);
        cur->right=recur(preorder, inorder, p, mid+1, i2);
        return cur;
    }
};

Using a hash map for O(1) index lookup:

class Solution {
public:
    TreeNode* deduceTree(vector<int>& preorder, vector<int>& inorder) {
        this->preorder = preorder;
        for(int i = 0; i < inorder.size(); i++)
            hmap[inorder[i]] = i;
        return recur(0, 0, inorder.size() - 1);
    }
private:
    vector<int> preorder;
    unordered_map<int, int> hmap;
    TreeNode* recur(int root, int left, int right) { 
        if(left > right) return nullptr;                        // base case
        TreeNode* node = new TreeNode(preorder[root]);          // build root node
        int i = hmap[preorder[root]];                           // locate root in inorder
        node->left = recur(root + 1, left, i - 1);              // recurse left subtree
        node->right = recur(root + i - left + 1, i + 1, right); // recurse right subtree
        return node;                                            // return root
    }
};

Verify Postorder Traversal Sequence of BST

Auxiliary monotonic stack, traversing from right to left.

Every element in the right subtree must be less than its ancestor node.

class Solution {
public:
    bool verifyTreeOrder(vector<int>& postorder) {
        int root=INT_MAX;
        stack<int> s;

        for(int j=postorder.size()-1; j>=0; --j) {
            if(postorder[j]>=root) return false;
            while(!s.empty() && postorder[j]<s.top()) {
                root = s.top();
                s.pop();
            }
            s.push(postorder[j]);
        }

        return true;
    }
};

DFS & BFS

Word Puzzle (Letter Maze)

A straightforward DFS approach.

Notes: container types must be passed by reference; be careful with loop variable initialization.

2D array initialization using the constructor:

class Solution {
public:
    bool wordPuzzle(vector<vector<char>>& grid, string target) {
        vector<vector<bool>> path(grid.size(), vector<bool>(grid[0].size(), false));

        for(int i=0;i<grid.size();++i) {
            for(int j=0;j<grid[0].size();++j) {
                if(ifMatched(grid, target, path, i, j, 0)) return true;
            }
        }

        return false;
    }
private:
    bool ifMatched(vector<vector<char>>& grid, string &target, vector<vector<bool>> &path, int i, int j, int p){
        if(i<0 || i>=grid.size() || j<0 || j>=grid[0].size() || path[i][j]) return false;

        if(grid[i][j]==target[p] && p==target.size()-1) return true;
        if(grid[i][j]==target[p]){
            path[i][j] = true;
            if(ifMatched(grid, target, path, i+1, j, p+1) || ifMatched(grid, target, path, i-1, j, p+1) || ifMatched(grid, target, path, i, j+1, p+1)
             || ifMatched(grid, target, path, i, j-1, p+1)) return true;
            path[i][j] = false;
            return false;
        }

        return false;

    }
};

Wardrobe Finishing

A wardrobe organizer divides a wardrobe into an m x n grid where grid[i][j] represents a cell to organize. The organizer starts at grid[0][0] and traverses row by row, column by column.

Rules: at each step, the organizer can move right or down, but cannot move outside the wardrobe. Cells where digit(i) + digit(j) > cnt do not need to be organized, where digit(x) is the sum of digits of x.

Return the total number of cells the organizer needs to organize.

BFS:

class Solution {
    // Compute digit sum of x
    int get(int x) {
        int res=0;
        for (; x; x /= 10) {
            res += x % 10;
        }
        return res;
    }
public:
    int wardrobeFinishing(int m, int n, int cnt) {
        if (!cnt) return 1;
        queue<pair<int,int> > Q;
        // Direction arrays for right and down
        int dx[2] = {0, 1};
        int dy[2] = {1, 0};
        vector<vector<int> > vis(m, vector<int>(n, 0));
        Q.push(make_pair(0, 0));
        vis[0][0] = 1;
        int ans = 1;
        while (!Q.empty()) {
            auto [x, y] = Q.front();
            Q.pop();
            for (int i = 0; i < 2; ++i) {
                int tx = dx[i] + x;
                int ty = dy[i] + y;
                if (tx < 0 || tx >= m || ty < 0 || ty >= n || vis[tx][ty] || get(tx) + get(ty) > cnt) continue;
                Q.push(make_pair(tx, ty));
                vis[tx][ty] = 1;
                ans++;
            }
        }
        return ans;
    }
};

Dynamic Programming

Longest Increasing Subsequence

Given an integer array nums, find the length of the longest strictly increasing subsequence.

DP with binary search optimization:

int lengthOfLIS(const std::vector<int>& nums) {
    std::vector<int> tails; // stores the smallest tail element for each increasing subsequence length

    for (int num : nums) {
        // binary search for the position of num in tails
        auto it = std::lower_bound(tails.begin(), tails.end(), num);

        // if num is larger than all elements in tails, append it
        if (it == tails.end()) {
            tails.push_back(num);
        } else {
            // otherwise, update the element at that position
            *it = num;
        }
    }

    return tails.size(); // size of tails equals the length of the LIS
}

The key insight: when we encounter a number smaller than the current tail, we replace the tail with it. If this doesn’t lead to a longer subsequence, there’s no loss; but if it does, the groundwork is already laid for extending the sequence.

Count Subarrays with Sum Equal to K

Given an array and a value, find the number of contiguous subarrays whose sum equals the value.

Uses prefix sums — not immediately obvious as a DP problem.

int subarraySumEqualsK(std::vector<int>& nums, int k) {
    int count = 0;
    int sum = 0; // current prefix sum
    std::unordered_map<int, int> prefixSums; // prefix sum -> count of occurrences
    prefixSums[0] = 1; // initialize: an empty prefix has sum 0

    for (int num : nums) {
        sum += num; // update prefix sum
        // check if (sum - k) exists in prefix sums
        if (prefixSums.find(sum - k) != prefixSums.end()) {
            count += prefixSums[sum - k]; // add the number of matching subarrays
        }
        // update prefix sum count
        prefixSums[sum]++;
    }

    return count;
}

Ugly Number

Watch out for duplicate cases.

Higher-complexity approach: priority queue.

Three-pointer DP (efficient):

class Solution {
public:
    int nthUglyNumber(int n) {
        if(n==0) return -1;
        vector<int> dp;
        dp.push_back(1);
        int p2=0, p3=0, p5=0;
        for(int i=1; i<n; ++i) {
            int v2=dp[p2]*2, v3=dp[p3]*3, v5=dp[p5]*5;
            int cur = min(v2, min(v3, v5));
            dp.push_back(cur);
            if(cur==v2) ++p2;
            if(cur==v3) ++p3;
            if(cur==v5) ++p5;
        }
        return dp[n-1];
    }
};

Dice Roll Probability

Classic dynamic programming:

class Solution {
public:
    vector<double> statisticsProbability(int num) {
        vector<double> dp(6, 1/6.0);
        for(int i=2; i<=num; ++i) {
            vector<double> tmp(5*num+1, 0);
            for(int j=0; j<5*num+1; ++j) {
                for(int k=min(j, int(dp.size())-1); k>=max(0, j-5); --k) {
                    tmp[j]+=dp[k]/6.0;
                }
            }
            dp=tmp;
        }
        return dp;
    }
};

Product of Array Except Self

Array arrayA records counts of biological populations. Return array arrayB where arrayB[i] is the product of all elements in arrayA except arrayA[i].

Essentially DP: prefix products + suffix products.

class Solution {
public:
    vector<int> statisticalResult(vector<int>& arrayA) {
        vector<int> ans(arrayA.size(), 1);
        int tmp=1;
        for(int i=1; i<arrayA.size(); ++i) {
            tmp*=arrayA[i-1];
            ans[i] = tmp;
        }

        tmp=1;
        for(int i=arrayA.size()-2; i>=0; --i) {
            tmp*=arrayA[i+1];
            ans[i] *= tmp;
        }

        return ans;
    }
};

Word Break

Given a string s and a dictionary wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.

DP + hash set:

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> dic;
        for(auto ele : wordDict) {
            dic.insert(ele);
        }

        vector<bool> dp(s.size(), false);
        for(int i=0; i<s.size(); ++i) {
            for(int j=0; j<i; ++j) {
                if(dp[j] && dic.find(s.substr(j+1, i-j))!=dic.end()) {
                    dp[i]=true;
                    break;
                }
            }
            if(dic.find(s.substr(0, i+1))!=dic.end()) {
                dp[i]=true;
            }
        }

        return dp[s.size()-1];
        
    }
};

Divide and Conquer

Count Reverse Pairs

Count the total number of reverse pairs in an array.

Merge sort — divide and conquer:

class Solution {
public:
    int reversePairs(vector<int>& record) {
        ans = 0;
        assist.resize(record.size());
        recur(record, 0, record.size()-1);
        return ans;
    }
private:
    int ans;
    vector<int> assist;
    void recur(vector<int>& record, int left, int right) {
        if(right<=left) return;

        int mid = left + (right-left)/2;
        recur(record, left, mid);
        recur(record, mid+1, right);

        int i=left, j=mid+1;
        for(int k=left; k<=right; ++k) {
            if(i>mid) {
                assist[k] = record[j++];
            }
            else if(j>right || record[i]<=record[j]) {
                assist[k] = record[i++];
            }
            else {
                assist[k] = record[j++];
                ans += mid-i+1;
            }
        }
        copy(assist.begin()+left, assist.begin()+right+1, record.begin()+left);

        return;
    }
};

Create Maximum Number

Given two integer arrays nums1 and nums2 of lengths m and n, representing two numbers digit by digit, and an integer k, create the maximum number of length k <= m + n from the digits of the two arrays, while preserving the relative order of digits from the same array.

Example 1:

Input: nums1 = [3,4,6,5], nums2 = [9,1,2,5,8,3], k = 5
Output: [9,8,6,5,3]

Example 2:

Input: nums1 = [6,7], nums2 = [6,0,4], k = 5
Output: [6,7,6,0,4]

Example 3:

Input: nums1 = [3,9], nums2 = [8,9], k = 3
Output: [9,8,9]

A hard problem: monotonic stack + divide and conquer, with a custom merge operation.

C++ implementation is quite tricky:

class Solution {
public:
    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
        vector<int> ans;
        int min_k = k - min(k, (int)nums2.size()), max_k = min(k, (int)nums1.size());
        for(int i=min_k; i<=max_k; ++i) {
            vector<int> a1 = maxOfOne(nums1, i);
            vector<int> a2 = maxOfOne(nums2, k-i);
            vector<int> merged = merge(a1, a2);
            ans = greatorV(ans, merged);
        }

        return ans;
    }
private:
    vector<int> maxOfOne(vector<int>& nums, int k) {
        if(k==0) return {};
        vector<int> ans(k);
        stack<int> s;
        int cnt=0, pop_num=nums.size()-k;
        for(auto ele : nums) {
            while(cnt<pop_num && !s.empty() && ele>s.top()) {
                s.pop();
                cnt++;
            }
            s.push(ele);
        }
        while(cnt<pop_num) {
            s.pop();
            cnt++;
        }

        for(int i=k-1; i>=0; --i) {
            ans[i] = s.top();
            s.pop();
        }
        cout<<"k="<<k<<endl;
        copy(ans.begin(), ans.end(), ostream_iterator<int>(cout, " "));
        cout<<endl;
        return ans;
    }

    vector<int> merge(vector<int>& a1, vector<int>& a2) {
        int len1=a1.size(), len2=a2.size();
        vector<int> ans;

        int p1=0, p2=0;
        while(p1<len1 || p2<len2) {
            if(p1==len1) {
                ans.push_back(a2[p2]);
                ++p2;
            }
            else if(p2==len2) {
                ans.push_back(a1[p1]);
                ++p1;
            }
            else if(a1[p1]>a2[p2]) {
                ans.push_back(a1[p1]);
                ++p1;
            }
            else if(a1[p1]<a2[p2]){
                ans.push_back(a2[p2]);
                ++p2;
            }
            else {
                bool flag = whichBigger(a1, a2, p1, p2);
                if(flag) {
                    ans.push_back(a1[p1]);
                    ++p1;
                }
                else {
                    ans.push_back(a2[p2]);
                    ++p2;
                }
            }
        } 
        return ans;
    }

    bool whichBigger(vector<int>& a1, vector<int>& a2, int p1, int p2) {
        int cur = a1[p1];
        while(p1<a1.size() && p2<a2.size()) {
            if(a1[p1]>a2[p2]) return true;
            if(a1[p1]<a2[p2]) return false;
            ++p1;
            ++p2;
        }

        if(p1==a1.size()) return false;
        else return true;
    }

    vector<int> greatorV(vector<int>& a1, vector<int>& a2) {
        if(a1.size()==0) return a2;
        int len = a1.size();
        for(int i=0; i<len; ++i) {
            if(a1[i]>a2[i]) return a1;
            if(a1[i]<a2[i]) return a2;
        }

        return a1;
    }



};

Bit Manipulation & Math

Bitwise Addition

Brute-force approach (personal):

class Solution {
public:
    int encryptionCalculate(int dataA, int dataB) {

        int ans = 0, curFlag = 1, carryFlag = 0;
        while(curFlag!=0) {
            ans |= ((dataA^dataB^carryFlag)&curFlag);
            if((dataA&curFlag)&&(dataB&curFlag) || (dataA&curFlag)&&(carryFlag&curFlag) || (dataB&curFlag)&&(carryFlag&curFlag)) {
                carryFlag = (curFlag<<1)&(-1);
            }
            else carryFlag = 0;
            curFlag<<=1;
        }
        return ans;
    }
};

Elegant approach: sum = XOR (non-carry sum) + carry; loop until carry is 0.

class Solution {
public:
    int encryptionCalculate(int dataA, int dataB) {
        while(dataB != 0)
        {
            int c = (unsigned int)(dataA & dataB) << 1;
            dataA ^= dataB;
            dataB = c;
        }
        return dataA;
    }
};

Find the Two Non-Duplicate Elements

Find the two elements that appear only once in an array where all other elements appear in pairs.

XOR property: x ^ x = 0.

The two non-duplicate elements x and y must differ in at least one bit:

class Solution {
public:
    vector<int> sockCollocation(vector<int>& sockets) {
        if(sockets.empty()) exit(1);
        int val1 = 0;
        for(int i=0; i<sockets.size(); ++i) {
            val1 ^= sockets[i];
        }

        int m = 1, flag = val1&m;
        while(flag==0) {
            m<<=1;
            flag = val1&m;
        }

        int valx=0, valy=0;
        for(int i=0; i<sockets.size(); ++i) {
            if(flag&sockets[i]) {
                valx ^= sockets[i];
            }
            else {
                valy ^= sockets[i];
            }
        }

        vector<int> ans = {valx, valy};
        return ans;
    }
};

Find the Single Non-Triplicate Element

Find the one element that appears only once in an array where all other elements appear exactly three times.

Bit manipulation + finite state machine.

The bitwise sum modulo 3 of all triplicate elements equals 0:

class Solution {
public:
    int trainingPlan(vector<int>& actions) {
        int ones = 0, twos = 0;
        for(int action : actions){
            ones = ones ^ action & ~twos;
            twos = twos ^ action & ~ones;
        }
        return ones;
    }
};

Cut Bamboo II

Given a bamboo of length bamboo_len (a positive integer), cut it into several pieces, each with a positive integer length. Return the maximum product of the piece lengths, modulo 1e9+7.

Math + fast exponentiation:

class Solution {
public:
    int cuttingBamboo(int bamboo_len) {
        long mod = 1000000007;
        if(bamboo_len<=3) return bamboo_len-1;
        int a = bamboo_len/3, b = bamboo_len%3, pow;
        long ans;
        if(b==2) {
            pow = a;
            ans = 2;
        }
        else if(b==1) {
            pow = a-1;
            ans = 4;
        }
        else {
            pow = a;
            ans = 1;
        }

        long x=3;
        while(pow>0) {
            if(pow%2==1) ans = (ans*x)%mod;
            x = (x*x)%mod;
            pow/=2;
        }
        
        return ans;
    }
};

Ice Breaking Game (Josephus Problem)

A group of num members numbered 0 ~ num-1 sit in a circle. Starting from member 0, count clockwise to the target-th member, who then leaves. Counting restarts from the next member. Return the number of the last remaining member.

Josephus problem — math + DP:

class Solution {
public:
    int iceBreakingGame(int num, int target) {
        int ans = 0;
        for(int i=1; i<=num; ++i) {
            ans = (ans+target)%i;
        }

        return ans;
    }
};