A C++ solution with explanations (different than others).


  • 0
    G
    class Solution {
    public:
        
        //
        // first sort the array.
        // the min Moves = Sum of partial sums of all differences between elements
        // for example: (1,4,6,10) -> Differences = (3,2,4)-> Partial_Sums = (3,5,9) -> Sum of Partial Sums = 17
        // Why ? Think of the diffrences as the minimum we have to move to get each element to equal to its neighbor.
        // the partial sums tells us for each i the minumum moves to make the first element equal to the (i + 1)th element in the original array.
        // But since we dont just change one element at a time but rather we change n - 1 at a time, for each i in partial sums
        // the sum of elements up to including i of the partial sums will tell us all the moves to make all elements between 1 to i + 1 equal.
        // it is best to play with examples and see this for yourself.
        //
        
        int minMoves(vector<int>& nums) 
        {
            sort(nums.begin(),nums.end());
            
            vector<int> Dists;
            Dists.reserve(nums.size() - 1);
            
            for(int i = 1; i < nums.size(); ++i)
            {
                Dists.push_back(nums[i] - nums[i - 1]);
            }
            
            vector<int> Sums(Dists.size());
            partial_sum(Dists.begin(),Dists.end(),Sums.begin());
            return accumulate(Sums.begin(),Sums.end(),0);
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.