462. Minimum Moves to Equal Array Elements II

Problem Overview

One move raises or lowers a single element by 1, and every element must finish on the same value.

Intuition

One move raises or lowers a single element by 1, and every element must finish on the same value. The meeting value that minimizes the total travel is a median. For an odd length that is the middle element. For an even length either of the two central elements gives the same total, so the lower of those two ranks is enough. Three way quickselect finds the element at rank (n minus 1) divided by 2. A random pivot splits the active range into values below the pivot, values equal to it, and values above it. When the rank falls inside the equal band, the pivot is the median and the search stops. Otherwise the search continues in the one band that still holds the rank. Grouping the equal values together finishes a long run of duplicates in a single partition. The search is a loop, so the call stack stays flat. After the median is known, each element contributes the absolute gap between itself and that median. The gaps are added in a 64 bit integer, because a long array of large gaps can pass 2 to the 31 before the total is returned as an int.

Algorithm

1Ask three way quickselect for the element at rank (n minus 1) divided by 2.
2Pick a random pivot in the active range and split that range into a lower band, an equal band, and an upper band.
3Return the pivot when the rank sits in the equal band. Otherwise shrink the range to the band that contains the rank.
4Add the absolute gap from every element to that median in a 64 bit integer.
5Return the total.

Example Walkthrough

Input: nums = [1, 2, 3]

1.The middle rank is 1, and the value there is 2.
2.The gaps from 2 are 1, 0, and 1.
3.Two moves turn the array into [2, 2, 2].

Output: 2

Common Pitfalls

•For an even length, either central value gives the same total. Rank (n minus 1) divided by 2 selects the lower one.
•A split that keeps equals on one side partitions a run of duplicates over and over. The equal band finishes that run at once.
•The sum of the gaps can pass a 32 bit integer. The total is accumulated in a 64 bit integer.
•Quickselect rearranges the array while it searches. The gaps are read after the median is known.

462.cs

// Approach: The value that minimizes the total of increments and decrements
// is a median. Three way quickselect finds it. Values equal to the pivot
// land in one band, so a long run of duplicates ends in a single partition.
// The search is a loop. The move count is the sum of absolute gaps from
// that median, accumulated in a 64 bit integer.
// Time: O(n) average Space: O(1)

public class Solution
{
    public int MinMoves2(int[] nums)
    {
        int median = Select(nums, (nums.Length - 1) / 2);
        long moves = 0;
        for (int i = 0; i < nums.Length; i++)
            moves += Math.Abs((long)nums[i] - median);
        return (int)moves;
    }

    private static int Select(int[] nums, int k)
    {
        int left = 0;
        int right = nums.Length - 1;
        while (left <= right)
        {
            int pivot = nums[Random.Shared.Next(left, right + 1)];
            int lt = left;
            int i = left;
            int gt = right;
            while (i <= gt)
            {
                if (nums[i] < pivot)
                    Swap(nums, lt++, i++);
                else if (nums[i] > pivot)
                    Swap(nums, i, gt--);
                else
                    i++;
            }

            if (k < lt)
                right = lt - 1;
            else if (k > gt)
                left = gt + 1;
            else
                return pivot;
        }
        return nums[k];
    }

    private static void Swap(int[] nums, int i, int j)
    {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

Was this solution helpful?