LeetCode 3020: Find the Maximum Number of Elements in Subset – Complete Python Solution

The LeetCode 3020 problem – "Find the Maximum Number of Elements in Subset" is a fascinating Medium-difficulty challenge that tests your understanding of frequency counting, greedy algorithms, and mathematical patterns. It was featured in Weekly Contest 382 and has become a popular interview question.

In this article, we'll break down the problem step by step, explore the intuition behind the solution, and implement an efficient O(n) Python solution without relying on external libraries. Whether you're preparing for coding interviews or sharpening your algorithmic skills, this guide will help you master this problem.

The valid pattern is a symmetric sequence where each element (except the central peak) appears exactly twice, and every step toward the centre is the square of the previous element.
For a given starting number x, the required chain is fixed: x, x², x⁴, x⁸, ….

Key Steps

1. Count frequencies of every number in nums.

2. Initialize answer to 1 (any single element forms a valid subset).

3. Handle the special case x = 1

   • Since 1² = 1, the chain never ends.

   • If the count of 1s is odd, use all of them.

   • If the count is even, use count - 1 (to make it odd).

4. For every other distinct number x, try to build the longest possible chain greedily:

   • Start with cur = x, length = 0.

   • While there are at least 2 copies of cur, take them as a pair → length += 2, then move to the next power cur = cur² (stop if overflow or cur² > 10⁹).

   • After the loop, check if the current cur has exactly 1 copy – if yes, use it as the peak → length += 1.

   • Otherwise, we only collected pairs – we must drop one copy to make the total length odd → length -= 1.

   • Update the global answer with this length.

5. Return the maximum length found.

This greedy approach is optimal because the chain is deterministic and taking as many pairs as possible can never hurt the ability to include a peak later.

Complexity

• Time complexity:
  $O(n)$
  We traverse the array once to build frequencies, and for each distinct number we follow at most about 5 square steps (since values are bounded by ${10}^9$, squaring grows extremely fast). Thus the total work is linear in the number of elements.

• Space complexity:
  $O(n)$
  We store a frequency dictionary with at most n distinct keys.

Appracoes with Counter Libararies

class Solution(object):
    def maximumLength(self, nums):
        from collections import Counter
        cnt=Counter(nums)
        ans=1
        if 1 in cnt:
            c=cnt[1]
            ans=max(ans, c if c%2 else c-1)
        for x in cnt:
            if x==1:
                continue
            cur=x
            length=0
            while cnt.get(cur,0)>=2:
                length+=2
                if cur>10**9//cur:
                    break
                cur=cur*cur
            if cnt.get(cur,0)==1:
                length+=1
            else:
                length-=1
            ans=max(ans,length)
        return ans

Approach Without Using Counter

The problem requires selecting a subset that can be arranged as a symmetric square‑power chain.
We count frequencies using a plain dictionary (no imports). Then for each distinct starting number (except 1), we greedily take pairs until we cannot, then decide whether we have a peak. The special case x = 1 is handled separately because 1² = 1 creates an infinite chain.

Algorithm Steps

1. Build frequency map with freq = {} and loop over nums.

2. Start ans = 1 (any single element is valid).

3. For x = 1, if its count is odd → use all; if even → use count - 1.

4. For every other distinct number x:

   • cur = x, length = 0.

   • While freq.get(cur, 0) >= 2:

     • take two copies (length += 2).

     • stop if cur > 10**9 // cur (overflow).

     • cur = cur * cur.

   • After loop, if freq.get(cur, 0) == 1 → use as peak (length += 1); else we have only pairs → subtract 1 to make length odd.

   • update ans with length.

5. Return ans.

Complexity

• Time: O(n) – one pass to count, and each distinct number follows at most ~5 square steps (since values ≤ 10⁹).

• Space: O(n) – frequency map.

Code (No Libraries, No Imports)

class Solution(object):
    def maximumLength(self, nums):
        freq = {}
        for num in nums:
            freq[num] = freq.get(num, 0) + 1

        ans = 1
        max_val = 10**9

        # special case: 1
        if 1 in freq:
            c = freq[1]
            ans = max(ans, c if c % 2 else c - 1)

        get = freq.get  # local reference for speed

        for x in freq:
            if x == 1:
                continue

            cur = x
            length = 0

            # collect pairs
            while get(cur, 0) >= 2:
                length += 2
                if cur > max_val // cur:
                    break
                cur = cur * cur

            # peak or adjust
            if get(cur, 0) == 1:
                length += 1
            else:
                length -= 1

            if length > ans:
                ans = length

        return ans