Jobs

Interviews

Discussions

Maximize Sum Of Array After K Negations

Easy

Uber

16 views

Topics:

ArraysGreedy Algorithms

Given an integer array nums and an integer k, modify the array in the following way:

choose an index i and replace nums[i] with -nums[i].

You should apply this process exactly k times. You may choose the same index i multiple times.

Return the largest possible sum of the array after modifying it in this way.

Example 1:

Input: nums = [4,2,3], k = 1
Output: 5
Explanation: Choose index 1 and nums becomes [4,-2,3].

Example 2:

Input: nums = [3,-1,0,2], k = 3
Output: 6
Explanation: Choose indices (1, 2, 2) and nums becomes [3,1,0,2].

Example 3:

Input: nums = [2,-3,-1,5,-4], k = 2
Output: 13
Explanation: Choose indices (1, 4) and nums becomes [2,3,-1,5,4].

Constraints:

1 <= nums.length <= 10⁴
-100 <= nums[i] <= 100
1 <= k <= 10⁴

Maximize Sum Of Array After K Negations

Easy

Uber

16 views

Topics:

ArraysGreedy Algorithms

Given an integer array nums and an integer k, modify the array in the following way:

choose an index i and replace nums[i] with -nums[i].

You should apply this process exactly k times. You may choose the same index i multiple times.

Return the largest possible sum of the array after modifying it in this way.

Example 1:

Input: nums = [4,2,3], k = 1
Output: 5
Explanation: Choose index 1 and nums becomes [4,-2,3].

Example 2:

Input: nums = [3,-1,0,2], k = 3
Output: 6
Explanation: Choose indices (1, 2, 2) and nums becomes [3,1,0,2].

Example 3:

Input: nums = [2,-3,-1,5,-4], k = 2
Output: 13
Explanation: Choose indices (1, 4) and nums becomes [2,3,-1,5,4].

Constraints:

1 <= nums.length <= 10⁴
-100 <= nums[i] <= 100
1 <= k <= 10⁴

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 are the possible ranges for the values within the input array and for K?
Can the input array be empty or null, and what should I return in those cases?
If, after K negations, the sum cannot be further maximized (e.g., K is larger than the array size and all negative numbers are negated), how should I handle the remaining negations; should I alternate negating the smallest positive number?
Is there a specific data type for the numbers in the array, such as integers or floating-point numbers?
Are there any constraints on the value of K relative to the array length (e.g., K can be greater than the length of the array)?

Brute Force Solution

Approach

The brute force approach means trying every possible combination of negating numbers in the collection. We want to find the combination that produces the highest total sum after negating some numbers.

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

Consider all possible combinations of which numbers to negate. For instance, negate the first number, or the second number, or the first and second numbers, and so on.
For each of these combinations, negate the selected numbers.
If we are allowed to negate a specific number multiple times, consider all the different ways to pick the same number more than once. For example, negate the first number once, twice, three times, and so on, up to the allowed number of negations.
After negating a particular combination of numbers, calculate the sum of all the numbers in the collection.
Keep track of the largest sum that you find across all these combinations.
Once you have considered all possible combinations, return the largest sum that you found.

Code Implementation

def maximize_sum_after_k_negations_brute_force(numbers, k):
    maximum_sum = float('-inf')
    number_of_elements = len(numbers)

    # Iterate through all possible combinations of negations.
    for i in range(1 << number_of_elements):
        temp_numbers = numbers[:]
        negation_count = 0

        # Determine which numbers to negate based on the bitmask.
        for index in range(number_of_elements):
            if (i >> index) & 1:
                temp_numbers[index] *= -1
                negation_count += 1

        # If the number of negations is less than k, negate the smallest number until k is reached.
        while negation_count < k:
            # Find the index of the smallest absolute value element
            minimum_absolute_index = 0
            for index in range(1, number_of_elements):
                if abs(temp_numbers[index]) < abs(temp_numbers[minimum_absolute_index]):
                    minimum_absolute_index = index

            temp_numbers[minimum_absolute_index] *= -1
            negation_count += 1

        current_sum = sum(temp_numbers)

        # Keep track of the maximum sum found so far.
        maximum_sum = max(maximum_sum, current_sum)

    return maximum_sum

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(2^(n+k)) – The brute force approach explores all possible combinations of negating elements. For each element, we can either negate it or not, leading to 2^n possibilities initially. Because we can negate a number multiple times up to k times, this further increases the combinations to consider, where each of the k negations can be applied to any of the n elements. This creates an exponential growth in possibilities. Effectively, the time complexity approximates O(2^(n+k)) where n is the number of elements and k is the number of negations allowed.

