Maximum Twin Sum Of A Linked List Leetcode Problem 2130 [Python]

If you're looking for a detailed solution to the LeetCode problem "Maximum Twin Sum Of A Linked List," you're in the right place.

In this blog post, we'll break down the problem, explore the constraints, and provide an efficient Python solution to solve it.

We'll also dive into the time and space complexity of our solution and explain the reasoning behind our approach.

Let's get started!

Problem Overview

The problem statement goes as follows:

You are given a linked list of even length, where each node is paired with its "twin" node.

The twin of the ith node (0-indexed) in the linked list is the (n-1-i)th node, where n is the length of the linked list.

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

Your task is to find the maximum twin sum in the linked list.

Let's consider a few examples to better understand the problem:

Example 1:

Input: head = [5,4,2,1]
Output: 6

Explanation: In this case, nodes 0 and 1 are the twins of nodes 3 and 2, respectively.

All of them have a twin sum of 6. There are no other nodes with twins in the linked list.

Thus, the maximum twin sum is 6.

Example 2:

Input: head = [4,2,2,3]
Output: 7

Explanation: The nodes with twins in this linked list are as follows:
– Node 0 is the twin of node 3, with a twin sum of 4 + 3 = 7.
– Node 1 is the twin of node 2, with a twin sum of 2 + 2 = 4. In this case, the maximum twin sum is max(7, 4), which is 7.

Example 3:

Input: head = [1,100000]
Output: 100001

Explanation: In this example, there is only one pair of nodes with twins in the linked list.

The twin sum is 1 + 100000 = 100001, which is also the maximum twin sum.

Constraints:

The number of nodes in the list is an even integer in the range [2, 105].
Each node's value (Node.val) is in the range [1, 105].

Now that we have a clear understanding of the problem, let's move on to the solution.

Understanding the Constraints

Before we dive into the solution, it's crucial to understand the constraints given in the problem statement.

These constraints help us determine the efficiency and feasibility of our solution.

Here's what we need to consider:

The linked list has an even number of nodes: This means we will always have pairs of nodes to compare.
The range of node values is [1, 105]: We don't need to worry about extreme values, making the problem manageable.

With these constraints in mind, let's move on to the solution.

Maximum Twin Sum Of A Linked List LeetCode Problem Solution

To solve this problem efficiently, we will use the two-pointer technique with a bit of linked list manipulation.

We'll explain our approach step by step.

1. Bruteforce Approach

A brute-force approach could involve iterating through all possible pairs of nodes and calculating their sums, keeping track of the maximum sum.

However, this approach would have a time complexity of O(n^2), which is not efficient for large input sizes.

2. An Efficient Approach with Linked List Reversal

To achieve a more efficient solution, we will follow these steps:

Initialize two pointers, slow and fast, to the head of the linked list.

We'll use these pointers to find the middle of the linked list.

Also, initialize a prev pointer, which will help us reverse the first half of the linked list.

While the fast pointer and fast.next are not null, we will move the fast pointer two steps forward and reverse the first half of the linked list by adjusting the next pointers.
After reaching the middle of the linked list, we will have slow at the beginning of the second half and prev at the end of the first half, with the prev pointers reversed.
Initialize a variable res to store the maximum twin sum, initially set to 0.
While the slow pointer is not null, we will calculate the twin sum as the sum of the values pointed to by prev and slow.

We will update res with the maximum of its current value and the calculated twin sum.

Move the prev and slow pointers to the next nodes and continue the process until we have considered all possible pairs.
Return the value stored in res as the maximum twin sum.

Python Code Solution

Here's the Python code implementation of our efficient approach:

View on GitHub ➹

class Solution:
    def pairSum(self, head):
        slow, fast = head, head
        prev = None

        # Find the middle of the linked list and reverse the first half
        while fast and fast.next:
            fast = fast.next.next
            tmp = slow.next
            slow.next = prev
            prev = slow
            slow = tmp

        res = 0

        # Calculate the maximum twin sum
        while slow:
            res = max(res, prev.val + slow.val)
            prev = prev.next
            slow = slow.next

        return res

This code efficiently finds the maximum twin sum of the linked list by reversing the first half of the list and then comparing pairs of nodes from both halves.

Time and Space Complexity

Let's analyze the time and space complexity of our solution:

Time Complexity: The time complexity of our solution is O(n), where n is the number of nodes in the linked list.

We iterate through the linked list twice, but the length of the list is always even, so we can consider it as O(n).

Space Complexity: The space complexity is O(1), which means our solution uses constant extra space.

We don't create any additional data structures that depend on the input size.

Reasoning Behind Our Approach

The reasoning behind our approach lies in optimizing the traversal of the linked list and efficiently finding the maximum twin sum.

We use the two-pointer technique to reach the middle of the linked list and reverse the first half to simplify the comparison of twin pairs.

By considering both halves of the list, we calculate the twin sums and keep track of the maximum sum.

This approach minimizes memory usage and runtime, making it a robust solution for the given problem.

Conclusion

In this blog post, we tackled the LeetCode problem Maximum Twin Sum Of A Linked List with a detailed Python solution.

We explained the problem, considered the constraints, and presented an efficient approach that uses the two-pointer technique and linked list manipulation.

The code solution has a time complexity of O(n) and a space complexity of O(1), making it an optimal solution for finding the maximum twin sum in a linked list.

If you found this guide helpful, please consider liking and subscribing for more coding and algorithm-related content.

And remember, coding challenges like this one are an excellent way to improve your problem-solving skills and prepare

for coding interviews.

For the original problem statement and more details, you can visit the LeetCode problem page.

Happy coding!