Abstract / Summary

Find the highest combined strength of a group where no two members dislike each other.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 26% (100k+ submissions).

Typical patterns to solve this problem:

• Array
• Backtracking
• Bit Manipulation
• Dynamic Programming
• Enumeration
• Greedy
• Sorting

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The maxStrength method computes the greatest possible product that can be obtained from a subset of the input integers. Zeros are ignored because they would nullify the product, and the algorithm carefully treats negative numbers to ensure the final product is maximized. Special handling is provided for cases where the input consists solely of zeros or contains only a single non-zero element.

Key Steps

Removing zeros

nonzero = [ n for n in nums if n != 0 ]
if not nonzero:
    return 0

All zero values are filtered out, producing a list nonzero. If the filtered list is empty, the function returns 0 immediately, because any product involving only zeros would be zero.

Handling a single non-zero element

if len(nonzero) == 1:
    return max(nums)   # if nonzero[0] is negative, then use potential zeros in nums

When exactly one non-zero number remains, the function returns the maximum element of the original list. This allows a zero to be chosen over a negative number, yielding a product of 0, which is larger than any negative product.

Accumulating positives and collecting negatives

result   = 1
negative = []
for n in nonzero:
    if n > 0:               # all positive scores belong to the group
        result *= n
    else:
        negative.append(n)

Positive numbers are multiplied directly into result. Negative numbers are stored in the list negative for later processing.

Adjusting the negative list for an even count

negative.sort()
if len(negative) & 1:
    negative.pop()          # remove the largest if odd size

The negatives are sorted in ascending order (most negative to least negative). If the count of negatives is odd, the least harmful negative (the one closest to zero) is removed, guaranteeing an even number of negatives for the final product.

Final multiplication and return

return result * prod(negative)

The product of the accumulated positives (result) and the remaining negatives (computed with the built-in prod) is returned as the maximum achievable strength.

Edge Cases Handled

The implementation explicitly addresses the situation where the input contains only zeros, returning 0 without further computation. When a single non-zero element is present, the function chooses between that element and zero, ensuring the result is never a negative product when a zero is available. An odd number of negative values is corrected by discarding the negative with the smallest absolute magnitude, thereby avoiding a negative final product. The early return for an empty nonzero list prevents unnecessary processing.

Performance Optimizations

The algorithm performs a single pass over the filtered list to separate positives from negatives, minimizing iteration overhead. Sorting is applied solely to the subset of negative numbers, which is typically much smaller than the full input, reducing the cost of ordering. The use of Python’s built-in prod function leverages highly optimized C-level code for the final multiplication, avoiding explicit loops in Python. Early exit conditions for all-zero inputs and single-element cases prevent unnecessary work, contributing to overall efficiency.

Imagine having a big basket full of colorful number toys. Some toys are magic positive numbers, some are grumpy negative numbers, and some are just plain zeros. The goal is to pick out a group of these toys and multiply them together to get the biggest number possible.

First, the code looks at the basket and decides to put all the boring zeros aside because they make everything they touch turn into a zero. If the basket is left empty after moving the zeros away, it just keeps things simple.

When there is only one toy left, it thinks about whether that toy is a grumpy negative one or a happy positive one.

For the rest of the numbers, it starts a collection. All the positive numbers are great, so they all get multiplied together to make the total grow. The grumpy negative numbers are a bit tricky. If there is an even number of them, they can pair up with each other to become positive, which makes the total even bigger. If there is an odd number of them, one grumpy number has to be left out so the rest can become helpful positive partners.

Once the group of numbers is picked, it multiplies them all together to find the final secret champion number.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: loglinear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster		Java	C++		Python	TS
	WalkCCC		Java	C++		Python
	leetcode.ca		Java	C++	Go	Python	TS
	Progiez		Java	C++		Python
github	charles-wangkai		Java
	fsq	Rust
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
fsq	Rust

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality