What is the time complexity of LeetCode 1775. Equal Sum Arrays With Minimum Number of Operations?

The Python solution on this page runs in O(n).

What is the space complexity of LeetCode 1775. Equal Sum Arrays With Minimum Number of Operations?

The Python solution on this page uses O(n) auxiliary space.

Equal Sum Arrays With Minimum Number of Operations — LeetCode 1775 Python Solution

MediumGreedyArrayHash TableCounting

Problem: #1775
Pattern: Greedy
Reading time: 3 min
Source: leetcode.com

The problem

You are given two arrays of integers nums1 and nums2, possibly of different lengths. The values in the arrays are between 1 and 6, inclusive.

Example

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

Python solution

Python

class Solution:
    def minOperations(self, nums1: List[int], nums2: List[int]) -> int:
        s1, s2 = sum(nums1), sum(nums2)
        if s1 == s2:
            return 0
        if s1 > s2:
            return self.minOperations(nums2, nums1)
        arr = [6 - v for v in nums1] + [v - 1 for v in nums2]
        d = s2 - s1
        for i, v in enumerate(sorted(arr, reverse=True), 1):
            d -= v
            if d <= 0:
                return i
        return -1

Complexity

Measure	Complexity
Time	O(n)
Space	O(n) auxiliary

Pattern: Greedy

Take the locally best option every time — when you can prove that never costs you later. LeetCode 1775. Equal Sum Arrays With Minimum Number of Operations is filed here because LeetCode tags it Greedy, which is the vocabulary this hub collects.

The greedy guide has the Python template for the pattern and the 346 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1775. Equal Sum Arrays With Minimum Number of Operations?: LeetCode 1775. Equal Sum Arrays With Minimum Number of Operations is rated Medium on LeetCode.
What is the time complexity of LeetCode 1775. Equal Sum Arrays With Minimum Number of Operations?: The Python solution on this page runs in O(n).
What is the space complexity of LeetCode 1775. Equal Sum Arrays With Minimum Number of Operations?: The Python solution on this page uses O(n) auxiliary space.
What topics does LeetCode 1775. Equal Sum Arrays With Minimum Number of Operations cover?: LeetCode 1775. Equal Sum Arrays With Minimum Number of Operations is tagged Greedy, Array, Hash Table and Counting on LeetCode.