Java solution with thinking process


  • 7
    Z

    Hi there! I am sharing my full thinking process under time pressure and solution. The resultant array elements must be all the same. Let's say some integer k, so final array looks like [k,k,k,...,k]. The number of moves to get that array can be calculated by, moves = |k - a1| + |k-a2| + ...+|k-ai|+...+|k-an|. Note that some elements are greater than k and some elements are less. Thus, it worth to know the number of elements that are less than k, and the number of elements that are greater that k. If know them we can reformulate the equation as moves = Nlessk - sumLess +sumGreater-Ngreaterk. Now the equation gets more "programmable", and we have to search for such k, that minimizes value of moves. It is obvious that k must be selected among the original array elements, because it reduces the number of operations at least by one. Thus, we came up with an idea. For each element in array calculate moves, then select minimum among them. Now, we see another problem, how to calculate them number of elements that are less than k and their sum? The same problem occurs for greater elements. Naive solution is to calculate number of smalles elements and greater elements along with their sum for each element of the array seperately. That would give us solution with O(n^2) time complexity.
    Can we do better? Yes we can, if we sort out the original array first, we can immediately know both the number of elements that are less than the current element and the number of elements that are greater that the current element. In addition we have to know total sum of elements and sum of elements before each element. Finally we came up with O(nlog(n)) time and O(1) space solution! Below is the code for that solution:

    public class Solution {
        public int minMoves2(int[] nums) {
            if(nums==null||  nums.length==0) return 0;
            long moves = Integer.MAX_VALUE;
            Arrays.sort(nums);
            long totalSum = 0L;
            long sum = 0L;
            for(int i =0;i<nums.length;i++){
                totalSum += (long)nums[i];
            }
            for(int i =0;i<nums.length;i++){
                long m = (long)(i-(nums.length-i-1)-1)*(long)nums[i]-sum+(totalSum-sum);
                moves = Math.min(m, moves);
                sum+=nums[i];
            }
            return (int)moves;
        }
    }
    

    Can we do better? Yes, we can! Let's think about k. Intuitively that value must be the median element in the original sorted array. Proof of that fact is simple, just look at our equation moves = numLessk-sumLess + sumGreater - numGreaterk. Let's take derivative from that function by k. dmoves/dk = numLess-numGreater. The moves becomes minimum when the derivative is zero, so numLess-numGreater = 0 or numsLess = numGreater. Which is possible only when the element is the median element. We can find k in O(1) time. Instead of brute forcing all elements in the array we just consider the middle element in the sorted array. Despite generally the time complexity remains being O(nlog(n)), due to sorting, it improves performance very much. Further it can be optimized up to O(n), by using Quick select algorithm, and you can find this solution here

    public class Solution {
        public int minMoves2(int[] nums) {
            if(nums==null||  nums.length==0) return 0;
            long moves = Integer.MAX_VALUE;
            Arrays.sort(nums);
            long totalSum = 0L;
            long sum = 0L;
            for(int i =0;i<nums.length;i++){
                totalSum += (long)nums[i];
               if(i<nums.length/2) sum+=(long)nums[i];
            }
           
            int k = nums.length/2;
            moves = (long)(k-(nums.length-k-1)-1)*(long)nums[k]-sum+(totalSum-sum);
               
            return (int)moves;
        }
    }
    

    P.S: I have demonstrated the calculation of moves to be understandable, that is why it looks poor. Also be careful with shortening equation for moves in the first code. Because it may exceed the integer range if not to be careful with multiplications. Sorry for poor code.


  • 1
    J

    Thanks for sharing.

    It is obvious that k must be selected among the original array elements, because it reduces the number of operations at least by one.

    It doesn't sound very obvious to me though. Can you explain more on this?


  • 0
    Z

    @jonsnow1984 Hi! Let's consider some number k that does not belong to the array (Final array [k,k,k,k...,k]). Then it would be necessary to change all elements to achieve the final array. If we select k that belongs to the array, then at least one element remains without change.


  • 0
    Y

    @ZhassanB However, this only proves that the number of moving elements becomes smaller but it does not prove that the total movements will be smaller. Actually, the statement that we should always choose from the existing numbers in the array as 'k' is wrong. For example, if length is even, then every number in [medianLeft, medianRight] is okay to choose.


  • 1
    Z

    @yuchenlin Let's consider special case, when array has only two elements [a,b]. Then there are three cases:

    1. k<a && k<b
    2. k>a && k> b
    3. k<a && k>b

    In the first case number of moves equals a-k+b-k, and it is not hard to mention that the expression has minimum when k -> b or k->a. The second case is analogically the same. In the third case moves = a-k+k-b = a-b, which already shows that anyway result will be the same if k = a or k == b.
    Now let's consider when there are 3 elements [a,b,c]. Let's skip the cases when k is more than all elements and k is less than all elements, because it is clear that minimum cannot be reached for that cases. Then we have two cases:

    1. k>a && k> b && k<c
    2. k>a && k>b && k<c

    In the first case, moves = k-a+k-b+c-k = k - a - b + c, thus you can understand that k must be equal to a or b to minimize the moves. The second case shows analogically the same thing. Know let's consider general case when array has n elements [a1,a2,a3,... an]. The same way as in previous example, let's skip the corner cases when k is larger than all elements and k is less than all elements. Then moves = k - a1 + k - a2 + ...+ k - ai + a(i+1) -k + a(i+2) -k +...+ an-k. (where k >ai && k<a(i+1)) As a result k's in the expression will compensate each other and it gives some the expression like an +a(n-1)+...+ai-k+a(i-1) -k +...+aj-k-a(j-1)-a(j-2)- ...-a2-a1. From here it is understandable that k must be equal to ai in order to minimize the result of the expression. Analogically you can see that fact considering the case when k is more than most of the elements.

    P.S: Actually, it is also understandable from that explanation that minimum can be reached when k equals to the median element.


  • 0
    Y

    @ZhassanB Great explanation! Thank you


Log in to reply
 

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