Maximum Strength of a Group

Med

#2443Time: O(2^N), where N is the length of `nums`. For each element, there are two choices (include or exclude), leading to `2^N` total subsets to explore.Space: O(N), where N is the length of `nums`. This space is used by the recursion stack, which can go up to N levels deep.

Patterns

Dynamic Programming Greedy Backtracking Bit Manipulation Enumeration

Algorithms

Sorting

Data structures

Array

Prompt

You are given a 0-indexed integer array nums representing the score of students in an exam. The teacher would like to form one non-empty group of students with maximal strength, where the strength of a group of students of indices i₀, i₁, i₂, ... , i_k is defined as nums[i₀] * nums[i₁] * nums[i₂] * ... * nums[i_k].

Return the maximum strength of a group the teacher can create.

Example 1:

Input: nums = [3,-1,-5,2,5,-9]
Output: 1350
Explanation: One way to form a group of maximal strength is to group the students at indices [0,2,3,4,5]. Their strength is 3 * (-5) * 2 * 5 * (-9) = 1350, which we can show is optimal.

Example 2:

Input: nums = [-4,-5,-4]
Output: 20
Explanation: Group the students at indices [0, 1] . Then, we&rsquo;ll have a resulting strength of 20. We cannot achieve greater strength.

Constraints:

1 <= nums.length <= 13
-9 <= nums[i] <= 9

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves generating all possible non-empty subsets of the given nums array and calculating the product (strength) for each. The maximum product found among all subsets is the answer. Given the small constraint on the input size (nums.length <= 13), exploring all 2^N - 1 non-empty subsets is computationally feasible. We can implement this using a backtracking algorithm.

Algorithm

Initialize a global variable maxStrength to a very small number (e.g., Long.MIN_VALUE).
Create a recursive function backtrack(index, currentProduct, count). The count parameter tracks the number of elements in the current subset to handle the non-empty constraint.
Base Case: If index reaches the end of the nums array:
- If count > 0, it means the current subset is non-empty. Update the global maximum: maxStrength = Math.max(maxStrength, currentProduct).
- Return from the function.
Recursive Step: For the element at the current index, explore two possibilities:
1. Include nums[index]: Make a recursive call backtrack(index + 1, currentProduct * nums[index], count + 1).
2. Exclude nums[index]: Make another recursive call backtrack(index + 1, currentProduct, count).
To start the process, make an initial call backtrack(0, 1L, 0) from the main function.
After the recursion completes, maxStrength will hold the maximum product of any non-empty subset.

Walkthrough

A backtracking function is used to explore all subset combinations. The function, say backtrack(index, currentProduct, count), keeps track of the current index in the array, the product of the elements chosen so far, and the number of elements in the current subset.

For each element, we branch into two recursive calls: one where the element is included in the subset (and its value is multiplied into currentProduct), and one where it's excluded. When we reach the end of the array, we have formed a complete subset. If this subset is not empty (which we check using the count variable), we compare its product with a globally maintained maximum strength and update it if the current product is greater.

The initial call starts at index 0 with a product of 1 and a count of 0. The use of a long for the product is crucial to prevent overflow, as the strength can become very large.

