Sponsored
Sponsored
This approach is based on converting the problem into another known dynamic programming problem, similar to the 'House Robber' problem. The idea is to first calculate the total points for each number by multiplying its value by its frequency in the array. This allows us to transform the problem into finding the optimal way to select values in a linear array where selecting one value prevents selecting its direct neighbors.
Time Complexity: O(n + m) where n is the number of elements in nums and m is the maximum number in nums.
Space Complexity: O(m) used by the points array.
1def deleteAndEarn(nums):
2 max_num = max(nums)
3 points = [0] * (max_num + 1)
4 for num in nums:
5 points[num] += num
6
7 take, skip = 0, 0
8 for point in points:
9 take, skip = skip + point, max(take, skip)
10 return max(take, skip)This Python solution starts by identifying the maximum number in the array to establish the range of a new points array. It increments each position in the points array by the value times its occurrence. We then iterate over this points array, applying a dynamic programming strategy similar to solving 'House Robber', determining for each value whether taking it or skipping it yields more points.
This approach uses a map to store the points for each number, avoiding the space usage related to the maximum number in the points array and processing only numbers that exist in the input. We can still utilize a dynamic programming strategy to compute maximum points.
Time Complexity: O(n + k) where n is the number of elements and k is the number of unique elements in nums.
Space Complexity: O(k) for storing elements in map.
1function deleteAndEarn(nums) {
2 constThe JavaScript solution uses a Map to compute and store accumulated points for each unique number in the nums array. After converting map keys to a sorted array, a dynamic programming approach determines the optimal points without ever allocating an unnecessary large array.