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 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
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.
What it practices
- Prefix sums
- Carry running totals or prefix state so any range question becomes a lookup.
Related katas
- Contiguous Array Medium Free Longest subarray holding as many zeros as ones.
- Product of Array Except Self Medium Free For each index, return the product of all other elements, without division.
- Subarray Sum Equals K Medium Free Count contiguous subarrays whose elements sum to a target k.
- Subarrays Divisible by K Medium Free Count the subarrays whose sum is divisible by k.