3727. Maximum Alternating Sum of Squares

Time: O(n + V)

Space: O(V)

Problem Overview

You may rearrange the array freely, and the score adds the squares at even indices and subtracts the squares at odd indices.

Intuition

You may rearrange the array freely, and the score adds the squares at even indices and subtracts the squares at odd indices. With n elements there are n / 2 odd slots, so exactly n / 2 squares are subtracted and the rest are added. To make the score as large as possible, the subtracted squares should be the smallest ones. The score is then the total of all squares minus twice the smallest half. A square depends only on the absolute value, and those values are small, so counting them replaces a full sort.

Algorithm

1In one pass, add every square to a 64-bit total and record the largest absolute value.
2Count how many times each absolute value appears.
3Walk the counts from 0 upward, taking values until n / 2 of them have been taken, and add up their squares.
4Return the total minus twice that smallest half sum.

Example Walkthrough

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

1.The squares are 1, 1, 4, 4, 9, 9, which add up to 28.
2.n / 2 is 3, so the three smallest squares 1, 1, and 4 are subtracted. Their sum is 6.
3.An order such as [3,1,-3,-1,2,-2] adds 9, 9, and 4 and subtracts 1, 1, and 4.
4.The score is 28 minus 2 times 6.

Output: 16

Common Pitfalls

•Negative numbers have the same square as their absolute value, so sort or count by absolute value.
•With an odd length, the extra element goes to an even index and is added, so only n / 2 squares are subtracted.
•Squares can reach 1.6e9, and their sum overflows an int. Keep the total in a long.
•Sorting works but costs n log n time. Counting the small absolute values is linear.

3727.cs

// Approach: After rearranging, n / 2 squares are subtracted and the rest are
// added, so subtract the n / 2 smallest squares. That gives the total of all
// squares minus twice the sum of the smallest half. A square only depends on
// |x|, so counting absolute values replaces the sort, and walking the counts
// from 0 upward collects the smallest half.
// Time: O(n + V) Space: O(V), where V is the largest |nums[i]|

public class Solution
{
    public long MaxAlternatingSum(int[] nums)
    {
        int maxAbs = 0;
        long total = 0;
        foreach (int x in nums)
        {
            int a = x < 0 ? -x : x;
            if (a > maxAbs)
                maxAbs = a;
            total += (long)a * a;
        }

        int[] count = new int[maxAbs + 1];
        foreach (int x in nums)
            count[x < 0 ? -x : x]++;

        long smallest = 0;
        int need = nums.Length / 2;
        for (int v = 0; need > 0; v++)
        {
            int take = Math.Min(count[v], need);
            smallest += (long)take * v * v;
            need -= take;
        }
        return total - 2 * smallest;
    }
}

Was this solution helpful?