Maximum Strength of a Group — Solution in Python, Java & C++
Maximum Strength of a Group solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Maximum Strength of a Group is a medium coding problem on arrays, sorting and greedy, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Sorting, Greedy, Enumeration
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
nums[i] is the score of the i-th student in a CodeKairo study group. Pick a non-empty group of students; the group's strength is the product of their scores.
Return the maximum strength any group can have.
The original allows up to 13 students; here there are at most 9 so the product fits in a 32-bit integer.
Example 1
Input: nums = [3,-1,-5,2,5,-9]
Output: 1350
Explanation: Take 3, -5, 2, 5 and -9: the two negatives cancel.
Example 2
Input: nums = [-2,0,-3,4]
Output: 24
Example 3
Input: nums = [0,-7]
Output: 0
Explanation: The single negative is worse than the group `[0]`.
Constraints
1 <= nums.length <= 9-9 <= nums[i] <= 9
Hints for Maximum Strength of a Group
Hint 1
Every positive score helps; zeros never help unless nothing better exists.
Hint 2
Negative scores come in pairs. With an odd number of negatives, drop the one closest to zero.
Hint 3
Watch the corner cases: a single element, or nothing left to multiply (then the answer is 0 if a zero exists).
How to solve Maximum Strength of a Group
Multiply all positives and all negatives, except that with an odd count of negatives you drop the one with the smallest absolute value. Zeros are only the fallback when no factor survives.
Approach
- If there is one element, return it.
- Multiply all positive values. Sort the negatives; multiply all of them, or all but the largest (closest to zero) if their count is odd.
- If no factor was used at all, the remaining elements are zeros (plus at most one negative) — return 0.
- Otherwise return the product.
Why it works
Any positive factor greater than or equal to 1 never lowers a positive product, and a pair of negatives multiplies to a positive, so the best product uses every positive and an even number of negatives — the most negative ones, which have the largest absolute values. When that leaves an empty group, a zero gives 0, which beats any negative group.
Complexity
- Time —
O(n log n) - Space —
O(n)
Pitfalls
- A single negative element must be returned as is — the group cannot be empty.
- With one negative and some zeros the answer is 0, not the negative.
- Under the original 13 elements the product needs 64 bits.
Reference solution
Python
from typing import List
def maxStrength(nums: List[int]) -> int:
if len(nums) == 1:
return nums[0]
prod = 1
used = 0
for x in nums:
if x > 0:
prod *= x
used += 1
neg = sorted(x for x in nums if x < 0)
take = len(neg) - (len(neg) % 2)
for x in neg[:take]:
prod *= x
used += 1
return prod if used > 0 else 0Java
public static int maxStrength(int[] nums) {
if (nums.length == 1) return nums[0];
long prod = 1;
int used = 0;
List<Integer> neg = new ArrayList<>();
for (int x : nums) {
if (x > 0) { prod *= x; used++; }
else if (x < 0) neg.add(x);
}
Collections.sort(neg);
int take = neg.size() - (neg.size() % 2);
for (int j = 0; j < take; j++) { prod *= neg.get(j); used++; }
return used > 0 ? (int) prod : 0;
}C++
int maxStrength(vector<int>& nums) {
if (nums.size() == 1) return nums[0];
long long prod = 1;
int used = 0;
vector<int> neg;
for (int x : nums) {
if (x > 0) { prod *= x; used++; }
else if (x < 0) neg.push_back(x);
}
sort(neg.begin(), neg.end());
int take = neg.size() - (neg.size() % 2);
for (int j = 0; j < take; j++) { prod *= neg[j]; used++; }
return used > 0 ? (int)prod : 0;
}JavaScript
var maxStrength = function(nums) {
if (nums.length === 1) return nums[0];
var prod = 1, used = 0, neg = [];
for (var i = 0; i < nums.length; i++) {
if (nums[i] > 0) { prod *= nums[i]; used++; }
else if (nums[i] < 0) neg.push(nums[i]);
}
neg.sort(function(a, b) { return a - b; });
var take = neg.length - (neg.length % 2);
for (var j = 0; j < take; j++) { prod *= neg[j]; used++; }
return used > 0 ? prod : 0;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms