Maximize Sum After At Most K Digit Rearrangements solution and explanation
The problem
You are given an integer array nums of length n and an integer k.
In one operation, you may choose any element of nums and rearrange its decimal digits in any order to form a new integer.
Return the maximum possible sum of the array after performing at most k operations.
Example 1:
Input: nums = [123,45], k = 1
Output: 366
Explanation:
- We choose
nums[0] = 123and rearrange its digits to form 321. - The array becomes
[321, 45]. Thus, the total sum is321 + 45 = 366.
Example 2:
Input: nums = [102,90,14], k = 2
Output: 341
Explanation:
- We choose
nums[0] = 102and rearrange its digits to form 210. - We choose
nums[2] = 14and rearrange its digits to form 41. - The array becomes
[210, 90, 41]. Thus, the total sum is210 + 90 + 41 = 341.
Constraints:
1 <= n == nums.length <= 1051 <= nums[i] <= 1091 <= k <= n
Approach overview
Problem Overview: You get an array of integers and an integer k. In one operation you can rearrange the digits of any one number. You may use at most k operations. Return the maximum possible sum of the array.
Approach 1: Dynamic Programming over Operations (O(n * k) time, O(k) space)
For each number, compute its best possible value after one rearrangement. The best arrangement is the digits sorted in descending order, which gives the largest value. Call the gain the difference between the sorted value and the original value. Then run a knapsack-style DP. dp[j] holds the maximum sum using exactly j rearrangements so far. For each number, update the DP from high j to low j so each number is used at most once. This is correct but slow when k is large, and it is the approach to reach for when you want to confirm the greedy idea.
Approach 2: Greedy with Sorted Gains (O(n * d log d + n log n) time, O(n) space)
Each rearrangement is only useful if it increases the number, so only positive gains matter. Compute the gain for every number as described above, where d is the digit count. Sort the gains in descending order. Start from the original sum and add the top k positive gains. The key insight is that rearranging a number is independent of rearranging any other number, so the problem reduces to choosing the k largest independent gains. There is no need for a DP table. Prefer this approach in interviews and production code because it is simple and fast.
Recommended for interviews: Start by explaining the DP approach. It shows you understand that each number is an independent choice with a fixed gain. Then move to the greedy and justify why picking the k largest positive gains is optimal. The brute force shows understanding, but the greedy shows skill. Discuss the trade-off with the greedy algorithms pattern and dynamic programming to show you can pick the right tool.
Solution
Thinking
nreaches10^5, and each value has at most10digits. One operation rearranges the digits of a single number, so the change in the array sum is the rearranged value minus the original value.Writing the digits from largest to smallest produces the largest integer those digits can form, and the gain is never negative. Gains of different numbers do not interfere, so the operations should be spent on the numbers with the largest gains.
Compute the maximum rearrangement
t[i]for every number, then sort the indices by the gaint[i]-nums[i]in descending order. Replace the firstkvalues byt[i], keep the rest unchanged, and sum them.
For each nums[i], count the occurrences of digits 0 through 9, then append them from 9 down to 0. The result t[i] is the largest rearrangement. Since nums[i]\ge 1, the leading digit is the largest digit and is not zero. The gain t[i]-nums[i] is nonnegative.
Sort the indices by gain in descending order. After sorting, take the value from t for the first k positions and keep the original nums value for the rest. Their sum is the answer. A nonnegative gain means performing fewer operations cannot increase the sum, so at most k operations means choosing the k largest gains.
Each number has a constant number of digits. The time complexity is O(nlog n) and the space complexity is O(n), where n is the length of the array.
class Solution:
def maximizeSum(self, nums: list[int], k: int) -> int:
def f(x: int) -> int:
cnt = [0] * 10
while x:
x, v = divmod(x, 10)
cnt[v] += 1
y = 0
for i in range(9, -1, -1):
for _ in range(cnt[i]):
y = y * 10 + i
return y
n = len(nums)
t = [f(x) for x in nums]
ids = list(range(n))
ids.sort(key=lambda i: t[i] - nums[i], reverse=True)
return sum(t[ids[i]] if i < k else nums[ids[i]] for i in range(n))class Solution {
public long maximizeSum(int[] nums, int k) {
int n = nums.length;
int[] t = new int[n];
for (int i = 0; i < n; i++) {
int x = nums[i];
int[] cnt = new int[10];
while (x > 0) {
int v = x % 10;
x /= 10;
cnt[v]++;
}
int y = 0;
for (int j = 9; j >= 0; j--) {
for (int c = 0; c < cnt[j]; c++) {
y = y * 10 + j;
}
}
t[i] = y;
}
Integer[] ids = new Integer[n];
Arrays.setAll(ids, i -> i);
Arrays.sort(ids, (i, j) -> Integer.compare(t[j] - nums[j], t[i] - nums[i]));
long ans = 0;
for (int i = 0; i < n; i++) {
int x = nums[ids[i]];
ans += i < k ? t[ids[i]] : x;
}
return ans;
}
}class Solution {
public:
long long maximizeSum(vector<int>& nums, int k) {
auto f = [](int x) {
int cnt[10] = {};
while (x) {
int v = x % 10;
x /= 10;
cnt[v]++;
}
int y = 0;
for (int i = 9; i >= 0; i--) {
for (int j = 0; j < cnt[i]; j++) {
y = y * 10 + i;
}
}
return y;
};
int n = nums.size();
vector<int> t(n);
vector<int> ids(n);
iota(ids.begin(), ids.end(), 0);
for (int i = 0; i < n; i++) {
t[i] = f(nums[i]);
}
sort(ids.begin(), ids.end(), [&](int i, int j) {
return t[i] - nums[i] > t[j] - nums[j];
});
long long ans = 0;
for (int i = 0; i < n; i++) {
int x = nums[ids[i]];
ans += i < k ? t[ids[i]] : x;
}
return ans;
}
};function maximizeSum(nums: number[], k: number): number {
const f = (x: number): number => {
const cnt = Array(10).fill(0);
while (x > 0) {
const v = x % 10;
x = Math.floor(x / 10);
cnt[v]++;
}
let y = 0;
for (let i = 9; i >= 0; i--) {
for (let j = 0; j < cnt[i]; j++) {
y = y * 10 + i;
}
}
return y;
};
const n = nums.length;
const t = nums.map(x => f(x));
const ids = Array.from({ length: n }, (_, i) => i);
ids.sort((i, j) => t[j] - nums[j] - (t[i] - nums[i]));
let ans = 0;
for (let i = 0; i < n; i++) {
const x = nums[ids[i]];
ans += i < k ? t[ids[i]] : x;
}
return ans;
}func maximizeSum(nums []int, k int) int64 {
f := func(x int) int {
cnt := [10]int{}
for x > 0 {
v := x % 10
x /= 10
cnt[v]++
}
y := 0
for i := 9; i >= 0; i-- {
for j := 0; j < cnt[i]; j++ {
y = y*10 + i
}
}
return y
}
n := len(nums)
t := make([]int, n)
ids := make([]int, n)
for i, x := range nums {
t[i] = f(x)
ids[i] = i
}
sort.Slice(ids, func(i, j int) bool {
return t[ids[i]]-nums[ids[i]] > t[ids[j]]-nums[ids[j]]
})
var ans int64
for i := 0; i < n; i++ {
x := nums[ids[i]]
if i < k {
ans += int64(t[ids[i]])
} else {
ans += int64(x)
}
}
return ans
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming | O(n * k) | O(k) | When you want to verify the greedy or k is small |
| Greedy with Sorted Gains | O(n * d log d + n log n) | O(n) | General case and interviews (optimal) |
Frequently asked questions
Is Maximize Sum After At Most K Digit Rearrangements easy or hard?
It is a medium problem. The rearrangement logic is straightforward once you see that each number's gain is independent. The difficulty lies in recognizing the greedy choice and proving that picking the largest positive gains is optimal.
Maximize Sum After At Most K Digit Rearrangements Python solution?
In Python, convert each number to a string, sort its digits in reverse order with sorted(s, reverse=True), and compute the gain as the new integer minus the original. Filter positive gains, sort them with reverse=True, and return the original sum plus the sum of the first k gains.
How to solve Maximize Sum After At Most K Digit Rearrangements in O(n log n)?
Sort each number's digits descending to get its best value and compute the gain against the original. Collect all positive gains, sort them in descending order, and add the first k to the original sum. The sort of gains is the O(n log n) step.
What is the best approach for Maximize Sum After At Most K Digit Rearrangements?
The best approach is greedy. Compute the gain from sorting each number's digits in descending order, keep only the positive gains, sort them, and add the top k to the original sum. It runs in O(n log n) plus digit sorting time.
What data structure is used in Maximize Sum After At Most K Digit Rearrangements?
The greedy solution uses an array or list to store gains and relies on sorting. The DP solution uses a one-dimensional array of size k+1 as a knapsack table. No hash map or tree is required.
What is the time complexity of Maximize Sum After At Most K Digit Rearrangements?
The greedy solution runs in O(n * d log d + n log n) time, where n is the array length and d is the maximum number of digits per number. The DP solution runs in O(n * k) time. Space for the greedy is O(n).
Is Maximize Sum After At Most K Digit Rearrangements asked at Google, Amazon, or Meta?
FleetCode tags this problem under General and does not list specific company tags. Check company-tagged problem sets on other platforms if you need to confirm interview frequency for a specific employer.