Minimum coverage by heaters

Ayush Tiwari
Last Updated: May 13, 2022

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

  1. Iterate from 1 to n in houses and for the ith index of houses.
    1. Find the distance of the first heater on its left, let's say d1.
    2. Find the distance of the first heater on its right, let's say d2.
    3. Distance required for ith house is min(d1,d2) stores in distance[i].
  2. 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 complexityO(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

Efficient Approach

In the efficient approach, we are doing the same thing as the brute force approach but in a smart way. First, we short the houses array and heaters array, and then we 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. This can easily be optimised with the help of two-pointers.

Let us understand the approach with an example-

 h = house,  * = heater  M = INT_MAX

        h   h   h   h   h   h   h   h   h    houses

        1   2   3   4   5   6   7   8   9    index

        *           *       *                heaters   

        0   2   1   0   1   0   -   -   -    (distance to nearest RHS heater)

        0   1   2   0   1   0   1   2   3    (distance to nearest LHS heater)

        0   1   1   0   1   0   1   2   3    (res = minimum of above two)

The result is the maximum value in res, which is 3.

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)
{
    // sort the houses and heaters array
    sort(houses, houses + n);
    sort(heaters, heaters + m);
    int distance[n] = {INT_MAX};
    int i = 0;
    int j = 0;
    // find the diatance of minmimum distance heater on left side of house
    while (i < n && j < m)
    {
        if (houses[i] <= heaters[j])
        {
            distance[i] = heaters[j] - houses[i];
            i++;
        }
        else
            j++;
    }
    // find the diatance of minmimum distance heater on right side of house
    i = n - 1;
    j = m - 1;
    while (i >= 0 && j >= 0)
    {
        if (houses[i] >= heaters[j])
        {
            distance[i] = min(distance[i], houses[i] - heaters[j]);
            i--;
        }
        else
            j--;
    }
    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 complexityO(NlogN+MlogM),O(NlogN) and O(MlogN) required for sorting the houses and heaters array.

Space complexity - O(N). for storing distance for each house
 

Frequently Asked Questions

Q1. What is the Two Pointers approach?

Ans: Two pointer algorithm is one of the most asked questions in any programming interview or contest. This approach optimizes the runtime by utilizing some order (not necessarily sorting) of data. It is generally applied on lists (arrays), linked lists, and binary search trees. This is generally used to search pairs in a sorted array. This approach works in constant space. 

 

Q2. Write the function to find maximum and minimum elements in array or vector in c++.

Ans: Minimum element can be found with the help of the *min_element() function provided in STL. The maximum element can be found with the help of the *max_element() function provided in STL.

 

Q3. How do we sort the vector in the range [l,r] in c++?

Ans: We can sort the array by using sort function:

    sort(vector.begin() + l, vector.begin() + r + 1);

Key takeaways

In this article, we've discussed the heaters range problem. Here an effective method has been used, which is called dynamic programming. This is a crucial topic, and there are numerous exciting problems related to this topic. Some of them are Verify Preorder Sequence in Binary Search TreeCount Subarrays Having Product Less Than K.

I would suggest you solve them to gain more confidence on this topic. These questions are asked during various coding contests as well as placements tests.

To practice more such problems, Codestudio is a one-stop destination. This platform will help you acquire effective coding techniques and give you an overview of student interview experience in various product-based companies.

Happy Coding!

Coding and practicing in Code studio.

Was this article helpful ?
0 upvotes