1826. Faulty Sensor

Problem Statement

link: LeetCode.cn LeetCode 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.

For example, if the correct data is [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:

Input: sensor1 = [2,3,4,5], sensor2 = [2,1,3,4] Output: 1

Input: sensor1 = [2,2,2,2,2], sensor2 = [2,2,2,2,5] Output: -1

Input: sensor1 = [2,3,2,2,3,2], sensor2 = [2,3,2,3,2,7] Output: 2

Constraints: sensor1.length == sensor2.length 1 <= sensor1.length <= 100 1 <= sensor1[i], sensor2[i] <= 100

Solution Approach

The solution identifies the faulty sensor by comparing the sequences after checking potential discrepancies in both sensors, returning the faulty sensor or -1 if both are valid or it’s impossible to determine.

Algorithm

1. Initial Alignment: The solution starts by finding the first index where sensor1 and sensor2 differ, indicating a potential drop in one of the sensors.
2. Validation Check: It then verifies if the rest of the data from that point onwards matches between the two sensors when considering each sensor as potentially faulty.
3. Fault Determination: By checking both possible faulty scenarios, the solution determines which sensor, if any, has the defect, returning the appropriate sensor number or -1 if no clear defect is found.

Complexity

time complexity: O(n) space complexity: O(1)

Implement

    class Solution:
    def badSensor(self, sensor1: List[int], sensor2: List[int]) -> int:
        n = len(sensor1)
        index = 0
        while index < n and sensor1[index] == sensor2[index]:
            index += 1
        if index >= n - 1:
            return -1
        flag1 = self.check(sensor1, sensor2, index, index + 1)
        flag2 = self.check(sensor1, sensor2, index + 1, index)
        if flag1 and flag2:
            return -1
        return 1 if flag1 else 2
    
    def check(self, sensor1: List[int], sensor2: List[int], index1: int, index2: int) -> bool:
        n = len(sensor1)
        while index1 < n and index2 < n:
            if sensor1[index1] != sensor2[index2]:
                return False
            index1 += 1
            index2 += 1
        return True

    
    

Twitter  facebook  Email