Maximum Twin Sum of a Linked List
MedPrompt
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 node0is the twin of node3, and node1is the twin of node2. These are the only nodes with twins forn = 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. Example 3:
Input: head = [1,100000]
Output: 100001
Explanation:
There is only one node with a twin in the linked list having twin sum of 1 + 100000 = 100001.
Constraints:
- The number of nodes in the list is an even integer in the range
[2, 105]. 1 <= Node.val <= 105
Approaches
2 approaches with complexity analysis and trade-offs.
A straightforward approach is to first convert the linked list into a more flexible data structure like an ArrayList. By storing all node values in an array, we can easily access any element by its index. This allows us to pair the i-th element with the (n-1-i)-th element directly.
Algorithm
- Create an empty
java.util.ArrayList<Integer>to store the node values. - Traverse the linked list from the
head, adding each node's value to theArrayList. - Initialize a variable
maxTwinSumto 0. - Initialize two pointers,
left = 0andright = list.size() - 1. - Loop while
left < right:- a. Calculate
currentSum = list.get(left) + list.get(right). - b. Update
maxTwinSum = Math.max(maxTwinSum, currentSum). - c. Increment
leftand decrementright.
- a. Calculate
- Return
maxTwinSum.
Walkthrough
First, we iterate through the entire linked list from head to tail. During this traversal, we add the value of each node to an ArrayList. After the list is fully traversed, the ArrayList contains all the node values in order.
We then use a two-pointer technique on the ArrayList. One pointer (left) starts at the beginning (index 0), and the other (right) starts at the end (index n-1). We iterate as long as left is less than right. In each iteration, we calculate the sum of the values at the left and right indices, which corresponds to a twin sum. We keep track of the maximum sum found so far. After each sum calculation, we move the pointers closer to the center (left++, right--). The loop terminates when the pointers meet or cross, at which point we have checked all twin pairs. The maximum sum recorded is the result.
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */class Solution { public int pairSum(ListNode head) { java.util.List<Integer> values = new java.util.ArrayList<>(); ListNode current = head; while (current != null) { values.add(current.val); current = current.next; } int left = 0; int right = values.size() - 1; int maxTwinSum = 0; while (left < right) { int currentSum = values.get(left) + values.get(right); maxTwinSum = Math.max(maxTwinSum, currentSum); left++; right--; } return maxTwinSum; }}Complexity
Time
O(n), where n is the number of nodes. The first traversal to populate the list takes O(n) time, and the second pass with two pointers takes O(n/2) = O(n) time.
Space
O(n), as we need an `ArrayList` to store the values of all n nodes in the linked list.
Trade-offs
Pros
Simple to understand and implement.
Does not modify the original linked list structure.
Cons
Requires extra space proportional to the size of the linked list, which can be significant for large lists.
Solutions
Solution
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public int pairSum ( ListNode head ) { List < Integer > s = new ArrayList <>(); for (; head != null ; head = head . next ) { s . add ( head . val ); } int ans = 0 , n = s . size (); for ( int i = 0 ; i < ( n >> 1 ); ++ i ) { ans = Math . max ( ans , s . get ( i ) + s . get ( n - 1 - i )); } return ans ; } }Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.