320. Twin Totals
A relay team stands in a line stored as a chain with an even number of runners, and each node holds one runner's speed score. The coach pairs the runners symmetrically: the first runner with the last, the second with the second to last, and so on, until the middle is reached. Each such pair is called a twin pair.
Given the head of the chain, which always has an even length, compute the sum of the two scores in every twin pair and return the largest of these sums. The chain may hold up to 100,000 nodes, and you cannot index into it, so walking from the end to find each partner would be far too slow. Try to find the middle first and match the two halves in a single pass.
Example 1
- Input:
- head = [3,8,2,9,4,6]
- Output:
- 12
- Explanation:
The twin pairs are (3, 6), (8, 4) and (2, 9) with sums 9, 12 and 11, so the answer is 12.
Example 2
- Input:
- head = [40,15,15,40]
- Output:
- 80
- Explanation:
The pairs are (40, 40) with sum 80 and (15, 15) with sum 30, so the answer is 80.
Constraints
2 ≤ chain length ≤ 105, and the length is even
-105 ≤ node value ≤ 105
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,600 msC++ 400 msJava 800 msJavaScript 800 msTypeScript 800 ms
Expected complexity
- Time
- O(n)
- Space
- O(1)