Space Complexity

O(2^N) – The described brute force approach involves considering all possible combinations of negating numbers. This implicitly requires a way to track which numbers are negated in each combination. The total number of combinations is 2^N, where N is the number of elements in the input array. Each combination, in the worst case, may need to be stored (implicitly via recursion or explicitly in a list), leading to an auxiliary space complexity of O(2^N) to represent all possible combinations. There are no other significant data structures used, hence the overall auxiliary space is O(2^N).

Optimal Solution

Approach

The key is to realize that negating the smallest number repeatedly is the most efficient way to maximize the sum if we have remaining negations. We want to flip the most negative numbers to positive first, and handle edge cases carefully.

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

First, figure out if we need to negate any numbers at all. If the number of allowed negations is zero, just sum up all the numbers in the list as they are.
If we can negate numbers, we want to start by flipping the most negative numbers to positive. This makes the biggest impact on the overall sum.
Sort the numbers from most negative to most positive. This will make it easy to find the smallest numbers (the most negative or, if all are positive, the smallest positive).
Go through the sorted numbers and flip the negative ones to positive until you run out of allowed negations.
If you still have negations left after flipping all negative numbers to positive, you are left with all positive numbers.
If you have an odd number of negations remaining, flip the smallest number (which is now positive) to negative to decrease the sum as little as possible. If you have an even number of negations left, flipping the smallest number twice doesn't change the sum, so we're done.
Finally, sum up all the numbers in the list to get the maximized sum after the negations.

Code Implementation

def maximize_sum_after_k_negations(numbers, allowed_negations):
    if allowed_negations == 0:
        return sum(numbers)

    numbers.sort()

    # Flip the most negative numbers to positive first.
    for index in range(len(numbers)):
        if numbers[index] < 0 and allowed_negations > 0:
            numbers[index] = -numbers[index]
            allowed_negations -= 1

    # Re-sort after flipping negative numbers.
    numbers.sort()

    # If negations remain, and it's an odd number,
    # negate the smallest number to minimize impact.
    if allowed_negations % 2 != 0:
        numbers[0] = -numbers[0]

    return sum(numbers)

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n log n) – The dominant operation is sorting the input array of size n. Common sorting algorithms like merge sort or quicksort have a time complexity of O(n log n). The other operations such as iterating through the array to negate numbers or summing the elements take O(n) time. Since O(n log n) grows faster than O(n), the overall time complexity is determined by the sorting step, resulting in O(n log n).

Space Complexity

O(1) – The algorithm primarily sorts the input array in-place. Although sorting algorithms can sometimes use auxiliary space, the plain English description doesn't specify an auxiliary sorting method. Beyond the input array itself, the algorithm only uses a few constant space variables for iteration and potentially temporary storage during swapping elements, if the sort is in-place. Therefore, the extra space used does not scale with the input size N. Thus, the space complexity is O(1).

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 immediately since there are no elements to sum.
K is zero	Return the sum of the original array.
Array contains only positive numbers and K is odd	Negate the smallest number in the array after sorting to minimize the reduction in sum.
Array contains only positive numbers and K is even	Return the sum of the original array since an even number of negations will result in the original values.
Array contains only negative numbers and K is odd	Negate the largest negative number (closest to zero) to maximize the sum.
Array contains only negative numbers and K is even	Return the sum of the absolute values of the array elements.
Array contains zeros and K is a positive number	If a zero exists, prioritize negating elements until K is zero or we reach the zero element, effectively ignoring extra negations on zero.
K is larger than the array size	Reduce K modulo 2 after negating all negative numbers, then if K is still odd, negate the smallest element, otherwise stop.

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 are the possible ranges for the values within the input array and for K?
Can the input array be empty or null, and what should I return in those cases?
If, after K negations, the sum cannot be further maximized (e.g., K is larger than the array size and all negative numbers are negated), how should I handle the remaining negations; should I alternate negating the smallest positive number?
Is there a specific data type for the numbers in the array, such as integers or floating-point numbers?
Are there any constraints on the value of K relative to the array length (e.g., K can be greater than the length of the array)?

