Lexicographically Largest Power Array solution and explanation
The problem
You are given an integer array nums of length n. You may rearrange its elements to form any permutation perm.
Define an array power of length 15. For each 0 <= i < 15, power[i] is the largest integer j, where 0 <= j <= n, such that the first j elements of perm all have the (14 - i)th bit set.
Bit positions are indexed from right to left, starting with the 0th bit.
Return the lexicographically largest possible power array.
Example 1:
Input: nums = [7,5]
Output: [0,0,0,0,0,0,0,0,0,0,0,0,2,1,2]
Explanation:
Choose perm = [7, 5].
- Both elements have bit 2 set, so
power[12] = 2. - The first element has bit 1 set, but the second does not, so
power[13] = 1. - Both elements have bit 0 set, so
power[14] = 2.
All higher bits are unset in the first element, so the remaining entries are 0.
Example 2:
Input: nums = [3,1,7]
Output: [0,0,0,0,0,0,0,0,0,0,0,0,1,2,3]
Explanation:
Choose perm = [7, 3, 1].
- The first element has bit 2 set, but the second does not, so
power[12] = 1. - The first two elements have bit 1 set, but the third does not, so
power[13] = 2. - All three elements have bit 0 set, so
power[14] = 3.
All higher bits are unset in the first element, so the remaining entries are 0.
Constraints:
1 <= nums.length <= 5 * 1040 <= nums[i] < 215
Approach overview
Problem Overview: You are given a multiset of integers and you can rearrange them. The power array is defined by placing a value at each position and raising it to that position's 1-based exponent. You want the lexicographically largest power array. Because the first differing position decides the result, every earlier position is worth more than all later positions combined.
Approach 1: Brute Force Permutations (O(n! · n log n))
Generate every permutation of the input using recursion or next_permutation. For each permutation, compute each power with fast exponentiation and compare the resulting power array with the current best. This runs in O(n! · n log n) time and O(n) extra space. It is only useful for n <= 8 or as a reference implementation to validate the greedy.
Approach 2: Greedy with Two Heaps (O(n log n))
Lexicographic order lets you greedily choose the best remaining element for position 0, then forget it and move to position 1. The key observation is the parity of the exponent. For an odd exponent, x^e is strictly increasing over all integers, even negative ones, so the best choice is the maximum remaining value. For an even exponent, x^e = |x|^e, so the sign disappears and the best choice is the value with the largest absolute value.
Maintain two max-heaps over the remaining values: one ordered by actual value and one by absolute value. At position i, pop from the heap that matches the exponent parity. When an element is popped from one heap, mark it as deleted; when it reaches the top of the other heap later, skip it. Each push/pop costs O(log n), so the total is O(n log n) time and O(n) space. If all values are positive, this reduces to ordinary descending sort, but the heap version handles negative numbers without changing the code path.
Approach 3: Greedy with Balanced BST or Segment Tree (O(n log n))
Instead of lazy-deleting between two heaps, keep the remaining elements in an ordered multiset. For an odd exponent, query the maximum value; for an even exponent, query the maximum by absolute value. Remove the chosen element in O(log n). A TreeMap with counts in Java or a segment tree over compressed values works with duplicates. This approach has the same complexity as two heaps but is often easier to reason about during a proof of correctness.
Recommended for interviews: Use the two-heap greedy. Start with brute force to show correctness, then introduce the parity rule. Explain that even exponents compare by absolute value and odd exponents compare by numeric value; this is the insight that solves the whole problem. Mentioning the balanced BST alternative demonstrates that you understand the deletion tradeoff.
The written solution for this problem is still being prepared. Try it yourself in the meantime.
Try solving it yourselfComplexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Permutations | O(n! · n log n) | O(n) | Validation on small n |
| Greedy with Two Heaps | O(n log n) | O(n) | General case, handles negatives |
| Greedy with Balanced BST | O(n log n) | O(n) | When TreeMap/SortedList is available and duplicates are allowed |
Frequently asked questions
Is Lexicographically Largest Power Array easy or hard?
It is rated Hard with a 23.6% acceptance rate. The two-heap greedy is compact, but deriving the odd/even exponent rule and proving it is safe for negative numbers is the hard part.
Lexicographically Largest Power Array Python/Java solution
In Python, store `(-x, x)` and `(-abs(x), x)` in two heaps. In Java, use `PriorityQueue<Integer>(Comparator.reverseOrder())` and a custom comparator on `Math.abs`, plus a separate map to lazy-delete duplicates. Then alternate between heaps according to exponent parity.
How to solve Lexicographically Largest Power Array with heaps?
Push all values into a max-heap by numeric value and another max-heap by absolute value. When processing index i, pop from the heap matching exponent parity until an undeleted element is found, place it in the result, and lazy-delete it from the other heap. This maintains the greedy candidate in O(log n) per step.
What is the best approach for Lexicographically Largest Power Array?
The best approach is a greedy selection driven by two max-heaps. At each position, if the exponent is odd choose the largest remaining integer; if it is even choose the remaining integer with the largest absolute value. This gives O(n log n) time and O(n) space.
Is Lexicographically Largest Power Array asked at Google/Amazon/Meta?
This is a hard greedy/heap problem, and the underlying pattern of maintaining two dynamic extremes while constructing a lexicographically optimal sequence is frequently tested by Google and Amazon. There is no public confirmation that this exact problem appears, but the skills it tests are interview-relevant.
What data structure is used in Lexicographically Largest Power Array?
A max-heap is the core data structure, but you need two heaps: one ordered by the actual integer and one ordered by absolute value. Implementations include Python's heap with negative keys, Java's PriorityQueue with a reverse comparator, and C++'s priority_queue.
What is the time complexity of Lexicographically Largest Power Array?
The optimal two-heap solution runs in O(n log n) time. Inserting every element into the two heaps costs O(n), and each of the n deletions costs O(log n). Brute force permutation search is O(n! · n log n), so it is unusable for n > 8.