Leetcode 1775. Equal Sum Arrays With Minimum Number of Operations

Problem statement

https://leetcode.com/problems/equal-sum-arrays-with-minimum-number-of-operations/

Solution

The idea is the following: let A be the array with smaller sum. Then we need to increase some elements of it and we want to decrease some elements of B. If we have element x in A, then we can increase it upto 6 - x, if we have element x in B, we can decrease it upto x - 1. So, the idea is to create array of possible moves, then sort in in decreasing order and take the biggest moves, such that their sum >= than sum(B) - sum(A).

Complexity

It is O(n log n) for time and O(n) for spaces. In fact, time can be made O(n), if we use bucket sort.

Code

class Solution:
    def minOperations(self, A, B):
        if sum(A) > sum(B):
            A, B = B, A
        moves = sorted([6 - x for x in A] + [x - 1 for x in B])[::-1]
        gap = sum(B) - sum(A)
        it = 0
        
        while gap > 0 and it < len(moves):
            gap -= moves[it]
            it += 1
            
        return it if gap <= 0 else -1