LeetCode 3645 - Maximum Total from Optimal Activation Order

Difficulty: 🟡 Medium
Topics: Array, Two Pointers, Greedy, Sorting, Heap (Priority Queue)

Solution

Problem Understanding

This problem involves determining the maximum total value achievable by activating elements in an array under a set of constraints. We are given two arrays, value and limit, both of length n. Each element starts inactive, and activating an element adds its corresponding value[i] to the total. However, activation is only allowed if the current number of active elements is strictly less than limit[i].

Additionally, there is a cascading deactivation rule: after activating an element, if the number of active elements becomes x, all elements with limit[j] <= x become permanently inactive, even if they were previously active. The goal is to select an activation order that maximizes the sum of activated value[i].

Key points in understanding the problem:

The order of activation matters due to both the limit restriction and the cascading inactivation.
Each element’s limit[i] defines a threshold for when it can be activated and when it can be deactivated.
Edge cases include situations where multiple elements have the same limit or where limits are small, forcing immediate deactivation.

Constraints indicate the problem can be large (n <= 10^5), so a brute-force approach that tries all activation orders is infeasible. Input values and limits are positive integers, ensuring there is no ambiguity about activation eligibility.

Important edge cases include all limits being 1 (which forces immediate deactivation), large n values, and elements with very high value but low limit that must be carefully scheduled.

Approaches

Brute Force

The brute-force approach would consider all n! permutations of the activation order, compute the total for each, and select the maximum. For each permutation, you would track the number of active elements and apply the cascading inactivation rules. While this produces a correct answer, it is computationally infeasible for n up to 10^5 because factorial time grows extremely fast.

Optimal Approach

The key observation is that we should activate elements with higher value first, but only if their limit allows it. This naturally leads to a priority-based greedy strategy: at each step, pick the currently available element with the highest value that can be activated under the current number of active elements.

To implement this efficiently:

Sort elements by limit[i] in ascending order. This allows processing elements in order of when they become impossible to activate.
Use a max-heap (priority queue) to always choose the available element with the largest value[i].
Activate elements in this order, tracking the number of active elements, and update the heap to remove elements whose limit is reached due to cascading inactivation.

This ensures we maximize total value while respecting the activation constraints.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n!)	O(n)	Consider all permutations, infeasible for n=10^5
Optimal	O(n log n)	O(n)	Sort elements and use max-heap for greedy activation

Algorithm Walkthrough

Pair each element’s value with its limit, resulting in tuples (value[i], limit[i]).
Sort the elements by limit[i] in ascending order. This ensures we consider elements that could deactivate first.
Initialize a max-heap (priority queue) to store the available elements by their value in descending order.
Track a counter active representing the current number of active elements.
Iterate through the sorted elements:
Push each element’s value into the heap.
While the number of elements in the heap exceeds the next limit threshold (due to sorting by limit), pop the largest element and activate it.
Increment the active counter with each activation.
Remove elements from the heap whose limit would cause cascading deactivation.
Sum the values of activated elements to obtain the maximum total.

Why it works: The algorithm maintains the invariant that we always activate the largest available value that satisfies the current constraints. Sorting by limit ensures cascading inactivation is handled correctly. The max-heap guarantees we greedily choose the optimal elements at each step.

Python Solution

from typing import List
import heapq

class Solution:
    def maxTotal(self, value: List[int], limit: List[int]) -> int:
        n = len(value)
        elements = sorted(zip(limit, value))
        max_heap = []
        total = 0
        active = 0
        
        for lmt, val in elements:
            heapq.heappush(max_heap, -val)
            # Activate elements as long as active count < current element limit
            while active < lmt and max_heap:
                total += -heapq.heappop(max_heap)
                active += 1
                
        return total

This code sorts elements by limit and uses a max-heap to activate the highest-value elements allowed at each step. The negation is used because Python's heapq implements a min-heap by default. The while loop ensures we activate as many elements as possible before reaching a limit threshold that would deactivate elements.

Go Solution

package main

import (
    "container/heap"
    "sort"
)

type IntHeap []int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] > h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *IntHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *IntHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

func maxTotal(value []int, limit []int) int64 {
    n := len(value)
    elements := make([][2]int, n)
    for i := 0; i < n; i++ {
        elements[i] = [2]int{limit[i], value[i]}
    }
    
    sort.Slice(elements, func(i, j int) bool {
        return elements[i][0] < elements[j][0]
    })
    
    h := &IntHeap{}
    heap.Init(h)
    var total int64
    active := 0
    
    for _, el := range elements {
        lmt, val := el[0], el[1]
        heap.Push(h, val)
        for active < lmt && h.Len() > 0 {
            total += int64(heap.Pop(h).(int))
            active++
        }
    }
    
    return total
}

In Go, a max-heap is implemented by reversing the comparison in the Less function. The rest of the algorithm follows the Python version closely, using slices and type casting for the heap.

Worked Examples

Example 1: value = [3,5,8], limit = [2,1,3]

Step	Active Elements	Heap	Activated Value	Total
1	0	5	5	5
2	1	3,8	8	13
3	2	3	3	16

Output: 16

Example 2: value = [4,2,6], limit = [1,1,1]

Step	Active Elements	Heap	Activated Value	Total
1	0	6,4,2	6	6

Output: 6

Example 3: value = [4,1,5,2], limit = [3,3,2,3]

Step	Active Elements	Heap	Activated Value	Total
1	0	5,4,2,1	5	5
2	1	4,2,1	4	9
3	2	2,1	2	11
4	3	1	1	12

Output: 12

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting takes O(n log n), each element pushed/popped in heap at most once, each operation O(log n)
Space	O(n)	Heap stores up to n elements

Sorting dominates the complexity, and the heap ensures we select the maximum value efficiently at each activation step.

Test Cases

# Provided examples
assert Solution().maxTotal([3,5,8], [2,1,3]) == 16  # Example 1
assert Solution().maxTotal([4,2,6], [1,1,1]) == 6   # Example 2
assert Solution().maxTotal([4,1,5,2], [3,3,2,3]) == 12  # Example 3

# Edge cases
assert Solution().maxTotal([10], [1]) ==