An experiment is being conducted in a lab. To ensure accuracy, there are two sensors collecting data simultaneously. You are given two arrays sensor1 and sensor2, where sensor1[i] and sensor2[i] are the ith data points collected by the two sensors.
However, this type of sensor has a chance of being defective, which causes exactly one data point to be dropped. After the data is dropped, all the data points to the right of the dropped data are shifted one place to the left, and the last data point is replaced with some random value. It is guaranteed that this random value will not be equal to the dropped value.
[1,2,3,4,5] and 3 is dropped, the sensor could return [1,2,4,5,7] (the last position can be any value, not just 7).We know that there is a defect in at most one of the sensors. Return the sensor number (1 or 2) with the defect. If there is no defect in either sensor or if it is impossible to determine the defective sensor, return -1.
Example 1:
Input: sensor1 = [2,3,4,5], sensor2 = [2,1,3,4] Output: 1 Explanation: Sensor 2 has the correct values. The second data point from sensor 2 is dropped, and the last value of sensor 1 is replaced by a 5.
Example 2:
Input: sensor1 = [2,2,2,2,2], sensor2 = [2,2,2,2,5] Output: -1 Explanation: It is impossible to determine which sensor has a defect. Dropping the last value for either sensor could produce the output for the other sensor.
Example 3:
Input: sensor1 = [2,3,2,2,3,2], sensor2 = [2,3,2,3,2,7] Output: 2 Explanation: Sensor 1 has the correct values. The fourth data point from sensor 1 is dropped, and the last value of sensor 1 is replaced by a 7.
Constraints:
sensor1.length == sensor2.length1 <= sensor1.length <= 1001 <= sensor1[i], sensor2[i] <= 100Problem Overview: Two sensors record integer readings in arrays of equal length. Exactly one sensor may be faulty and drops a value at some position, causing the remaining values to shift left while the last reading becomes inconsistent. Your task is to determine which sensor is faulty, or return -1 if it cannot be determined.
Approach 1: Brute Force Shift Verification (O(n^2) time, O(1) space)
Start by locating the first index where sensor1[i] != sensor2[i]. From that position, simulate the scenario where each sensor could be faulty. For example, assume sensor1 dropped a value and check whether sensor1[i+1...] matches sensor2[i...n-2]. Then repeat assuming sensor2 dropped a value. Because each check scans the remaining array, this approach may re-traverse large portions of the data, resulting in O(n^2) time in the worst case while using constant extra space.
Approach 2: Single Pass Traversal (O(n) time, O(1) space)
A more efficient strategy uses a single linear scan across the array. Iterate until the first mismatch appears. At that point, compare the remaining segments while skipping one element from either array. If skipping one element in sensor1 aligns the rest of the sequence with sensor2, sensor1 is faulty. If skipping one element in sensor2 aligns the rest with sensor1, sensor2 is faulty. This behaves like a lightweight two pointers comparison where the offset starts after the mismatch. If both possibilities remain valid or neither works, return -1.
The key observation: only the first mismatch matters. Before that point both sensors match perfectly, and after the dropped value every element shifts by exactly one position. A single traversal check confirms which sequence experienced the shift.
Recommended for interviews: The linear traversal approach is the expected solution. It demonstrates that you can detect the first divergence and reason about shifted sequences without unnecessary nested loops. Mentioning the brute force idea first shows clear thinking, but implementing the O(n) traversal with constant space proves strong algorithmic instincts.
Traverse both arrays, find the first unequal position i. If i \lt n - 1, loop to compare sensor1[i + 1] and sensor2[i], if they are not equal, it indicates that sensor 1 is defective, return 1; otherwise compare sensor1[i] and sensor2[i + 1], if they are not equal, it indicates that sensor 2 is defective, return 2.
If the traversal ends, it means that the defective sensor cannot be determined, return -1.
The time complexity is O(n), where n is the length of the array. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Shift Verification | O(n^2) | O(1) | Conceptual starting point when reasoning about how a dropped value shifts the sequence |
| Single Pass Traversal (Shift Check) | O(n) | O(1) | Optimal solution for interviews and production; detect first mismatch and verify the shifted segment |
1826. Faulty Sensor (Leetcode Easy) • Programming Live with Larry • 301 views views
Watch 3 more video solutions →Practice Faulty Sensor with our built-in code editor and test cases.
Practice on FleetCode