Missing Test Case - 1488. Avoid Flood in The City #32719
Description
LeetCode Username
code-chaser
Problem Number, Title, and Link
1488. Avoid Flood in The City https://leetcode.com/problems/avoid-flood-in-the-city
Bug Category
Missing test case (Incorrect/Inefficient Code getting accepted because of missing test cases)
Bug Description
Solution with time complexity O(n^2) is getting accepted where the constraint on n is 0 < n <= 100000. Solution can be in O(n * log(n)).
Testcase
This can be verified simply by inputting this list as custom testcase:
[
0, 0, 0, ... (L / 4 times),
1, 2, 3, ..., L / 4,
0, 0, 0, ... (L / 4 times),
1, 2, 3, ..., L / 4
]
where: L = maximum size of the list = 10^5.
It gives TLE on adding this testcase, which is the expected behavior. But on submitting, it's getting accepted.
GitHub is not allowing me to paste the complete testcase here as it exceeds the character limit. So I've created a gist to share the testcase: https://gist.github.com/code-chaser/9d7741c4fa168bc45715f31cb4e3f571
Click to expand (Python script to generate testcase)
The list can be simply produced by the following python script
max_size = 100000
k = int(max_size / 4)
l = ([0] * k + [(i + 1) for i in range(k)]) * 2
print(l)Language Used for Code
C++
Code used for Submit/Run operation
class Solution {
public:
vector<int> avoidFlood(vector<int>& rains) {
vector<int> ans(rains.size());
vector<int> emptyArray;
map<int, int> latestRain;
priority_queue<int, vector<int>, greater<int>> dryDays;
for (int i = 0; i < rains.size(); i++) {
if (rains[i] > 0) {
ans[i] = -1;
if (latestRain.find(rains[i]) == latestRain.end()) {
latestRain[rains[i]] = i;
} else {
queue<int> tempStorage;
while ((!dryDays.empty()) && (dryDays.top() < latestRain[rains[i]])) {
tempStorage.push(dryDays.top());
dryDays.pop();
}
if ((!dryDays.empty()) && (dryDays.top() > latestRain[rains[i]])) {
ans[dryDays.top()] = rains[i];
dryDays.pop();
latestRain[rains[i]] = i;
} else {
return emptyArray;
}
while (!tempStorage.empty()) {
dryDays.push(tempStorage.front());
tempStorage.pop();
}
}
} else {
dryDays.push(i);
}
}
while (!dryDays.empty()) {
ans[dryDays.top()] = 1;
dryDays.pop();
}
return ans;
}
};Expected behavior
"Time Limit Exceeded" instead of "Accepted".
Screenshots
Rather than screenshot, sharing the accepted submission link: https://leetcode.com/problems/avoid-flood-in-the-city/submissions/1793741393/.
Additional context
Not required