[BUG] - Time Limit Too Strict - 3479. Fruits Into Baskets III #27715
Description
LeetCode Username
killer-whale
Problem Number, Title, and Link
- Fruits Into Baskets III https://leetcode.com/problems/fruits-into-baskets-iii/description/
Bug Category
Problem constraints
Bug Description
It is possible to submit an O(n * log(n) * log(n)) solution in Python and receive Time Limit Exceeded. Solutions with this time complexity using a Segment Tree and Binary Search should be Accepted, given that the time complexity is reasonable for the constraints, where n is at most 10^5.
Here is an O(n * log(n) * log(n)) getting TLE: https://leetcode.com/problems/fruits-into-baskets-iii/submissions/1567853898/
Language Used for Code
Python/Python3
Code used for Submit/Run operation
class Solution:
def numOfUnplacedFruits(self, fruits: List[int], baskets: List[int]) -> int:
n = len(fruits)
st = SegmentTree(baskets, func=max)
t = 0
for fruit in fruits:
def ok(i):
return st.query(0, i + 1) >= fruit
idx = findmin(0, n, ok)
if idx == n:
t += 1
else:
st[idx] = 0
return t
def findmin(low: int, high: int, check) -> int:
while low < high:
mid = low + (high - low) // 2
if check(mid):
high = mid
else:
low = mid + 1
return low
class SegmentTree:
def __init__(self, data, default=0, func=max):
"""initialize the segment tree with data"""
self._default = default
self._func = func
self._len = len(data)
self._size = _size = 1 << (self._len - 1).bit_length()
self.data = [default] * (2 * _size)
self.data[_size:_size + self._len] = data
for i in reversed(range(_size)):
self.data[i] = func(self.data[i + i], self.data[i + i + 1])
def __delitem__(self, idx):
self[idx] = self._default
def __getitem__(self, idx):
return self.data[idx + self._size]
def __setitem__(self, idx, value):
idx += self._size
self.data[idx] = value
idx >>= 1
while idx:
self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
idx >>= 1
def __len__(self):
return self._len
def query(self, start, stop):
"""func of data[start, stop)"""
start += self._size
stop += self._size
res_left = res_right = self._default
while start < stop:
if start & 1:
res_left = self._func(res_left, self.data[start])
start += 1
if stop & 1:
stop -= 1
res_right = self._func(self.data[stop], res_right)
start >>= 1
stop >>= 1
return self._func(res_left, res_right)
def __repr__(self):
return "SegmentTree({0})".format(self.data)Expected behavior
The above solution should be accepted and the Weekly Contest 439 rankings should be corrected for those who solved this problem using a segment tree and binary search in Python in O(n * log(n) * log(n)) time complexity.
Screenshots
No response
Additional context
No response