Heaters Leetcode Solution In C++/Python/Java
Heaters Problem Description:
Winter is coming! During the contest, your first job is to design a standard heater with a fixed warm radius to warm all the houses.
Every house can be warmed, as long as the house is within the heater's warm radius range.
Given the positions of houses and heaters on a horizontal line, return the minimum radius standard of heaters so that those heaters could cover all houses.
Notice that all the heaters follow your radius standard, and the warm radius will be the same.
Examples:
Input: houses = [1,2,3], heaters = [2]
Output: 1
Explanation: The only heater was placed in position 2, and if we use the radius 1 standard, then all the houses can be warmed.
Input: houses = [1,2,3,4], heaters = [1,4]
Output: 1
Explanation: The two heaters were placed at positions 1 and 4. We need to use a radius 1 standard, then all the houses can be warmed.
Input: houses = [1,5], heaters = [2]
Output: 3
Explanation: The only heater is placed at position 2. The house at 1 needs a radius of 1 to be covered, but the house at 5 is 3 units away from the heater. Therefore, we need a radius of 3 to ensure all houses are warmed.
Constraints:
1 ≤ houses.length, heaters.length ≤ 3 * 10⁴
1 ≤ houses[i], heaters[i] ≤ 10⁹
Brute Force Approach
To approach the problem, we are given an integer array houses and an integer array heaters, and we need to determine the minimum radius required for heaters so that all houses are covered. Each heater warms all houses within its warm radius range.
Our goal is to find the smallest radius such that every house is within the range of at least one heater.
What can be the minimum radius needed?
The minimum radius required should be 0, i.e., if every house already has a heater at its position, no additional radius is needed.
What would be the maximum radius?
The maximum radius required should be the largest distance between a house and its closest heater. This is because, at this radius, all houses will be within the range of at least one heater.
Since 1 ≤ houses[i], heaters[i] ≤ 10⁹, in the worst case, the required radius can go up to 1e9. Therefore, we take the maximum possible radius as 1e9 and search within this range.
Thus, our search space for the answer ranges from 0 to the 1e9. Now, the problem reduces to finding the minimum radius such that all houses are covered by at least one heater.
A basic approach is to iterate through all possible radii from 0 to 1e9 and check whether all houses can be warmed with that radius. If it is possible, then it is a valid solution; otherwise, we increase the radius and check again. We continue this process until we find the smallest radius that allows us to warm all houses.
Since the range from 0 to 1e9 covers all possible radii, starting from the smallest and stopping at the first valid radius will give us the desired result.
Consider the example with houses = [1,2,3,4] and heaters = [1,4].
We start by taking the smallest possible radius, which is 0, as the minimum possible radius to cover all houses, and the largest possible radius, which we assume to be 1e9, as the maximum possible radius.
We then check whether all houses can be warmed at each of these radii:
- For radius = 0, only houses at positions 1 and 4 are warmed. Houses at 2 and 3 are not covered, so it doesn't work.
- For radius = 1, houses at 1, 2, 3, and 4 are all warmed. Since all houses are covered, this works.
- For radius = 2, houses at 1, 2, 3, and 4 are all warmed. Since all houses are covered, this works.
Since radius = 1 is the smallest radius where all houses can be warmed, it is the minimum required radius.
So, the answer is 1.
Let's call the smallest radius needed to cover all houses as minRadius.
Any radius between 0 and minRadius - 1 won't work because it will always leave some houses uncovered.
However, any radius from minRadius to 1e9 will allow us to cover all houses.
Therefore, minRadius is the smallest required radius to warm all houses, and we return minRadius as the answer.
How Can We Determine if a Given Radius is Valid (Real World Example)?
Imagine you have a row of houses, and each house needs to be warmed by a heater. Each heater has a fixed warm radius, and your goal is to find the minimum possible radius that ensures every house is covered. However, houses and heaters are placed at different positions, so you need to determine whether, given a certain radius, all houses can be covered.
To achieve this, we simulate the process of checking whether all houses fall within the range of at least one heater.
Imagine you're moving along the street, checking if each house can be covered by a nearby heater. You use two pointers:
- i (index for houses): This keeps track of the houses as we move forward.
- j (index for heaters): This keeps track of the heaters as we check their coverage.
As you move along the street, you check whether a house falls within the range of the current heater.
Before we start the search, we must ensure both houses and heaters are sorted.
- This is because we are using a two-pointer approach where we compare the closest heater to each house.
- If the arrays are not sorted, we might miss the closest heater for a house, leading to incorrect results.
- Sorting allows us to traverse both lists efficiently without unnecessary backtracking.
- Checking If a House is Covered
- If the current heater at heaters[j] can warm the current house at houses[i] within the given radius mid, then this house is successfully warmed.
- This can be done easily by (abs(houses[i] - heaters[j]) <= k), where k is the radius of heater.
- We move to the next house (i++) since it is covered.
If a house is covered by the current heater, you don’t need to check further for this house; just move to the next one.
- Moving to the Next Heater (j++)
- If the current heater cannot warm the house at position houses[i], then the heater is too far.
- In this case, we move to the next heater (j++) in hopes that it will cover the house.
We keep going until either all houses are covered (i >= houses.size()) or we run out of heaters. If all houses are covered, then the given radius is valid. If we run out of heaters while some houses remain uncovered, then the given radius is too small.
If all houses are covered, we return true → The radius k is valid. If some houses remain uncovered, we return false → The radius k is too small, and we need to increase it.
Let's understand with an example:
Heaters Example:
Input: houses = [1,5], heaters = [2]
Step 1: Identify Search Range
- Minimum radius = 0 (houses can be exactly at heaters)
- Maximum radius = 1e9
- We need to find the smallest radius that ensures every house is covered by at least one heater.
Step 2: Checking for Valid Radii
Radius = 0:
- Heater at position 2 can cover:
- House at 1? No (|1 - 2| = 1 > 0)
- House at 5? No (|5 - 2| = 3 > 0)
- Not all houses are covered → Invalid radius
Radius = 1:
- Heater at 2 can cover:
- House at 1? Yes (|1 - 2| = 1 ≤ 1)
- House at 5? No (|5 - 2| = 3 > 1)
- Not all houses are covered → Invalid radius
Radius = 2:
- Heater at 2 can cover:
- House at 1? Yes (|1 - 2| = 1 ≤ 2)
- House at 5? No (|5 - 2| = 3 > 2)
- Not all houses are covered → Invalid radius
Radius = 3:
- Heater at 2 can cover:
- House at 1? Yes (|1 - 2| = 1 ≤ 3)
- House at 5? Yes (|5 - 2| = 3 ≤ 3)
- All houses are covered → Valid radius
Conclusion
The minimum radius required to cover all houses is 3.
Output: 3
Steps to Implement the Solution:
Define the Helper Function (isPossible):
- Initialize two pointers, i for houses and j for heaters.
- Traverse through both houses and heaters using a two-pointer approach:
- If the current house is within the coverage range of the current heater (abs(houses[i] - heaters[j]) ≤ mid), move to the next house.
- Otherwise, move to the next heater to check if it can cover the house.
- If all houses are covered by some heater, return true; otherwise, return false.
Find the Range for the Radius:
- Initialize low as 0, representing the minimum possible radius.
- Initialize high as 1e9, representing the maximum possible radius.
- Sort both houses and heaters to efficiently check coverage using two pointers.
Iterate Over All Possible Radii:
- Iterate from low to high to check all possible radii:
- For each radius i, use the isPossible function to check if all houses can be covered.
- If a valid radius i is found, store it as minRadius and break the loop.
Return the Result:
- Return minRadius as the smallest radius required to cover all houses.
Heaters Leetcode Solution
Heaters Leetcode Solution / Code Implementation
1. Heater solution in C++ Try on Compiler
class Solution {
// Function to check if a given radius (mid) is sufficient to cover all houses
bool isPossible(vector<int>& houses, vector<int>& heaters, long long mid) {
// Pointer for houses
int i = 0;
// Pointer for heaters
int j = 0;
// Traverse both houses and heaters
while (i < houses.size() && j < heaters.size()) {
// If the house is within the range of the heater, move to the next house
if (abs(houses[i] - heaters[j]) <= mid) {
i++;
} else {
// Otherwise, move to the next heater to try covering the house
j++;
}
}
// If all houses are covered, return true
return i >= houses.size();
}
public:
// Function to find the minimum radius required to cover all houses
int findRadius(vector<int>& houses, vector<int>& heaters) {
// Minimum possible radius
long long low = 0;
// Maximum possible radius
long long high = 1e9;
// Sort both houses and heaters to use a two-pointer approach
sort(houses.begin(), houses.end());
sort(heaters.begin(), heaters.end());
long long minRadius = 0;
// Perform linear search from low to high to find the smallest valid radius
for (int i = low; i <= high; i++) {
if (isPossible(houses, heaters, i)) {
minRadius = i;
break;
}
}
// Return the minimum valid radius
return minRadius;
}
};
2. Heater solution in Java Try on Compiler
import java.util.Arrays;
class Solution {
// Function to check if a given radius (mid) is sufficient to cover all houses
private boolean isPossible(int[] houses, int[] heaters, long mid) {
int i = 0; // Pointer for houses
int j = 0; // Pointer for heaters
// Traverse both houses and heaters
while (i < houses.length && j < heaters.length) {
// If the house is within the range of the heater, move to the next house
if (Math.abs(houses[i] - heaters[j]) <= mid) {
i++;
} else {
// Otherwise, move to the next heater to try covering the house
j++;
}
}
// If all houses are covered, return true
return i >= houses.length;
}
// Function to find the minimum radius required to cover all houses
public int findRadius(int[] houses, int[] heaters) {
long low = 0; // Minimum possible radius
long high = (long) 1e9; // Maximum possible radius
// Sort both houses and heaters to use a two-pointer approach
Arrays.sort(houses);
Arrays.sort(heaters);
long minRadius = 0;
// Perform linear search from low to high to find the smallest valid radius
for (long i = low; i <= high; i++) {
if (isPossible(houses, heaters, i)) {
minRadius = i;
break;
}
}
// Return the minimum valid radius
return (int) minRadius;
}
}
3. Heater solution in Python Try on Compiler
class Solution:
# Function to check if a given radius (mid) is sufficient to cover all houses
def isPossible(self, houses, heaters, mid):
i = 0 # Pointer for houses
j = 0 # Pointer for heaters
# Traverse both houses and heaters
while i < len(houses) and j < len(heaters):
# If the house is within the range of the heater, move to the next house
if abs(houses[i] - heaters[j]) <= mid:
i += 1
else:
# Otherwise, move to the next heater to try covering the house
j += 1
# If all houses are covered, return True
return i >= len(houses)
# Function to find the minimum radius required to cover all houses
def findRadius(self, houses, heaters):
low = 0 # Minimum possible radius
high = int(1e9) # Maximum possible radius
# Sort both houses and heaters to use a two-pointer approach
houses.sort()
heaters.sort()
minRadius = 0
# Perform linear search from low to high to find the smallest valid radius
for i in range(low, high + 1):
if self.isPossible(houses, heaters, i):
minRadius = i
break
# Return the minimum valid radius
return minRadius
4. Heater solution in Javascript Try on Compiler
/**
* @param {number[]} houses
* @param {number[]} heaters
* @return {number}
*/
// Function to check if a given radius (mid) is sufficient to cover all houses
var isPossible = function (houses, heaters, mid) {
let i = 0; // Pointer for houses
let j = 0; // Pointer for heaters
// Traverse both houses and heaters
while (i < houses.length && j < heaters.length) {
// If the house is within the range of the heater, move to the next house
if (Math.abs(houses[i] - heaters[j]) <= mid) {
i++;
} else {
// Otherwise, move to the next heater to try covering the house
j++;
}
}
// If all houses are covered, return true
return i >= houses.length;
}
var findRadius = function (houses, heaters) {
let low = 0; // Minimum possible radius
let high = 1e9; // Maximum possible radius
// Sort both houses and heaters to use a two-pointer approach
houses.sort((a, b) => a - b);
heaters.sort((a, b) => a - b);
let minRadius = 0;
// Perform linear search from low to high to find the smallest valid radius
for (let i = low; i <= high; i++) {
if (isPossible(houses, heaters, i)) {
minRadius = i;
break;
}
}
// Return the minimum valid radius
return minRadius;
};Heaters Complexity Analysis (Brute Force)
Time Complexity: O(maxRadius × (n + m))
- Sorting Step
Before applying the search, we sort both houses and heaters arrays.
- Sorting takes O(n log n) for houses and O(m log m) for heaters using an efficient sorting algorithm like Quicksort or Mergesort.
- Here, n = number of houses, m = number of heaters.
- Sorting complexity:
O(n log n) + O(m log m)
- Searching for the Minimum Radius
We iterate from 0 to maxRadius (high limit) using a linear search.
- Worst-case scenario: We check all high values from 0 to maxRadius.
- This results in O(maxRadius) iterations, which is extremely inefficient, as maxRadius is up to 1e9.
- Checking Validity (isPossible Function)
For each radius, we check if it covers all houses using a two-pointer approach.
- The two-pointer approach processes both houses and heaters in a single pass.
- It runs in O(n + m) time in the worst case.
Total Time Complexity
- Sorting: O(n log n) + O(m log m)
- Linear Search: O(maxRadius)
- Checking Validity (isPossible): O(n + m) per iteration
Since we are iterating from 0 to maxRadius and calling isPossible in each step, the total complexity is: O(maxRadius × (n + m))
Space Complexity: O(n + m)
- Auxiliary Space Complexity: O(1)
The algorithm only uses a few integer variables like low, high, mid, minRadius, i, j, etc. These are just primitive variables that occupy O(1) space.
Therefore, the auxiliary space complexity is O(1). - Total Space Complexity: O(n + m)
We sort the input arrays, but we do not create any additional data structures apart from the given houses and heaters arrays.
The input itself takes O(n + m) space, where n = size of houses and m = size of heaters.
Therefore, the total space complexity is O(n + m)
Will Brute Force Work Against the Given Constraints?
For the current solution, the time complexity is O(maxRadius × (n + m)), where n is the number of houses (1 ≤ houses.length ≤ 3 × 10⁴) and m is the number of heaters (1 ≤ heaters.length ≤ 3 × 10⁴). In the worst-case scenario, maxRadius can be as large as 10⁹ (since 1 ≤ houses[i], heaters[i] ≤ 10⁹), which leads to a time complexity of O(maxRadius × (n + m)).
This can become inefficient because maxRadius can be very large(1e9), making the solution impractical for many inputs, particularly when maxRadius is close to its upper bound.
Given the constraints, with n and m up to 3 × 10⁴ and maxRadius reaching up to 10⁹, the solution may not execute efficiently for a wide range of inputs, especially when maxRadius is large. While it may work well for inputs with a smaller maxRadius, this time complexity does not guarantee that it will perform optimally for all cases.
In competitive programming environments, problems generally allow up to 10⁶ operations per test case. For most typical inputs, the solution might work fine, but in the worst-case scenario, the time complexity could exceed the limits. Optimizations are necessary to handle inputs where maxRadius is large, making the solution more efficient and suitable for all possible cases.
How to optimize it?
In the previous approach, we looked at the minimum and maximum possible heater radius and checked every radius in that range to find the smallest radius that could cover all houses. This gave us O(maxRadius × (n + m)) time complexity, which was too slow and caused TLE (Time Limit Exceeded).
Now, let’s think about improving this.
The main issue was that we checked every radius from 0 to the maximum possible value, which took a lot of time.
Can we make this part faster?
Yes! Here’s the hint:
We are searching for the minimum radius that works, and we know it lies between 0 and the maxRadius i.e 1e9.
Now that we know the two endpoints, 0 and the maximum radius, let's make a few observations:
- The data structure is sorted:
We sort houses and heaters first, allowing us to use a two-pointer approach efficiently. Sorting ensures that we process houses and heaters in a logical order, reducing unnecessary computations. - The search space is monotonic:
- If a certain radius allows us to warm all houses, then any larger radius will also work.
- If a certain radius does not allow us to warm all houses, then any smaller radius will also fail.
- For example, with houses = [1,2,3,4] and heaters = [1,4], the algorithm will fail to warm all houses for radius 0 since some houses are out of the heaters' range. Starting from radius 1, it will succeed in covering all houses, and the search will find that 1 is the minimum radius where this happens.
This illustrates the monotonic property: once a radius works, it will continue to work for all larger values.
- The middle element helps minimize or maximize the search space:
If we take the middle value of the current range and check if it works (i.e., can we cover all houses with this radius?), we can narrow the search space:
If it works, we move to the left half to find a smaller valid radius.
If it doesn’t work, we move to the right half to find a larger valid radius.
If we plot a graph with possible radius values on the x-axis and whether we can cover all houses on the y-axis, we can observe the following:
- For a given radius, we can either cover all houses or not.
- Before the minimum valid radius (mindays equivalent), we cannot warm all houses. This is because the heaters’ range is too small to reach all houses.
- From the minimum valid radius onward, all houses can be warmed, and this condition remains valid as the radius increases.
Thus, the minimum radius represents the smallest possible value at which all houses can be covered, and from that point forward, increasing the radius remains feasible but unnecessary.
With these points in mind, it's clear that instead of linearly checking all values from 0 to the maximum possible radius, we can take the middle value and continually reduce the search space.
Does this approach remind you of something you've seen before?
Yes, we are applying binary search here. By leveraging the sorted and monotonic properties of the radius range, we efficiently narrow down the search space to find the minimum radius that meets the condition, instead of checking each radius linearly.
Heaters Binary Search Algorithm
Binary search can help us quickly find the minimum radius required to warm all houses.
We can simply use binary search to determine the smallest radius that ensures every house is covered by at least one heater.
Start by taking the middle value between low (minimum possible radius) and high (maximum possible radius). If this mid-radius satisfies the condition that all houses are covered by at least one heater within this range, we store it as a potential answer and narrow the search space to the left half, looking for a smaller valid radius. Otherwise, we move the search to the right half to find a larger valid radius.
We continue this process as long as low <= high.
Once the condition breaks, the stored answer is returned as the minimum radius required. By using binary search, we can cut the search space in half at each step, which makes the solution much faster and avoids the TLE issue.
Let us understand this with a video.
heaters-optimal-approach-animation
Let's understand with an example:
Heaters Example:
Input: houses = [1,5], heaters = [2]
Step 1: Identify Search Range
- low = 0, high = 1e9 (Theoretically)
- However, the maximum required radius is max(abs(1 - 2), abs(5 - 2)) = 3
- So, we can start with high = 3 to avoid unnecessary calculations
Step 2: Apply Binary Search
Iteration 1:
- mid = (0 + 3) / 2 = 1
- Check if radius 1 covers all houses:
- House 1 is within 1 unit of heater 2
- House 5 is not within 1 unit of heater 2
- Not valid → Increase radius → low = mid + 1 = 2
Iteration 2:
- mid = (2 + 3) / 2 = 2
- Check if radius 2 covers all houses:
- House 1 is within 2 units of heater 2
- House 5 is not within 2 units of heater 2
- Not valid → Increase radius → low = mid + 1 = 3
Iteration 3:
- mid = (3 + 3) / 2 = 3
- Check if radius 3 covers all houses:
- House 1 is within 3 units of heater 2
- House 5 is within 3 units of heater 2
- Valid → Store answer = 3 and reduce radius → high = mid - 1 = 2
Conclusion
Binary search ends when low > high. The minimum radius required to cover all houses is 3.
Output: 3
How to code it up:
Here are concise steps to code up the solution generically:
Sort Houses and Heaters
- Sorting is required for efficient two-pointer traversal.
Use Binary Search on Radius
- Set the search range low = 0 and high = 1e9 (maximum possible radius).
- Perform binary search to find the minimum valid radius.
Check Feasibility of a Given Radius (isPossible Function)
- Use two-pointer technique to check if all houses can be covered by heaters within the given radius.
Adjust Search Space Based on Feasibility
- If the current radius works, update minRadius and search for a smaller value.
- If it doesn’t work, increase the search radius.
Return the Minimum Valid Radius
- The binary search ensures we find the smallest possible radius that covers all houses.
Heaters Leetcode Solution
Heaters Leetcode Solution / Code Implementation
1. Heaters solution in C++ Try on Compiler
class Solution {
// Helper function to check if a given radius 'mid' can cover all houses
bool isPossible(vector<int>& houses, vector<int>& heaters, long long mid)
{
// Pointer for houses
int i = 0;
// Pointer for heaters
int j = 0;
// Traverse both houses and heaters
while (i < houses.size() && j < heaters.size())
{
// If the house is within the range of the heater, move to the next house
if (abs(houses[i] - heaters[j]) <= mid)
{
i++;
}
// Otherwise, move to the next heater to try covering the house
else
{
j++;
}
}
// Return true if all houses are covered
return i >= houses.size();
}
public:
// Function to find the minimum radius required to cover all houses
int findRadius(vector<int>& houses, vector<int>& heaters) {
// Minimum possible radius
long long low = 0;
// Maximum possible radius
long long high = 1e9;
// Sort both houses and heaters to use a two-pointer approach
sort(houses.begin(), houses.end());
sort(heaters.begin(), heaters.end());
// Variable to store the minimum valid radius
long long minRadius = 0;
// Perform binary search to find the optimal radius
while (low <= high)
{
// Calculate the middle radius
long long mid = low + (high - low) / 2;
// Check if the current radius can cover all houses
if (isPossible(houses, heaters, mid))
{
// Store the valid radius and try to minimize it further
minRadius = mid;
high = mid - 1;
}
// If the radius is not sufficient, increase it
else
{
low = mid + 1;
}
}
// Return the minimum valid radius
return minRadius;
}
};
2. Heaters solution in Java Try on Compiler
import java.util.Arrays;
class Solution {
// Helper function to check if a given radius 'mid' can cover all houses
private boolean isPossible(int[] houses, int[] heaters, long mid) {
// Pointer for houses
int i = 0;
// Pointer for heaters
int j = 0;
// Traverse both houses and heaters
while (i < houses.length && j < heaters.length) {
// If the house is within the range of the heater, move to the next house
if (Math.abs(houses[i] - heaters[j]) <= mid) {
i++;
}
// Otherwise, move to the next heater to try covering the house
else {
j++;
}
}
// Return true if all houses are covered
return i >= houses.length;
}
// Function to find the minimum radius required to cover all houses
public int findRadius(int[] houses, int[] heaters) {
// Minimum possible radius
long low = 0;
// Maximum possible radius
long high = (long) 1e9;
// Sort both houses and heaters to use a two-pointer approach
Arrays.sort(houses);
Arrays.sort(heaters);
// Variable to store the minimum valid radius
long minRadius = 0;
// Perform binary search to find the optimal radius
while (low <= high) {
// Calculate the middle radius
long mid = low + (high - low) / 2;
// Check if the current radius can cover all houses
if (isPossible(houses, heaters, mid)) {
// Store the valid radius and try to minimize it further
minRadius = mid;
high = mid - 1;
}
// If the radius is not sufficient, increase it
else {
low = mid + 1;
}
}
// Return the minimum valid radius
return (int) minRadius;
}
}
3. Heaters solution in Python Try on Compiler
class Solution:
# Helper function to check if a given radius 'mid' can cover all houses
def isPossible(self, houses, heaters, mid):
# Pointer for houses
i = 0
# Pointer for heaters
j = 0
# Traverse both houses and heaters
while i < len(houses) and j < len(heaters):
# If the house is within the range of the heater, move to the next house
if abs(houses[i] - heaters[j]) <= mid:
i += 1
# Otherwise, move to the next heater to try covering the house
else:
j += 1
# Return True if all houses are covered
return i >= len(houses)
# Function to find the minimum radius required to cover all houses
def findRadius(self, houses, heaters):
# Minimum possible radius
low = 0
# Maximum possible radius
high = int(1e9)
# Sort both houses and heaters to use a two-pointer approach
houses.sort()
heaters.sort()
# Variable to store the minimum valid radius
minRadius = 0
# Perform binary search to find the optimal radius
while low <= high:
# Calculate the middle radius
mid = low + (high - low) // 2
# Check if the current radius can cover all houses
if self.isPossible(houses, heaters, mid):
# Store the valid radius and try to minimize it further
minRadius = mid
high = mid - 1
# If the radius is not sufficient, increase it
else:
low = mid + 1
# Return the minimum valid radius
return minRadius
4. Heaters solution in Javascript Try on Compiler
/**
* @param {number[]} houses
* @param {number[]} heaters
* @return {number}
*/
// Function to check if a given radius (mid) is sufficient to cover all houses
var isPossible = function (houses, heaters, mid) {
let i = 0; // Pointer for houses
let j = 0; // Pointer for heaters
// Traverse both houses and heaters
while (i < houses.length && j < heaters.length) {
// If the house is within the range of the heater, move to the next house
if (Math.abs(houses[i] - heaters[j]) <= mid) {
i++;
} else {
// Otherwise, move to the next heater to try covering the house
j++;
}
}
// If all houses are covered, return true
return i >= houses.length;
}
var findRadius = function (houses, heaters) {
// Minimum possible radius
let low = 0;
// Maximum possible radius
let high = 1e9;
// Sort both houses and heaters to use a two-pointer approach
houses.sort((a, b) => a - b);
heaters.sort((a, b) => a - b);
// Variable to store the minimum valid radius
let minRadius = 0;
// Perform binary search to find the optimal radius
while (low <= high) {
// Calculate the middle radius
let mid = Math.floor(low + (high - low) / 2);
// Check if the current radius can cover all houses
if (isPossible(houses, heaters, mid)) {
// Store the valid radius and try to minimize it further
minRadius = mid;
high = mid - 1;
}
// If the radius is not sufficient, increase it
else {
low = mid + 1;
}
}
// Return the minimum valid radius
return minRadius;
};Heaters Complexity Analysis (Binary Search)
Time Complexity: O(n log n + m log m)
The binary search approach for finding the minimum radius consists of three main steps:
- Sorting the input arrays
- Binary search to find the optimal radius
- Checking if a given radius is sufficient using a two-pointer traversal
Step 1: Sorting the Input Arrays
- Sorting houses and heaters requires O(n log n + m log m) time, where:
- n is the number of houses.
- m is the number of heaters.
- This is the dominant cost outside of the binary search.
Step 2: Binary Search on the Radius
- The search space for low to high is [0, 1e9], meaning the binary search runs in O(log 1e9) = O(30) iterations.
Step 3: Checking If a Given Radius Works
- In each binary search iteration, we check if the current mid radius can cover all houses.
- This check is performed using a two-pointer technique, iterating through both houses and heaters at most once.
- Since both arrays are sorted, this check runs in O(n + m).
Final Time Complexity
Since the binary search runs O(30) ≈ O(1) times and each iteration requires O(n + m) time, the final complexity is:
O(n log n + m log m) + O(30 * (n + m))
≈ O(n log n + m log m + n + m)
≈ O(n log n + m log m)
Thus, the dominant term is the sorting step, making the overall time complexity O(n log n + m log m)
Space Complexity: O(n)
- Auxiliary Space Complexity: O(1)
The algorithm only uses a few integer variables like low, high, mid, minRadius, i, j, etc. These are just primitive variables that occupy O(1) space.
Therefore, the auxiliary space complexity is O(1). - Total Space Complexity: O(n + m)
We sort the input arrays, but we do not create any additional data structures apart from the given houses and heaters arrays.
The input itself takes O(n + m) space, where n = size of houses and m = size of heaters.
Therefore, the total space complexity is O(n + m)
Similar Problems
Many array problems on Leetcode can be efficiently solved using techniques like Two Pointers, Binary Search, and Sorting. For example, when dealing with partitioning or searching within an array, Sorting can help structure the data for optimized searching. Two Pointers is particularly useful for problems involving pairwise comparisons, such as finding pairs that satisfy a condition in a sorted array. Meanwhile, Binary Search is a powerful tool for optimizing problems where we need to minimize or maximize a certain value within constraints. By combining these techniques strategically, we can significantly improve efficiency and solve complex problems with ease.
Now we have successfully tackled this problem, let's try these similar problems.
A conveyor belt has packages that must be shipped from one port to another within D days.The ith package on the conveyor belt has a weight of weights[i]. Each day, we load the ship with packages on the conveyor belt (in the order given by weights). We may not load more weight than the maximum weight capacity of the ship.Return the least weight capacity of the ship that will result in all the packages on the conveyor belt being shipped within D days.
2. Sqrt(x)
Given a non-negative integer x, return the square root of x rounded down to the nearest integer. The returned integer should be non-negative as well.You must not use any built-in exponent function or operator.For example, do not use pow(x, 0.5) in C++ or x ** 0.5 in Python.