Number of Students Unable to Eat Lunch - Leetcode 1700 - Python

0:00 - Read the problem
0:19 - Drawing Explanation
6:03 - Coding Explanation

leetcode 1700

#neetcode #leetcode #python

[loflog]

With the inflation these days, no one’s eating lunch

[amongus-rqhb]

Finished on my own and came for the explanation. Thanks

[gabrieldavi]

I was really overthinking this problem.

[xavier]

class Solution:
def countStudents(self, students: List[int], sandwiches: List[int]) -> int:
i = 0 # initialize pointer to first student
while i < len(students) and len(students) != 0: # break if we have not found a student to pair with the first sandwich or all students are fed (no students left)
if students[i] == sandwiches[0]: # if i-th student matches first sandwich
students.pop(i) # removes the i-th student and first sandwich as a pair
sandwiches.pop(0)
i=0 # then resets pointer to first student
else:
i+=1 # otherwise if student sandwich pair not found, point to next student
return len(students) # return students who have not eaten

O(n^2) but still idk how to work with queues

[JoshPeterson]

This is in the DSA course, but the video isn't linked

[SkegAudio]

Bruh I OVER ENGINEERED the heck out of it on my first go:

class Node:
def __init__(self, pref):
self.pref = pref
self.next = None

class Queue:
def __init__(self):
self.front = Node(-1)
self.back = self.front
self.len = 0
self.checked = 0

def enqueue(self, pref) -> None:
self.back.next = Node(pref)
self.back = self.back.next
self.len += 1

def dequeue(self) -> None:
if self.front == self.back:
return None
self.front.next = self.front.next.next
if not self.front.next:
self.back = self.front
self.len -= 1


class Solution:
def countStudents(self, students: List[int], sandwiches: List[int]) -> int:

que = Queue()

for student in students:
que.enqueue(student)

for sandwich in sandwiches:

while que.checked != que.len:

if que.front.next.pref == sandwich:
que.dequeue()
que.checked = 0
break
else:

que.dequeue()
que.checked += 1

if que.checked == que.len:
break

return que.len


EDIT: Okay with the help of Grok and your solution I ended with the following ->
def countStudents(students: List[int], sandwiches: List[int]) -> int:
prefs = Counter(students) # Count preferences
for sandwich in sandwiches:
if prefs[sandwich] == 0: # No student likes this sandwich
break
prefs[sandwich] -= 1 # Serve it, reduce count
return sum(prefs.values()) # Remaining students

Much cleaner and efficient

[vader]

You don't even need the "res" variable. You can just return "cnt[1 - s]" (and 0 if we reach outside the loop). In the else branch, cnt[s] is zero. cnt[1 - s] is the count of the other preference which is obviously all that can remain. And if we reach outside the loop, all the sandwiches were eaten.

[AhmedMarzookisabeast]

Solution looks good I did it thinking of queues in mind and did a .pop() and .append() as I came from the Neetcode queue section seems a bit overengineered now.
class Solution:
def countStudents(self, students: list[int], sandwiches: list[int]) -> int:
students_left = len(students)

while students_left > 0:
if students[0] == sandwiches[0] and students_left:
students.pop(0)
sandwiches.pop(0)
students_left = len(students)
else:
student = students.pop(0)
students.append(student)
students_left -= 1
return len(students)

[doc]

You need to add this to the DSA course now. There is no link in the Queue's section even though you have the video here (I arrived here by chance via google). (Edit: never mind. I see why you maybe didn't add this video. Because you didn't use a Queue, no?)

Nice to see you're still doing leetcodes though. This is the first recent leetcode video I've seen. I was worried I'd eventually run out of content.

[spsc]

I did a simulation using deque in cpp

class Solution {
public:
int countStudents(vector<int>& st, vector<int>& sd)
{
deque<int> q(st.begin(), st.end());
int i=0, cnt=0;
while(!q.empty())
{
int curr=q.front();
q.pop_front();
if(curr!=sd[i])
{
++cnt;
q.push_back(curr);
}
else
{
++i;
cnt=0;
}
if(cnt==q.size())
break;
}
return q.size();
}
};


Edit1: Did your method as well

class Solution {
public:
int countStudents(vector<int>& st, vector<int>& sd)
{
int ans=st.size();
vector<int>hashh(2);
hashh[0]=count(st.begin(), st.end(), 0);
hashh[1]=ans-hashh[0];

for(int i:sd)
{
if(hashh[i]>0)
{
--ans;
--hashh[i];
}
else
return ans;
}
return 0;
}
};

[licokr]

I initially approached with a dequeue (the same approach the problem tells) and the time complexity was O(n ^ 2). I thought there would be a better solution and there is. I focused on the question too much... Thank you so much👍
This is the code I wrote after watching your solution. I used cnt to calc the remaining students

cnt = Counter(students)

for s in sandwiches:
if cnt[s] == 0:
break
cnt[s] -= 1

return cnt[0] + cnt[1]

ps: either cnt[0] or cnt[1] is not zero if there are students unable to eat lunch.

[hyperboliq]

Any issue with just simulating the problem with deques here? :

from collections import deque
class Solution:
def countStudents(self, students: List[int], sandwiches: List[int]) -> int:
sandwiches, students = deque(sandwiches), deque(students)
skips = 0
while skips < len(students):
if students[0] == sandwiches[0]:
skips = 0
students.popleft()
sandwiches.popleft()
else:
skips+=1

return len(students)

[Shanoro]

You have this video as a solution in your Pro course in the section Queues. This video does not solve anything with a queue.

[Timjstewart]

Nice solution to what is, sadly and literally, a first world problem.

[sx.]

neet how did u learn everything? what’s resources did u use?

[DBagg-zzip]

oh I just did this one but messed around popping from the student list

[ShreyBhardwaj-mrtl]

How are you implementing the rule that if the student does not get what he wants i.e the top of the stack, then he moves to the end of the queue? Can anyone pls explain?

[seanmorris]

What drawing pad do you use for writing your thoughts out on screen?

[innazhogova]

The question makes no sense. Why is the video & the correct solution approaching both inputs like they're queues? Didn't it say that sandwiches is a stack? There's definitely a mistake in the description.

[jenwans]

Do you have simple problems and sol. for blokes like me?