1class Solution {2    long maxStrength = Long.MIN_VALUE;3 4    public long maxStrength(int[] nums) {5        backtrack(0, 1L, 0, nums);6        return maxStrength;7    }8 9    private void backtrack(int index, long currentProduct, int count, int[] nums) {10        if (index == nums.length) {11            if (count > 0) {12                maxStrength = Math.max(maxStrength, currentProduct);13            }14            return;15        }16 17        // Choice 1: Include nums[index]18        backtrack(index + 1, currentProduct * nums[index], count + 1, nums);19 20        // Choice 2: Exclude nums[index]21        backtrack(index + 1, currentProduct, count, nums);22    }23}

Complexity

Time

O(2^N), where N is the length of `nums`. For each element, there are two choices (include or exclude), leading to `2^N` total subsets to explore.

Space

O(N), where N is the length of `nums`. This space is used by the recursion stack, which can go up to N levels deep.

Trade-offs

Pros

Conceptually simple and straightforward to implement.
Guaranteed to find the correct answer as it exhaustively checks every possibility.

Cons

Highly inefficient for larger input sizes.
The time complexity grows exponentially with the size of the input array.
It is only feasible because of the small problem constraint (nums.length <= 13).

A greedy approach provides a highly efficient solution by making locally optimal choices. The key insight is how different types of numbers affect the product. Positive numbers always increase the strength, so we should include all of them. Negative numbers are beneficial in pairs. An even number of negative numbers results in a positive product, while an odd number results in a negative one. If we must have a negative product, we want it to be as close to zero as possible. If we have an odd number of negatives, we can make the product positive by excluding one of them. To maximize the result, we should exclude the negative number with the smallest absolute value (the one closest to zero).

Algorithm

Handle the base case: If the array has only one element, its strength is the element itself.
Initialize variables: product = 1L, negCount = 0, posCount = 0, zeroCount = 0, and maxNeg = Integer.MIN_VALUE to track the largest negative number (closest to zero).
Iterate through the nums array once to populate these variables.
- For a positive number, multiply it into product and increment posCount.
- For a negative number, multiply it into product, increment negCount, and update maxNeg.
- For a zero, just increment zeroCount.
After the loop, analyze the counts to determine the final result:
- If the array contained only zeros, the result is 0.
- If the count of negative numbers (negCount) is odd:
  - A special case: if there are no positive numbers (posCount == 0), only one negative number (negCount == 1), and at least one zero (zeroCount > 0), the maximum strength is 0 (by choosing a zero).
  - Otherwise, to maximize the product, we must remove the effect of one negative number. We remove the one with the smallest absolute value, which is maxNeg. This is done by dividing product by maxNeg.
If negCount is even, the product of all non-zero numbers is already positive and maximized.
Return the final calculated product.

Walkthrough

This approach avoids generating subsets and instead calculates the result based on properties of the numbers in the array. We iterate through the array just once to gather key statistics.

We maintain a running product of all non-zero numbers. We also count the number of positive, negative, and zero elements. Crucially, we keep track of the negative number with the highest value (e.g., -1 is greater than -5).

After the initial pass, we check the count of negative numbers. If it's even, the total product of non-zero numbers is already the maximum possible strength. If the count is odd, the product is negative. To make it positive and maximize it, we must effectively remove one negative number. The best one to remove is the one that has the least impact on the magnitude, which is the negative number with the smallest absolute value (maxNeg). We achieve this by dividing our running product by maxNeg.

Edge cases are critical: if the array contains only zeros, the answer is 0. If it contains only one negative number and some zeros, the max strength is 0 (by picking a zero instead of the negative number). The code handles these scenarios to ensure correctness.

1class Solution {2    public long maxStrength(int[] nums) {3        if (nums.length == 1) {4            return nums[0];5        }6 7        long product = 1;8        int negCount = 0;9        int posCount = 0;10        int zeroCount = 0;11        int maxNeg = Integer.MIN_VALUE;12        boolean hasNonZero = false;13 14        for (int num : nums) {15            if (num > 0) {16                product *= num;17                posCount++;18                hasNonZero = true;19            } else if (num < 0) {20                product *= num;21                negCount++;22                maxNeg = Math.max(maxNeg, num);23                hasNonZero = true;24            } else {25                zeroCount++;26            }27        }28 29        if (!hasNonZero) { // All zeros30            return 0;31        }32 33        if (negCount % 2 != 0) { // Odd number of negatives34            // If there's only one negative and no positives, the max strength is 0 (if zeros exist)35            if (negCount == 1 && posCount == 0 && zeroCount > 0) {36                return 0;37            }38            // To maximize, remove the negative number with the smallest absolute value39            product /= maxNeg;40        }41 42        return product;43    }44}

Complexity

Time

O(N), where N is the length of `nums`. The algorithm involves a single pass through the array.

Space

O(1). We only use a fixed number of variables to store counts and the running product, regardless of the input size.

Trade-offs

Pros

Extremely efficient with linear time complexity.
Uses constant extra space, making it optimal for memory usage.
Scales well to much larger input sizes beyond the problem's constraints.

Cons

The logic can be complex due to the need to handle multiple edge cases involving zeros, single negative numbers, and combinations thereof.

Solutions

Solution

1class Solution {2public3  long maxStrength(int[] nums) {4    Arrays.sort(nums);5    int n = nums.length;6    if (n == 1) {7      return nums[0];8    }9    if (nums[1] == 0 && nums[n - 1] == 0) {10      return 0;11    }12    long ans = 1;13    int i = 0;14    while (i < n) {15      if (nums[i] < 0 && i + 1 < n && nums[i + 1] < 0) {16        ans *= nums[i] * nums[i + 1];17        i += 2;18      } else if (nums[i] <= 0) {19        i += 1;20      } else {21        ans *= nums[i];22        i += 1;23      }24    }25    return ans;26  }27}

1class Solution {2public:3  long long maxStrength(vector<int> &nums) {4    sort(nums.begin(), nums.end());5    int n = nums.size();6    if (n == 1) {7      return nums[0];8    }9    if (nums[1] == 0 && nums[n - 1] == 0) {10      return 0;11    }12    long long ans = 1;13    int i = 0;14    while (i < n) {15      if (nums[i] < 0 && i + 1 < n && nums[i + 1] < 0) {16        ans *= nums[i] * nums[i + 1];17        i += 2;18      } else if (nums[i] <= 0) {19        i += 1;20      } else {21        ans *= nums[i];22        i += 1;23      }24    }25    return ans;26  }27};

1class Solution:2    def maxStrength(self, nums: List[int]) -> int: nums . sort() n = len(nums) if n == 1: return nums[0] if nums[1] == nums[- 1] == 0: return 0 ans, i = 1, 0 while i < n: if nums[i] < 0 and i + 1 < n and nums[i + 1] < 0: ans *= nums[i] * nums[i + 1] i += 2 elif nums[i] <= 0: i += 1 else: ans *= nums[i] i += 1 return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem