When we are preparing ourselves for an interview of any product-based company, we must be proficient in competitive programming and have a good sense of data structures and algorithms. To brush up on our problem-solving skills and concepts like two pointers, one should try the below problem. We have also discussed the solution with the required time and space complexity.

Problem Statement

The troops of N monsters are lined up. Each troop has M members and is represented as an array of M integers p1, p2, p3, p4,...., pm where pi is the power of ith member.

Rohan, the savior of the town, is here to destroy the sequence of consecutive troops of monsters of maximum length. He has M weapons with which he can attack monsters. The ith weapon affects the ith member of all the troops. If the power of an ith member of any troop is zero, then that member remains unaffected.

The troop is destroyed when the power of all of its members becomes zero. Rohan can make at most K shots. The task is to find out the number of shots by Rohanâ€™s weapons of each type so that the sequence of consecutive troops of maximum length gets destroyed.

Example

Input: N = 4, M = 2, K = 5

1 3 2 4 1 2 3 2

Output: 3 2

Explanation: For the maximum length of consecutive troops, we can destroy third and fourth troops where the 1st members of each troop get finished with a total of 3 shots and the 2nd members of each troop get finished with a total of 2 shots. Thus the answer is 3 2, with which a maximum of 2 troops will be destroyed.

Input: N = 3, M = 2, K = 2

1 2 1 1 2 2

Output: 1 1

Explanation: As K is only 2 and the sum for every troop is more than 2 except for the second troop whose sum is 2, so we can only have one troop of monsters killed by Rohan giving 1 shot to each of the members.

From the above problem statement, we can understand that for a particular contiguous subsegment of troops, we have to calculate the sum of the column-wise maximums of powers of every troop in the subsegment. Until this sum of maximums is less than or equal to â€˜Kâ€™, we can keep increasing this subsegment with the help of two pointers.

Approach

Let us consider a segment from â€˜lâ€™ to â€˜râ€™. To destroy this segment, Rohan will need the following number of shots:

Where P[i][j], is the power of the â€˜jâ€™th member in the ith troop.

If this sum is less than or equal to â€˜Kâ€™, Rohan can kill the segment of troops from â€˜lâ€™ to â€˜râ€™. In this case, we will simply increase the right border of the segment, i.e., increase â€˜râ€™, and in the other case, when the sum is greater than â€˜Kâ€™, we will increase the left border, i.e., increase â€˜lâ€™.

And we will keep updating the answer after every change in the segment.

In order to find the maximum power from a segment, we can use a priority queue, as it can give us the troop with maximum power for a particular index with the cost of just O(log(N)). Else we will need to iterate through all the members of the troops to obtain the member with the maximum power.

Below is the implementation of the above approach.

Implementation

// Program to solve the kill monsters problem.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
// Function to return the vector of the number of shots.
vector<int> killMonsters(int N, int M, int K)
{
// Variables to implement two pointers.
int l = 0, x, r, mx = 0;
/*
Priority queue to prioritize the
more powerful members.
*/
priority_queue<pair<int, int>> pq[M];
/*
Vector to store the number of shots
for each type of member.
*/
vector<int> shots(M, 0);
/*
Iterating through each troop and
updating the maximum length segment.
*/
for (int i = 0; i < N; i++)
{
// Second pointer.
r = i;
// Pushing the powers in the priority queue.
for (int j = 0; j < M; j++)
{
// Input of powers.
cin >> x;
pq[j].push({x, i});
}
/*
Updating the range of the segment
satisfying the given conditions.
*/
while (l <= r)
{
int sum = 0;
for (int j = 0; j < M; j++)
{
while (pq[j].top().second < l)
pq[j].pop();
sum += pq[j].top().first;
}
if (sum <= K)
break;
l++;
}
// Updating the answer vector after every change.
if (r - l + 1 > mx)
{
mx = r - l + 1;
for (int j = 0; j < M; j++)
shots[j] = pq[j].top().first;
}
}
// Finally returning the number of shots.
return shots;
}
// Main function.
int main()
{
// Input of the variables.
int N, M, K;
cin >> N >> M >> K;
// Vector to store the number of shots.
vector<int> shots = killMonsters(N, M, K);
// Final output.
for (int i = 0; i < M; i++)
cout << shots[i] << " ";
return 0;
}

Input

4 2 7
1 2
1 3
2 2
3 4

Output

3 4

Complexity Analysis

Time Complexity

O(N * M * log(M)), where â€˜Nâ€™ and â€˜Mâ€™ are the number of troops and number of members in every troop respectively. Explanation: In the function killMonsters(), we are iterating through each troop and adjusting the length of the segment with the help of two pointers. So, iterating through â€˜Nâ€™ troops and then â€˜Mâ€™ members give us the complexity of O(N * M), but we are using a priority queue to prioritize the powers, which increases a factor of log(M) into the final time complexity. Thus the final time complexity is O(N * M * log(M)).

Space Complexity

O(N * M), where â€˜Nâ€™ and â€˜Mâ€™ are the numbers of troops and number of members in every troop, respectively. Explanation: We use the priority queue to store the powers of the â€˜Mâ€™ members of every â€˜Nâ€™ troop; thus, space complexity sums up to O(N * M).

FAQs

Why are we using two pointers method in this program? While finding the current longest valid subsegment after each iteration, it becomes easier when you have two variables that can be slid towards left or right to expand or compress the range. So this is the reason we are using two-pointers.

What is the use of priority queue in the above program? To find the number of shots for destroying the troops of the current segment, we need to extract the maximum power among members from each index, which can be efficiently done with the help of a priority queue with a cost of O(log(N)).

What is the time complexity of the above algorithm? The time complexity of the above algorithm can be calculated by analyzing the most costly function, i.e., killMonsters(). So from the analysis of the above function, we can conclude that the overall time complexity of the above program is O(N * M * log(M)).

What is the space complexity of the above algorithm? We used a priority queue to store the powers of the â€˜Mâ€™ members of every â€˜Nâ€™ troop which sums up to O(N * M).

Why are we inserting elements in pairs to the priority queue? We are inserting pairs so that we can have a track of indices, that which troop this power belongs to. This helps us to distinguish the powers of a particular troop from other troops.

Key Takeaways

The above problem is an interesting competitive programming problem involving the use of two-pointers. Solving these types of problems is the key to boosting your problem-solving skills.

Find more such interesting questions on our practice platform Coding Ninjas Studio if you want to learn more before jumping into practicing, head over to our library section for many such interesting blogs. Keep learning.