Merging Multiple Sorted Linked Lists

Efficiently combining several pre-sorted linked structures requires a mechanism to consistently extract the minimum available element across all sources. A min-heap provides an optimal approach for this task, maintaining a pool of candidate nodes and guaranteeing logarithmic insertion and extraction times.

By initializing the priority queue with the head of each non-empty list, the algorithm repeatedly extracts the smallest node, appends it to a result chain, and pushes the extracted node's successor back into the heap. Utilizing a sentinel node simplifies edge-case handling during list construction.

struct NodeComparator {
    bool operator()(ListNode* a, ListNode* b) {
        return a->val > b->val;
    }
};

class Solution {
public:
    ListNode* mergeKLists(std::vector<ListNode*>& lists) {
        std::priority_queue<ListNode*, std::vector<ListNode*>, NodeComparator> min_heap;
        for (auto* node : lists) {
            if (node) min_heap.push(node);
        }

        ListNode dummy(0);
        ListNode* tail = &dummy;

        while (!min_heap.empty()) {
            ListNode* smallest = min_heap.top();
            min_heap.pop();
            tail->next = smallest;
            tail = tail->next;
            if (smallest->next) {
                min_heap.push(smallest->next);
            }
        }
        return dummy.next;
    }
};

The time complexity scales as O(N log k), where N represents the total number of nodes and k is the number of input lists. Space complexity remains O(k) due to the heap storage.

Computing the Median of Two Sorted Arrays

Achieving logarithmic time complexity for this problem eliminates linear merging or traversal. The optimal strategy involves performing a binary search on the smaller array to find a partition point that divides both arrays into left and right halves. The goal is to ensure all element in the combined left half are less than or equal to all elements in the combined right half, with the left half containing exactly (m + n + 1) / 2 elements.

Boundary conditions are managed using sentinel values (INT_MIN and INT_MAX) to represent non-existent elements when a partition falls at the extreme ends of an array.

class Solution {
public:
    double findMedianSortedArrays(std::vector<int>& nums1, std::vector<int>& nums2) {
        if (nums1.size() > nums2.size()) {
            return findMedianSortedArrays(nums2, nums1);
        }

        int m = nums1.size();
        int n = nums2.size();
        int left = 0, right = m;
        int half_len = (m + n + 1) / 2;

        while (left <= right) {
            int partition1 = (left + right) / 2;
            int partition2 = half_len - partition1;

            int max_left1 = (partition1 == 0) ? INT_MIN : nums1[partition1 - 1];
            int min_right1 = (partition1 == m) ? INT_MAX : nums1[partition1];

            int max_left2 = (partition2 == 0) ? INT_MIN : nums2[partition2 - 1];
            int min_right2 = (partition2 == n) ? INT_MAX : nums2[partition2];

            if (max_left1 <= min_right2 && max_left2 <= min_right1) {
                if ((m + n) % 2 == 0) {
                    return (std::max(max_left1, max_left2) + std::min(min_right1, min_right2)) / 2.0;
                }
                return std::max(max_left1, max_left2);
            } else if (max_left1 > min_right2) {
                right = partition1 - 1;
            } else {
                left = partition1 + 1;
            }
        }
        return 0.0;
    }
};

This partition-based approach guarantees O(log(min(m, n))) runtime and O(1) auxiliary space, satisfying strict performance constraints.

Reversing Linked List Nodes in Fixed-Sized Groups

Modifying pointer references in segments requires careful boundary tracking to avoid disconnecting the chain. The process involves validating whether a complete group of size k exists, reversing the internal pointers of that segment, and correctly reattaching the reversed portion to the preceding and succeeding nodes.

A dummy head node streamlines the reattachment logic for the very first group. The reversal itself uses a standard three-pointer technique applied strictly within the identified boundaries.

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        if (!head || k == 1) return head;

        ListNode dummy(0);
        dummy.next = head;
        ListNode* group_prev = &dummy;

        while (true) {
            ListNode* kth_node = group_prev;
            for (int i = 0; i < k && kth_node; ++i) {
                kth_node = kth_node->next;
            }
            if (!kth_node) break;

            ListNode* group_next = kth_node->next;
            ListNode* prev = group_next;
            ListNode* curr = group_prev->next;

            while (curr != group_next) {
                ListNode* temp = curr->next;
                curr->next = prev;
                prev = curr;
                curr = temp;
            }

            ListNode* new_group_prev = group_prev->next;
            group_prev->next = kth_node;
            group_prev = new_group_prev;
        }
        return dummy.next;
    }
};

The algorithm processes each node a constant number of times, yielding O(N) time complexity. Pointer manipulation occurs in-place, maintaining O(1) space complexity.

Maximizing Profit with Limited Stock Transactions

Dynamic programming effectively models the state transitions between holding an asset and maintaining liquid capital across a sequence of daily prices. For a maximum of k transactions, two state arrays track the optimal financial position: one for the maximum balance after buying (hold) and another for the maximum balance after selling (cash).

When k exceeds half the number of trading days, the constraint becomes irrelevant, and a greedy approach capturing every positive price difference yields the optimal result in linear time. Otherwise, the DP state machine iterates through each price, updating transaction states sequentially.

class Solution {
public:
    int maxProfit(int k, std::vector<int>& prices) {
        if (prices.empty() || k == 0) return 0;

        if (k >= prices.size() / 2) {
            int profit = 0;
            for (size_t i = 1; i < prices.size(); ++i) {
                if (prices[i] > prices[i - 1]) {
                    profit += prices[i] - prices[i - 1];
                }
            }
            return profit;
        }

        std::vector<int> hold(k + 1, INT_MIN);
        std::vector<int> cash(k + 1, 0);

        for (int price : prices) {
            for (int t = 1; t <= k; ++t) {
                hold[t] = std::max(hold[t], cash[t - 1] - price);
                cash[t] = std::max(cash[t], hold[t] + price);
            }
        }
        return cash[k];
    }
};

State transitions insure that each buy operation deducts from the profit of the previous completed sale, while each sell operation realizes the gain from the current holding. The solution operates in O(k * N) time with O(k) space overhead.