1826. Faulty Sensor


Problem Description

In this lab experiment, we have two sensors (sensor1 and sensor2) collecting data points simultaneously. Unfortunately, there is a possibility that one of the sensors is defective. A defective sensor would skip exactly one data point. Once this happens, all subsequent data points shift one position to the left, and a random value that is distinct from the dropped value is placed at the end. Your task is to determine which sensor, if any, is defective. If sensor1[i] doesn't match sensor2[i], clearly one of the sensors has missed a data point. If no discrepancy is found or it's impossible to tell which sensor is defective, you should return -1. A key point of consideration is that any defect only happens in at most one sensor, never in both. To solve this, we need to analyze the sequences and look for anomalies that indicate the occurrence of a defect.

Intuition

The intuition behind the solution is to compare the data sequences item by item. Since the data is shifted after the point of defect, if two corresponding values are different, this indicates a potential defect. We can iterate through the sensor data until we find the first pair of unequal readings. Once this happens, we continue to compare subsequent values, but this time offset by one position. The logic behind these comparisons is as follows: If the rest of sensor1 matches the shifted sequence of sensor2, this suggests sensor2 dropped the data point. Conversely, if sensor1's shifted sequence matches the rest of sensor2, this suggests sensor1 is the defective one. If the sequences continue to match, we cannot determine which sensor is defective. In code, this is implemented by iterating twice, where the second iteration includes the offset to check the rest of the data sequences. Accordingly, we return 1 if sensor1 is defective, 2 if sensor2 is defective, or -1 if the defective sensor cannot be determined.

Learn more about Two Pointers patterns.

Solution Approach

The algorithm takes advantage of the fact that after the defect occurs, all subsequent data is shifted left by one, and the last data value is arbitrary. The approach can be broken down into the following steps:

  1. Initial Comparison: A while loop runs as long as the index i is less than the length of the sensor arrays minus one. We ignore the last values because we know they are unreliable after a data drop has occurred. Inside this loop, we compare sensor1[i] to sensor2[i] for each index. The loop breaks on the first inequality, which is the possible point of defect.

  2. Check Remaining Values with Offset: After a potential defect point is found, a second while loop initiates. It has two conditions that are checked at each index:

    • If sensor1[i + 1] is not equal to sensor2[i], this implies that sensor2 may have dropped a data point because the remaining elements of sensor1 match the shifted sequence of sensor2.
    • If sensor1[i] is not equal to sensor2[i + 1], this implies that sensor1 may have dropped a data point because the remaining elements of sensor2 match the shifted sequence of sensor1.
  3. Return the Defective Sensor: Depending on which condition is met first and consistently after the potential defect point, the solution can identify which sensor is defective:

    • return 1 if sensor1's remaining values match sensor2's shifted sequence, indicating that sensor1 is the defective one.
    • return 2 if sensor2's remaining values match sensor1's shifted sequence, indicating that sensor2 is the defective one.
    • If neither condition matches or the initial comparison loop runs to the end without finding a discrepancy, return -1 because it's not possible to determine which sensor, if any, is defective.

By separating the detection of the defect point and the identification of the defective sensor into two loops, the implementation simplifies the logic for detecting the defect and handles the edge cases where defect detection is impossible.

Here is the key portion of the Python code reflecting this logic:

1# ... assuming the initial part of the Solution class is defined ...
2
3def badSensor(self, sensor1: List[int], sensor2: List[int]) -> int:
4    # Initial comparison to find the potential defect point
5    i, n = 0, len(sensor1)
6    while i < n - 1 and sensor1[i] == sensor2[i]:
7        i += 1
8
9    # Check remaining values with offset
10    sensor1Defect = sensor2Defect = False
11    for j in range(i, n - 1):
12        if sensor1[j + 1] != sensor2[j]:
13            sensor1Defect = True
14        if sensor1[j] != sensor2[j + 1]:
15            sensor2Defect = True
16
17    # Decide and return which sensor is defective, if possible
18    if sensor1Defect and not sensor2Defect:
19        return 2
20    elif sensor2Defect and not sensor1Defect:
21        return 1
22    else:
23        return -1

This solution is easy to understand and has a linear time complexity of O(n), where n is the number of data points collected by the sensors.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Suppose we have the following sensor data:

  • sensor1: [1, 2, 3, 4, 5, 6]
  • sensor2: [1, 2, 4, 5, 6, 7]
  1. Initial Comparison: We compare the elements at each corresponding index:

    • sensor1[0] is 1 and sensor2[0] is also 1. No discrepancy.
    • sensor1[1] is 2 and sensor2[1] is also 2. No discrepancy.
    • sensor1[2] is 3 but sensor2[2] is 4. We found a discrepancy at index 2.
  2. Check Remaining Values with Offset: We now check the remaining values considering an offset beginning from the point of discrepancy.

    • For sensor1, we compare sensor2[2] with sensor1[3]. They match (both are 4).
    • We see that subsequent pairs also match when sensor1 is offset by one: sensor2[3] with sensor1[4] (both are 5) and sensor2[4] with sensor1[5] (both are 6).

Now let's check the other way:

  • For sensor2, we compare sensor1[2] with sensor2[3]. They do not match (sensor1[2] is 3 and sensor2[3] is 5).
  • We immediately know that sensor2 cannot be the defective one because the off-setting does not align the sequences.
  1. Return the Defective Sensor: Since the remaining values after the discrepancy align when we offset sensor1 but not when we offset sensor2, we can conclude that the defective sensor is sensor1.

Based on this example, the badSensor function would return 1, indicating that sensor1 is defective.

Python Solution

1from typing import List
2
3class Solution:
4    def badSensor(self, sensor1: List[int], sensor2: List[int]) -> int:
5        # Initialize index and get the length of the sensor arrays
6        index, length = 0, len(sensor1)
7      
8        # Find the first mismatch in the sensor readings
9        while index < length - 1:
10            if sensor1[index] != sensor2[index]:
11                break
12            index += 1
13      
14        # Variables to track whether the mismatch pattern is consistent with one sensor failing
15        mismatch_sensor1, mismatch_sensor2 = False, False
16      
17        # Continue checking for mismatches and determine which sensor, if any, is bad
18        while index < length - 1:
19            # Check if the rest of sensor1 matches with sensor2 shifted once
20            if sensor1[index + 1] != sensor2[index]:
21                mismatch_sensor1 = True
22            # Check if the rest of sensor2 matches with sensor1 shifted once
23            if sensor1[index] != sensor2[index + 1]:
24                mismatch_sensor2 = True
25            # If both sensors have mismatches after shifting, we can't determine the bad one
26            if mismatch_sensor1 and mismatch_sensor2:
27                return -1
28          
29            index += 1
30      
31        # If only sensor1 had mismatches, sensor2 is bad
32        if mismatch_sensor1:
33            return 2
34        # If only sensor2 had mismatches, sensor1 is bad
35        elif mismatch_sensor2:
36            return 1
37        # If there were no mismatches, we cannot determine the bad sensor
38        else:
39            return -1
40
41# Note: The method name 'badSensor' remains unchanged as requested.
42

Java Solution

1class Solution {
2  
3    /**
4     * Determines which sensor, if any, is faulty.
5     *
6     * @param sensor1 Array of readings from the first sensor.
7     * @param sensor2 Array of readings from the second sensor.
8     * @return The number of the faulty sensor (1 or 2), or -1 if it cannot be determined.
9     */
10    public int badSensor(int[] sensor1, int[] sensor2) {
11        int index = 0; // Index to iterate through sensor readings.
12        int length = sensor1.length; // Assuming both sensors have the same length of readings.
13      
14        // Move through the readings while they are the same for both sensors.
15        for (; index < length - 1 && sensor1[index] == sensor2[index]; ++index) {
16            // No operation, just incrementing index.
17        }
18      
19        // Continue examining the readings after the first discrepancy.
20        for (; index < length - 1; ++index) {
21            // If the reading from sensor1 is not equal to the previous reading of sensor2, sensor1 is bad.
22            if (sensor1[index + 1] != sensor2[index]) {
23                return 1; // sensor1 is faulty.
24            }
25            // If the reading from sensor2 is not equal to the previous reading of sensor1, sensor2 is bad.
26            if (sensor1[index] != sensor2[index + 1]) {
27                return 2; // sensor2 is faulty.
28            }
29        }
30      
31        // If neither sensor is conclusively found to be faulty, return -1.
32        return -1;
33    }
34}
35

