We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Difference in Sums After Removal of Elements

Number: 2267

Difficulty: Hard

Paid? No

Companies: Amazon

Problem Description

Given an integer array nums of length 3 * n, you are allowed to remove exactly n elements (as a subsequence) from nums. The remaining 2 * n elements are then divided into two consecutive parts of size n each. Let sum_first be the sum of the first n elements and sum_second be the sum of the last n elements. Your task is to remove n elements such that the difference (sum_first - sum_second) is minimized.

Key Insights

  • We are effectively choosing which elements to remove to balance the sums of the two contiguous parts.
  • The problem can be reframed as: maximize the sum of the first part (by selecting n large elements from the first 2n) and minimize the sum of the second part (by selecting n small elements from the last 2n).
  • Two heaps (a min-heap and a max-heap) are used to greedily maintain the best candidate sums while sliding over valid subarrays.
  • Precompute the maximum sum possible for the left part and the minimum sum possible for the right part for every potential partition point in the middle.

Space and Time Complexity

Time Complexity: O(n log n) – Each of the two passes over n elements involves heap operations, each costing O(log n). Space Complexity: O(n) – For storing the heaps and precomputed prefix/suffix arrays.

Solution

We solve the problem in two phases:

  1. For the left segment (first 2n elements), maintain a min-heap while iterating from left to right. Start by adding the first n elements and computing their sum. Then continue through indices n to 2n-1, adding each element to the heap and removing the smallest element (if necessary) in order to always retain the n largest elements from the left portion. Store the sum at each step as a candidate for sum_first.
  2. For the right segment (last 2n elements), maintain a max-heap while iterating backwards from right to left. Start by adding the last n elements and computing their sum. Then continue backwards through indices 2n-1 downto n, adding each element and removing the largest element (ensuring we keep the n smallest elements from this portion). Store the sum at each step as a candidate for sum_second.
  3. Finally, iterate over all valid split points (from n to 2*n) and compute the difference: leftSum[i] - rightSum[i]. The minimum of these differences is the answer.

Important details:

  • The heaps allow us to efficiently update the running sums as we consider including a new candidate element and possibly excluding a less optimal element.
  • The pre-computation of candidate sums for every partition point is key to achieving an O(n log n) solution without exploring all removal subsequences.

Code Solutions

import heapq

def minimumDifference(nums):
    n = len(nums) // 3
    # left_max[i] will store the maximum sum of n selected elements 
    # from the subarray nums[0:i] (i from n to 2*n)
    left_max = [0] * (2 * n + 1)
    min_heap = []
    current_sum = 0
    # Process the first n elements - we have no choice but to pick them all.
    for i in range(n):
        current_sum += nums[i]
        heapq.heappush(min_heap, nums[i])
    left_max[n] = current_sum

    # For i from n to 2*n-1, try to update the selected n elements.
    for i in range(n, 2*n):
        heapq.heappush(min_heap, nums[i])
        current_sum += nums[i]
        # Remove the smallest element to keep only n elements (largest possible sum).
        smallest = heapq.heappop(min_heap)
        current_sum -= smallest
        left_max[i + 1] = current_sum

    # right_min[i] will store the minimum sum of n selected elements 
    # from the subarray nums[i:3*n] (i from 2*n down to n)
    right_min = [0] * (2 * n + 1)
    max_heap = []
    current_sum = 0
    # Process the last n elements - again, no choice but to pick them all.
    for i in range(3*n - 1, 2*n - 1, -1):
        current_sum += nums[i]
        # We use a max_heap by pushing negative values.
        heapq.heappush(max_heap, -nums[i])
    right_min[2 * n] = current_sum

    # For i from 2*n-1 downto n, update the minimum possible sum (keeping n smallest elements).
    for i in range(2*n - 1, n - 1, -1):
        heapq.heappush(max_heap, -nums[i])
        current_sum += nums[i]
        # Remove the largest (which is the smallest negative) to maintain n elements.
        largest = -heapq.heappop(max_heap)
        current_sum -= largest
        right_min[i] = current_sum

    # Compute the minimal difference left_max[i] - right_min[i] for i from n to 2*n.
    answer = float('inf')
    for i in range(n, 2*n + 1):
        answer = min(answer, left_max[i] - right_min[i])
    return answer

# Example usage:
print(minimumDifference([3,1,2]))  # Expected output: -1
print(minimumDifference([7,9,5,8,1,3]))  # Expected output: 1
← Back to All Questions