Skip to main content
Talentd

Maximum Element-Sum of a Complete Subset of Indices - Solution & Explanation

HardArrayMathNumber Theory15 min readAsked at: Purplle
Practice this problem

Problem Statement

You are given a 1-indexed array nums. Your task is to select a complete subset from nums where every pair of selected indices multiplied is a perfect square,. i. e. if you select ai and aj, i * j must be a perfect square.

Return the sum of the complete subset with the maximum sum.

 

Example 1:

Input: nums = [8,7,3,5,7,2,4,9]

Output: 16

Explanation:

We select elements at indices 2 and 8 and 2 * 8 is a perfect square.

Example 2:

Input: nums = [8,10,3,8,1,13,7,9,4]

Output: 20

Explanation:

We select elements at indices 1, 4, and 9. 1 * 4, 1 * 9, 4 * 9 are perfect squares.

 

Constraints:

  • 1 <= n == nums.length <= 104
  • 1 <= nums[i] <= 109

Approach Overview

Problem Overview: You are given an array nums indexed from 1. A subset of indices is considered complete if for every pair (i, j) in the subset, the product i * j is a perfect square. The goal is to choose such a subset and maximize the sum of the corresponding array values.

Approach 1: Factorization-Based Grouping (O(n log n) time, O(n) space)

The key observation comes from number theory. Two numbers produce a perfect square when multiplied if their prime factorizations have matching parity for every prime. This means their square-free kernel (the product of primes with odd exponent after removing square factors) must be identical. Iterate through indices i from 1 to n, compute the square‑free representation of i by removing squared prime factors, and use it as a grouping key. Accumulate nums[i-1] into a hash map keyed by this kernel. Every group represents indices that can form a complete subset because any pair within the group produces a perfect square product. The answer is the maximum accumulated sum among these groups. This approach combines array traversal with prime factorization techniques.

Approach 2: Graph Connectivity Concept (O(n sqrt(n)) time, O(n) space)

Another way to model the condition is through connectivity. Treat each index as a node in a graph. Connect i to indices of the form i * k^2 as long as they remain within bounds. Multiplying by a square preserves the square‑free kernel, which means all reachable nodes belong to the same valid subset. Starting from each index, perform DFS/BFS and collect all indices reachable via square multipliers. Sum the corresponding values in nums and track the maximum. This approach explicitly builds the relationship implied by the math property and is easier to reason about conceptually, though it is slower than the direct grouping method.

Recommended for interviews: The factorization-based grouping is the expected optimal solution. It shows understanding of the mathematical constraint behind perfect squares and avoids constructing explicit graph edges. The graph perspective helps build intuition, but the grouping solution demonstrates stronger algorithmic insight and cleaner implementation using math and hashing.

Approach 1: Approach 1: Factorization-Based Grouping

The goal is to group indices based on common factors from their prime factorizations. For two indices i and j, i * j is a perfect square if all primes in its factorization appear an even number of times. Use this property to group indices and compute the subset with the maximum sum.

The solution loops through potential starting points for complete subsets which would form perfect squares. It leverages the mathematical property that multiples of a common base can help create such relationships.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

The time complexity is O(n√n) due to checking factors, and the space complexity is O(1) as we use a constant amount of extra space.

Try this approach in the editor →

Approach 2: Approach 2: Graph Connectivity Concept

Construct a graph with nodes representing indices, and edges exist if their product is a perfect square. Find components (connected subsets) in this graph, and find the sum of the component with maximum node weight (i.e., element value sum).

Using depth-first search (DFS) to find connected components of indices, with each connection defined by their product being a perfect square, achieves the graph-based result maximum.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

The solution has O(n^2) time complexity due to pair checks and O(n) space for visited tracking.

Try this approach in the editor →

Approach 3: Enumeration

We note that if a number can be expressed in the form of k times j^2, then all numbers of this form have the same k.

Therefore, we can enumerate k in the range [1,..n], and then start enumerating j from 1, each time adding the value of nums[k times j^2 - 1] to t, until k times j^2 > n. At this point, update the answer to ans = max(ans, t).

Finally, return the answer ans.

The time complexity is O(n), where n is the length of the array. The space complexity is O(1).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Factorization-Based Grouping

The time complexity is O(n√n) due to checking factors, and the space complexity is O(1) as we use a constant amount of extra space.

Approach 2: Graph Connectivity Concept

The solution has O(n^2) time complexity due to pair checks and O(n) space for visited tracking.

Enumeration—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Factorization-Based GroupingO(n log n)O(n)Best general solution. Uses square-free kernel grouping to aggregate sums efficiently.
Graph Connectivity via Square MultipliersO(n sqrt(n))O(n)Useful for conceptual understanding of the index relationships or when modeling the problem as components.

Video Solution

🔴 2862. Maximum Element-Sum of a Complete Subset of Indices II Weekly Contest 363 II Leetcode 2862 • Aryan Mittal • 2,045 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Maximum Element-Sum of a Complete Subset of Indices easy or hard?
Maximum Element-Sum of a Complete Subset of Indices is classified as Hard on LeetCode. The challenge comes from recognizing the number theory property that converts the pairwise perfect-square condition into grouping by square-free index factors.
Maximum Element-Sum of a Complete Subset of Indices Python/Java solution
Python and Java implementations typically compute the square-free kernel for each index, store cumulative sums in a hash map, and track the maximum group sum. The logic is identical across languages and runs in O(n log n) time with O(n) space.
How to solve Maximum Element-Sum of a Complete Subset of Indices in O(n)?
A near-linear solution is possible by precomputing smallest prime factors using a sieve and deriving the square-free kernel of each index in constant amortized time. Group indices by this kernel and accumulate sums, effectively achieving O(n) to O(n log log n) preprocessing with O(n) traversal.
What is the best approach for Maximum Element-Sum of a Complete Subset of Indices?
The optimal approach groups indices by their square-free kernel using prime factorization. If two indices have the same square-free representation, their product is guaranteed to be a perfect square. Summing array values for each group and returning the maximum produces the result in O(n log n) time and O(n) space.
Is Maximum Element-Sum of a Complete Subset of Indices asked at Google/Amazon/Meta?
This problem is categorized as Hard and involves number theory and mathematical transformations, patterns commonly seen in interviews at companies like Google, Amazon, and Meta. Variations involving perfect squares, factorization, or index grouping appear in algorithmic interview rounds.
What data structure is used in Maximum Element-Sum of a Complete Subset of Indices?
The main data structure is a hash map that groups indices by their square-free kernel. Additional tools include prime factorization or sieve arrays for number theory preprocessing, along with basic array traversal.
What is the time complexity of Maximum Element-Sum of a Complete Subset of Indices?
The optimal factorization-based grouping runs in O(n log n) time with O(n) space. Each index is reduced to its square-free form using prime factorization or precomputed smallest prime factors, and values are aggregated using a hash map.

Ready to solve this problem?

Practice Maximum Element-Sum of a Complete Subset of Indices with our built-in code editor and test cases.

Practice on FleetCode
Previous

Constrained Subsequence Sum

Next

Maximum Alternating Subsequence Sum