Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Maximize Sum of Device Ratings solution and explanation

MediumArrayGreedyMatrixSorting5 min read39.4% acceptanceUpdated 27 Jul 2026
Asked atGoogleAmazon
Practise Maximize Sum of Device Ratings
17:34
Leetcode 3961 Weekly Contest 506 Q3 | Maximize Sum of Device Ratings | Easy Solution🔥CodeSprint · 17:34 · 542 viewsWatch on YouTube
6 more videos on this problem
  1. Leetcode 3961 Weekly Contest 506 Q3 | Maximize Sum of Device Ratings | Easy Solution🔥CodeSprint · 17:34 · 542 views
  2. Weekly Contest 506 🔥 Leetcode 3961 | Maximize Sum of Device Ratings (Q3) | Greedy Logic + Dry Run Study Placement · 25:47 · 253 views
  3. Leetcode 3961 | Maximize Sum of Device Ratings | Leetcode weekly contest 506CodeWithMeGuys · 29:57 · 251 views
  4. Leetcode Weekly 506 | Maximize Sum of Device Ratings | Q3Algonaline · 16:11 · 105 views
  5. Maximize Sum of Device Ratings | Leetcode 3961 | Explanation With Code | javacodewithsitaram · 26:22 · 85 views
  6. 3961. Maximize Sum of Device Ratings LeetCode Weekly Contest 506 | Greedy Solution O(N) with Dry runBEASTCODES · 29:33 · 42 views
  7. Weekly Contest 506 | Leetcode 3961 | Maximize Sum of Device RatingsCode Like Him · 7:20 · 29 views

The problem

You are given a 2D integer array units of size m × n where units[i][j] represents the capacity of the jth unit in the ith device. Each device contains exactly n units.

The rating of a device is the minimum capacity among all its units.

You may perform the following operation any number of times (including zero):

  • Choose a device i that has not been used as a source before.
  • Remove exactly one unit from device i and add it to any different device.
  • Then mark device i as used, so it cannot be chosen again as a source.

Return the maximum possible sum of the ratings of all devices after any number of such operations.

Note:

  • Devices can receive units from multiple devices, regardless of whether they have been selected.
  • The rating of an empty device is 0.

Example 1:

Input: units = [[1,3],[2,2]]

Output: 4

Explanation:

  • ​​​​​​​​​​​​​​Select device i = 0 and transfer units[0][0] = 1 to device i = 1.
  • After the transfer, the ratings are:
    • Device 0 = [3]: rating[0] = 3
    • Device 1 = [2, 2, 1]: rating[1] = 1
  • Thus, the sum of ratings is 3 + 1 = 4.

Example 2:

Input: units = [[1,2,3],[4,5,6]]

Output: 6

Explanation:

  • Select device i = 1 and transfer units[1][0] = 4 to device i = 0.
  • After the transfer, the ratings are:
    • Device 0 = [1, 2, 3, 4]: rating[0] = 1
    • Device 1 = [5, 6]: rating[1] = 5
  • Thus, the sum of ratings is 1 + 5 = 6.

Example 3:

Input: units = [[5,5,5],[1,1,1]]

Output: 6

Explanation:

  • No transfers increase the sum of ratings. Thus, the sum of ratings is 5 + 1 = 6.

Constraints:

  • 1 <= m == units.length <= 105
  • 1 <= n == units[i].length <= 105
  • m * n <= 2 * 105
  • 1 <= units[i][j] <= 105

Approach overview

Problem Overview: You are given an array representing device ratings. Activating certain devices may restrict activating adjacent ones, so the goal is to choose a subset of devices that maximizes the total rating while respecting the constraint.

Approach 1: Brute Force Recursion (Exponential Time, O(2^n) time, O(n) space)

Try every possible subset of devices. At each index, you either activate the current device or skip it. If you activate it, the next device cannot be chosen, so the recursion jumps two indices forward. If you skip it, continue with the next index. This approach explores the full decision tree and guarantees the correct answer, but the repeated recalculation of overlapping subproblems causes exponential runtime.

Approach 2: Dynamic Programming with Memoization (O(n) time, O(n) space)

The recursive solution repeatedly solves the same states. Store results in a memo array where dp[i] represents the maximum rating achievable starting from index i. For each position, compute max(rating[i] + dp[i+2], dp[i+1]). Each state is evaluated once, reducing complexity to linear time. This method clearly exposes the overlapping subproblem structure typical in dynamic programming problems.

Approach 3: Bottom-Up DP (O(n) time, O(n) space)

Instead of recursion, build the solution iteratively. Define dp[i] as the best sum achievable considering the first i devices. The transition becomes dp[i] = max(dp[i-1], dp[i-2] + rating[i]). Iterate through the array once while maintaining this relationship. This version avoids recursion overhead and is easier to reason about during interviews. The approach relies on recognizing optimal substructure within the array.

Approach 4: Space Optimized DP (O(n) time, O(1) space)

The DP transition only depends on the previous two states. Instead of maintaining the entire DP array, track two variables representing dp[i-1] and dp[i-2]. For each device rating, compute the new best value and shift the variables forward. This keeps memory usage constant while preserving the same linear runtime. The logic mirrors classic patterns seen in many dynamic programming optimization problems.

Recommended for interviews: Start by describing the brute force choice of picking or skipping a device to show understanding of the problem structure. Then transition to dynamic programming, which interviewers typically expect. The space‑optimized DP solution demonstrates strong problem‑solving ability because it recognizes that only two previous states are required.

