3020. Find the Maximum Number of Elements in Subset

MediumArrayHash TableEnumeration
Leetcode Link

Problem Description

You are given an array called nums which only contains positive integers. Your goal is to create the longest possible subset from nums that can fit a specific pattern when arranged in a 0-indexed array. The pattern is such that it forms a palindrome with squares of the base number increasing until the middle of the array, and then decreasing symmetrically. For example, a valid pattern is [x, x^2, x^4, ..., x^(k/2), x^k, x^(k/2), ..., x^4, x^2, x], where x is a base number and k is a non-negative power of 2.

For example, the arrays [2, 4, 16, 4, 2] and [3, 9, 3] meet the criteria for the pattern (palindromic and squares of x), while [2, 4, 8, 4, 2] does not because 8 is not a repeated square of 2 within a palindromic structure. Your task is to return the maximum number of elements in such a subset that meets the described conditions.

Intuition

To solve this problem, we need to analyze the properties of the required pattern. We can see that we can always have at most one number that is not 1 and can be squared multiple times to contribute to the length of our pattern (for example, one instance of 2, two instances of 4, four instances of 16, and so forth). Numbers like 1 can be directly repeated since 1^2 is still 1.

The main observation is that in the valid subset, other than 1, each number can only appear once, and its square can appear at most once too (if present in the original array), forming pairs that will contribute to the pattern symmetrically.

Given such a pattern with a non-repeating core and symmetric structure, a hash table (dictionary in Python) can help us to count the occurrences of each number. By traversing the array and squaring the numbers while they still appear more than once, we determine the maximum length of the subset that can be created.

Numbers that are not 1 will contribute in pairs (except for the center of the pattern if unpaired), whilst 1 can contribute singly but has to be an odd count (or one less than an even count), to ensure that we can place it symmetrically around the center. This way, the code computes the maximum possible length of a subset fitting the given pattern by iterating over each number and its count while updating the maximum length.

Solution Approach

The solution adopts a hash table to keep track of the occurrences of each element in the array nums. In Python, this is done using the Counter class from the collections module, which creates a dictionary-like object that maps elements to their respective counts.

The algorithm proceeds as follows:

  • Initialize a counter cnt with the counts of each number in nums.
  • Start with calculating the contribution of the number 1. Since ones can be freely placed in the pattern without squaring, you can take all of them if there's an odd count, or one less if there's an even count, to ensure symmetry. This is handled by ans = cnt[1] - (cnt[1] % 2 ^ 1).
  • Remove 1 from the counter as it has been handled separately, del cnt[1].

Next, for each unique number x in the counter that is not 1:

  • A temporary variable t is introduced to keep track of the contribution of a number to the subset pattern's length.
  • While the count of x is more than 1, square x and increase t by 2. This represents adding both x and its square to the subset pattern.
  • After exiting the while loop, if there is still one instance of x left, increment t by 1 because it can be used as the central element of the pattern. Otherwise, decrement t by 1 as you've gone one step too far (you've made an even number of selections when you can only have an odd number).
  • Update the answer ans with the maximum of the current answer and the tentative contribution t.

The logic of squaring the numbers and checking their counts reflects the idea that numbers in our desired subset can appear either as a single center of the pattern or as pairs flanking the center. Since we are to find the maximum number of elements that can be included, we persistently square the elements and add to our count as long as they can appear in pairs.

After iterating over all numbers in the hash table, we end up with the ans variable holding the maximum possible number of elements that comprise a valid pattern. The result is then returned as the final answer.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

The three-steps of Depth First Search are:

  1. Identify states;
  2. Draw the state-space tree;
  3. DFS on the state-space tree.

Example Walkthrough

Suppose we are given the array nums = [1, 1, 1, 2, 2, 3, 3, 3, 4, 16, 4].

Following the solution approach:

  1. Initialize the counter cnt with counts of each number.

    1cnt = Counter([1, 1, 1, 2, 2, 3, 3, 3, 4, 16, 4])
    2// cnt = {1: 3, 2: 2, 3: 3, 4: 2, 16: 1}
  2. Calculate the contribution of number 1:

    1ans = 3 - (3 % 2 ^ 1) = 3 - 0 = 3

    We can use all three 1s as they are odd in count and can form a symmetric pattern around the center.

  3. Remove 1 from the counter since it's been handled.

    1del cnt[1]
    2// cnt = {2: 2, 3: 3, 4: 2, 16: 1}
  4. Process other numbers starting from the smallest.

    • For 2 in nums:

      • t is initialized to 0.
      • x is now 2, and we have 2 twos.
      • We cannot square 2 to find another 2 in the array, so the contribution of 2 to t remains 0.
    • For 3 in nums:

      • t is initialized to 0.
      • We have three 3s, but we can't square 3 to find another 3 in the array. However, there is an odd count, so we can use one of them as the center. Hence, t is increased by 1.
    • For 4 in nums:

      • t is initialized to 0.
      • We have two 4s. We can square 4, and indeed there is a 16 in the array, which is 4 squared. This means we can add two 4s, and one 16 to the pattern, increasing t by 2 for the 4s, and by 1 for the 16 as the center. Thus, t is increased by 3.

      Update ans with the max of current ans and t:

      1ans = max(3, 0 + 3) = 3

    So, our maximum length is 3 from the 1s and 3 from the 4, 16, 4.

  5. The algorithm has traversed all numbers in cnt and now ans holds the maximum possible number of elements, which is 6.

Therefore, for nums = [1, 1, 1, 2, 2, 3, 3, 3, 4, 16, 4], the subset [1, 1, 1, 4, 16, 4] reflects the longest subset that can fit the pattern with a length of 6.

Solution Implementation

