“This is the 28th day of my participation in the First Challenge 2022. For details: First Challenge 2022”

preface

This is the fourth Hard question in the Biweekly Contest 71, examining the use of heap data structures, or priority queues.

describe

You are given a 0-indexed integer array nums consisting of 3 * n elements.

You are allowed to remove any subsequence of elements of size exactly n from nums. The remaining 2 * n elements will be divided into two equal parts:

  • The first n elements belonging to the first part and their sum is sumfirst.
  • The next n elements belonging to the second part and their sum is sumsecond.

The difference in sums of the two parts is denoted as sumfirst – sumsecond.

  • For example, if sumfirst = 3 and sumsecond = 2, their difference is 1.
  • Similarly, if sumfirst = 2 and sumsecond = 3, their difference is -1.

Return the minimum difference possible between the sums of the two parts after the removal of n elements.

Example 1:

Input: nums = [1,2] Output: -1 Explanation: Here, nums has 3 elements, so n = 1. Thus we have to remove 1 element from nums and divide the array into two equal parts. - If we remove nums[0] = 2, The array will be [1,2]. The difference in sums of the two parts will be 1-2 = -1. -if we remove the sums [1] = 1, The difference in sums of the two parts will be 2 = 1. -if we remove the sums of sums [2] = 2, The array will be [3,1]. The difference in sums of the two parts will be 3-1 = 2 Of the two parts is min(-1,1,2) = -1.Copy the code

Note:

nums.length == 3 * n
1 <= n <= 10^5
1 <= nums[i] <= 10^5
Copy the code

parsing

Given a 0 – indexed integer array nums consisting of 3 * N elements. You can remove any subsequence of elements of exactly size N from NUMS. The remaining 2 * n elements will be divided into two equal parts:

  • The first n elements in the first part, their sum is sumfirst.
  • The next n elements belong to the second part, and their sum is sumsecond.

The difference between the sum of the two parts is expressed as sumfirst – sumsecond. For example, if sumFirst = 3 and sumSecond = 2, their difference is 1. Returns the smallest possible difference between the sum of two parts after deleting n elements.

I didn’t have any idea at the beginning, but I saw the big guy’s solution process. It was really simple and easy to understand, and the content was concise. I’m just going to clarify the big guy’s thinking here.

This problem can be translated into another problem, which is to divide numS into two parts. To minimize the final difference, let the sum of the front part be the smallest and the sum of the back part be the largest.

N = len(nums)//3, where the heap data structure is used, we first find the sum of the smallest N digits in the range of nums[n-1:2 *N] from left to right, I, and add them to the preMin. Similarly, we use the heap data structure and find the sum of the N largest digits within the range of NUMS [I :] from right to left at every position I within the range of NUMS [N:2*N+1] and add them to sufMax. After getting sufMax, we need to reverse sufMax. Premin-sufmax = nums[: I] = nums[I :] = nums[I :] = nums[I :]

Time is O(NlogN), just right, no timeouts, space is O(N).

answer

class Solution(object):
    def minimumDifference(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        N = len(nums)//3
        # preMin
        preMin = [sum(nums[:N])]
        curMin = sum(nums[:N])
        pre_hp = [-x for x in nums[:N]]
        heapq.heapify(pre_hp)
        for i in range(N, 2*N):
            val = -heapq.heappop(pre_hp)
            curMin -= val
            tmp = min(val, nums[i])
            curMin += tmp
            preMin.append(curMin)
            heapq.heappush(pre_hp, -tmp)
        # sufMax
        sufMax = [sum(nums[-N:])]
        curMax = sum(nums[-N:])
        suf_hp = [x for x in nums[2*N:]]
        heapq.heapify(suf_hp)
        for i in range(2*N-1, N-1, -1):
            val = heapq.heappop(suf_hp)
            curMax -= val
            tmp = max(val, nums[i])
            curMax += tmp
            sufMax.append(curMax)
            heapq.heappush(suf_hp, tmp)
        # find min diff    
        sufMax = sufMax[::-1]
        result = float('inf')
        for a,b in zip(preMin, sufMax):
            result = min(result, a-b)
        return result	
Copy the code

The results

109/109 Test cases passed. Status: Accepted Runtime: 4865 MS Memory Usage: 44.2 MBCopy the code

The original link

Leetcode.com/contest/biw…

Your support is my biggest motivation