Maximum Strength of a Group

Medium
1470.

Maximum Strength of a Group

Maximum Strength of a Group is a medium coding problem on arrays, sorting and greedy, asked in Amazon and Google interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var maxStrength = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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

  1. Hint 1

    Every positive score helps; zeros never help unless nothing better exists.

  2. Hint 2

    Negative scores come in pairs. With an odd number of negatives, drop the one closest to zero.

  3. 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

  1. If there is one element, return it.
  2. Multiply all positive values. Sort the negatives; multiply all of them, or all but the largest (closest to zero) if their count is odd.
  3. If no factor was used at all, the remaining elements are zeros (plus at most one negative) — return 0.
  4. 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 0

Java

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