Tejav
#3020

Find the Maximum Number of Elements in Subset

Medium
ArrayHash TableEnumerationHash MapArray
LeetCode ↗

Approaches

Brute ForceOptimal
Complexity Comparison
Brute ForceOptimal Solution★
Time
O(n²)
O(n)
Space
O(n)
O(n)
💡

Intuition

Time O(n)Space O(n)

The optimal approach leverages the properties of numbers and their squares. We can efficiently find the longest valid subset by iterating through the numbers and checking for their squares in a single pass.

⚙️

Algorithm

3 steps
  1. 1Step 1: Create a HashSet from the input array for fast lookups.
  2. 2Step 2: For each number greater than 1, initialize a count and check for its squares in the set.
  3. 3Step 3: Update the maximum count based on valid elements found.
solution.py18 lines
1# Full working Python code
2from collections import Counter
3
4def maxSubset(nums):
5    num_set = set(nums)
6    max_count = 0
7    for num in nums:
8        if num > 1:
9            count = 0
10            current = num
11            while current in num_set:
12                count += 1
13                current *= current  # Square the number
14            max_count = max(max_count, count)
15    return max_count
16
17# Example usage
18print(maxSubset([5, 4, 1, 2, 2]))  # Output: 3
ℹ

Complexity note: The time complexity is O(n) because we only traverse the array once and check for squares in the HashSet. The space complexity is O(n) due to storing the numbers in a HashSet.

  • 1The pattern of valid subsets is based on powers of 2.
  • 2Using a HashSet allows for efficient lookup of squares.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.