Skip to main content
Talentd

Maximum Strength of a Group - Solution & Explanation

MediumArrayDynamic ProgrammingBacktrackingGreedy24 min read
Practice this problem

Problem Statement

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 i0, i1, i2, ... , ik is defined as nums[i0] * nums[i1] * nums[i2] * ... * nums[ik​].

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’ll have a resulting strength of 20. We cannot achieve greater strength.

 

Constraints:

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

Approach Overview

Problem Overview: You are given an integer array where each value represents the strength of a member. The task is to select a non-empty subset whose product is maximized. Because the array can contain positive numbers, negative numbers, and zeros, choosing which elements to multiply becomes a careful balancing act.

Approach 1: Backtracking (O(2^n) time, O(n) space)

This method enumerates every possible non-empty subset and computes the product for each. You recursively decide whether to include or exclude each element while maintaining the current product. The maximum product seen during enumeration becomes the result. This approach is conceptually simple and demonstrates the full search space, but it becomes impractical as the array grows because the number of subsets doubles with every new element.

Backtracking is useful when explaining the brute-force baseline during interviews. It also helps illustrate why smarter strategies are needed for larger inputs. The recursion depth is at most n, giving O(n) auxiliary space. However, the exponential O(2^n) runtime makes it unsuitable for production scenarios.

Approach 2: Sorting and Greedy Multiplication (O(n log n) time, O(1) space)

The optimal strategy relies on how multiplication behaves with positive and negative numbers. Positive numbers always increase the product, while negative numbers can increase it only when paired together. Start by sorting the array so negatives and positives are grouped. Multiply all positive numbers. For negatives, pair them from the smallest values (largest magnitude) because the product of two negatives becomes positive.

If there is an odd count of negatives, skip the one closest to zero because including it would flip the sign of the product. Zeros act as neutralizers: if every other choice leads to a negative product, selecting zero can yield a better result. This greedy reasoning ensures you keep only values that contribute positively to the final product.

This approach leverages properties of multiplication rather than exploring every subset. Sorting simplifies pairing logic and ensures the strongest negatives are combined first. The algorithm runs in O(n log n) time due to sorting and uses constant extra space. It commonly appears in problems involving greedy selection and sign management within array processing. Some solutions also connect this reasoning to state transitions similar to dynamic programming maximum-product problems.

Recommended for interviews: Interviewers expect the greedy reasoning. Starting with the backtracking solution shows you understand the brute-force search space, but transitioning to the sorting-based greedy method demonstrates algorithmic insight and the ability to exploit mathematical properties of multiplication.

Approach 1: Approach 1: Backtracking

This approach explores all possible subsets of the given array using backtracking to compute the maximum product (strength). The idea is to explore each index, either including it in the product calculation or not, while keeping track of the current product. If the subset is non-empty, update the maximum strength encountered.

The backtracking function will recursively select or skip each element, updating the product when the element is included, and backtracking to try the next configuration.

This solution uses a recursive backtracking function to explore all subsets of the array. Each call considers the current element either picked or not picked in the subset, updating the product accordingly. The function maintains the maximum product seen across all valid, non-empty subsets.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(2^n), where n is the number of elements in the array. This is because we explore every subset.
Space Complexity: O(n), due to the recursive call stack.

Try this approach in the editor →

Approach 2: Approach 2: Sorting and Greedy Multiplication

This approach involves sorting the array first to easily group the largest elements to maximize the product, taking care of negative numbers' interaction. The strategy involves first taking care of zeroes, then pairing negatives for positive products, and finally selecting the largest positive numbers.

After sorting, we use a greedy technique to pair negatives from the start (most negative) to make products positive, add largest positives, and consider if one last negative or zero as standalone can improve the product depending on the overall product value.

This solution sorts the array and assesses counts of negatives, zeros, and positives. Negatives are paired if possible, and positives are multiplied directly. Handling at the end includes consideration of the largest negative subset pairing.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n) due to sorting the array.
Space Complexity: O(1), only a few extra variables are used.

