<p>You are given two arrays of integers <code>nums1</code> and <code><font face="monospace">nums2</font></code>, possibly of different lengths. The values in the arrays are between <code>1</code> and <code>6</code>, inclusive.</p>

<p>In one operation, you can change any integer&#39;s value in <strong>any </strong>of the arrays to <strong>any</strong> value between <code>1</code> and <code>6</code>, inclusive.</p>

<p>Return <em>the minimum number of operations required to make the sum of values in </em><code>nums1</code><em> equal to the sum of values in </em><code>nums2</code><em>.</em> Return <code>-1</code>​​​​​ if it is not possible to make the sum of the two arrays equal.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums1 = [1,2,3,4,5,6], nums2 = [1,1,2,2,2,2]
<strong>Output:</strong> 3
<strong>Explanation:</strong> You can make the sums of nums1 and nums2 equal with 3 operations. All indices are 0-indexed.
- Change nums2[0] to 6. nums1 = [1,2,3,4,5,6], nums2 = [<u><strong>6</strong></u>,1,2,2,2,2].
- Change nums1[5] to 1. nums1 = [1,2,3,4,5,<strong><u>1</u></strong>], nums2 = [6,1,2,2,2,2].
- Change nums1[2] to 2. nums1 = [1,2,<strong><u>2</u></strong>,4,5,1], nums2 = [6,1,2,2,2,2].
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums1 = [1,1,1,1,1,1,1], nums2 = [6]
<strong>Output:</strong> -1
<strong>Explanation:</strong> There is no way to decrease the sum of nums1 or to increase the sum of nums2 to make them equal.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> nums1 = [6,6], nums2 = [1]
<strong>Output:</strong> 3
<strong>Explanation:</strong> You can make the sums of nums1 and nums2 equal with 3 operations. All indices are 0-indexed. 
- Change nums1[0] to 2. nums1 = [<strong><u>2</u></strong>,6], nums2 = [1].
- Change nums1[1] to 2. nums1 = [2,<strong><u>2</u></strong>], nums2 = [1].
- Change nums2[0] to 4. nums1 = [2,2], nums2 = [<strong><u>4</u></strong>].
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums1.length, nums2.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= nums1[i], nums2[i] &lt;= 6</code></li>
</ul>

class Solution:
    # solution using counting sort: O(n)    
    def minOperations(self, nums1: List[int], nums2: List[int]) -> int:
        n1, n2 = len(nums1), len(nums2)
        def does_exist(n1, n2):
            if n1 < n2:
                return n1*6 >= n2
            else:
                return n2*6 >= n1

        if not does_exist(n1, n2):
            return -1

        sum1, sum2 = sum(nums1), sum(nums2)
        diff = abs(sum1 - sum2)

        #  we want greater array to be first
        if(sum1 < sum2):
            nums1, nums2 = nums2, nums1

        cnt_dict = defaultdict(int)

        # counting sort for nums1
        # for elem in nums1:
        #     cnt_dict[elem] += 1

        # nums1 = []
        # for num in range(6, 0, -1):  # The range is from 1 to 6, inclusive
        #     nums1.extend([num] * cnt_dict[num])

        count = [0] * 7  # 0th index will not be used

        # Count the occurrences of each number in nums
        for num in nums1:
            count[num] += 1

        # Build the sorted list
        nums1 = []
        for num in range(6, 0, -1):  # Reverse order for descending sort
            nums1.extend([num] * count[num])

        # counting sort for nums2
        count = [0] * 7  # 0th index will not be used

        for elem in nums2:
            count[elem] += 1

        nums2 = []

        # for num in range(1, 7):  # The range is from 1 to 6, inclusive
        #     nums2.extend([num] * cnt_dict[num])
    
        for num in range(1, 7):  # Reverse order for descending sort
            nums2.extend([num] * count[num])

        cnt = 0
        while diff > 0:
            if (not nums2 or (nums1 and nums1[0]-1 > 6-nums2[0])):
                diff -= (nums1.pop(0) - 1)
            else:
                diff -= (6 - nums2.pop(0))

            cnt += 1

        return cnt


    # Solution using min and max heap: O(nlog(n))
    # def minOperations(self, nums1: List[int], nums2: List[int]) -> int:
    #     n1, n2 = len(nums1), len(nums2)
    #     def does_exist(n1, n2):
    #         if n1 < n2:
    #             return n1*6 >= n2
    #         else:
    #             return n2*6 >= n1

    #     if not does_exist(n1, n2):
    #         return -1

    #     sum1, sum2 = sum(nums1), sum(nums2)
    #     diff = abs(sum1 - sum2)

    #     #  we want greater array to be first
    #     if(sum1 < sum2):
    #         nums1, nums2 = nums2, nums1

    #     # max heap for grater array
    #     nums1 = [-x for x in nums1]
    #     heapq.heapify(nums1)
        
    #     # min heap for smaller array
    #     heapq.heapify(nums2)

    #     cnt = 0

    #      # While there is a difference to eliminate
    #     while diff > 0:
    #         # Decide which heap to pop from (choose the most effective reduction)
    #         if nums1 and (not nums2 or -nums1[0] - 1 > 6 - nums2[0]):
    #             # Reduce from nums1's max element
    #             max_reduce = -heapq.heappop(nums1) - 1
    #             diff -= max_reduce
    #         else:
    #             # Increase from nums2's min element
    #             max_increase = 6 - heapq.heappop(nums2)
    #             diff -= max_increase
                
    #         cnt += 1

    #     return cnt
22000