Skip to main content
Talentd

Maximum Number of Upgradable Servers - Solution & Explanation

MediumPremiumFree on FleetCodeArrayMathBinary Search6 min readAsked at: Snowflake
Practice this problem

Problem Statement

You have n data centers and need to upgrade their servers.

You are given four arrays count, upgrade, sell, and money of length n, which show:

  • The number of servers
  • The cost of upgrading a single server
  • The money you get by selling a server
  • The money you initially have

for each data center respectively.

Return an array answer, where for each data center, the corresponding element in answer represents the maximum number of servers that can be upgraded.

Note that the money from one data center cannot be used for another data center.

 

Example 1:

Input: count = [4,3], upgrade = [3,5], sell = [4,2], money = [8,9]

Output: [3,2]

Explanation:

For the first data center, if we sell one server, we'll have 8 + 4 = 12 units of money and we can upgrade the remaining 3 servers.

For the second data center, if we sell one server, we'll have 9 + 2 = 11 units of money and we can upgrade the remaining 2 servers.

Example 2:

Input: count = [1], upgrade = [2], sell = [1], money = [1]

Output: [0]

 

Constraints:

  • 1 <= count.length == upgrade.length == sell.length == money.length <= 105
  • 1 <= count[i], upgrade[i], sell[i], money[i] <= 105

Approach Overview

Problem Overview: You are given an array describing servers and the resources required to upgrade them. Each upgrade consumes a limited shared budget. The task is to determine the maximum number of servers you can upgrade without exceeding the available resources.

Approach 1: Brute Force Simulation (O(n^2) time, O(1) space)

The most direct way is to try upgrading every possible subset size of servers. For a candidate count k, iterate through servers and calculate the resource required to upgrade each one, then check if the total cost of any k servers fits within the budget. This requires repeatedly recomputing upgrade costs and scanning the array. The approach is straightforward but inefficient because each candidate size requires scanning the array and recomputing totals.

Approach 2: Mathematical Cost Calculation + Binary Search (O(n log n) time, O(1) space)

A more efficient solution treats the answer as a monotonic search problem. If you can upgrade k servers within the budget, you can also upgrade any number smaller than k. That property allows binary search over the number of servers. For a given candidate k, compute the minimum cost required to upgrade k servers using a direct mathematical formula derived from the upgrade rules. The calculation iterates through the array and accumulates the resource requirement for each server. If the total exceeds the budget, the candidate is infeasible.

The key insight is that the upgrade requirement can be computed with simple arithmetic rather than simulating each upgrade step. Using mathematical reasoning, you derive the number of operations or resources required per server and sum them efficiently. Binary search reduces the number of checks from n to log n, giving a significant speed improvement.

Recommended for interviews: The mathematical approach with binary search is the expected solution. Brute force demonstrates the basic understanding of the problem constraints, but interviewers look for recognizing the monotonic property and applying binary search to minimize checks while computing upgrade cost using a direct formula.

Solution

For each data center, we assume that we can upgrade x servers, then x times upgrade[i] leq count[i] times sell[i] + money[i]. That is, x leq \frac{count[i] times sell[i] + money[i]}{upgrade[i] + sell[i]}. Also, x leq count[i], so we can take the minimum of the two.

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

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force SimulationO(n^2)O(1)Useful for understanding the upgrade cost calculation and validating logic on small inputs
Mathematics + Binary SearchO(n log n)O(1)Best general solution when the feasibility of upgrading k servers is monotonic

Video Solution

3155. Maximum Number of Upgradable Servers (Leetcode Medium) • Programming Live with Larry • 551 views views

Frequently Asked Questions

Is Maximum Number of Upgradable Servers easy or hard?
Maximum Number of Upgradable Servers is typically classified as a medium difficulty problem. The challenge lies in recognizing the monotonic property that allows binary search on the answer and deriving the correct mathematical formula for upgrade cost calculation.
Maximum Number of Upgradable Servers Python/Java solution
Implement a helper function that calculates the cost to upgrade k servers using arithmetic operations over the array. Then perform binary search on k from 0 to n. This logic can be implemented identically in Python, Java, C++, Go, or TypeScript because it relies on simple loops and integer math.
How to solve Maximum Number of Upgradable Servers in O(n log n)?
Binary search the number of servers you attempt to upgrade. For each candidate value k, compute the total upgrade cost using a mathematical formula derived from the problem constraints. If the cost is within the budget, increase the search range; otherwise decrease it. This feasibility check leads to an overall O(n log n) solution.
What is the best approach for Maximum Number of Upgradable Servers?
The optimal approach uses mathematical cost calculation combined with binary search. The number of servers that can be upgraded forms a monotonic range, so you binary search the answer and compute the upgrade cost for each candidate. This reduces the complexity to O(n log n) while using constant extra space.
Is Maximum Number of Upgradable Servers asked at Google/Amazon/Meta?
Problems involving resource allocation, binary search on answer, and mathematical feasibility checks frequently appear in interviews at companies like Google, Amazon, and Meta. Variations of server capacity or upgrade budgeting problems are common because they test optimization and algorithmic reasoning.
What data structure is used in Maximum Number of Upgradable Servers?
The main data structure is an array representing the servers and their upgrade requirements. The algorithm primarily performs array iteration and arithmetic calculations, with binary search applied to determine the optimal number of servers that can be upgraded.
What is the time complexity of Maximum Number of Upgradable Servers?
The optimized solution runs in O(n log n) time. Binary search determines the maximum number of upgradable servers in log n iterations, and each feasibility check scans the array to compute upgrade cost. Space complexity is O(1) because only a few variables are used for calculations.

Ready to solve this problem?

Practice Maximum Number of Upgradable Servers with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays