LeetCode 3020 - Find the Maximum Number of Elements in Subset

LeetCode Problem 3020

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Enumeration

Solution

Problem Understanding

The problem gives us an array of positive integers and asks us to choose the largest possible subset that can be rearranged into a very specific symmetric structure.

The required structure looks like this:

$$[x, x^2, x^4, \dots, x^{k/2}, x^k, x^{k/2}, \dots, x^4, x^2, x]$$

where $k$ is a power of two.

The sequence grows by repeatedly squaring the previous value until it reaches a peak, then mirrors itself back down. Every value except the middle element appears exactly twice because of the symmetry.

For example:

• [2, 4, 16, 4, 2] is valid because:

• $2^2 = 4$

• $4^2 = 16$

• then the sequence mirrors back

• [3, 9, 3] is valid because:

• $3^2 = 9$

• [2, 4, 8, 4, 2] is invalid because $4^2 \neq 8$

The task is to determine the maximum possible size of such a subset.

A very important observation is that every element except the center must appear twice. Therefore, if we want to build a chain like:

$$x \rightarrow x^2 \rightarrow x^4 \rightarrow x^8$$

then:

• x must appear at least twice
• x² must appear at least twice
• x⁴ must appear at least twice
• the final peak value only needs to appear once

The constraints are large:

• nums.length <= 10^5
• nums[i] <= 10^9

This immediately tells us that brute force subset generation is impossible because there are $2^n$ subsets.

There are also several tricky edge cases:

• The number 1 is special because:

$$1^2 = 1$$

so the chain never changes.

• Large squaring operations can grow extremely quickly.
• Some numbers may exist only once, meaning they cannot appear in mirrored positions.
• Multiple possible chains may overlap, so we must carefully compute the maximum valid length.

Approaches

Brute Force Approach

A brute force solution would try every subset of the array and check whether it can be rearranged into the required pattern.

To verify a subset, we would:

1. Sort or arrange the subset.
2. Attempt to construct a valid squaring chain.
3. Check symmetry and frequency requirements.

This approach is correct because it explores every possible subset, guaranteeing that the maximum valid one will eventually be found.

However, the number of subsets is:

$$2^n$$

With $n = 10^5$, this is completely infeasible.

Even generating all subsets for $n = 30$ would already be too expensive.

Optimal Approach

The key observation is that the structure is entirely determined by repeated squaring.

If we start from some value x, then the only possible next values are:

$$x^2, x^4, x^8, \dots$$

This means we do not need to explore arbitrary subsets. We only need to examine valid squaring chains.

We count the frequency of every number using a hash map.

For a chain:

$$x \rightarrow x^2 \rightarrow x^4 \rightarrow \dots$$

every non-peak value must appear at least twice because it appears on both sides of the symmetric array.

The final peak value may appear once.

Therefore:

• if a number has frequency at least 2, we can extend the chain
• if it only appears once, it can only serve as the center

The number 1 requires special handling because squaring never changes it. A valid sequence of ones must always have odd length:

$$[1], [1,1,1], [1,1,1,1,1], \dots$$

So if there are c ones:

• if c is odd, answer contribution is c
• if c is even, answer contribution is c - 1

This leads to an efficient frequency-based solution.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n)	O(n)	Enumerates every subset
Optimal	O(n + m log log M)	O(n)	Uses frequency counting and squaring chains

Here:

• m is the number of distinct values
• M is the maximum value

The squaring chains grow extremely quickly, so each chain is very short.

Algorithm Walkthrough

1. Build a frequency map of all numbers using a hash table.

This allows us to quickly determine how many times each value appears. 2. Handle the special case for the number 1.

Since:

$$1^2 = 1$$

any valid sequence consisting only of ones must have odd length.

If the count of ones is:

• odd, we can use all of them
• even, we must leave one unused

3. Iterate through every distinct number greater than 1.

Treat each number as a possible starting value of a chain. 4. Repeatedly square the current value.

While the current value exists at least twice:

• we can place one copy on the left
• one copy on the right

This contributes 2 elements to the sequence. 5. Continue extending the chain.

Move from:

$$x \rightarrow x^2 \rightarrow x^4 \rightarrow \dots$$

until the next required number is unavailable. 6. Determine the peak element.

If the current number still exists at least once, it can become the center of the sequence, contributing 1. 7. Track the maximum sequence length across all starting values.

Why it works

The sequence structure uniquely determines which values are required at every level of the chain.

Every internal layer must appear twice because of symmetry, while the center only needs one occurrence.

By greedily extending the chain as long as frequency constraints allow, we construct the longest valid sequence for each starting value. Since every possible chain start is examined, the global maximum is guaranteed to be found.

Python Solution

from typing import List
from collections import Counter

class Solution:
    def maximumLength(self, nums: List[int]) -> int:
        frequency = Counter(nums)

        answer = 1

        # Special handling for 1
        if 1 in frequency:
            ones = frequency[1]

            if ones % 2 == 0:
                answer = max(answer, ones - 1)
            else:
                answer = max(answer, ones)

        for value in frequency:
            if value == 1:
                continue

            current = value
            length = 0

            while frequency.get(current, 0) >= 2:
                length += 2
                current = current * current

            if frequency.get(current, 0) >= 1:
                length += 1
            else:
                length -= 1

            answer = max(answer, length)

        return answer

The implementation begins by building a frequency map with Counter. This gives constant-time access to the number of occurrences of each value.

The variable answer stores the best sequence length found so far.

The number 1 is processed separately because its squaring chain never changes. The longest valid sequence of ones must have odd length, so we either use all ones or all but one.

For every other distinct value, we attempt to build the longest possible squaring chain.

