Skip to content
Katabench
Try free

Sum of Absolute Differences

Medium About 20 min Free, no account needed

For each element of a sorted array, the total distance to all the others.

The brief

Given an integer array nums sorted in non-decreasing order, return an array result where result[i] is the sum of |nums[i] - nums[j]| over every other index j.

The performance bar

The obvious approach compares every pair, O(n2). The hidden test has 100,000 elements, so the quadratic version is too slow. You need O(n), and the array being sorted is the lever: at each index the smaller and larger elements sit on known sides.

Starter code

C#
using System;

public class Solution
{
    // TODO: return result[i] = sum over j of |nums[i] - nums[j]| (input sorted ascending).
    public long[] SumOfAbsoluteDifferences(int[] nums)
    {
        throw new NotImplementedException();
    }
}

How it is graded

Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.

C# coding challenges →

What it practices

Prefix sums
Carry running totals or prefix state so any range question becomes a lookup.

Related katas