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.