Solution

Adding a unit to a device can only decrease or keep its rating unchanged. Therefore, if n = 1, we can directly return the sum of all device ratings.

Otherwise, we sort the units of each device in ascending order, take the smallest unit from each device, and concentrate them into one device with rating mn. If we concentrate them into device i, the rating of device i changes from the second smallest value mn2 to mn, so the total rating decreases by mn2 - mn. To maximize the total rating, we should choose the device with the smallest decrease, i.e., the device with the smallest mn2.

The time complexity is O(m times n), where m and n are the number of devices and the number of units per device, respectively. The space complexity is O(1).

class Solution:
    def maxRatings(self, units: List[List[int]]) -> int:
        n = len(units[0])
        if n == 1:
            return sum(x[0] for x in units)

        ans = 0
        mn = mn2 = inf
        for x in units:
            x.sort()
            ans += x[1]
            mn2 = min(mn2, x[1])
            mn = min(mn, x[0])
        ans -= mn2 - mn
        return ans
class Solution {
    public long maxRatings(int[][] units) {
        int n = units[0].length;
        if (n == 1) {
            long ans = 0;
            for (int[] x : units) {
                ans += x[0];
            }
            return ans;
        }

        long ans = 0;
        int mn = Integer.MAX_VALUE;
        int mn2 = Integer.MAX_VALUE;

        for (int[] x : units) {
            Arrays.sort(x);
            ans += x[1];
            mn2 = Math.min(mn2, x[1]);
            mn = Math.min(mn, x[0]);
        }

        ans -= (mn2 - mn);

        return ans;
    }
}
class Solution {
public:
    long long maxRatings(vector<vector<int>>& units) {
        int n = units[0].size();
        if (n == 1) {
            long long ans = 0;
            for (auto& x : units) {
                ans += x[0];
            }
            return ans;
        }

        long long ans = 0;
        int mn = INT_MAX;
        int mn2 = INT_MAX;

        for (auto& x : units) {
            sort(x.begin(), x.end());
            ans += x[1];
            mn2 = min(mn2, x[1]);
            mn = min(mn, x[0]);
        }

        return ans - (mn2 - mn);
    }
};
function maxRatings(units: number[][]): number {
    const n = units[0].length;

    if (n === 1) {
        let ans = 0;
        for (const x of units) {
            ans += x[0];
        }
        return ans;
    }

    let ans = 0;
    let mn = Infinity;
    let mn2 = Infinity;

    for (const x of units) {
        x.sort((a, b) => a - b);
        ans += x[1];
        mn2 = Math.min(mn2, x[1]);
        mn = Math.min(mn, x[0]);
    }

    return ans - (mn2 - mn);
}
func maxRatings(units [][]int) int64 {
	n := len(units[0])
	if n == 1 {
		var ans int64
		for _, x := range units {
			ans += int64(x[0])
		}
		return ans
	}

	var ans int64
	mn, mn2 := int(^uint(0)>>1), int(^uint(0)>>1)

	for _, x := range units {
		sort.Ints(x)
		ans += int64(x[1])
		if x[1] < mn2 {
			mn2 = x[1]
		}
		if x[0] < mn {
			mn = x[0]
		}
	}

	return ans - int64(mn2-mn)
}
Try this approach in the editor

Complexity analysis

ApproachTimeSpaceWhen to Use
Brute Force RecursionO(2^n)O(n)Useful for understanding the decision tree and problem structure
DP with MemoizationO(n)O(n)General solution when using recursion with caching
Bottom-Up Dynamic ProgrammingO(n)O(n)Preferred iterative DP approach in interviews
Space Optimized DPO(n)O(1)When memory efficiency matters and only previous states are required

Frequently asked questions

Is Maximize Sum of Device Ratings easy or hard?

The problem is typically classified as medium difficulty. The main challenge is recognizing the dynamic programming pattern and understanding why selecting a device prevents choosing its adjacent neighbor.

Maximize Sum of Device Ratings Python/Java solution

Most implementations use a loop with two variables tracking previous DP states. The logic is identical across languages like Python, Java, and C++: update current = max(prev1, prev2 + rating) and shift the variables forward.

How to solve Maximize Sum of Device Ratings in O(n)?

Use dynamic programming. Maintain two variables representing the maximum rating up to the previous device and the device before that. For each rating, compute max(skip current, take current + value two positions back). Iterate through the array once.

What is the best approach for Maximize Sum of Device Ratings?

The most efficient solution uses dynamic programming with constant space. Track the best rating sum including or excluding the current device. At each step compute max(previous best, rating[i] + best two steps back). This runs in O(n) time and O(1) space.

Is Maximize Sum of Device Ratings asked at Google/Amazon/Meta?

Problems with the same structure frequently appear in interviews at companies like Amazon, Google, and Meta because they test recognition of dynamic programming patterns similar to the classic House Robber problem.

What data structure is used in Maximize Sum of Device Ratings?

The solution primarily uses arrays or simple variables for dynamic programming state tracking. No complex data structures are required, though understanding array traversal and DP state transitions is essential.

What is the time complexity of Maximize Sum of Device Ratings?

The optimal dynamic programming solution runs in O(n) time because each device rating is processed once. Space complexity can be reduced to O(1) by storing only the last two DP states instead of a full array.

Comments

Now write it yourselfClose this page and solve Maximize Sum of Device Ratings in the editor, without looking.
Practise Maximize Sum of Device Ratings