C++ Solution

1class Solution {
2public:
3    // Function to determine which sensor is bad
4    int badSensor(vector<int>& sensor1, vector<int>& sensor2) {
5        int index = 0; // This will store the first index where the two sensors differ
6        int size = sensor1.size(); // Assuming both sensors have the same size readings
7      
8        // Iterate until sensors readings are the same or we reach the second to last element
9        for (; index < size - 1 && sensor1[index] == sensor2[index]; ++index) {}
10      
11        // If the loop had gone all the way to the second to last element without any difference found
12        // then there is no bad sensor or it is not possible to determine it based on the last reading.
13        if (index == size - 1) {
14            return -1;
15        }
16      
17        // Iterate through the rest of the sensor readings starting from the point of discrepancy
18        for (; index < size - 1; ++index) {
19            // If we find a discrepancy where the next value in sensor1 doesn't match the current
20            // value in sensor2, then sensor1 is likely bad
21            if (sensor1[index + 1] != sensor2[index]) {
22                return 1; // Sensor 1 is bad
23            }
24          
25            // If the discrepancy is such that the current value in sensor1 doesn't match the next value in
26            // sensor2, then sensor2 is likely bad
27            if (sensor1[index] != sensor2[index + 1]) {
28                return 2; // Sensor 2 is bad
29            }
30        }
31      
32        // If none of the sensors is conclusively found to be bad, return -1.
33        // This also covers the case when the discrepancy is found at the last pair of readings
34        return -1;
35    }
36};
37

Typescript Solution

1function badSensor(sensor1: number[], sensor2: number[]): number {
2    // Initialize the index to compare both sensor arrays
3    let index = 0;
4    // Get the length of the sensor arrays
5    const length = sensor1.length;
6
7    // Find the first mismatch between the two sensor readings
8    while (index < length - 1 && sensor1[index] === sensor2[index]) {
9        index++;
10    }
11
12    // If no mismatch was found before the last element, return -1
13    if (index === length - 1) {
14        return -1;
15    }
16
17    // Check if sensor1 could be the bad sensor
18    if (isSensorBad(sensor1, sensor2, index)) {
19        return 1;
20    }
21    // Check if sensor2 could be the bad sensor
22    if (isSensorBad(sensor2, sensor1, index)) {
23        return 2;
24    }
25
26    // If neither sensor is confirmed bad, return -1
27    return -1;
28}
29
30function isSensorBad(sensorA: number[], sensorB: number[], startIndex: number): boolean {
31    // Compare the readings between sensorA and sensorB from the startIndex
32    for (let i = startIndex; i < sensorA.length - 1; i++) {
33        if (sensorA[i + 1] !== sensorB[i]) {
34            return true;
35        }
36    }
37    // If all subsequent readings match after the startIndex, this sensor is not bad
38    return false;
39}
40

Time and Space Complexity

Time Complexity

The given Python code has two main loops. The first loop increments i until it finds the first mismatch between sensor1 and sensor2 or reaches the second to last index. The worst-case scenario for this loop is O(n - 1) if the mismatch is at the last compared element or there's no mismatch. The second loop can also iterate up to O(n - 1) in the worst case (when checking for mismatches and deciding which sensor is bad). Therefore, the worst-case time complexity is O(n - 1) + O(n - 1) which simplifies to O(n) as we drop constants for Big O notation.

Space Complexity

The space complexity of the solution is O(1). It uses a constant amount of extra space for the variables i and n, regardless of the input size. No additional data structures are used that grow with input size.

Learn more about how to find time and space complexity quickly.


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