LeetCode Problem 3727

Difficulty: 🟡 Medium
Topics: Array, Greedy, Sorting

Solution

LeetCode 3727 - Maximum Alternating Sum of Squares

Problem Understanding

We are given an integer array nums, and we are allowed to rearrange its elements in any order before computing a score.

The score of a rearranged array arr is defined as:

$$arr[0]^2 - arr[1]^2 + arr[2]^2 - arr[3]^2 + \cdots$$

The sign alternates between positive and negative positions. Elements at even indices contribute their square positively, while elements at odd indices contribute their square negatively.

The key observation is that the actual value of each element does not matter after squaring. A number such as 3 and -3 both contribute 9. Therefore, the problem effectively becomes arranging the squared values so that the largest possible values receive positive signs and the smallest possible values receive negative signs.

The input array can contain up to 10^5 elements, which immediately rules out any algorithm that tries all permutations. Since the values themselves are bounded by ±40000, their squares fit comfortably inside a 64 bit integer, but the total sum can exceed 32 bit limits. This is why the Go signature returns int64.

Several edge cases are worth considering:

• Arrays of length 1, where the only element receives a positive sign.
• Arrays containing both positive and negative numbers with identical absolute values.
• Arrays where every value is zero.
• Arrays with an odd number of elements, causing one more positive position than negative positions.
• Arrays with very large magnitudes, requiring 64 bit arithmetic.

Approaches

Brute Force

A brute force solution would generate every possible permutation of the array. For each permutation, we would compute the alternating sum of squares and keep the maximum result.

This approach is correct because it explicitly examines every possible arrangement and therefore cannot miss the optimal one.

Unfortunately, an array of length n has n! permutations. Even for relatively small values of n, this becomes computationally impossible. Since n can be as large as 100000, brute force is completely infeasible.

Key Insight

Because every element is squared before contributing to the score, only its squared value matters.

Let:

$$v_i = nums[i]^2$$

The problem becomes:

$$+v_{a_1} - v_{a_2} + v_{a_3} - v_{a_4} + \cdots$$

Suppose two values x and y satisfy x ≥ y.

If one of them occupies a positive position and the other occupies a negative position, the contribution is maximized when:

$$+x - y$$

rather than:

$$+y - x$$

The difference between these two choices is:

$$(x-y) - (y-x) = 2(x-y) \ge 0$$

Therefore, larger squared values should always be assigned to positive positions whenever possible.

Since there are a fixed number of positive slots and negative slots, the optimal strategy is:

1. Compute all squared values.
2. Sort them in descending order.
3. Assign signs alternately starting with positive.

After sorting descending:

$$v_1 \ge v_2 \ge v_3 \ge \cdots$$

the optimal score becomes:

$$v_1 - v_2 + v_3 - v_4 + \cdots$$

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n! · n)	O(n)	Enumerates every permutation
Optimal	O(n log n)	O(n)	Sort squared values and alternate signs

Algorithm Walkthrough

Optimal Algorithm

1. Create a new array containing the square of every element in nums.

This transforms the problem into working only with nonnegative values, since signs disappear after squaring. 2. Sort the squared values in descending order.

The largest values should be placed in positions that receive positive signs. 3. Initialize an accumulator answer = 0. 4. Iterate through the sorted array.

If the index is even, add the value to the answer because even positions receive positive signs. 5. If the index is odd, subtract the value from the answer because odd positions receive negative signs. 6. After processing all values, return the accumulated answer.

Why it works

After squaring, the score depends only on assigning values to positive and negative positions. Any larger value contributes more when placed in a positive position than in a negative position. Sorting in descending order guarantees that every larger value is paired with a positive sign before any smaller value can claim that positive position. By an exchange argument, any arrangement violating this property can be improved by swapping elements. Therefore the descending order arrangement produces the maximum possible alternating score.

Python Solution

from typing import List

class Solution:
    def maxAlternatingSum(self, nums: List[int]) -> int:
        squares = [x * x for x in nums]
        squares.sort(reverse=True)

        answer = 0

        for i, value in enumerate(squares):
            if i % 2 == 0:
                answer += value
            else:
                answer -= value

        return answer

The implementation first converts every element into its square. This removes any distinction between positive and negative numbers because both contribute the same squared value.

The squared values are then sorted in descending order. Once sorted, the largest value naturally occupies the first positive slot, the second largest occupies the first negative slot, the third largest occupies the second positive slot, and so on.

The final loop computes the alternating sum directly. Even indices are added and odd indices are subtracted. The resulting value is returned as the maximum achievable score.

Go Solution

package main

import "sort"

