Introduction
This blog finds the minimum heaters range so it can warm all the houses.
Problem Statement
You are given two arrays, houses[] and heaters[] of length n and m, containing positive distinct integers representing the houses positions and heater positions. You need to find out the minimum range of heaters so it can warm all the houses, i.e., we have to find the heaters range so that it can warm all houses.
Let's take an example to understand this problem better.
Sample Examples
Example 1:
Given houses[] = {1,2,3,4}
Given heaters[] = {1,4}
Output - 1
Explanation:
With range =1, the heater at position 1 warms the houses[0], and houses[1], the heater at position 4 warms the houses[2] and houses[3].
Example 2:
Given houses[] = {2,3,5,8}
Given heaters[] = {1}
Output - 7
Explanation:
There is only one heater at position one so, it has to warm the houses[3], which is at position 8, so the range is 7.
Example 3:
Given houses[] = {4,100}
Given heaters[] = {4,100,500}
Output - 0
Explanation:
For every house, the heater is present in the same position, so the range is zero.
Brute Force Approach
The brute force approach of this problem is very simple; we have to find the maximum distance of heaters to each house either on its left side or right side. For a particular house, we consider the minimum distance of the heater on the left and the heater on the right.
Steps of Algorithm
-
Iterate from 1 to n in houses and for the ith index of houses.
- Find the distance of the first heater on its left, let's say d1.
- Find the distance of the first heater on its right, let's say d2.
- Distance required for ith house is min(d1,d2) stores in distance[i].
- Return the maximum element in the distance [].
Implementation in C++
#include <bits/stdc++.h>
using namespace std;
// function to find heaters range
int range_heaters(int houses[], int heaters[], int n, int m)
{
int distance[n] = {INT_MAX};
for (int i = 0; i < n; i++)
{
int right_heater = INT_MAX;
int left_heater = INT_MAX;
for (int j = 0; j < m; j++)
{
// for left heaters
if (heaters[j] <= houses[i])
left_heater = min(left_heater, houses[i] - heaters[j]);
// for right heaters
if (heaters[j] > houses[i])
right_heater = min(right_heater, heaters[j] - houses[i]);
}
distance[i] = min(right_heater, left_heater);
}
int ans = *max_element(distance, distance + n);
return ans;
}
// driver code
int main()
{
int n, m; // size of houses and heaters array
cin >> n >> m;
int houses[n], heaters[n];
for (int i = 0; i < n; i++)
cin >> houses[i];
for (int i = 0; i < m; i++)
cin >> heaters[i];
int ans = range_heaters(houses, heaters, n, m);
cout << "Heaters Range: " << ans << endl;
}
Input:
4 2
1 2 3 4
1 4
Output:
Heaters Range: 1
Complexity Analysis
Time complexity - O(N*M), For each house store the minimum distance of the left heater and right heater with two nested loops.
Space complexity - O(N). for storing distance for each house
Recommended topic, kth largest element in an array and Euclid GCD Algorithm