Problem

An experiment is being conducted in a lab. To ensure accuracy, there aretwo 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 or2 _) with the defect. If there isno defect in either sensor or if it isimpossible to determine the defective sensor, return _-1 .

Examples

Example 1:

1
2
3
4

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:

1
2
3
4

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:

1
2
3
4

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.length
  • 1 <= sensor1.length <= 100
  • 1 <= sensor1[i], sensor2[i] <= 100

Solution

Method 1 – Two Pointers and Simulation

Intuition

We compare the two arrays from left to right. The first index where they differ is a candidate for the dropped value. We check if removing that value from either sensor can make the rest of the arrays match (except for the last value, which can be any value except the dropped one). If both are possible, or neither is possible, return -1. Otherwise, return the sensor number with the defect.

Approach

  1. Iterate from left to right until the first mismatch at index i.
  2. Try skipping sensor1[i] in sensor1 and compare the rest with sensor2 (except the last value).
  3. Try skipping sensor2[i] in sensor2 and compare the rest with sensor1 (except the last value).
  4. If only one of the above is possible, return the corresponding sensor number. If both or neither, return -1.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
public:
    int badSensor(vector<int>& s1, vector<int>& s2) {
        int n = s1.size(), i = 0;
        while (i < n && s1[i] == s2[i]) ++i;
        if (i == n-1 || i == n) return -1;
        bool f1 = true, f2 = true;
        for (int j = i; j < n-1; ++j) {
            if (s1[j+1] != s2[j]) f1 = false;
            if (s2[j+1] != s1[j]) f2 = false;
        }
        if (f1 && !f2) return 1;
        if (!f1 && f2) return 2;
        return -1;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

func badSensor(s1, s2 []int) int {
    n := len(s1)
    i := 0
    for i < n && s1[i] == s2[i] { i++ }
    if i == n-1 || i == n { return -1 }
    f1, f2 := true, true
    for j := i; j < n-1; j++ {
        if s1[j+1] != s2[j] { f1 = false }
        if s2[j+1] != s1[j] { f2 = false }
    }
    if f1 && !f2 { return 1 }
    if !f1 && f2 { return 2 }
    return -1
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    public int badSensor(int[] s1, int[] s2) {
        int n = s1.length, i = 0;
        while (i < n && s1[i] == s2[i]) i++;
        if (i == n-1 || i == n) return -1;
        boolean f1 = true, f2 = true;
        for (int j = i; j < n-1; ++j) {
            if (s1[j+1] != s2[j]) f1 = false;
            if (s2[j+1] != s1[j]) f2 = false;
        }
        if (f1 && !f2) return 1;
        if (!f1 && f2) return 2;
        return -1;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    fun badSensor(s1: IntArray, s2: IntArray): Int {
        val n = s1.size
        var i = 0
        while (i < n && s1[i] == s2[i]) i++
        if (i == n-1 || i == n) return -1
        var f1 = true
        var f2 = true
        for (j in i until n-1) {
            if (s1[j+1] != s2[j]) f1 = false
            if (s2[j+1] != s1[j]) f2 = false
        }
        return when {
            f1 && !f2 -> 1
            !f1 && f2 -> 2
            else -> -1
        }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def badSensor(self, sensor1: list[int], sensor2: list[int]) -> int:
        n = len(sensor1)
        i = 0
        while i < n and sensor1[i] == sensor2[i]:
            i += 1
        if i == n-1 or i == n:
            return -1
        f1 = all(sensor1[j+1] == sensor2[j] for j in range(i, n-1))
        f2 = all(sensor2[j+1] == sensor1[j] for j in range(i, n-1))
        if f1 and not f2:
            return 1
        if not f1 and f2:
            return 2
        return -1
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

impl Solution {
    pub fn bad_sensor(sensor1: Vec<i32>, sensor2: Vec<i32>) -> i32 {
        let n = sensor1.len();
        let mut i = 0;
        while i < n && sensor1[i] == sensor2[i] { i += 1; }
        if i == n-1 || i == n { return -1; }
        let mut f1 = true;
        let mut f2 = true;
        for j in i..n-1 {
            if sensor1[j+1] != sensor2[j] { f1 = false; }
            if sensor2[j+1] != sensor1[j] { f2 = false; }
        }
        if f1 && !f2 { return 1; }
        if !f1 && f2 { return 2; }
        -1
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    badSensor(sensor1: number[], sensor2: number[]): number {
        const n = sensor1.length;
        let i = 0;
        while (i < n && sensor1[i] === sensor2[i]) i++;
        if (i === n-1 || i === n) return -1;
        let f1 = true, f2 = true;
        for (let j = i; j < n-1; ++j) {
            if (sensor1[j+1] !== sensor2[j]) f1 = false;
            if (sensor2[j+1] !== sensor1[j]) f2 = false;
        }
        if (f1 && !f2) return 1;
        if (!f1 && f2) return 2;
        return -1;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the sensors. We scan the arrays at most twice.
  • 🧺 Space complexity: O(1), only a few variables are used.