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

TheLeetCode 3020 problem – "Find the Maximum Number of Elements in Subset"is a fascinatingMedium-difficulty challenge that tests your understanding offrequency counting,greedy algorithms, andmathematical patterns. It was featured inWeekly Contest 382and 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 efficientO(n) Python solutionwithout 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 numberx, the required chain is fixed:x, x², x⁴, x⁸, ….

Key Steps

1. Count frequenciesof every number innums.

2. Initialize answerto1(any single element forms a valid subset).

3. Handle the special casex = 1

   • Since1² = 1, the chain never ends.

   • If the count of1s isodd, use all of them.

   • If the count iseven, usecount - 1(to make it odd).

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

   • Start withcur = x,length = 0.

   • While there areat least 2copies ofcur, take them as a pair →length += 2, then move to the next powercur = cur²(stop if overflow orcur² > 10⁹).

   • After the loop, check if the currentcurhasexactly 1copy – 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 thislength.

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:
  
  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 by109, squaring grows extremely fast). Thus the total work is linear in the number of elements.

• Space complexity:
  
  We store a frequency dictionary with at mostndistinct 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 UsingCounter

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 casex = 1is handled separately because1² = 1creates an infinite chain.

Algorithm Steps

1. Build frequency map withfreq = {}and loop overnums.

2. Startans = 1(any single element is valid).

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

4. For every other distinct numberx:

   • cur = x,length = 0.

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

     • take two copies (length += 2).

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

     • cur = cur * cur.

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

   • updateanswithlength.

5. Returnans.

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