14 ms java O(n) solution, very intuitive idea


  • 0
    G

    my idea is, for anyone that need give out X , X might be the max move number, for example, input is [0, 3, 0], other than that, the math.abs() of aggregated move needed so far need be compared to the current maxMove.

    public class Solution {
    public int findMinMoves(int[] m) {
    if(m == null || m.length == 0)
    {
    return -1;
    }

        int sum = 0;
        for(int i:m)
        {
            sum+=i;
        }
        
        if(sum%m.length !=0)
        {
            return -1;
        }
        
        int avg = sum/m.length;
        int maxMove = 0;
        int maxMoveAbs = 0 ;
        
        
        for(int i:m)
        {
            int delta = i -avg;
            if(delta == 0)
            {
                continue;
            }
            
            maxMove  = maxMove + delta;
            if(delta > 0)
            {
                //to give out
                maxMoveAbs =  Math.max(maxMoveAbs, delta));
            }
            maxMoveAbs =  Math.max(maxMoveAbs, Math.abs(maxMove));
            
        }
        return maxMoveAbs;
    }
    

    }


  • 0
    G

Log in to reply
 

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