2025 May 17 Problems

67 views
Skip to first unread message

daryl...@gmail.com

unread,
May 17, 2025, 12:40:37 PMMay 17
to leetcode-meetup
Feel free to work on any of the problems you want; we'll have people present their solutions at 11:30.

Please post your solutions to this thread so others can use this as a reference.

Medium and hard problems have been carried over.

278. First Bad Problem Easy 45.8%

2332. The Latest Time to Catch a Bus Medium 28.2%



Please download and import the following iCalendar (.ics) files to your calendar system.

Anuj Patnaik

unread,
May 17, 2025, 1:01:08 PMMay 17
to leetcode-meetup
# The isBadVersion API is already defined for you.
# def isBadVersion(version: int) -> bool:

class Solution:
def firstBadVersion(self, n: int) -> int:
left = 1
right = n
while(left < right):
mid = (left + right)//2
if isBadVersion(mid) == True:
right = mid
if isBadVersion(mid) == False:
left = mid + 1
return left
#Time: O(log(n))
#Space: O(1)

FloM

unread,
May 17, 2025, 1:14:46 PMMay 17
to leetcode-meetup
278. First Bad Problem Easy 45.8%
Time: O(lg(n)) Mem: O(1)
class Solution {
public:

int firstBadVersion(int n) {
size_t rt = n;
size_t lt = 1;

while(lt < rt)
{
size_t md = lt + ((rt - lt)/2);

if (!isBadVersion(md))
{
lt = md+1;
}
else
{
rt = md;
}

}

return lt;

}
};

J D

unread,
May 17, 2025, 1:36:11 PMMay 17
to leetcod...@googlegroups.com
        int latestTimeCatchTheBus(vector<int>& buses, vector<int>& passengers, int capacity)
        {
                int result = 0;
                priority_queue<int, vector<int>, greater<int>> minbuses;
                for (auto i : buses)
                        minbuses.push(i);

                priority_queue<int, vector<int>, greater<int>> minpass;
                for (auto i : passengers)
                        minpass.push(i);

                priority_queue<int> pastpassengers;
                int i = 0;
                int currentcap = 0;
                int lastbus = 0;
                int lastcap = 0;
                while (!minbuses.empty())
                {
                        int currentbus = minbuses.top();
                        int currpass = minpass.top();
                        lastcap = currentcap;
                        if ((currpass <= currentbus) &&(currentcap < capacity) && (!minpass.empty()))
                        {
                                currentcap++;
                                pastpassengers.push(currpass);
                                minpass.pop();
                        }
                        else
                        {
                                currentbus = minbuses.top();
                                lastbus = currentbus;
                                minbuses.pop();
                                currentcap = 0;
                        }
                }
                if (lastcap == 0) return lastbus;
                int lastpass = pastpassengers.top();
                if (lastcap < capacity)
                {
                        if (lastbus - lastpass > 0)
                        {
                                return lastbus;
                        }
                }
                if (!pastpassengers.empty())
                {
                        pastpassengers.pop();
                        int penul = pastpassengers.top();
                        while ((lastpass - penul < 2) && (lastpass - penul > 0))
                        {
                                lastpass = penul;
                                pastpassengers.pop();
                                penul = pastpassengers.top();

                        }

                }
                result = lastpass-1;
                return result;
        }

--
whatspp group: http://whatsapp.techbayarea.us/
---
You received this message because you are subscribed to the Google Groups "leetcode-meetup" group.
To unsubscribe from this group and stop receiving emails from it, send an email to leetcode-meet...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/leetcode-meetup/0a46a1bc-39cc-4efb-8121-1566d3785692n%40googlegroups.com.

Tarini Pattanaik

unread,
May 17, 2025, 1:37:23 PMMay 17
to leetcod...@googlegroups.com
278. First Bad Version Time complexity: O(log n) Space complexity: O(1) public class Solution extends VersionControl {
public int firstBadVersion(int n) {
int left = 0;
int right = n;
int mid = 0;

while (left < right) {
mid = left + (right - left) / 2;
if (isBadVersion(mid)) {
right = mid;
} else {
left = mid + 1;
}
}

return left;
}
}

On Sat, May 17, 2025 at 10:14 AM FloM <flo...@gmail.com> wrote:
--

Allen S.

unread,
May 17, 2025, 1:42:45 PMMay 17
to leetcode-meetup
tc := Big O(log n)
sc := Big O(1) func firstBadVersion(n int) int {
l, r := 1, n
for l <= r {
m := l + (r - l)/2
if isBadVersion(m) {
r = m - 1
} else {
l = m + 1
}
}
return l
}