Brute Force Solution

Approach

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

Consider all possible combinations of which numbers to negate. For instance, negate the first number, or the second number, or the first and second numbers, and so on.
For each of these combinations, negate the selected numbers.
If we are allowed to negate a specific number multiple times, consider all the different ways to pick the same number more than once. For example, negate the first number once, twice, three times, and so on, up to the allowed number of negations.
After negating a particular combination of numbers, calculate the sum of all the numbers in the collection.
Keep track of the largest sum that you find across all these combinations.
Once you have considered all possible combinations, return the largest sum that you found.

Code Implementation

def maximize_sum_after_k_negations_brute_force(numbers, k):
    maximum_sum = float('-inf')
    number_of_elements = len(numbers)

    # Iterate through all possible combinations of negations.
    for i in range(1 << number_of_elements):
        temp_numbers = numbers[:]
        negation_count = 0

        # Determine which numbers to negate based on the bitmask.
        for index in range(number_of_elements):
            if (i >> index) & 1:
                temp_numbers[index] *= -1
                negation_count += 1

        # If the number of negations is less than k, negate the smallest number until k is reached.
        while negation_count < k:
            # Find the index of the smallest absolute value element
            minimum_absolute_index = 0
            for index in range(1, number_of_elements):
                if abs(temp_numbers[index]) < abs(temp_numbers[minimum_absolute_index]):
                    minimum_absolute_index = index

            temp_numbers[minimum_absolute_index] *= -1
            negation_count += 1

        current_sum = sum(temp_numbers)

        # Keep track of the maximum sum found so far.
        maximum_sum = max(maximum_sum, current_sum)

    return maximum_sum

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, figure out if we need to negate any numbers at all. If the number of allowed negations is zero, just sum up all the numbers in the list as they are.
If we can negate numbers, we want to start by flipping the most negative numbers to positive. This makes the biggest impact on the overall sum.
Sort the numbers from most negative to most positive. This will make it easy to find the smallest numbers (the most negative or, if all are positive, the smallest positive).
Go through the sorted numbers and flip the negative ones to positive until you run out of allowed negations.
If you still have negations left after flipping all negative numbers to positive, you are left with all positive numbers.
If you have an odd number of negations remaining, flip the smallest number (which is now positive) to negative to decrease the sum as little as possible. If you have an even number of negations left, flipping the smallest number twice doesn't change the sum, so we're done.
Finally, sum up all the numbers in the list to get the maximized sum after the negations.

Code Implementation

def maximize_sum_after_k_negations(numbers, allowed_negations):
    if allowed_negations == 0:
        return sum(numbers)

    numbers.sort()

    # Flip the most negative numbers to positive first.
    for index in range(len(numbers)):
        if numbers[index] < 0 and allowed_negations > 0:
            numbers[index] = -numbers[index]
            allowed_negations -= 1

    # Re-sort after flipping negative numbers.
    numbers.sort()

    # If negations remain, and it's an odd number,
    # negate the smallest number to minimize impact.
    if allowed_negations % 2 != 0:
        numbers[0] = -numbers[0]

    return sum(numbers)

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 immediately since there are no elements to sum.
K is zero	Return the sum of the original array.
Array contains only positive numbers and K is odd	Negate the smallest number in the array after sorting to minimize the reduction in sum.
Array contains only positive numbers and K is even	Return the sum of the original array since an even number of negations will result in the original values.
Array contains only negative numbers and K is odd	Negate the largest negative number (closest to zero) to maximize the sum.
Array contains only negative numbers and K is even	Return the sum of the absolute values of the array elements.
Array contains zeros and K is a positive number	If a zero exists, prioritize negating elements until K is zero or we reach the zero element, effectively ignoring extra negations on zero.
K is larger than the array size	Reduce K modulo 2 after negating all negative numbers, then if K is still odd, negate the smallest element, otherwise stop.