DAY 102 - 2130. Maximum Twin Sum of a Linked List

Hello People!. Continuing our challenge until we break it , we continue on our path to learn linked list and solve it's leetcode problems. Today we are going to do a very easy problem and the intuition behind this can be sometimes hard to catch, so let's start.

Question: 2130. Maximum Twin Sum of a Linked List

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.

Example 1:

Input: head = [5,4,2,1]
Output: 6
Explanation:
Nodes 0 and 1 are the twins of nodes 3 and 2, respectively. All have twin sum = 6.
There are no other nodes with twins in the linked list.
Thus, the maximum twin sum of the linked list is 6.

Example 2:

Input: head = [4,2,2,3]
Output: 7
Explanation:
The nodes with twins present in this linked list are:

• Node 0 is the twin of node 3 having a twin sum of 4 + 3 = 7.
• Node 1 is the twin of node 2 having a twin sum of 2 + 2 = 4. Thus, the maximum twin sum of the linked list is max(7, 4) = 7.

Problem Breakdown:

• We are given a singly linked list of even length each having value from 0 to 10^5.
• We are also given a pair relation, to simplify the relation it's the first node from the start and last node. They make a pair and we move ahead from start to next node and we move back from last node to our second last node, sequentially every such two nodes form a pair.
• Okay so, if anyone has done a little bit of coding questions, this is pretty easy, We can simply take a vector to store the values and use a while loop to traverse from both ends using two pointers and find the maximum.
• Yes but in this approach we will be using O(N) extra space, the challenge lies in solving this without using extra space.

So how do we do it? Let's head down to approach.

Intuition:

• So the challenge is we can only move forward in our linked list.
• If we could move back we could solve this right, obviously we can't make this into a doubly linked list so how do we move back.
• Let's first identify which nodes do we need, L0 & LN , L1 & LN-1 , L2 & LN-2 and so on...
• If we carefully see our mid pointer will have it's next node as it's pair.
• If we can somehow travel in reverse after our mid, we will be able to get the solution.
• Let's try doing this exactly, we divide our linked list into two parts, one is our left part and one is our right part.
• When we reverse a linked list the last node is our head.
• After we reverse it, we now have a pointer to last node and we can move forward.

Continuing on our intuition let's write the approach:

Approach:

1. Reverse the Right Half of the List:
   • First, we identify the middle of the linked list using Floyd's Tortoise and Hare algorithm. We do this by having two pointers, slow and fast, traverse the list at different speeds. When they meet, slow points to the middle node.
   • Next, the right half of the linked list is reversed. Reversing the list makes it easier to calculate the maximum pair sum.

• In case you don't know this approach, check out my article on it : Floyd's tortoise and hare algorithm

1. Find the Maximum Pair Sum:

   • With the right half of the list reversed, we initialize two pointers, p1 and p2, at the heads of the original and reversed lists, respectively.
   • As the pointers traverse the lists, the maximum sum of pairs is calculated. We do this by by summing the values of nodes pointed to by p1 and p2 and updating the maximum sum (maxi) if we encounter larger sum.
   • We continue the process until both pointers reach the end of their respective lists.

2. Return the Maximum Sum:

   • The maximum pair sum (maxi) is the result of the problem and hence we return it.

Code:

/**
 * 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:

    ListNode* reverseList(ListNode* head){
    if(!head) return head;

    ListNode* prev = NULL;
    ListNode* cur = head;
    ListNode* nex = cur->next;

    while(cur){
        cur->next = prev;
        prev = cur;
        cur = nex;
        if(nex) nex = nex->next;
    }
    return prev;
}

    int pairSum(ListNode* head) {

        //find the middle node of the list using floyd's tortoise and hare
    ListNode* slow = head;
    ListNode* fast = head;

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

        if(slow == fast){
            break;
        }
    }

    //slow points to middle of the list
    //cut the list from middle


    //reverse the right list
    ListNode* p1 = head;
    ListNode* p2 = reverseList(slow);

    int maxi = INT_MIN;
    while(p2){
        maxi = max(maxi,p1->val + p2->val);
        p1 = p1->next;
        p2 = p2->next;
    }
    return maxi;
    }
};

Time and Space Complexity

Now, let's analyze the time and space complexity of this solution:

• Time Complexity: We traverse the entire linked list twice. The first traversal finds the middle of the list, and the second traversal calculates the maximum pair sum. Therefore, the time complexity is O(N), where N is the number of nodes in the linked list.

• Space Complexity: We use a constant amount of extra space for variables. No additional data structures or memory allocation is required, resulting in a space complexity of O(1).