Leetcode 1826. Faulty Sensor Solution

Problem Explanation

In this problem, there are two sensors collecting data simultaneously in a lab experiment. Both sensors have a chance of being defective, causing exactly one data point to be dropped. The dropped data point moves all the data points to the right of it one position to the left and replaces the last data point with a random value. We are given two arrays, sensor1 and sensor2 containing the data points collected by each sensor. We are asked to find out which sensor has the defect or return -1 if it's not possible to determine the defective sensor or if there's no defect in either sensor.

Problem Approach

The solution to this problem can be achieved by comparing the two sensor arrays to find out which one has a defect. We can make use of helper functions to perform this comparison.

We will loop through both arrays comparing their values. If the values are equal, we move to the next index in both arrays. If the values are not equal, we store the value of the first array and move to the next index. We continue the loop and if we reach the end of the second array, we check if the last value of the second array is not equal to the stored dropped value.

Based on the True/False results of the helper function, we will determine the defective sensor (1 or 2) or return -1 if it's impossible to find out or there is no defect in either sensor.

Example Walkthrough

Let's walk through an example:

1sensor1 = [2, 3, 4, 5]
2sensor2 = [2, 1, 3, 4]

We can see that the second data point from sensor2 is dropped, and the last value of sensor1 is replaced by a 5. So the correct output is 1 (sensor1 having a defect).

Solution

C++

1class Solution {
2 public:
3  int badSensor(vector<int>& sensor1, vector<int>& sensor2) {
4    const bool oneDefect = canReplace(sensor2, sensor1);
5    const bool twoDefect = canReplace(sensor1, sensor2);
6    if (oneDefect && twoDefect)
7      return -1;
8    if (!oneDefect && !twoDefect)
9      return -1;
10    return oneDefect ? 1 : 2; // Return the sensor with a defect
11  }
12
13 private:
14  // Helper function to compare the sensor arrays
15  bool canReplace(const vector<int>& A, const vector<int>& B) {
16    int i = 0;  // A's index
17    int j = 0;  // B's index
18    int droppedValue = -1;
19
20    // Loop through both arrays while comparing their values
21    while (i < A.size())
22      if (A[i] == B[j]) {
23        ++i;
24        ++j;
25      } else {
26        droppedValue = A[i];
27        ++i;
28      }
29
30    // Check the last value of B and the dropped value
31    return j == B.size() - 1 && B[j] != droppedValue;
32  }
33};
34

Java

1class Solution {
2    public int badSensor(int[] sensor1, int[] sensor2) {
3        boolean oneDefect = canReplace(sensor2, sensor1);
4        boolean twoDefect = canReplace(sensor1, sensor2);
5       
6        if (oneDefect && twoDefect) return -1;
7        if (!oneDefect && !twoDefect) return -1;
8       
9        return oneDefect ? 1 : 2; // Return the sensor with a defect
10    }
11
12    // Helper function to compare the sensor arrays
13    private boolean canReplace(int[] A, int[] B) {
14        int i = 0; // A's index
15        int j = 0; // B's index
16        int droppedValue = -1;
17
18        // Loop through both arrays while comparing their values
19        while (i < A.length) {
20            if (A[i] == B[j]) {
21                i++;
22                j++;
23            } else {
24                droppedValue = A[i];
25                i++;
26            }
27        }
28
29        // Check the last value of B and the dropped value
30        return j == B.length - 1 && B[j] != droppedValue;
31    }
32}

Python

1class Solution:
2    def badSensor(self, sensor1: List[int], sensor2: List[int]) -> int:
3        def canReplace(A, B):
4            i, j = 0, 0  # Indexes for A and B
5
6            # Loop through both lists while comparing their values
7            while i < len(A):
8                if A[i] == B[j]:
9                    i += 1
10                    j += 1
11                else:
12                    droppedValue = A[i]
13                    i += 1
14
15            # Check the last value of B and the dropped value
16            return j == len(B) - 1 and B[j] != droppedValue
17
18        oneDefect = canReplace(sensor1, sensor2)
19        twoDefect = canReplace(sensor2, sensor1)
20
21        if oneDefect and twoDefect:
22            return -1
23        if not oneDefect and not twoDefect:
24            return -1
25
26        return 1 if oneDefect else 2  # Return the sensor with a defect

JavaScript

1class Solution {
2  badSensor(sensor1, sensor2) {
3    const oneDefect = this.canReplace(sensor2, sensor1);
4    const twoDefect = this.canReplace(sensor1, sensor2);
5    if (oneDefect && twoDefect) return -1;
6    if (!oneDefect && !twoDefect) return -1;
7    return oneDefect ? 1 : 2; // Return the sensor with a defect
8  }
9
10  // Helper function to compare the sensor arrays
11  canReplace(A, B) {
12    let i = 0; // A's index
13    let j = 0; // B's index
14    let droppedValue = -1;
15
16    // Loop through both arrays while comparing their values
17    while (i < A.length) {
18      if (A[i] === B[j]) {
19        i++;
20        j++;
21      } else {
22        droppedValue = A[i];
23        i++;
24      }
25    }
26
27    // Check the last value of B and the dropped value
28    return j === B.length - 1 && B[j] !== droppedValue;
29  }
30}
31

C#

1public class Solution {
2    public int BadSensor(int[] sensor1, int[] sensor2) {
3        bool oneDefect = CanReplace(sensor2, sensor1);
4        bool twoDefect = CanReplace(sensor1, sensor2);
5       
6        if (oneDefect && twoDefect) return -1;
7        if (!oneDefect && !twoDefect) return -1;
8       
9        return oneDefect ? 1 : 2; // Return the sensor with a defect
10    }
11
12    // Helper function to compare the sensor arrays
13    private bool CanReplace(int[] A, int[] B) {
14        int i = 0; // A's index
15        int j = 0; // B's index
16        int droppedValue = -1;
17
18        // Loop through arrays while comparing their values
19        while (i < A.Length) {
20            if (A[i] == B[j]) {
21                i++;
22                j++;
23            } else {
24                droppedValue = A[i];
25                i++;
26            }
27        }
28
29        // Check the last value of B and the dropped value
30        return j == B.Length - 1 && B[j] != droppedValue;
31    }
32}
33```## Concluding Remarks
34
35We demonstrated the solution to the "Check if One Array Can Be Obtained from the Other by Moving Sliding and Deleting" problem using helper functions and array comparisons in C++, Java, Python, JavaScript, and C#. This problem is a good example of how to use array manipulations and helper functions to compare elements in two different arrays.