Hash Table Fundamentals

The std::unordered_map and std::unordered_set are critical for O(1) average time complexity lookups. When using unordered_map<int, int>, map.find(key) returns an iterator to the entry if present, or map.end() if not. Similarly, unordered_set provides find() and count() methods to verify existence.

Array Deduplication

// Method 1: Using unordered_set
// Method 2: Sorting followed by erase-unique idiom
std::sort(arr.begin(), arr.end());
arr.erase(std::unique(arr.begin(), arr.end()), arr.end());

Two-Pointer Techniques

Pair Summation

Given a array nums and a target, find the indices of two numbers that sum to the target. Using a hash map allows us to store visited values and their indices to achieve linear time complexity.

std::vector<int> findPair(const std::vector<int>& nums, int target) {
    std::unordered_map<int, int> seen;
    for (int i = 0; i < nums.size(); ++i) {
        int complement = target - nums[i];
        if (seen.count(complement)) return {seen[complement], i};
        seen[nums[i]] = i;
    }
    return {};
}

Container With Most Water

Use two pointers starting at both ends of the array. To potentially find a larger area, always move the pointer pointing to the shorter vertical line, as moving the longer one will only decrease the width without increasing height.

Sliding Window Patterns

Longest Substring Without Repeating Characters

Maintain a window using a set to track unique characters. If a duplicate is encountered, increment the left boundary and remove elements until the substring becomes valid again.

int maxLength(const std::string& s) {
    std::unordered_set<char> window;
    int maxLen = 0, left = 0;
    for (int right = 0; right < s.length(); ++right) {
        while (window.count(s[right])) {
            window.erase(s[left++]);
        }
        window.insert(s[right]);
        maxLen = std::max(maxLen, (int)window.size());
    }
    return maxLen;
}

Linked List Operations

Cycle Detection

Use Floyd's Cycle-Finding Algorithm (Tortoise and Hare). A fast pointer moves twice as quickly as a slow pointer. If they meet, a cycle exists. To find the entry point, reset one pointer to the head and move both at a constant speed; they will collide at the start of the cycle.

ListNode* detectCycle(ListNode* head) {
    ListNode *fast = head, *slow = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            ListNode* entry = head;
            while (entry != slow) {
                entry = entry->next;
                slow = slow->next;
            }
            return entry;
        }
    }
    return nullptr;
}

Tree Traversal and Manipulation

Maximum Depth of Binary Tree

Level-order traversal is often the most intuitive approach for depth-related problems.

int getDepth(TreeNode* root) {
    if (!root) return 0;
    return 1 + std::max(getDepth(root->left), getDepth(root->right));
}

Valid Binary Search Tree

Ensure that every node's value falls within a strict range determined by its ancestors. Use long integers to handle INT_MIN and INT_MAX edge cases.

bool isValid(TreeNode* node, long minVal, long maxVal) {
    if (!node) return true;
    if (node->val <= minVal || node->val >= maxVal) return false;
    return isValid(node->left, minVal, node->val) && 
           isValid(node->right, node->val, maxVal);
}