func maxAlternatingSum(nums []int) int64 {
	squares := make([]int64, len(nums))

	for i, x := range nums {
		v := int64(x)
		squares[i] = v * v
	}

	sort.Slice(squares, func(i, j int) bool {
		return squares[i] > squares[j]
	})

	var answer int64 = 0

	for i, value := range squares {
		if i%2 == 0 {
			answer += value
		} else {
			answer -= value
		}
	}

	return answer
}

The Go implementation follows the same logic as the Python version. The primary difference is that all squared values are stored as int64 to avoid overflow when summing many large squares. The built in sort.Slice function is used to sort in descending order.

Worked Examples

Example 1

Input

nums = [1, 2, 3]

Step 1: Square all values

Original	Square
1	1
2	4
3	9

Result:

[1, 4, 9]

Step 2: Sort descending

[9, 4, 1]

Step 3: Compute alternating score

Index	Value	Sign	Running Total
0	9	+	9
1	4	-	5
2	1	+	6

Final answer:

6

One corresponding arrangement is:

[3, 2, 1]

whose score is:

3² - 2² + 1² = 9 - 4 + 1 = 6

Example 2

Input

nums = [1, -1, 2, -2, 3, -3]

Step 1: Square all values

[1, 1, 4, 4, 9, 9]

Step 2: Sort descending

[9, 9, 4, 4, 1, 1]

Step 3: Compute alternating score

Index	Value	Sign	Running Total
0	9	+	9
1	9	-	0
2	4	+	4
3	4	-	0
4	1	+	1
5	1	-	0

Final answer:

0

A valid arrangement achieving this score is:

[3, -3, 2, -2, 1, -1]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting dominates the running time
Space	O(n)	Stores the squared values

The squaring pass requires linear time. The sorting step requires O(n log n) time, which dominates the overall complexity. The algorithm stores a separate array of squared values, resulting in O(n) auxiliary space.

Test Cases

sol = Solution()

assert sol.maxAlternatingSum([1, 2, 3]) == 6          # basic increasing values
assert sol.maxAlternatingSum([1, -1, 2, -2, 3, -3]) == 0  # duplicate squares

assert sol.maxAlternatingSum([5]) == 25              # single element
assert sol.maxAlternatingSum([0]) == 0               # single zero

assert sol.maxAlternatingSum([0, 0, 0]) == 0         # all zeros

assert sol.maxAlternatingSum([-4, -3, -2, -1]) == 10 # all negative values

assert sol.maxAlternatingSum([10, -10]) == 0         # equal squares

assert sol.maxAlternatingSum([1, 100]) == 9999       # largest square positive

assert sol.maxAlternatingSum([40000]) == 1600000000  # maximum magnitude

assert sol.maxAlternatingSum([2, 2, 2, 2, 2]) == 4  # repeated values

assert sol.maxAlternatingSum([1, 2, 3, 4, 5]) == 15 # odd length

assert sol.maxAlternatingSum([1, 2, 3, 4]) == 4     # even length

Test Summary

Test	Why
[1,2,3]	Basic example
[1,-1,2,-2,3,-3]	Duplicate squared values
[5]	Single element
[0]	Smallest possible score
[0,0,0]	All values identical
[-4,-3,-2,-1]	All negative inputs
[10,-10]	Equal absolute values
[1,100]	Strongly unbalanced magnitudes
[40000]	Maximum allowed magnitude
[2,2,2,2,2]	Repeated values
[1,2,3,4,5]	Odd length array
[1,2,3,4]	Even length array

Edge Cases

Single Element Array

When the array contains only one element, there is only a single positive position and no negative positions. The answer is simply the square of that element. The algorithm handles this naturally because the sorted array contains one value and the loop adds it.

Multiple Values With The Same Square

Values such as 3 and -3 produce the same squared value. A buggy solution might incorrectly try to exploit the original sign. Since only squares matter, equal squared values are interchangeable. Sorting squared values correctly treats them as identical contributions.

All Zeros

If every element is zero, every squared value is also zero. Regardless of the arrangement, the score remains zero. The algorithm sorts the zeros and alternately adds and subtracts them, producing zero as expected.

Odd Number Of Elements

An odd length array contains one more positive position than negative positions. This means the smallest remaining value after pairing still receives a positive sign. Sorting descending automatically places the extra value at the end of the alternating pattern, ensuring the maximum score.

Large Magnitudes

The maximum element magnitude is 40000, whose square is 1,600,000,000. Summing many such values can exceed a 32 bit integer. The Go implementation explicitly uses int64, ensuring correct behavior for the largest possible inputs.