Last Updated: 23 Apr, 2021

Defend The Village

Moderate

Asked in company

Solve now

Problem statement

You are given an array/list of positive integers ‘HOUSES’ that represents the positions of 'N' different houses in Ninja’s village on a horizontal line. There is an attack by the enemy that a group of 'M' Ninjas positioned at different houses can stop as long as the houses are within their radius range. The positions of these 'M' Ninjas are given in an array/list 'NINJAS'.

Your task is to return the minimum radius standard of the defender Ninjas so that those Ninjas could defend all houses in 'HOUSES' array.

Example :

Suppose given ‘HOUSES’ is [1,2,3] and ‘NINJAS’ is [2] then
The defending radius range of the ninjas (‘NINJAS’) is 1 since there is only one ninja that is defending at position 2, and if we use the radius 1 standard, then all the houses can be protected.

Input Format :

The first line of input contains a single integer ‘T’ denoting the number of test cases given. Then next ‘T’ lines follow:

The first line of each test case input contains two space-separated integers, where  the first integer 'N' represents the length of the ‘HOUSES’ array while the second integer 'M' represents the length of ‘NINJAS' array.

The second line of each test contains ‘N’ space-separated integers which are the elements of the position of houses (‘HOUSES’) array.

The third line of each test contains ‘M’ space-separated integers which are the elements of the position of Ninjas (‘NINJAS’) array.

Output Format :

For every test case, print an integer denoting the minimum radius standard of (‘NINJAS’) Ninjas so that those Ninjas could defend all houses.

Note :

1. You do not need to print anything, it has already been taken care of. Just Implement the given function.
2. Notice that all the ninjas (‘NINJAS’) follow your radius standard, and the defending radius will be the same.

Constraint :

1 <= T <= 10
1 <= N, M <= 3 * 10^3
1 <= HOUSES[i], NINJAS[i] <= 10^9

Where 'HOUSES[i]' represent the position of 'ith' house and 'NINJAS[i]' represent the position of 'ith' Ninja.

Time Limit: 1 sec

Solve now

Approaches

01 Approach

A possible solution could be to take each house ‘i’ (‘HOUSE’[i]) and check if it has a Ninja guarding it that is if (‘HOUSE’[i] == ‘NINJA’[i]) both have the same position. Then this house ‘i’ is already equipped with a Ninja and we can continue to evaluate the next house.

If the position of house ‘i' is smaller than all elements of the ‘NINJAS’ array, record the distance from ‘i’ to the first element of the ‘NINJAS’ array.

If the position of house ‘i’ is larger than all elements of the ‘NINJAS’ array, record the distance from ‘i’ to the last element of the ‘NINJAS’ array.

If the position of house ‘i’ in between the two adjacent elements (positions) of the ‘NINJAS’ array, calculate the distances from the left and right of ‘HOUSE’[i] respectively and take the minimum value, and only when the defending radius satisfies this value, the house ‘i’ can be covered by the defending range of the left or right Ninja. Finally, return the resultant standard radius range which can now be set for all the houses.

The algorithm to calculate the required will be:-

Sort the ‘HOUSES’ and ‘NINJAS’ arrays in ascending order.
Initialize a variable ‘RESULT’ for storing the maximum guarding distance of a ninja’s from a house and another variable ‘DISTANCE’ for keeping track of the possible distance calculated in every iteration.
Now, traverse the given array of houses by iterating from 0 to ‘N’ which is the total size of the ‘HOUSES’ array.
For every ‘HOUSE’[i], initialise a variable ‘j’ = 0 and iterate over the ‘NINJAS’ array in a while loop until we find the position of the first Ninja that is greater than or equal to the position of ‘HOUSE’[i]. Break if ‘j’ reaches the last index of the ‘NINJAS’ array or position of ‘NINJA’[i] is not less than that of ‘HOUSE’[i].
After the while loop, for every value of ‘j’ we get we calculate the distances of the ‘HOUSE’[i] and ‘NINJA’[j] as follows:
- ‘DISTANCE’ = ‘NINJAS’[j] - ‘HOUSES’[i], when ‘j’ == 0.
- ‘DISTANCE’ = ‘HOUSES’[i] - ‘NINJAS’[‘M’-1], when ‘j’ == ‘M’-1.
- ‘DISTANCE’ = min(‘NINJAS’[j] - ‘HOUSES’[i], ‘HOUSES’[i] - ‘NINJAS’[‘j’-1]), otherwise.
Now we keep checking if there exists a possible minimum distance radius range that is greater than our result ‘RESULT’ and update the result ‘RESULT’ with the value of ‘DISTANCE’ if such is the case.
Finally, return the result ‘RESULT’.

Solve now

02 Approach

An efficient solution that we can use here is while traversing the array of the house, we keep calculating the nearest Ninja that would be able to defend the houses by making a binary search which can be used to find the exact index for a particular house position or -1 if it doesn't exist. We can modify binary search to yield the index of the nearest number. For our problem, this means that we would be able to find the index of the closest Ninja in O(log(M)).

The algorithm to calculate the required will be:-

Initialize a variable ‘RES’ for storing the maximum guarding distance of a Ninja from a house with a value of the minimum integer value available in that language.
Now, traverse the given array of houses by iterating from 0 to ‘N’ which is the total size of the (‘HOUSES’) houses array.
For every ‘HOUSES[i]’, we binary search for the nearest Ninja that can defend the house and calculate the distance of the Ninja’s position with the ‘HOUSES’[i] and check if it’s is the largest radius range yet that we have gotten which could cover all the houses.
In the binary search function, we initialize the distance ‘DIST’ with a value equal to the maximum integer value available in the language that we are using for implementing the solution and we try to find out the nearest index of the Ninja that would be able to defend the given house and return the index.
Finally, we can return the ‘RES’.

Solve now