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

Find Minimum Cost to Remove Array Elements

Number: 3776

Difficulty: Medium

Paid? No

Companies: DE Shaw

Problem Description

Given an integer array nums, you want to remove all elements by repeatedly performing one of the following operations until nums is empty: • If there are at least 3 elements, choose any two elements from the first three elements of nums and remove them. The cost of this operation is the maximum of the two removed. • If fewer than 3 elements remain, remove all of them in one operation; the cost is the maximum of these remaining elements. Return the minimum total cost required to remove all the elements from nums.

Key Insights

  • Because the removal is restricted to the first three elements of the current array, the order of processing matters.
  • When there are at least 3 elements, you have three choices; each choice removes a different pair and leaves a different “leftover” element at the front.
  • The decision you make now changes the configuration (or “window”) of the next state.
  • A dynamic programming (DP) approach is useful where the state is defined by both the index in the original array (elements not yet seen) and the current "window" (list of leftover elements from previous steps).
  • When the window has fewer than three elements and no further elements remain, you must remove all in one operation with cost equal to the maximum among them.

Space and Time Complexity

Time Complexity: O(n) – The DP state is defined by an index (up to n) and a small window (at most 3 elements), so the overall number of states is linear. Space Complexity: O(n) – Due to memoization and recursion stack, where n is the length of nums.

Solution

We use recursion with memoization (DP) to simulate the removal process. The DP state is defined by two parameters:

  1. i – the current index in the nums array that has not been added to our current “window.”
  2. window – a tuple of numbers (in order) representing the current first few elements available for processing. This window can have size 0, 1, 2, or 3. If the window has less than three elements and there are still elements in the array, we “fill” the window by appending nums[i] and moving to the next index. When the window size is 3, we have three possible removal operations (remove positions 0 and 1, positions 0 and 2, or positions 1 and 2). Each removal costs the maximum of the two removed numbers, and the remaining number stays in the window for the next state. If there are no more elements to add and the window size is less than 3, we remove all the remaining elements in one step (cost = maximum of the window).

The DP recursion returns the minimal cost from the current state. We memoize the computed states (i, window) to avoid recomputation. The algorithm uses a simple DFS over the state space with finite possibilities since the window size is limited.

Code Solutions

# Python solution using recursion with memoization

def minRemovalCost(nums):
    from functools import lru_cache

    n = len(nums)
    
    # dp(index, window): minimal cost starting from 'index' with current window (tuple) available.
    @lru_cache(maxsize=None)
    def dp(i, window):
        # window is stored as a tuple of integers representing the current elements.
        window = list(window)
        
        # If window size is less than 3 and there are remaining elements, fill the window.
        if len(window) < 3 and i < n:
            # Option: add the current element from nums to the window.
            new_window = window + [nums[i]]
            # Continue filling the window.
            return dp(i+1, tuple(new_window))
 
        # If no more elements to add and window has less than 3 elements, perform final removal.
        if i >= n and len(window) < 3:
            return max(window) if window else 0
        
        # Now window size is exactly 3. We try all possible removals of 2 out of 3.
        best = float('inf')
        # There are three choices:
        # Case 1: remove window[0] and window[1], leaving window[2]
        cost1 = max(window[0], window[1])
        best = min(best, cost1 + dp(i, (window[2],)))
        
        # Case 2: remove window[0] and window[2], leaving window[1]
        cost2 = max(window[0], window[2])
        best = min(best, cost2 + dp(i, (window[1],)))
        
        # Case 3: remove window[1] and window[2], leaving window[0]
        cost3 = max(window[1], window[2])
        best = min(best, cost3 + dp(i, (window[0],)))
        
        return best

    # Start with index 0 and an empty window.
    return dp(0, ())

# Example usage:
print(minRemovalCost([6,2,8,4]))  # Expected output: 12
print(minRemovalCost([2,1,3,3]))  # Expected output: 5
← Back to All Questions