Missing Test Case - 2092. Find All People With Secret #20660
Description
LeetCode Username
Kaltu
Problem number, title, and link
- Find All People With Secret https://leetcode.com/problems/find-all-people-with-secret/description/?envType=daily-question&envId=2024-02-24
Category of the bug
- Problem description
- Solved examples
- Problem constraints
- Problem hints
- Incorrect or missing "Related Topics"
- Incorrect test Case (Output of test case is incorrect as per the problem statement)
- Missing test Case (Incorrect/Inefficient Code getting accepted because of missing test cases)
- Editorial
- Programming language support
Description of the bug
Missing testcases to let inefficient Code get accepted.
Language used for code
Rust
Code used for Submit/Run operation
// Paste your code here. Don't remove ``` given
// above and below the code.
impl Solution {
pub fn find_all_people(n: i32, mut meetings: Vec<Vec<i32>>, first_person: i32) -> Vec<i32> {
let mut secret = vec![false; n as usize];
secret[0] = true;
secret[first_person as usize] = true;
meetings.sort_unstable_by_key(|x| x[2]);
let mut left = 0;
while left < meetings.len() { // <--- loop steps over different timestamps
let time = meetings[left][2];
let mut shared = true;
let mut right = left;
while shared { // <-- loop while there is an transaction happen in the network
shared = false;
right = left;
// ↓ naively loop over all edges in the network to perform essentially an inefficient BFS ↓
while right < meetings.len() && meetings[right][2] == time {
let x = meetings[right][0] as usize;
let y = meetings[right][1] as usize;
if secret[x] != secret[y] {
shared = true;
secret[x] = true;
secret[y] = true;
}
right += 1;
}
}
left = right;
}
secret
.into_iter()
.enumerate()
.filter(|x| x.1)
.map(|x| x.0 as i32)
.collect()
}
}Expected behavior
Time Limit Exceeded
Since the code uses a naive BFS that iterates through every edge in the network in a loop over the graph, in the worst case such that the edges form a perfect chain that needs to propagate the secret one edge by one edge, it will take
Despite and high time complexity, the code above is accepted and beats 100.00% of all other submissions.
The inefficiency can be proven by submitting a custom test case that is at the upper bound of the problem constraint, where
will correctly result in a TLE, instead of beating 100% of submissions.
Screenshots
https://leetcode.com/problems/find-all-people-with-secret/submissions/1184487902?envType=daily-question&envId=2024-02-24
As the screenshot shows, the testcase that is crafted such that it is exactly at the upper bound of the problem constraints will cause the code, as accepted and beating 100% of other submissions in speed, to actually get TLE
