Maximum Strength of a Group of Numbers (beats 97.26% in runtime)

In this blog post, I will show you how to solve a Leet code problem that asks you to find the maximum strength of a group of numbers. The strength of a group is defined as the product of all numbers in the group, and the group can be any non-empty subset of the given list of numbers. I will also analyse the code, get its time and space complexity, and explain the code in detail.

The Problem

The problem statement is as follows:

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.

For example, given nums = [3,-1,-5,2,5,-9], the maximum strength is 1350 because 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.

However, given nums = [-4,-5,-4], the maximum strength is 20 because one way to form a group of maximal strength is to group the students at indices [0, 1]. Their strength is (-4) * (-5) = 20.

The Approach

To solve this problem, we need to consider two cases:

1. If there are no zeros in the list, then we can use all the numbers in the list to form a group of maximal strength. In this case, we need to multiply all the numbers together and make sure the result is positive.
   To do that, we need to count how many negative numbers are in the list and keep track of the largest negative number (smallest positive absolute value).
   If there are an even number of negative numbers, then multiplying them together will give a positive result. If there are an odd number of negative numbers, then multiplying them together will give a negative result, so we need to divide by the largest negative number to make it positive.

2. If there are zeros in the list, then there can be three main scenarios.
   First, there are positive numbers in the list. In this case, the solution will be fairly simple, and our algorithm will work.
   Second, there are no positive numbers and there is just one negative number. In this case, the maximum group strength will be 0, because 0 > negative number.
   Third, there are no positive numbers and odd/even negative numbers. In this case, our algorithm will work fine.

Here is the full code for this problem:

class Solution:
    def maxStrength(self, nums: List[int]) -> int:

        if len(nums) == 1:
            return nums[0]

        result = 1
        negative_numbers_count = 0
        largest_negative_number = min(nums)
        largest_positive_number = -1
        zero_in_nums = False

        for i in nums:
            largest_positive_number = max(largest_positive_number, i)
            if i == 0:
                zero_in_nums = True
                continue
            if i < 0:
                negative_numbers_count += 1
                largest_negative_number = max(largest_negative_number, i)
            result *=i

        # it total negative numbers are odd, resutl will be negative
        # divding the largest -ve number means abs(-ve) will be the smallest postive
        if negative_numbers_count % 2 == 1:
            result //= largest_negative_number

        # for test cases like [0,-1], [0,0,0]
        if largest_positive_number == 0 and negative_numbers_count in [0,1]:
            return 0

        return result

The Complexity

The time complexity of this code is O(2^n), where n is the length of the list, because in the worst case, we have to explore all the subsets of the list, which are 2^n in number.

The space complexity of this code is O(n), where n is the length of the list, because in the worst case, we have to store n recursive calls in the call stack.

The Result

Here is a screenshot of the result of running this code on Leet code:

As you can see, this solution beats 97.26% of other Python3 submissions in runtime.
Solution

The Conclusion

In this blog post, I showed you how to solve a Leet code problem that asks you to find the maximum strength of a group of numbers. I also analysed the code, got its time and space complexity, and explained the code in detail. I hope you learned something from this post and enjoyed reading it. If you have any questions or feedback, feel free to leave a comment below. Thanks for reading!