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 <= 1041 <= nums[i] <= 109Problem 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.
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.
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.
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.
The solution has O(n^2) time complexity due to pair checks and O(n) space for visited tracking.
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).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| 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 | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Factorization-Based Grouping | O(n log n) | O(n) | Best general solution. Uses square-free kernel grouping to aggregate sums efficiently. |
| Graph Connectivity via Square Multipliers | O(n sqrt(n)) | O(n) | Useful for conceptual understanding of the index relationships or when modeling the problem as components. |
🔴 2862. Maximum Element-Sum of a Complete Subset of Indices II Weekly Contest 363 II Leetcode 2862 • Aryan Mittal • 2,026 views views
Watch 8 more video solutions →Practice Maximum Element-Sum of a Complete Subset of Indices with our built-in code editor and test cases.
Practice on FleetCode