Quick Overview

Maximize the score from removing integer occurrences when each choice also removes neighboring values, with duplicates and a sparse value range.

Maximize Points by Deleting Values and Their Neighbors

Company: Microsoft

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Online Assessment

You are given an array of positive integers `nums`. You may repeatedly choose an occurrence of a value `v` that is still present, remove that occurrence, and earn `v` points. That operation also removes every remaining occurrence of `v - 1` and `v + 1`, earning no points for those additional removals. Return the maximum total points you can earn. Other occurrences of `v` remain available unless you choose to remove them in later operations. ### Input - `nums`: an array of positive integers. Duplicate values are allowed. ### Output Return the maximum achievable total score as an integer. ### Constraints and Edge Cases - For this practice version, `1 <= nums.length <= 20000` and `1 <= nums[i] <= 1000000000`. - Input order does not affect which values an operation removes. - Removing an occurrence never earns points for any neighboring values removed as a side effect. - Values need not fill a continuous range, and the largest value can be much larger than the number of elements. - The result may exceed the range of a signed 32-bit integer. Use a numeric representation that holds the total exactly. ### Example 1 ```text nums = [2, 2, 3, 3, 3, 4] output = 9 ``` Choosing the three occurrences of `3` earns `9` points. Choosing both `2` occurrences and the `4` instead earns only `8`. ### Example 2 ```text nums = [1, 1, 3, 1000000000] output = 1000000005 ``` All occurrences can contribute to the score because none of their values differ by one.

Overview: Maximize the score from removing integer occurrences when each choice also removes neighboring values, with duplicates and a sparse value range.

Read the full Microsoft Software Engineer interview experience this question came from

You are given an array of positive integers `nums`. You may repeatedly choose an occurrence of a value `v` that is still present, remove that occurrence, and earn `v` points. That operation also removes every remaining occurrence of `v - 1` and `v + 1`, earning no points for those additional removals. Return the maximum total points you can earn. Other occurrences of `v` remain available unless you choose to remove them in later operations. ### Input - `nums`: an array of positive integers. Duplicate values are allowed. ### Output Return the maximum achievable total score as an integer. ### Constraints and Edge Cases - For this practice version, `1 <= nums.length <= 20000` and `1 <= nums[i] <= 1000000000`. - Input order does not affect which values an operation removes. - Removing an occurrence never earns points for any neighboring values removed as a side effect. - Values need not fill a continuous range, and the largest value can be much larger than the number of elements. - The result may exceed the range of a signed 32-bit integer. Use a numeric representation that holds the total exactly. ### Example 1 ```text nums = [2, 2, 3, 3, 3, 4] output = 9 ``` Choosing the three occurrences of `3` earns `9` points. Choosing both `2` occurrences and the `4` instead earns only `8`. ### Example 2 ```text nums = [1, 1, 3, 1000000000] output = 1000000005 ``` All occurrences can contribute to the score because none of their values differ by one.

Constraints

  • 1 <= nums.length <= 20000 and 1 <= nums[i] <= 1000000000; duplicate values and large gaps are allowed.
  • Selecting one occurrence of v earns v points and removes all remaining occurrences of v-1 and v+1 without earning their points.
  • Other occurrences of v remain available for later selections. Conflicts depend on values, not input positions.
  • Return only the exact maximum score; it can be as large as 20000000000000 and need not fit in a signed 32-bit integer.

Examples

Input: ([2, 2, 3, 3, 3, 4],)

Expected Output: 9

Explanation: Published sample 1: all three copies of 3 earn nine, beating the two copies of 2 plus 4.

Input: ([1, 1, 3, 1000000000],)

Expected Output: 1000000005

Explanation: Published sample 2: no present distinct values are consecutive, so every occurrence contributes.

Loading coding console...

Show the approach

Approach

Aggregate the available reward for each distinct value by adding that value once for every occurrence. If an optimal strategy takes any occurrence of a value, it can take all copies: taking another copy brings a positive reward and has no new conflict beyond the two neighboring values already ruled out. Thus choosing value v earns its whole aggregated weight, and distinct chosen values cannot differ by one.

Process the distinct values in increasing order. Keep take, the best score through the previous value when it is selected, and skip, the best score through that value when it is not selected. If the current value is exactly one greater than the previous value, selecting it must extend the previous skip state. Otherwise a gap separates them, so selecting it can extend the better of both states. In either case, skipping the current value keeps the better previous score.

These transitions cover every legal choice for the current value. Sorted order ensures only the immediately preceding distinct value can conflict with it, and only when the difference is one. By induction the two states retain the optimum for both possible current choices; their maximum after the last value is the global optimum. Aggregation preserves all duplicates and the operation's rule that neighboring removals earn no reward. The original array order is irrelevant and is not modified.

Let N be the number of occurrences and K the number of distinct values. Hash aggregation followed by sorting takes expected O(N + K log K) time; the Java and C++ ordered-map variants take O(N log(K+1)) time. All implementations use O(K) auxiliary space rather than allocating up to the largest value. The maximum score is 20000*1000000000 = 20000000000000. Java and C++ aggregate and run the dynamic program in 64-bit variables; adding to an already widened accumulator avoids an overflowing 32-bit frequency-times-value product. Python integers and JavaScript Number represent every allowed score exactly.

Time complexity:
Expected O(N + K log K) with hash aggregation and sorted keys; O(N log(K+1)) for the Java/C++ ordered-map variants.
Space complexity:
O(K) auxiliary space for K distinct values; no allocation proportional to the maximum value.