Maximum Twin Sum of a Linked List

Medium

Microsoft

1 view

Topics:

Linked ListsTwo Pointers

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.

Could you provide an algorithm to solve the maximum twin sum of a linked list? What is the time and space complexity of your approach? Are there any edge cases to consider?

Maximum Twin Sum of a Linked List

Medium

Microsoft

1 view

Topics:

Linked ListsTwo Pointers

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.

Could you provide an algorithm to solve the maximum twin sum of a linked list? What is the time and space complexity of your approach? Are there any edge cases to consider?

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the nodes in the linked list?
Can the linked list ever be empty, or will it always have at least two nodes?
Can you provide an example of a linked list and the expected output?
Is the length of the linked list always guaranteed to be even?
Is there any concern about integer overflow when calculating the twin sum?

Brute Force Solution

Approach

We need to find the largest sum of pairs in a linked list, where each pair is formed by the first and last node, the second and second-to-last node, and so on. A brute-force method systematically checks all possible pairings to find the one with the maximum sum. This involves examining every possible combination of 'twin' nodes and comparing their sums.

Here's how the algorithm would work step-by-step:

First, go through the entire linked list and store the value of each node.
Then, consider the first node and the last node as a pair. Calculate the sum of their values.
Next, consider the second node and the second-to-last node. Calculate the sum of their values.
Continue pairing nodes in this way, moving from the beginning and the end towards the middle of the list. Calculate the sum for each pair.
As you calculate each sum, compare it to the largest sum you've found so far. If the current sum is larger, remember it as the new largest sum.
Once you've considered all possible pairs, the largest sum you've remembered is the maximum twin sum of the linked list.

Code Implementation

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def maximum_twin_sum_brute_force(head):
    node_values = []
    current_node = head
    while current_node:
        node_values.append(current_node.val)
        current_node = current_node.next

    maximum_sum = 0
    list_length = len(node_values)

    # Iterate up to the middle to pair nodes from start and end
    for first_node_index in range(list_length // 2):
        second_node_index = list_length - 1 - first_node_index
        current_sum = node_values[first_node_index] + node_values[second_node_index]

        # Keep track of largest twin sum found so far
        if current_sum > maximum_sum:

            maximum_sum = current_sum

    return maximum_sum

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through the linked list once to store the values in an array, which takes O(n) time. The nested pairing process then compares each element with every other element to find twin sums. This involves comparing approximately n * (n-1) / 2 pairs. Therefore, the overall time complexity is dominated by the pair checking operation, which simplifies to O(n²).

Space Complexity

O(N) – The algorithm stores the value of each node in a linked list of size N. This requires creating an auxiliary data structure, specifically an array (or list), to hold these N values. Therefore, the auxiliary space used grows linearly with the input size N. Hence, the space complexity is O(N).

Optimal Solution

Approach

The challenge involves finding the largest sum of pairs in a linked list where the pairs are formed by matching the first node with the last, the second with the second-to-last, and so on. We can efficiently solve this by reversing the second half of the list and then comparing corresponding node values.

Here's how the algorithm would work step-by-step:

First, find the middle of the linked list.
Next, reverse the second half of the linked list, starting from the middle.
Now, traverse the original linked list from the beginning and the reversed second half simultaneously.
In each step, calculate the sum of the corresponding nodes from both halves.
Keep track of the maximum sum encountered during this process.
Finally, return the maximum twin sum.

Code Implementation

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def maximum_twin_sum(head):
    slow_pointer = head
    fast_pointer = head

    # Find the middle of the linked list
    while fast_pointer and fast_pointer.next:
        slow_pointer = slow_pointer.next
        fast_pointer = fast_pointer.next.next

    # Reverse the second half of the linked list
    previous_node = None
    current_node = slow_pointer
    while current_node:
        next_node = current_node.next
        current_node.next = previous_node
        previous_node = current_node
        current_node = next_node

    left_pointer = head
    right_pointer = previous_node
    maximum_sum = 0

    # Calculate the maximum twin sum by comparing values
    while right_pointer:
        current_sum = left_pointer.val + right_pointer.val

        # Store the running maximum twin sum
        maximum_sum = max(maximum_sum, current_sum)

        left_pointer = left_pointer.next
        right_pointer = right_pointer.next

    return maximum_sum

Big(O) Analysis

Time Complexity

O(n) – Finding the middle of the linked list involves traversing roughly n/2 nodes, which is O(n). Reversing the second half of the list also takes O(n/2) time, which simplifies to O(n). Finally, calculating the twin sums by traversing both halves of the list takes O(n/2) + O(n/2) time, also O(n). The dominant term is O(n), representing the overall time complexity.

Space Complexity

O(1) – The algorithm reverses the second half of the linked list in place, meaning it modifies the existing linked list structure rather than creating a new one. It uses a few pointer variables during the reversal process (previous, current, next) and during the sum calculation. These variables consume a constant amount of space regardless of the length N of the linked list. Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Null head input	Return 0 immediately as an empty list has no twin sums.
Linked list with only two nodes	The algorithm correctly calculates the sum of the two nodes as the maximum twin sum.
Linked list with a large number of nodes (close to memory limits)	The space complexity should be O(n/2) if using a stack or array to store the first half, so ensure the memory usage is acceptable for very large inputs, possibly by considering an in-place reversal of the first half of the list.
Linked list with all nodes having the same value	The algorithm correctly calculates the twin sum (which will be the same for all twins) and returns it.
Linked list with nodes containing negative values	The algorithm correctly handles negative values when calculating the twin sums, and finds the maximum.
Linked list with extreme boundary values that could cause integer overflow in the sum	Use a data type with a larger range (e.g., long) to store the twin sums to prevent overflow.
Linked list with a very skewed distribution of node values (e.g., one very large value and many small values)	The algorithm correctly calculates the twin sums, even if the distribution is skewed, by summing each node with its corresponding twin and finding the maximum.
Linked list length is not even	Handle this case by returning an error or throwing an exception, or by truncating the list in some sensible way, because it violates the problem definition.