Examples

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.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

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

Code

[{"language":"C++","code":"class Solution {\npublic:\n    int badSensor(vector<int>& s1, vector<int>& s2) {\n        int n = s1.size(), i = 0;\n        while (i < n && s1[i] == s2[i]) ++i;\n        if (i == n-1 || i == n) return -1;\n        bool f1 = true, f2 = true;\n        for (int j = i; j < n-1; ++j) {\n            if (s1[j+1] != s2[j]) f1 = false;\n            if (s2[j+1] != s1[j]) f2 = false;\n        }\n        if (f1 && !f2) return 1;\n        if (!f1 && f2) return 2;\n        return -1;\n    }\n};","lang":"cpp"},{"language":"Go","code":"func badSensor(s1, s2 []int) int {\n    n := len(s1)\n    i := 0\n    for i < n && s1[i] == s2[i] { i++ }\n    if i == n-1 || i == n { return -1 }\n    f1, f2 := true, true\n    for j := i; j < n-1; j++ {\n        if s1[j+1] != s2[j] { f1 = false }\n        if s2[j+1] != s1[j] { f2 = false }\n    }\n    if f1 && !f2 { return 1 }\n    if !f1 && f2 { return 2 }\n    return -1\n}","lang":"go"},{"language":"Java","code":"class Solution {\n    public int badSensor(int[] s1, int[] s2) {\n        int n = s1.length, i = 0;\n        while (i < n && s1[i] == s2[i]) i++;\n        if (i == n-1 || i == n) return -1;\n        boolean f1 = true, f2 = true;\n        for (int j = i; j < n-1; ++j) {\n            if (s1[j+1] != s2[j]) f1 = false;\n            if (s2[j+1] != s1[j]) f2 = false;\n        }\n        if (f1 && !f2) return 1;\n        if (!f1 && f2) return 2;\n        return -1;\n    }\n}","lang":"java"},{"language":"Kotlin","code":"class Solution {\n    fun badSensor(s1: IntArray, s2: IntArray): Int {\n        val n = s1.size\n        var i = 0\n        while (i < n && s1[i] == s2[i]) i++\n        if (i == n-1 || i == n) return -1\n        var f1 = true\n        var f2 = true\n        for

Related Tags