1from collections import Counter
2
3class Solution:
4    def maximumLength(self, nums: List[int]) -> int:
5        # Create a counter object for the occurrences of each number in `nums`
6        num_counter = Counter(nums)
7      
8        # Initialize `answer` to the number of 1's in the list, adjusting for odd counts by subtracting 1 if count of 1's is odd
9        answer = num_counter[1] - (num_counter[1] % 2 ^ 1)
10      
11        # Remove the count for 1's, since we have processed it already
12        del num_counter[1]
13      
14        # Iterate over the items in the counter
15        for number in num_counter:
16            temp_max_length = 0  # Initialize the temporary max sequence length
17          
18            # While there are at least two occurrences of the number, we can make a square
19            while num_counter[number] > 1:
20                number *= number  # Square the number
21                temp_max_length += 2  # Increase the length of the sequence by 2 for each pairing
22             
23            # Add 1 to the length if there is a single occurrence left, or subtract 1 if there was none
24            temp_max_length += 1 if num_counter[number] else -1
25          
26            # Update the running maximum length answer with the maximum of current and temporary max length
27            answer = max(answer, temp_max_length)
28      
29        # Return the calculated maximum length
30        return answer
31
1class Solution {
2    public int maximumLength(int[] nums) {
3        // Create a map to store the occurrence count of each number.
4        Map<Long, Integer> countMap = new HashMap<>();
5        // Populate the map with the occurrence count.
6        for (int num : nums) {
7            countMap.merge((long) num, 1, Integer::sum);
8        }
9      
10        // Remove the count of 1s from the map and handle it specially. 
11        // Ensure that if present, even number of 1s are counted towards the maximum length.
12        Integer countOfOnes = countMap.remove(1L);
13        int maxLen = (countOfOnes == null) ? 0 : countOfOnes - (countOfOnes % 2 ^ 1);
14      
15        // Iterate through the remaining numbers in the count map.
16        for (long num : countMap.keySet()) {
17            int localMaxLen = 0;
18            // While there is more than one occurrence of the number, square it and increment the local max length by 2.
19            while (countMap.getOrDefault(num, 0) > 1) {
20                num *= num;
21                localMaxLen += 2;
22            }
23            // Add to the local max length the count of the squared number, if it exists, otherwise subtract one.
24            localMaxLen += countMap.getOrDefault(num, -1);
25            // Update the global max length if the local max length is greater.
26            maxLen = Math.max(maxLen, localMaxLen);
27        }
28        // Return the maximum length found.
29        return maxLen;
30    }
31}
32
1#include <unordered_map>
2#include <vector>
3#include <algorithm>
4
5class Solution {
6public:
7    int maximumLength(std::vector<int>& nums) {
8        // Creating a hash map to store the frequency of each number.
9        std::unordered_map<long long, int> frequencyMap;
10      
11        // Counting the frequency of each number in the nums vector.
12        for (int num : nums) {
13            ++frequencyMap[num];
14        }
15      
16        // Initializing the maximum length with the frequency of 1 subtracted by 1
17        // if the count is odd (to make it even), as we're looking for pairs.
18        int maxLength = frequencyMap[1] - (frequencyMap[1] % 2 ^ 1);
19      
20        // Erasing the count of 1 from the map to not consider it again.
21        frequencyMap.erase(1);
22      
23        // Iterating through each unique number in the map (excluding 1).
24        for (auto& entry : frequencyMap) {
25            // Temporary variable to keep track of the sequence length.
26            int sequenceLength = 0;
27            // We'll be squaring the number to check for powers of the original number 
28            // (e.g., 2, 4, 16 for original number 2).
29            long long currentValue = entry.first;
30          
31            // While the current value is in the map and its frequency is more than 1,
32            // it means we have at least a pair, and we can form a longer sequence.
33            while (frequencyMap.count(currentValue) && frequencyMap[currentValue] > 1) {
34                currentValue *= currentValue; // Square the number.
35                sequenceLength += 2; // Increment the sequence length by 2 (for a pair).
36            }
37          
38            // If the current value still exists in the map, add 1 more to sequence length.
39            // Otherwise, subtract 1 to remove the extra value added when there's no pair.
40            sequenceLength += frequencyMap.count(currentValue) ? 1 : -1;
41          
42            // Set maxLength to the maximum value between its current value and
43            // sequenceLength for the current number.
44            maxLength = std::max(maxLength, sequenceLength);
45        }
46      
47        // Return the maximum sequence length calculated.
48        return maxLength;
49    }
50};
51
1function maximumLength(nums: number[]): number {
2    // Create a map to store the frequency of each number in the array
3    const frequencyMap: Map<number, number> = new Map();
4
5    // Populate the frequency map with the numbers from the nums array
6    for (const num of nums) {
7        frequencyMap.set(num, (frequencyMap.get(num) ?? 0) + 1);
8    }
9
10    // Initialize ans with the frequency of the number 1 if it exists, adjusting for parity
11    let maxCountSequence = frequencyMap.has(1) ? frequencyMap.get(1)! - (frequencyMap.get(1)! % 2 ^ 1) : 0;
12    frequencyMap.delete(1); // Remove 1 from the map as it is handled separately
13
14    // Iterate over the remaining entries in the frequency map
15    for (let [base, _] of frequencyMap) {
16        let sequenceCount = 0;
17
18        // While there are at least 2 occurrences of the base, multiply it by itself (square it)
19        // and increment the sequence count by 2
20        while (frequencyMap.has(base) && frequencyMap.get(base)! > 1) {
21            base *= base;
22            sequenceCount += 2;
23        }
24
25        // If there is an occurrence of the squared number, increment sequence count by 1
26        // otherwise, decrement it by 1
27        sequenceCount += frequencyMap.has(base) ? 1 : -1;
28
29        // Update the maxCountSequence to the maximum of current maxCountSequence and sequenceCount
30        maxCountSequence = Math.max(maxCountSequence, sequenceCount);
31    }
32
33    // Return the length of the longest sequence found
34    return maxCountSequence;
35}
36

Time and Space Complexity

The time complexity of the given code is indeed O(n * log log M) where n is the length of the nums array and M is the maximum value in the nums array. This is because we iterate through all elements (O(n)) to populate the Counter, and for each unique number x that is not 1, we may square it repeatedly until it's no longer found in cnt. Squaring a number repeatedly like this takes O(log log x) time for each unique x, assuming x is the maximum value M. Since the squaring process is bounded by the maximum value M, and since it is done for each unique element that is not 1, the complexity is O(n * log log M).

The space complexity is O(n) primarily due to the storage required for the Counter object, which would, in the worst case, store as many elements as are present in the array nums if all elements are unique.

Learn more about how to find time and space complexity quickly using problem constraints.


Fast Track Your Learning with Our Quick Skills Quiz:

What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


🪄