Skip to main content
Talentd

Maximum Alternating Sum of Squares - Solution & Explanation

MediumArrayGreedySorting7 min read
Practice this problem

Problem Statement

You are given an integer array nums. You may rearrange the elements in any order.

The alternating score of an array arr is defined as:

  • score = arr[0]2 - arr[1]2 + arr[2]2 - arr[3]2 + ...

Return an integer denoting the maximum possible alternating score of nums after rearranging its elements.

 

Example 1:

Input: nums = [1,2,3]

Output: 12

Explanation:

A possible rearrangement for nums is [2,1,3], which gives the maximum alternating score among all possible rearrangements.

The alternating score is calculated as:

score = 22 - 12 + 32 = 4 - 1 + 9 = 12

Example 2:

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

Output: 16

Explanation:

A possible rearrangement for nums is [-3,-1,-2,1,3,2], which gives the maximum alternating score among all possible rearrangements.

The alternating score is calculated as:

score = (-3)2 - (-1)2 + (-2)2 - (1)2 + (3)2 - (2)2 = 9 - 1 + 4 - 1 + 9 - 4 = 16

 

Constraints:

  • 1 <= nums.length <= 105
  • -4 * 104 <= nums[i] <= 4 * 104

Approach Overview

Problem Overview: You are given an array and must arrange the numbers to maximize an alternating expression of squared values: a1^2 - a2^2 + a3^2 - a4^2 .... The order of elements can be rearranged, so the goal is to place numbers in positions that maximize the final alternating sum.

Approach 1: Brute Force Permutations (O(n!))

The most direct approach tries every possible permutation of the array. For each permutation, compute the alternating sum of squares by iterating through the sequence and adding or subtracting nums[i]^2 depending on the index parity. Track the maximum result across all permutations. This guarantees correctness but becomes infeasible quickly because the number of permutations grows factorially. Time complexity is O(n!) and space complexity is O(n) for recursion or permutation storage.

Approach 2: Greedy Sorting (O(n log n))

The key observation: positions with a + sign should contain the largest squared values, while - positions should contain the smallest. Since squaring preserves order for non-negative magnitude comparisons, maximizing the expression reduces to selecting the largest values for the positive slots and the smallest for the negative slots. First compute or compare based on squared values, then sort the array. Assign the largest elements to indices contributing positively (0, 2, 4, ...) and the smallest elements to negative positions (1, 3, 5, ...). This greedy placement ensures the positive contributions dominate the subtraction terms.

This approach uses standard sorting followed by a single pass to compute the alternating sum. Sorting takes O(n log n) time and the final scan takes O(n). Extra space is O(1) if the array is sorted in place. The method relies on greedy reasoning: maximize positive contributions and minimize negative ones.

Conceptually, this problem combines array manipulation with greedy ordering strategies. Understanding how value magnitude affects the alternating expression is the main trick. Related techniques appear in problems involving rearranging values to optimize expressions using greedy algorithms, ordering elements with sorting, and iterating efficiently over an array.

Recommended for interviews: The greedy sorting approach is what interviewers expect. Mentioning the brute force permutation strategy shows you understand the search space, but recognizing that the largest squares should occupy positive positions demonstrates algorithmic insight. Implementing the sorted greedy solution with O(n log n) time and O(1) extra space is typically considered the optimal answer.

Solution

We can sort the elements of the array by their squared values, then place the elements with larger squared values at even indices and those with smaller squared values at odd indices.

The final alternating score is the sum of the squared values of the larger elements minus the sum of the squared values of the smaller elements, that is, the sum of the squares of the latter half of the sorted array nums minus the sum of the squares of the first half.

The time complexity is O(n log n) and the space complexity is O(log n), where n is the length of the array.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force PermutationsO(n!)O(n)Useful only for understanding the problem or very small arrays
Greedy with SortingO(n log n)O(1)General optimal approach; sort values then assign largest squares to positive positions

Video Solution

Maximum Alternating Sum of Squares|contest 473|leetcode contest 473 |leetcode contest 473 solution • Code Thoughts • 83 views views

Watch 2 more video solutions →

Frequently Asked Questions

Is Maximum Alternating Sum of Squares easy or hard?
Maximum Alternating Sum of Squares is generally considered a Medium-level problem. The implementation is straightforward once you recognize the greedy insight that larger squares should appear in positive positions. Identifying that ordering determines the optimal result is the main challenge.
Maximum Alternating Sum of Squares Python/Java solution
The typical implementation sorts the input array, then iterates through it while alternating between adding and subtracting squared values. This logic translates directly to Python, Java, C++, Go, or TypeScript with built-in sorting functions and a simple loop.
How to solve Maximum Alternating Sum of Squares in O(n)?
A strict O(n) solution generally is not used because the algorithm relies on ordering elements by magnitude. Determining which elements should occupy positive versus negative positions requires sorting, leading to O(n log n) complexity. Once sorted, the alternating sum can be computed in O(n).
What is the best approach for Maximum Alternating Sum of Squares?
The most effective solution uses a greedy strategy with sorting. Sort the array and place the largest values in positions contributing positively to the alternating expression while assigning the smallest values to negative positions. This maximizes the difference between added and subtracted squared values and runs in O(n log n) time with O(1) extra space.
Is Maximum Alternating Sum of Squares asked at Google/Amazon/Meta?
Problems involving rearranging arrays to maximize expressions appear frequently in interviews at companies like Amazon, Google, and Meta. While the exact problem name may vary, the underlying pattern—sorting combined with greedy placement—is a common interview topic.
What data structure is used in Maximum Alternating Sum of Squares?
The main data structure is a simple array. The algorithm relies on sorting the array and iterating through it to compute the alternating sum of squared values. No additional complex structures such as hash maps or trees are required.
What is the time complexity of Maximum Alternating Sum of Squares?
The optimal approach runs in O(n log n) time due to sorting the array. After sorting, computing the alternating sum of squares requires a single linear scan, which is O(n). Space complexity is O(1) if sorting is done in place.

Ready to solve this problem?

Practice Maximum Alternating Sum of Squares with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays