Maximum Unique Subarray Sum After Deletion

Easy

Microsoft

2 views

Topics:

ArraysSliding Windows

You are given an integer array nums.

You are allowed to delete any number of elements from nums without making it empty. After performing the deletions, select a subarray of nums such that:

All elements in the subarray are unique.
The sum of the elements in the subarray is maximized.

Return the maximum sum of such a subarray.

Example 1:

Input: nums = [1,2,3,4,5]

Output: 15

Explanation:

Select the entire array without deleting any element to obtain the maximum sum.

Example 2:

Input: nums = [1,1,0,1,1]

Output: 1

Explanation:

Delete the element nums[0] == 1, nums[1] == 1, nums[2] == 0, and nums[3] == 1. Select the entire array [1] to obtain the maximum sum.

Example 3:

Input: nums = [1,2,-1,-2,1,0,-1]

Output: 3

Explanation:

Delete the elements nums[2] == -1 and nums[3] == -2, and select the subarray [2, 1] from [1, 2, 1, 0, -1] to obtain the maximum sum.

Constraints:

1 <= nums.length <= 100
-100 <= nums[i] <= 100

Maximum Unique Subarray Sum After Deletion

Easy

Microsoft

2 views

Topics:

ArraysSliding Windows

You are given an integer array nums.

You are allowed to delete any number of elements from nums without making it empty. After performing the deletions, select a subarray of nums such that:

All elements in the subarray are unique.
The sum of the elements in the subarray is maximized.

Return the maximum sum of such a subarray.

Example 1:

Input: nums = [1,2,3,4,5]

Output: 15

Explanation:

Select the entire array without deleting any element to obtain the maximum sum.

Example 2:

Input: nums = [1,1,0,1,1]

Output: 1

Explanation:

Delete the element nums[0] == 1, nums[1] == 1, nums[2] == 0, and nums[3] == 1. Select the entire array [1] to obtain the maximum sum.

Example 3:

Input: nums = [1,2,-1,-2,1,0,-1]

Output: 3

Explanation:

Delete the elements nums[2] == -1 and nums[3] == -2, and select the subarray [2, 1] from [1, 2, 1, 0, -1] to obtain the maximum sum.

Constraints:

1 <= nums.length <= 100
-100 <= nums[i] <= 100

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum possible length of the `nums` array, and what is the maximum value of an element within `nums`?
Can the input array `nums` ever be empty or null?
If all subarrays result in the same maximum unique sum after deletion, is any valid subarray fine to remove?
By 'unique elements', do you mean elements that appear only once in the remaining array, or elements that are distinct from each other regardless of frequency?
Can you provide an example where removing different subarrays will result in different scores after taking into consideration the unique elements?

Brute Force Solution

Approach

The brute force approach to this problem is like trying out every possible piece of a larger sequence. We look at every consecutive section to see if it fits our needs, in this case finding the section with unique numbers that also adds up to the biggest sum.

Here's how the algorithm would work step-by-step:

Start by looking at just the first number in the sequence.
Then, look at the first two numbers together. Check if they are all different and calculate their sum.
Next, look at the first three numbers together. Check if they are all different and calculate their sum.
Keep doing this, extending the section from the start, one number at a time, and checking for uniqueness and calculating the sum.
Once you've checked all the sections that start with the first number, move on. Now start with the second number and repeat the process: just the second number, then the second and third, then the second, third, and fourth, and so on.
Continue this process, shifting the starting point each time, until you have checked all possible consecutive sections of numbers.
While you're checking each section, keep track of the highest sum you find among the sections that have all unique numbers.
At the end, you will have looked at every possible section and identified the one with the highest sum that contains only unique numbers.

Code Implementation

def maximum_unique_subarray(numbers):
    maximum_sum = 0
    
    for start_index in range(len(numbers)):  
        current_sum = 0
        seen_numbers = set()
        
        for end_index in range(start_index, len(numbers)):  
            current_number = numbers[end_index]

            # If we've seen the number before, it's not unique, so break
            if current_number in seen_numbers:
                break

            seen_numbers.add(current_number)
            current_sum += current_number

            # Update the maximum sum if we find a larger subarray sum
            if current_sum > maximum_sum:
                maximum_sum = current_sum

    return maximum_sum

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through all possible subarrays of the input array of size n. For each starting index i, it iterates through all ending indices j from i to n-1, defining a subarray. Inside the inner loop, the uniqueness of elements within the subarray is checked, and the sum is calculated if all elements are unique. This nested loop structure results in approximately n * (n+1) / 2 operations. Therefore, the time complexity is O(n²).

Space Complexity

O(N) – The brute force approach, as described, checks every possible subarray for uniqueness. To determine uniqueness within a subarray, a data structure (like a set or hash map) is needed to keep track of the numbers encountered so far in that subarray. In the worst case, a subarray could contain close to N elements. Therefore, the space needed for checking uniqueness within a single subarray can grow up to N, and this happens for multiple subarrays. Thus, the auxiliary space is O(N).

Optimal Solution

Approach

The key is to efficiently track a 'window' of numbers. We slide this window across the input, expanding it to include more numbers and shrinking it to remove numbers, always making sure that the numbers within the window are unique. By doing this, we can find the window with the maximum sum without checking every single possible subarray.

Here's how the algorithm would work step-by-step:

Start with an empty 'window' at the beginning of the list of numbers.
Gradually add numbers to the right side of the window as long as each new number is not already present in the window.
Keep track of the sum of the numbers currently in the window.
If you encounter a number that is already in the window, remove numbers from the left side of the window until the duplicate number is gone.
Update the sum of the numbers in the window after removing numbers from the left.
After each window adjustment, compare the current window's sum to the maximum sum seen so far, and update the maximum if needed.
Repeat steps 2-6 until you have moved the window across the entire list of numbers.
The maximum sum recorded is the answer.

Code Implementation

def maximum_unique_subarray(
    number_list
):
    window_start = 0
    window_sum = 0
    maximum_sum = 0
    seen_numbers = set()

    for window_end in range(len(number_list)):
        while number_list[window_end] in seen_numbers:
            # Shrink window if duplicate is found
            window_sum -= number_list[window_start]

            seen_numbers.remove(number_list[window_start])
            window_start += 1

        window_sum += number_list[window_end]
        seen_numbers.add(number_list[window_end])

        # Update maximum sum with each window update.
        maximum_sum = max(maximum_sum, window_sum)

    return maximum_sum

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array of size n using a sliding window approach. While the outer loop progresses through each element once, the inner loop (shrinking the window) might seem like it adds complexity. However, each element is added to and removed from the window at most once. Therefore, the total number of operations for both expanding and shrinking the window is proportional to n, leading to a linear time complexity.

Space Complexity

O(N) – The algorithm utilizes a window to store unique numbers. This window, implemented often as a set or hash map, can potentially store all the numbers in the input list in the worst case scenario (when all numbers are unique). Therefore, the space required for this window scales linearly with the input size N, where N is the number of elements in the input list. This auxiliary data structure contributes O(N) space complexity.

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 if the input array is null or empty, as there are no elements to sum.
Input array with only one element	Return the value of the single element if it's unique (which it will always be), since removing nothing is not allowed.
Array with all identical values	Calculate the sum of the unique element (the repeated value) for the entire array.
Array with all unique values	Iterate through all possible subarray removals and choose the option that results in largest sum of unique elements in the remaining array.
Large input array with a small number of unique elements	The sliding window approach should still be efficient as the size of the unique element set is limited and the rest is not relevant.
Integer overflow when calculating sums	Use `long` data type to store sums to prevent integer overflow for very large input numbers and large input size.
Array with extreme values (e.g., very large positive integers)	The solution should correctly handle large positive integers within the limits of the chosen data type (long).
Removing the first or last element	The algorithm needs to correctly consider cases where the removed subarray starts at index 0 or ends at index nums.length - 1.