[BUG] - Avoid Flood in The City #32735
Description
LeetCode Username
rutwik2808
Problem Number, Title, and Link
- 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
Bug Description
Test cases like the following should be added to Avoid Flood in The City (#1488), since currently some O(n²) solutions are being accepted.
Reason
The current test set does not appear to include large test cases.
Certain O(n²) implementations still pass, even though they exceed expected complexity for larger inputs.
Example of Test Case
[1, 2, 3, 4, ..., n/3, 0, 0, 0, 0, ..., 1, 2, 3, 4, ..., n/3]
[1, 2, 3, 4, ..., n/3, 0, 0, 0, 0, ..., n/3, n/3-1, n/3-2, n/3-3, ...,2,1]
Inefficient Code That Currently Passes
Language Used for Code
C++
Code used for Submit/Run operation
class Solution {
public:
vector<int> avoidFlood(vector<int>& rains) {
int n = rains.size();
unordered_map<int,int> lake;
for (int i = 0; i < n; i++) {
if (rains[i]) {
if (lake.count(rains[i])) {
int pIdx = lake[rains[i]];
int find = 0;
for (int j = pIdx; j < i; j++) {
if (!rains[j]) {
rains[j] = rains[i];
find = 1;
break;
}
}
if (find == 0) return {};
lake[rains[i]] = i;
rains[i] = -1;
} else {
lake[rains[i]] = i;
rains[i] = -1;
}
}
}
for (int i = 0; i < n; i++) {
if (rains[i] == 0) rains[i] = 1;
}
return rains;
}
};Expected behavior
The expected behavior is that this O(n²) solution should exceed time limits on larger test cases, ensuring only optimized O(n log n) solutions pass.
Screenshots
.
Additional context
No response