LeetCode Top Problems C++ — Two Sum, Reverse LL, Floyd, Kadane, BinSearch, BFS

// Top LeetCode Problems — C++ Solutions

// 1. Two Sum — HashMap O(n)
vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> seen; // value → index
    for (int i = 0; i < (int)nums.size(); i++) {
        int comp = target - nums[i];
        if (seen.count(comp))
            return {seen[comp], i};
        seen[nums[i]] = i;
    }
    return {};
}

// 2. Valid Parentheses — Stack O(n)
bool isValid(string s) {
    stack<char> st;
    for (char c : s) {
        if (c == '(' || c == '{' || c == '[') {
            st.push(c);
            continue;
        }
        if (st.empty())
            return false;
        if (c == ')' && st.top() != '(')
            return false;
        if (c == '}' && st.top() != '{')
            return false;
        if (c == ']' && st.top() != '[')
            return false;
        st.pop();
    }
    return st.empty();
}

// 3. Reverse Linked List — Two pointers O(n) O(1)
ListNode* reverseList(ListNode* head) {
    ListNode *prev = nullptr, *curr = head;
    while (curr) {
        ListNode* next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

// 4. Floyd's Cycle Detection — Fast/Slow O(n) O(1)
bool hasCycle(ListNode* head) {
    ListNode *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast)
            return true;
    }
    return false;
}
// Cycle start: reset slow=head; advance both by 1 until meet

// 5. Kadane's Max Subarray — DP O(n) O(1)
int maxSubArray(vector<int>& nums) {
    int maxS = nums[0], curr = nums[0];
    for (int i = 1; i < (int)nums.size(); i++) {
        curr = max(nums[i], curr + nums[i]); // restart or extend
        maxS = max(maxS, curr);
    }
    return maxS;
}

// 6. Binary Search — O(log n)
int search(vector<int>& nums, int target) {
    int lo = 0, hi = (int)nums.size() - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2; // avoids overflow vs (lo+hi)/2
        if (nums[mid] == target)
            return mid;
        if (nums[mid] < target)
            lo = mid + 1;
        else
            hi = mid - 1;
    }
    return -1;
}

// 7. Sliding Window — Longest substring without repeat O(n)
int lengthOfLongestSubstring(string s) {
    unordered_map<char, int> last;
    int res = 0, start = 0;
    for (int i = 0; i < (int)s.size(); i++) {
        if (last.count(s[i]) && last[s[i]] >= start)
            start = last[s[i]] + 1; // shrink window
        last[s[i]] = i;
        res = max(res, i - start + 1);
    }
    return res;
}

// 8. BFS Level Order — Queue O(n)
vector<vector<int>> levelOrder(TreeNode* root) {
    if (!root)
        return {};
    vector<vector<int>> res;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        int sz = q.size();
        res.push_back({});
        for (int i = 0; i < sz; i++) {
            auto* n = q.front();
            q.pop();
            res.back().push_back(n->val);
            if (n->left)
                q.push(n->left);
            if (n->right)
                q.push(n->right);
        }
    }
    return res;
}