Arrays and Strings

Merging Sorted Arrays

1. Naive Merge and Sort

class Solution {
public:
    void combineArrays(vector<int>& arr1, int m, vector<int>& arr2, int n) {
        for(int i = 0; i < n; ++i) {
            arr1[m + i] = arr2[i];
        }
        sort(arr1.begin(), arr1.end());
    }
};

2. Two-Pointer Forward Merge

class Solution {
public:
    void combineArrays(vector<int>& arr1, int m, vector<int>& arr2, int n) {
        int idx1 = 0, idx2 = 0;
        vector<int> combined(m + n);
        int current;
        while(idx1 < m || idx2 < n) {
            if(idx1 == m)          current = arr2[idx2++];
            else if(idx2 == n)     current = arr1[idx1++];
            else if(arr1[idx1] < arr2[idx2]) current = arr1[idx1++];
            else                            current = arr2[idx2++];
            combined[idx1 + idx2 - 1] = current;
        }
        for(int i = 0; i < m + n; ++i) arr1[i] = combined[i];
    }
};

3. Two-Pointer Reverse Merge

class Solution {
public:
    void combineArrays(vector<int>& arr1, int m, vector<int>& arr2, int n) {
        int p1 = m - 1, p2 = n - 1;
        int pos = m + n - 1;
        int value;
        while(p1 >= 0 || p2 >= 0) {
            if(p1 == -1)          value = arr2[p2--];
            else if(p2 == -1)     value = arr1[p1--];
            else if(arr1[p1] > arr2[p2]) value = arr1[p1--];
            else                         value = arr2[p2--];
            arr1[pos--] = value;
        }
    }
};

Removing Elements

1. Using Auxiliary Storage

int eraseValue(vector<int>& nums, int target) {
    vector<int> filtered;
    for(int i = 0; i < nums.size(); ++i) {
        if(nums[i] != target) filtered.push_back(nums[i]);
    }
    for(int i = 0; i < filtered.size(); ++i) nums[i] = filtered[i];
    return filtered.size();
}

2. Two-Pointer In-Place Reemoval

class Solution {
public:
    int eraseValue(vector<int>& nums, int target) {
        int writePos = 0;
        for(int readPos = 0; readPos < nums.size(); readPos++) {
            if(nums[readPos] != target) {
                nums[writePos++] = nums[readPos];
            }
        }
        return writePos;
    }
};

Eliminating Duplicates in a Sorted Array

int deduplicate(vector<int>& nums) {
    if(nums.empty()) return 0;
    int uniqueIdx = 0;
    for(int i = 0; i < nums.size(); i++) {
        if(nums[i] != nums[uniqueIdx]) {
            nums[++uniqueIdx] = nums[i];
        }
    }
    return uniqueIdx + 1;
}

Eliminating Duplicates Allowing at Most Two Copies

class Solution {
public:
    int deduplicateGeneral(vector<int>& nums, int k) {
        int slow = 0;
        for(int fast = 0; fast < nums.size(); fast++) {
            if(slow < k || nums[slow - k] != nums[fast]) {
                nums[slow++] = nums[fast];
            }
        }
        return slow;
    }

    int removeDuplicates(vector<int>& nums) {
        return deduplicateGeneral(nums, 2);
    }
};

Linked Lists

Intersection of Two Linked Lists

class Solution {
public:
    ListNode *findIntersection(ListNode *headA, ListNode *headB) {
        ListNode *nodeA = headA, *nodeB = headB;
        while(nodeA != nodeB) {
            nodeA = nodeA ? nodeA->next : headB;
            nodeB = nodeB ? nodeB->next : headA;
        }
        return nodeA;
    }
};

Reversing a Linked List

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *prev = nullptr, *curr = head, *nextNode;
        while(curr) {
            nextNode = curr->next;
            curr->next = prev;
            prev = curr;
            curr = nextNode;
        }
        return prev;
    }
};

Detecting a Cycle in a Linked List

class Solution {
public:
    bool hasLoop(ListNode *head) {
        ListNode *fast = head, *slow = head;
        while(fast && fast->next) {
            fast = fast->next->next;
            slow = slow->next;
            if(fast == slow) return true;
        }
        return false;
    }
};

Merging Two Sorted Lists

class Solution {
public:
    ListNode* mergeLists(ListNode* l1, ListNode* l2) {
        if(!l1) return l2;
        if(!l2) return l1;
        if(l1->val < l2->val) {
            l1->next = mergeLists(l1->next, l2);
            return l1;
        } else {
            l2->next = mergeLists(l1, l2->next);
            return l2;
        }
    }
};

Hash Tables

Two Sum

class Solution {
public:
    vector<int> findPair(vector<int>& numbers, int target) {
        unordered_map<int, int> seen;
        for(int i = 0; i < numbers.size(); i++) {
            int complement = target - numbers[i];
            if(seen.find(complement) != seen.end()) {
                return {seen[complement], i};
            }
            seen[numbers[i]] = i;
        }
        return {};
    }
};

Longest Consecutive Sequence

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> numSet(nums.begin(), nums.end());
        int maxLength = 0;
        for(int num : nums) {
            if(!numSet.count(num - 1)) {
                int currentNum = num;
                int currentLength = 1;
                while(numSet.count(currentNum + 1)) {
                    currentNum++;
                    currentLength++;
                }
                maxLength = max(maxLength, currentLength);
            }
        }
        return maxLength;
    }
};

Trees

Maximum Depth of a Binary Tree

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(!root) return 0;
        queue<TreeNode*> q;
        q.push(root);
        int depth = 0;
        while(!q.empty()) {
            int levelSize = q.size();
            depth++;
            for(int i = 0; i < levelSize; i++) {
                TreeNode* node = q.front(); q.pop();
                if(node->left) q.push(node->left);
                if(node->right) q.push(node->right);
            }
        }
        return depth;
    }
};

Symmetric Tree

class Solution {
    bool compareNodes(TreeNode* leftSide, TreeNode* rightSide) {
        if(!leftSide && !rightSide) return true;
        if(!leftSide || !rightSide) return false;
        if(leftSide->val != rightSide->val) return false;
        return compareNodes(leftSide->left, rightSide->right) &&
               compareNodes(leftSide->right, rightSide->left);
    }
public:
    bool isSymmetric(TreeNode* root) {
        if(!root) return true;
        return compareNodes(root->left, root->right);
    }
};

Lowest Common Ancestor

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(!root || 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;
        return left ? left : right;
    }
};