Gowrima Jayaramu

unread,
May 17, 2025, 2:13:52 PMMay 17
to leetcode-meetup
# Time: O(logn)
# Space: O(1)

class Solution:
def firstBadVersion(self, n: int) -> int:
lo, hi = 1, n+1
while lo < hi:
mid = lo + (hi-lo)//2

if isBadVersion(mid):
hi = mid
else:
lo = mid+1

return lo

FloM

unread,
May 17, 2025, 4:51:05 PMMay 17
to leetcode-meetup
2332. The Latest Time to Catch a Bus Medium 28.2%
Time: O(b log(b) + p*log(p)),  Memory: O(p + b) Where p is passengers and b is buses.
class Solution {
public:
int latestTimeCatchTheBus(vector<int>& buses, vector<int>& passengers, int capacity) {

// Min priority queues for bus times and passenger Times.
priority_queue<int, vector<int>, greater<int>> busTimes{};

priority_queue<int, vector<int>, greater<int>> passengerTimes{};
int lastBus = -1;
for(const int& b : buses)
{
busTimes.push(b);
lastBus = std::max(lastBus, b);
}

for(const int& p : passengers)
{
passengerTimes.push(p);
}

// Keep track of the last processed passenger.
int lastPassenger = -1;

// The latest time that a user can catch a bus is -1, so far.
// If there are no more buses to catch, then use the latest time.
int latest = -1;

// topBus is the next bus. It has not been takin off the priority queue.
int topBus = busTimes.top();

// Current load is zero. Load can not exceed capacity.
int load = 0;

while(!busTimes.empty())
{
// If there are buses in the priority queue, but no more passengers, then catch the last bus.
if (passengerTimes.empty())
{
latest = lastBus;
break;
}

// Every time I pop a passenger, If the bus is full, then I pop the bus and
// reset the load to zero. At this point at the top of the while loop, there
// is room for at least one passenger on the top bus.

// topPassenger is the next passenger.
int topPassenger = passengerTimes.top();

// If topPassenger's time slot is less than or equal to topBus' time slot, then
// put passenger on the bus.
if ( topPassenger <= topBus)
{
// Before passenger is put on bus, note if the user can squeeze in before
// the topPassenger.
// If the time slot before topPassenger is empty,
// then latest time for user is updated to topPassenger - 1.
if (topPassenger - 1 > lastPassenger)
{
latest = topPassenger - 1;
}

// Pop the passenger, simulates the passenger getting on the bus.
passengerTimes.pop();
lastPassenger = topPassenger; // update the last passenger is topPassenger.
++load;

// If the top passenger is the last passenger on the bus because the
// bus is full or top passenger has the same time slot as the top bus,
// the pop the top bus.
if ( (capacity == load) || (topBus == topPassenger) )
{
busTimes.pop();
topBus = busTimes.top();
load = 0;
}
}
// Else topPassenger's time slot is larger than topBus's timeSlot.
else
{
// There is room for the user on topBus. The user should use the top bus'
// time slot.
latest = topBus;
// Pop the topBus and reset load.
busTimes.pop();
topBus = busTimes.top();
load = 0;
}

}

return latest;
}
};

Allen S.

unread,
May 17, 2025, 7:08:26 PMMay 17
to leetcode-meetup
// sort, simulate traffic and do some yoga around the edge cases.
func latestTimeCatchTheBus(buses []int, passengers []int, capacity int) int {
slices.Sort(buses)
slices.Sort(passengers)
latestTime := 1
for i, j := 0, 0; i < len(buses); i++ { // simulate the flow of buses
k := capacity
seenLastMomentPassenger := false
// next bus time is buses[i], let's load it up-to K. Any passengers?
for k > 0 && j < len(passengers) && passengers[j] <= buses[i] {
// check for the gap
if j == 0 || passengers[j] - passengers[j - 1] > 1 {
latestTime = passengers[j] - 1
}

if buses[i] == passengers[j] {
seenLastMomentPassenger = true
}
j++ // next passenger
k-- // load the bus
}

// bus is not full, could we get on it last moment?
if k > 0 && !seenLastMomentPassenger {
latestTime = buses[i]
}

}

return latestTime
}

On Saturday, May 17, 2025 at 9:40:37 AM UTC-7 daryl...@gmail.com wrote:
Reply all
Reply to author
Forward
0 new messages