Find the Maximum Number of Elements in Subset solution and explanation
Google
9 more videos on this problem
Find the Maximum Number of Elements in Subset | Detailed Explanation | Dry Run | LeetCode 3020 | MIKcodestorywithMIK · 35:13 · 5K views
3020. Find the Maximum Number of Elements in Subset | Why Map & not Unordered MapAryan Mittal · 18:08 · 4K views
Find the Maximum Number of Elements in Subset 🔥 Leetcode 3020 | HashMap + Greedy Study Placement · 19:22 · 2K views
Find the Maximum Number of Elements in Subset | Leetcode - 3020Shivam Gupta · 19:26 · 1K views
3020 Find the Maximum Number of Elements in Subset || Count Frequency ✅Ayush Rao · 8:03 · 1K views
3020. Find the Maximum Number of Elements in Subset | Leetcode Daily - PythonLeetcode Daily · 7:37 · 667 views
3020. Find the Maximum Number of Elements in Subset (Leetcode Medium)Programming Live with Larry · 13:29 · 652 views
3020. Find the Maximum Number of Elements in Subset | LEETCODE WEEKLY 382 | DYNAMIC PROGRAMMINGcode Explainer · 9:32 · 553 views
Daily Leetcode #2279: Jun 27, 2026 - 3020. Find the Maximum Number of Elements in SubsetProgramming Live with Larry · 13:36 · 525 views
Find the Maximum Number of Elements in Subset | LeetCode 3020 - Pythonimpoldev · 11:46 · 428 views
The problem
You are given an array of positive integers nums.
You need to select a subset of nums which satisfies the following condition:
- You can place the selected elements in a 0-indexed array such that it follows the pattern:
[x, x2, x4, ..., xk/2, xk, xk/2, ..., x4, x2, x](Note thatkcan be be any non-negative power of2). For example,[2, 4, 16, 4, 2]and[3, 9, 3]follow the pattern while[2, 4, 8, 4, 2]does not.
Return the maximum number of elements in a subset that satisfies these conditions.
Example 1:
Input: nums = [5,4,1,2,2]
Output: 3
Explanation: We can select the subset {4,2,2}, which can be placed in the array as [2,4,2] which follows the pattern and 22 == 4. Hence the answer is 3.
Example 2:
Input: nums = [1,3,2,4]
Output: 1
Explanation: We can select the subset {1}, which can be placed in the array as [1] which follows the pattern. Hence the answer is 1. Note that we could have also selected the subsets {2}, {3}, or {4}, there may be multiple subsets which provide the same answer.
Constraints:
2 <= nums.length <= 1051 <= nums[i] <= 109
Approach overview
Problem Overview: You are given an array of integers and must select the largest subset that can be arranged into a symmetric sequence where values follow repeated squaring. A valid structure looks like x, x^2, x^4, ... , x^4, x^2, x. The goal is to maximize the number of elements while respecting the required power relationship between neighbors.
Approach 1: Count Frequency and Form Palindrome (Time: O(n + u log M), Space: O(u))
This approach uses a frequency map to count how often each number appears. For every possible starting value x, repeatedly check whether x, x^2, x^4, and further powers exist using fast hash lookups. Each level of the chain needs at least two occurrences to maintain symmetry on both sides of the sequence. The only exception is the middle element, which can appear once. Handling the value 1 requires special treatment because squaring never changes it, so the answer becomes the largest odd frequency of 1. This method relies heavily on hash table lookups and iterating through unique values in the array.
Approach 2: Using Power Properties (Time: O(n log M), Space: O(u))
This approach focuses on the mathematical property that every next element is the square of the previous one. Build a frequency map, then treat each number as a potential start of a power chain. Repeatedly square the current value and verify its presence in the map. If a value appears at least twice, it can extend the symmetric sequence on both sides. Once a value appears only once, it can act as the center and the chain stops. This method essentially performs controlled enumeration over possible bases while using constant‑time hash lookups to validate each power.
Recommended for interviews: The power‑property approach is what most interviewers expect. It demonstrates that you spotted the repeated squaring pattern and used a hash map to verify the chain efficiently. Showing the frequency-based reasoning first proves you understand the symmetry constraint, but the optimized enumeration of power chains highlights stronger algorithmic insight.
Approach 1: Count Frequency and Form Palindrome
This approach involves finding the occurrences of each number in the array and forming the maximal subset that can be arranged into the palindrome pattern described.
def maxSubset(nums):
from collections import Counter
count = Counter(nums)
max_len = 0
for val in count.values():
max_len += (val // 2) * 2
return max_len + 1 if max_len < len(nums) else max_len
nums = [5, 4, 1, 2, 2]
print(maxSubset(nums))import java.util.*;
public class MaxSubset {
public static int maxSubset(int[] nums) {
Map<Integer, Integer> countMap = new HashMap<>();
for (int num : nums) {
countMap.put(num, countMap.getOrDefault(num, 0) + 1);
}
int maxSize = 0;
for (int count : countMap.values()) {
maxSize += (count / 2) * 2;
}
return maxSize < nums.length ? maxSize + 1 : maxSize;
}
public static void main(String[] args) {
int[] nums = {5, 4, 1, 2, 2};
System.out.println(maxSubset(nums));
}
}#include <iostream>
#include <vector>
#include <map>
using namespace std;
int maxSubset(vector<int>& nums) {
map<int, int> countMap;
for (int num : nums) {
countMap[num]++;
}
int result = 0;
for (auto& [key, count] : countMap) {
result += (count / 2) * 2;
}
return result < nums.size() ? result + 1 : result;
}
int main() {
vector<int> nums = {5, 4, 1, 2, 2};
cout << maxSubset(nums) << endl;
return 0;
}function maxSubset(nums) {
let countMap = new Map();
for (let num of nums) {
countMap.set(num, (countMap.get(num) || 0) + 1);
}
let result = 0;
for (let count of countMap.values()) {
result += Math.floor(count / 2) * 2;
}
return result < nums.length ? result + 1 : result;
}
let nums = [5, 4, 1, 2, 2];
console.log(maxSubset(nums));#include <stdio.h>
#include <stdlib.h>
#define MAX_NUM 1000000000
int compare(const void *a, const void *b) {
return (*(int*)a - *(int*)b);
}
int maxSubset(int* nums, int numsSize) {
if (numsSize < 2) return 0;
qsort(nums, numsSize, sizeof(int), compare);
int maxLen = 0;
for(int i = 0; i < numsSize; ) {
int count = 1;
while(i + 1 < numsSize && nums[i] == nums[i + 1]) {
++count;
++i;
}
maxLen += count / 2 * 2;
++i;
}
return maxLen + 1;
}
int main() {
int nums[] = {5,4,1,2,2};
int numsSize = 5;
printf("%d\n", maxSubset(nums, numsSize));
return 0;
}using System;
using System.Collections.Generic;
class Program {
public static int MaxSubset(int[] nums) {
Dictionary<int, int> count = new Dictionary<int, int>();
foreach (int num in nums) {
if (!count.ContainsKey(num)) {
count[num] = 0;
}
count[num]++;
}
int maxLength = 0;
foreach (int val in count.Values) {
maxLength += (val / 2) * 2;
}
return maxLength < nums.Length ? maxLength + 1 : maxLength;
}
static void Main() {
int[] nums = {5, 4, 1, 2, 2};
Console.WriteLine(MaxSubset(nums));
}
}Using Python's collections.Counter, we can easily count the frequency of each integer in the list. The count is used to determine how many elements can form pairs; each forming a part of a palindromic structure. If not all numbers contribute to a perfect symmetric pair, one can be left as the central element.
Time Complexity: O(n), since counting and summation are both linear.
Space Complexity: O(n) due to the storage of frequency counts.
Approach 2: Using Power Properties
Here we exploit the mathematical properties of powers of 2 to directly compute the maximum subset possible without traversing explicitly looking for subsets.
def maxSubset(nums):
nums.sort()
max_len = 0
power = 1
i = 0
while i < len(nums):
count = 0
while i < len(nums) and nums[i] >= power:
if nums[i] % power == 0:
count += 1
i += 1
max_len = max(max_len, count)
power *= 2
return max_len
nums = [5, 4, 1, 2, 2]
print(maxSubset(nums))import java.util.*;
class Solution {
public int maxSubset(int[] nums) {
Arrays.sort(nums);
int maxLen = 0;
int power = 1;
int i = 0;
while (i < nums.length) {
int count = 0;
while (i < nums.length && nums[i] >= power) {
if (nums[i] % power == 0) {
count++;
}
i++;
}
maxLen = Math.max(maxLen, count);
power *= 2;
}
return maxLen;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {5, 4, 1, 2, 2};
System.out.println(sol.maxSubset(nums));
}
}#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
int maxSubset(vector<int>& nums) {
sort(nums.begin(), nums.end());
int globalMax = 0;
int currentPower = 1;
for (int i = 0; i < nums.size(); ++i) {
int count = 0;
while (i < nums.size() && nums[i] >= currentPower) {
if (nums[i] % currentPower == 0) {
++count;
}
++i;
}
globalMax = max(globalMax, count);
currentPower *= 2;
}
return globalMax;
}
int main() {
vector<int> nums = {5, 4, 1, 2, 2};
cout << maxSubset(nums) << endl;
return 0;
}function maxSubset(nums) {
nums.sort((a, b) => a - b);
let maxLen = 0;
let power = 1;
let i = 0;
while (i < nums.length) {
let count = 0;
while (i < nums.length && nums[i] >= power) {
if (nums[i] % power === 0) {
count++;
}
i++;
}
maxLen = Math.max(maxLen, count);
power *= 2;
}
return maxLen;
}
let nums = [5, 4, 1, 2, 2];
console.log(maxSubset(nums));#include <stdio.h>
#include <stdlib.h>
int maxSubset(int* nums, int numsSize) {
if (numsSize < 2) return 0;
int globalMax = 0;
int currentPower = 1;
int i = 0;
while (i < numsSize) {
int localMax = 0;
while ((currentPower <= nums[i]) && (i < numsSize)) {
localMax += (nums[i] % currentPower == 0);
++i;
}
globalMax = (globalMax > localMax) ? globalMax : localMax;
currentPower *= 2;
}
return globalMax;
}
int main() {
int nums[] = {5,4,1,2,2};
int numsSize = 5;
printf("%d\n", maxSubset(nums, numsSize));
return 0;
}using System;
using System.Linq;
class Solution {
public int MaxSubset(int[] nums) {
Array.Sort(nums);
int maxLen = 0;
int power = 1;
int i = 0;
while (i < nums.Length) {
int count = 0;
while (i < nums.Length && nums[i] >= power) {
if (nums[i] % power == 0) {
count++;
}
i++;
}
maxLen = Math.Max(maxLen, count);
power *= 2;
}
return maxLen;
}
static void Main() {
Solution sol = new Solution();
int[] nums = {5, 4, 1, 2, 2};
Console.WriteLine(sol.MaxSubset(nums));
}
}The sorted order of numbers allows for efficient bilateral searches of power matches for every increasing power of two. Maximum matched power index counts track which power size could delineate the well-aligned subset structure akin to the constraints provided. This strategy trims excessive evaluative checks by guaranteeing exponential bounds on factors considered.
Time Complexity: O(n log n), dominated by the sorting step.
Space Complexity: O(1); using auxiliary space with constant scope increase per power loops.
Approach 3: Hash Table + Enumeration
We use a hash table cnt to record the occurrence count of each element in the array nums. For each element x, we can keep squaring it until its count in the hash table cnt is less than 2. At this point, we check if the count of x in the hash table cnt is 1. If it is, it means that x can still be included in the subset. Otherwise, we need to remove an element from the subset to ensure the subset count is odd. Then we update the answer and continue to enumerate the next element.
Note that we need to handle the case of x = 1 specially.
The time complexity is O(n times log log M), and the space complexity is O(n). Here, n and M are the length of the array nums and the maximum value in the array nums, respectively.
function maximumLength(nums: number[]): number {
const cnt: Map<number, number> = new Map();
for (const x of nums) {
cnt.set(x, (cnt.get(x) ?? 0) + 1);
}
let ans = cnt.has(1) ? cnt.get(1)! - ((cnt.get(1)! % 2) ^ 1) : 0;
cnt.delete(1);
for (let [x, _] of cnt) {
let t = 0;
while (cnt.has(x) && cnt.get(x)! > 1) {
x = x * x;
t += 2;
}
t += cnt.has(x) ? 1 : -1;
ans = Math.max(ans, t);
}
return ans;
}func maximumLength(nums []int) (ans int) {
cnt := map[int]int{}
for _, x := range nums {
cnt[x]++
}
ans = cnt[1] - (cnt[1]%2 ^ 1)
delete(cnt, 1)
for x := range cnt {
t := 0
for cnt[x] > 1 {
x = x * x
t += 2
}
if cnt[x] > 0 {
t += 1
} else {
t -= 1
}
ans = max(ans, t)
}
return
}use std::collections::HashMap;
impl Solution {
pub fn maximum_length(nums: Vec<i32>) -> i32 {
let mut cnt: HashMap<i64, i32> = HashMap::new();
for &x in &nums {
*cnt.entry(x as i64).or_insert(0) += 1;
}
let mut ans = 0;
if let Some(t) = cnt.remove(&1) {
ans = t - ((t % 2) ^ 1);
}
for &key in cnt.keys() {
let mut x = key;
let mut t = 0;
while *cnt.get(&x).unwrap_or(&0) > 1 {
x = x * x;
t += 2;
}
t += cnt.get(&x).unwrap_or(&-1);
ans = ans.max(t);
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Count Frequency and Form Palindrome | Time Complexity: O(n), since counting and summation are both linear. |
| Using Power Properties | Time Complexity: O(n log n), dominated by the sorting step. |
| Hash Table + Enumeration | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Count Frequency and Form Palindrome | O(n + u log M) | O(u) | Good for reasoning about symmetric structure and validating frequency constraints |
| Using Power Properties | O(n log M) | O(u) | Best general solution; leverages repeated squaring pattern with hash lookups |
Frequently asked questions
Is Find the Maximum Number of Elements in Subset easy or hard?
The problem is classified as Medium difficulty on LeetCode. The challenge comes from recognizing the repeated squaring pattern and correctly handling frequency constraints, especially the special case where the value 1 can appear multiple times.
Find the Maximum Number of Elements in Subset Python/Java solution
Implementations in Python or Java follow the same idea: build a frequency map, iterate through possible starting numbers, and repeatedly square the value while verifying counts. The algorithm maintains the maximum length of a valid symmetric power chain.
How to solve Find the Maximum Number of Elements in Subset in O(n)?
You first count frequencies using a hash map in O(n). Then iterate through unique values and attempt to extend a chain by repeatedly squaring the number while checking the map. Each step is a constant‑time lookup, so the overall complexity stays close to linear for typical constraints.
What is the best approach for Find the Maximum Number of Elements in Subset?
The most effective approach uses the repeated squaring property of numbers. Build a frequency hash map, then treat each value as a starting point and repeatedly check whether its squared value exists. Each level requires two occurrences to maintain symmetry, except the center element. This solution runs in about O(n log M) time with O(n) space.
Is Find the Maximum Number of Elements in Subset asked at Google/Amazon/Meta?
Problems combining hash maps with mathematical patterns like power chains frequently appear in interviews at companies such as Amazon, Google, and Meta. They test your ability to recognize numeric patterns and efficiently validate them using hash-based lookups.
What data structure is used in Find the Maximum Number of Elements in Subset?
A hash table (or hash map) is the core data structure. It stores the frequency of every number in the array, enabling constant-time checks when verifying whether squared values exist in the sequence.
What is the time complexity of Find the Maximum Number of Elements in Subset?
The typical optimized solution runs in O(n log M) time, where n is the number of elements and M is the maximum value in the array. Each candidate value forms a chain through repeated squaring while hash map lookups remain O(1). Space complexity is O(n) for storing frequencies.