Leetcode 2130 - Maximum Twin Sum of a Linked List

Link to problem

Description

In a linked list of size n, where n is even, the ith node (0-indexed) of the linked list is known as the twin of the (n-1-i)th node, if 0 <= i <= (n / 2) - 1.

• For example, if n = 4, then node 0 is the twin of node 3, and node 1 is the twin of node 2. These are the only nodes with twins for n = 4.

The twin sum is defined as the sum of a node and its twin.

Given the head of a linked list with even length, return the maximum twin sum of the linked list.

Solution

I guessed that this could work even if you brute forced it by keeping all the content in the linked list into a vector. However, this problem probably wants us to use fast slow pointer, even better if we could do this in one pass.

Fast Slow Pointer, O(n/2) space

We first start off by using fast slow pointer to find the middle, at the same time we store the first half of the linked list in a vector. Then we use this vector to combine with the second half of the list to find the maximum sum.

Time and space complexity of this solution will be O(n) and O(n), respectively.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    int pairSum(ListNode* head) {
        vector<int> sum;
        ListNode *fast = head, *slow = head;
        int output = numeric_limits<int>::min();

        while (fast) {
            sum.push_back(slow->val);

            fast = fast->next->next;
            slow = slow->next;
        }

        size_t n = sum.size() * 2;
        size_t i = sum.size();
        while (slow) {
            output = max(output, sum[n-1-i] + slow->val);
            i++;
            slow = slow->next;
        }

        return output;
    }
};

Fast Slow Pointer, O(1) space

Similar to the first solution, we still need to find the middle by using fast slow pointer. However, this time we reverse the second half of the linked list and iterate through the list from both ends to find the maximum sum.

class Solution {
public:
    int pairSum(ListNode* head) {
        ListNode *fast = head->next, *slow = head;
        int output = 0;

        while (fast->next) {
            fast = fast->next->next;
            slow = slow->next;
        }

        ListNode *next = nullptr, *prev = nullptr;
        slow = slow->next;
        while (slow) {
            next = slow->next;
            slow->next = prev;
            prev = slow;
            slow = next;
        }

        while (prev) {
            output = max(output, head->val + prev->val);
            head = head->next;
            prev = prev->next;
        }

        return output;
    }
};

Well, in leetcode, whatever I did to the linked list, its not my responsibility to deal with memory leak or anything related. Therefore, I guess that reversing half of the list is fine.

Brute Force, O(n) time O(n) space

Actually the performance is not too bad, the execution time is still comparable to the second solution. My guess is that prefetching and caching helped when dealing with vector.

class Solution {
public:
    int pairSum(ListNode* head) {
        vector<int> temp;
        int output = 0;

        while (head) {
            temp.push_back(head->val);
            head = head->next;
        }

        for (size_t i = 0; i < temp.size() / 2; i++) {
            output = max(output, temp[i] + temp[temp.size()-i-1]);
        }

        return output;
    }
};