Problem of The Day: 26/04/2023 | Seating Arrangement | Yash Dwivedi

Welcome to our daily problem solving session where Yash will be tackling the Problem of The Day. We will be discussing the entire problem step-by-step and work towards developing an optimized solution. This will not only help you brush up your concepts of Data Structures and Algorithms, but will also help you build up problem solving skills.

So come along and solve the POD of 26th April 2023 with us!



Daily solutions will be streamed live exclusively on our channel! So start solving today and subscribe to our channel for the free coding lessons.

-----------------------------------------------------------------------------------------



-----------------------------------------------------------------------------------------

Follow us and stay updated on everything happening in the world of geeks:


#GFGPractice #GeeksforGeeks #ProblemofTheDay #CodingQuestions #POTD

[Rishit.Chaudhary]

Hi Yash,
Great video, as always. Your explanation of the code was beneficial!

Not only that, but I also tried out the optimisation I suggested in the chat of using a tighter range in the for-loop, and it worked like a charm! When I submitted it on the GFG platform, it passed all the test cases with flying colours.

The reason the optimisation worked is as follows:
The technique we used involves blocking seat 0 if unoccupied, which means we can seat a person there. As a result, seat 1 becomes unavailable due to the problem's constraints. Conversely, if seat 0 is already occupied, we cannot seat anyone in seat 1 anyway. This is why it makes sense to skip checking seat 1 in the for-loop. We can apply a similar argument to justify skipping the check for seat `m-2` in the for-loop.

Therefore, it is reasonable to iterate from i = 2 to i = m-3 (inclusive of both limits) as an optimisation.

By the way, I've also included the optimised code below.

Optimised Code:

//User function Template for C++

class Solution{
public:
bool is_possible_to_get_seats(int n, int m, vector<int>& seats){
int count = 0;
if (seats[0] == 0 and seats[1] == 0) {
count++;
seats[0] = 1;
}
if (seats[m-1] == 0 and seats[m-2] == 0) {
count++;
seats[m-1] = 1;
}

for (int i = 2; i < m-2; i++) {
if (seats[i] == 0 and seats[i-1] == 0 and seats[i+1] == 0) {
count++;
seats[i] = 1;
}
}

return count >= n;
}
};


Please do let me know if you have any feedback or suggestions.

Thanks!