The loop:

while frequency.get(current, 0) >= 2:

checks whether the current value can occupy mirrored positions in the sequence. If so, we add 2 to the length and square the current value.

After the loop finishes, we check whether the final value exists at least once. If it does, it becomes the center element.

If it does not exist, then the last added pair was invalid for forming a complete symmetric structure, so we subtract one.

Finally, we update the global maximum answer.

Go Solution

package main

func maximumLength(nums []int) int {
	frequency := make(map[int]int)

	for _, num := range nums {
		frequency[num]++
	}

	answer := 1

	// Special handling for 1
	if count, exists := frequency[1]; exists {
		if count%2 == 0 {
			if count-1 > answer {
				answer = count - 1
			}
		} else {
			if count > answer {
				answer = count
			}
		}
	}

	for value := range frequency {
		if value == 1 {
			continue
		}

		current := value
		length := 0

		for frequency[current] >= 2 {
			length += 2
			current = current * current
		}

		if frequency[current] >= 1 {
			length++
		} else {
			length--
		}

		if length > answer {
			answer = length
		}
	}

	return answer
}

The Go implementation follows the same logic as the Python solution.

A map[int]int is used instead of Python's Counter.

One subtle difference is that Go map lookups return zero values for missing keys, so:

frequency[current]

naturally behaves like Python's get(current, 0).

Integer overflow is not a practical concern here because once values become very large, they stop existing in the frequency map and the loop terminates quickly.

Worked Examples

Example 1

Input:

nums = [5,4,1,2,2]

Frequency map:

Value	Count
1	1
2	2
4	1
5	1

Initial answer from ones:

answer = 1

Now examine value 2.

Step	Current	Frequency	Length
Start	2	2	0
Use mirrored pair	2	2	2
Square	4	1	2
Use center	4	1	3

Resulting sequence:

[2,4,2]

Length is 3.

Now examine value 4.

Step	Current	Frequency	Length
Start	4	1	0
Cannot form pair	4	1	0
Use center	4	1	1

Maximum answer remains:

3

Example 2

Input:

nums = [1,3,2,4]

Frequency map:

Value	Count
1	1
2	1
3	1
4	1

Ones contribution:

answer = 1

Every other value appears only once, so none can form mirrored pairs.

Each contributes only:

length = 1

Final answer:

1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + m log log M)	Frequency construction plus short squaring chains
Space	O(n)	Hash map storing frequencies

The frequency map requires linear space in the number of distinct elements.

The squaring chains are extremely short because values grow exponentially:

$$x, x^2, x^4, x^8$$

Even starting from 2, the sequence exceeds $10^9$ after very few squaring operations.

Therefore, the total chain-processing work is very small.

Test Cases

from typing import List

class Solution:
    def maximumLength(self, nums: List[int]) -> int:
        from collections import Counter

        frequency = Counter(nums)

        answer = 1

        if 1 in frequency:
            ones = frequency[1]

            if ones % 2 == 0:
                answer = max(answer, ones - 1)
            else:
                answer = max(answer, ones)

        for value in frequency:
            if value == 1:
                continue

            current = value
            length = 0

            while frequency.get(current, 0) >= 2:
                length += 2
                current *= current

            if frequency.get(current, 0) >= 1:
                length += 1
            else:
                length -= 1

            answer = max(answer, length)

        return answer

solution = Solution()

assert solution.maximumLength([5,4,1,2,2]) == 3  # example 1
assert solution.maximumLength([1,3,2,4]) == 1  # example 2

assert solution.maximumLength([1,1,1]) == 3  # odd count of ones
assert solution.maximumLength([1,1,1,1]) == 3  # even count of ones

assert solution.maximumLength([2,2,4]) == 3  # simple valid chain
assert solution.maximumLength([2,2,4,4,16]) == 5  # deeper chain

assert solution.maximumLength([2]) == 1  # single element
assert solution.maximumLength([10,10]) == 1  # pair without valid center

assert solution.maximumLength([3,3,9,9,81]) == 5  # multiple squaring levels

assert solution.maximumLength([2,2,4,4,16,16,256]) == 7  # long chain

assert solution.maximumLength([2,2,4,16]) == 3  # missing duplicated middle

assert solution.maximumLength([1000000000]) == 1  # large value

Test Summary

Test	Why
[5,4,1,2,2]	Validates sample case with chain length 3
[1,3,2,4]	Validates case where only singleton subsets work
[1,1,1]	Tests odd count of ones
[1,1,1,1]	Tests even count of ones
[2,2,4]	Tests minimal nontrivial chain
[2,2,4,4,16]	Tests multi-level squaring
[2]	Tests single-element input
[10,10]	Tests pair without valid center
[3,3,9,9,81]	Tests another deep chain
[2,2,4,4,16,16,256]	Tests maximum-length chain growth
[2,2,4,16]	Tests incomplete chain
[1000000000]	Tests large-number handling

Edge Cases

One important edge case involves the number 1. Since squaring 1 always produces 1, the normal chain-extension logic would loop forever if handled naively. The implementation treats 1 separately and uses the observation that a valid symmetric sequence must have odd length. This guarantees correct handling without infinite loops.

Another tricky case occurs when a value appears exactly twice but its square does not exist. For example:

[10,10]

We can place one 10 on each side, but there is no valid center. The implementation detects this because the chain eventually ends without a usable middle value, and it subtracts one from the computed length.

A third important edge case is extremely large values. Squaring grows very quickly, so values can exceed the problem constraints almost immediately. The implementation avoids unnecessary processing because it only continues while the squared value exists in the frequency map. Missing values terminate the chain naturally.