Try this approach in the editor →

Approach 3: Binary Enumeration

The problem is actually to find the maximum product of all subsets. Since the length of the array does not exceed 13, we can consider using the method of binary enumeration.

We enumerate all subsets in the range of [1, 2^n), and for each subset, we calculate its product, and finally return the maximum value.

The time complexity is O(2^n times n), where n is the length of the array. The space complexity is O(1).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Approach 4: Sorting + Greedy

First, we can sort the array. Based on the characteristics of the array, we can draw the following conclusions:

  • If there is only one element in the array, then the maximum strength value is this element.
  • If there are two or more elements in the array, and nums[1] = nums[n - 1] = 0, then the maximum strength value is 0.
  • Otherwise, we traverse the array from small to large. If the current element is less than 0 and the next element is also less than 0, then we multiply these two elements and accumulate the product into the answer. Otherwise, if the current element is less than or equal to 0, we skip it directly. If the current element is greater than 0, we multiply this element into the answer. Finally, we return the answer.

The time complexity is O(n times log n), and the space complexity is O(log n). Where n is the length of the array.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Backtracking

Time Complexity: O(2^n), where n is the number of elements in the array. This is because we explore every subset.
Space Complexity: O(n), due to the recursive call stack.

Approach 2: Sorting and Greedy Multiplication

Time Complexity: O(n log n) due to sorting the array.
Space Complexity: O(1), only a few extra variables are used.

Binary Enumeration—
Sorting + Greedy—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Backtracking EnumerationO(2^n)O(n)Understanding the brute-force search space or when n is very small
Sorting + Greedy MultiplicationO(n log n)O(1)General case; efficiently handles positives, negatives, and zeros

Video Solution

Maximum Strength of a Group | Leetcode 2708 | BiWeekly 105 • Tech Courses • 737 views views

Watch 6 more video solutions →

Frequently Asked Questions

Is Maximum Strength of a Group easy or hard?
Maximum Strength of a Group is rated Medium difficulty. The implementation is short, but identifying the correct greedy rule for handling negative numbers and zeros requires careful reasoning about how multiplication affects the final product.
How to solve Maximum Strength of a Group in O(n)?
You can achieve O(n) time by scanning the array once to count negatives, positives, and zeros while tracking the largest negative (closest to zero). Multiply all positives and pair negatives except one if their count is odd. This avoids sorting but requires careful handling of edge cases like all negatives or zeros.
What is the best approach for Maximum Strength of a Group?
The most practical approach is a greedy strategy combined with sorting. Multiply all positive numbers, pair negative numbers so their product becomes positive, and skip a leftover negative if the count is odd. This method runs in O(n log n) time due to sorting and uses constant extra space.
Is Maximum Strength of a Group asked at Google/Amazon/Meta?
Problems involving maximum product subsets and sign handling frequently appear in interviews at large tech companies such as Amazon, Google, and Meta. While the exact problem number may vary, the core concept of pairing negatives and maximizing multiplicative gain is a common interview pattern.
What data structure is used in Maximum Strength of a Group?
The problem primarily uses arrays for input storage. The optimal solution relies on sorting the array and applying greedy multiplication logic. No advanced data structures are required beyond simple iteration and arithmetic operations.
What is the time complexity of Maximum Strength of a Group?
The optimal greedy solution runs in O(n log n) time because the array is sorted before pairing negatives and multiplying positives. Space complexity is O(1) aside from the input array. A brute-force backtracking solution requires O(2^n) time since it evaluates every possible subset.
Maximum Strength of a Group Python or Java solution approach?
In Python or Java, the typical solution sorts the array, multiplies all positive numbers, and pairs negative numbers from the smallest values. If the negative count is odd, the least harmful negative is skipped. The implementation is straightforward using loops and basic arithmetic operations.

Ready to solve this problem?

Practice Maximum Strength of a Group with our built-in code editor and test cases.

Practice on FleetCode
Previous

Maximum Strength of K Disjoint Subarrays