Last Updated: 20 Oct, 2021

Candles Height

Moderate

Asked in company

Solve now

Problem statement

Ninja is solving questions on an array in which he has given an integer ‘N’, representing the number of candles numbered through 1 to ‘N’. Initially, the height of all the candles is 0. There are ‘Q’ queries given to Ninja. In each query, Ninja has two integers, ‘L’, and ‘R’, and Ninja should increase the height for each candle by 1 from ‘L’ to ‘R’ both inclusive. Ninja can only perform ‘Q’ - 1 queries out of ‘Q’ given queries. Find the maximum count of candles having height ‘K’ after performing ‘Q’ - 1 queries.

For example:

Let ‘N’ be: 2
Let queries be: [[1, 2], [1, 1]]
Let ‘K’ be: 1
Initial heights: [0, 0]
Removing query 1 and increasing heights in the range [1, 1] gives: [1, 0]. The number of candles having a height of 1 is 1.
Removing query 2 and increasing heights in the range [1, 2] gives: [1, 1]. The number of candles having a height of 1 is 2.
Hence, the answer is 2.

Input Format :

The first line of input contains an integer ‘T’, denoting the number of test cases.

The first line of each test case contains three space-separated integers, ‘N’, ‘K’, and ‘Q’, representing the number of candles, the height of the candle needed, and the number of queries.

The next ‘Q’ lines of each test contain two space-separated integers, ‘L’ and ‘R’, representing the range for each query.

Output Format :

For each test case, print a single integer representing the maximum count of the candle possible after performing ‘Q’ - 1 queries.

Print output of each test case in a separate line.

Note :

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10
1 <= N <= 10^6
1 <= Q <= 10^6
1 <= K <= Q
1 <= L <= R <= N

Time Limit: 1 sec

Solve now

Approaches

01 Approach

The basic idea is to run ‘Q’ - 1 queries by removing 1 query at a time. For each time, we find the number of candles with height equal to ‘K’ and find the maximum.

Here is the algorithm :

Create a variable (say, ‘ANS’) that will store the maximum count and initialize it with 0.
Run a loop from 0 to ‘Q’ (say, iterator ‘i’) that will run over all the queries.
- Create a ‘CANDLE’ array to store the heights of the candles.
- Run a loop from 0 to ‘Q’ (say, iterator ‘j’) that will run over all the queries by removing 1 query at a time.
  - Check if ‘j’ is not equal to ‘i’ to remove the ‘ith’ query
    - Update heights of candles from ‘L’ to ‘R’ for each ‘jth’ query.
- Run a loop from 0 to ‘N’ (say, iterator ‘j’) to count the number of candles having heights equal to ‘K’ and store it in a variable (say, ‘CNT’).
- Update ‘ANS’ by a maximum of ‘ANS’ and ‘CNT’.
Finally, return ‘ANS’.

Solve now

02 Approach

The basic idea is to make a difference array that can update heights in constant time and calculate the final heights of the candles in linear time. We create an array (say, ‘DIFF’) that will store the updated heights. We take all the queries and update the ‘DIFF’ array by incrementing index ‘L’ by 1 and decreasing index ‘R’ + 1 by 1. We then take the prefix sum of the ‘DIFF’ array to get the final heights of the candles after performing all ‘Q’ queries. As we take the prefix sum, this is the reason we need to decrease index ‘R’ + 1 by 1. Let us understand that by an example.

Let ‘N’ be 4. Initial heights: [0, 0, 0, 0]

Let the queries be: [1, 2], [2, 3]

We update index 1st by +1 and 3rd index by -1. Updated ‘DIFF’ array: [1, 0, -1, 0].

We update the index 2nd by +1 and the 4th index by -1. Updated ‘DIFF’ array: [1, 1, -1, -1].

‘DIFF’ array after updating by prefix sum: [1, 2, 1, 0].

Now we find the count of candles having heights ‘K’ by removing 1 query at a time. How do we find candles having height ‘K’ after removing a range [L, R].

Count of candles having height ‘K’ will be: Candles having height ‘K’ from 0 to ‘L’ - 1 + Candles having height ‘K’ + 1 from ‘L’ to ‘R’ + Candles having height ‘K’ from ‘R’ + 1 to ‘N’.

To find we can use prefix sum which stores candles having height ‘K’ and another prefix array which stores candles having height ‘K’ + 1.

Here is the algorithm :

Create an array (say, ‘DIFF’) of size ‘N’ that will store the heights and initialize it with 0.
Run a loop from 0 to ‘Q’ (say, iterator ‘i’) to run all the queries.
- Increment ‘DIFF[L]’ by 1
- Decrement ‘DIFF[R + 1]’ by 1, if ‘R’ + 1 is smaller than equal to ‘N’.
Create two arrays (say, ‘PREFIX1’ and ‘PREFIX2’) of size ‘N’ that will store the prefix sum of count with heights ‘K’ and ‘K’ + 1 respectively and initialize it with 0.
Run a loop from 0 to ‘N’ (say, iterator ‘i’) to calculate the heights of ‘N’ candles and store count.
- Update ‘DIFF[i]’ with sum of ‘DIFF[i]’ and ‘DIFF[i - 1]’.
- Update ‘PREFIX1[i]’ with sum of ‘PREFIX1[i]’ and ‘PREFIX1[i - 1]’ and add 1 if ‘DIFF[i]’ is equal to ‘K’.
- Update ‘PREFIX2[i]’ with sum of ‘PREFIX2[i]’ and ‘PREFIX2[i - 1]’ and add 1 if ‘DIFF[i]’ is equal to ‘K’ + 1.
Create a variable (say, ‘ANS’) to store the result and initialize it with 0.
Run a loop from 0 to ‘Q’ (say, iterator ‘i’) that will find count by removing one query at a time.
- Find the count of candles with height ‘K’ by removing the current query by adding ‘PREFIX1[l - 1]’, ‘PREFIX1[N]’, ‘PREFIX2[R + 1]’ and subtracting ‘PREFIX2[R]’ and ‘PREFIX2[L - 1]’ and store it in a variable (say, ‘CNT’).
- Find the maximum of ‘CNT’ and ‘ANS’.
Finally, return ‘ANS’.

Solve now