Skip to content

1826. Faulty Sensor 👎

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
 public:
  int badSensor(vector<int>& sensor1, vector<int>& sensor2) {
    const bool oneDefect = canReplace(sensor2, sensor1);
    const bool twoDefect = canReplace(sensor1, sensor2);
    if (oneDefect && twoDefect)
      return -1;
    if (!oneDefect && !twoDefect)
      return -1;
    return oneDefect ? 1 : 2;
  }

 private:
  bool canReplace(const vector<int>& A, const vector<int>& B) {
    int i = 0;  // A's index
    int j = 0;  // B's index
    int droppedValue = -1;

    while (i < A.size())
      if (A[i] == B[j]) {
        ++i;
        ++j;
      } else {
        droppedValue = A[i];
        ++i;
      }

    return j == B.size() - 1 && B[j] != droppedValue;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
  public int badSensor(int[] sensor1, int[] sensor2) {
    final boolean oneDefect = canReplace(sensor2, sensor1);
    final boolean twoDefect = canReplace(sensor1, sensor2);
    if (oneDefect && twoDefect)
      return -1;
    if (!oneDefect && !twoDefect)
      return -1;
    return oneDefect ? 1 : 2;
  }

  private boolean canReplace(int[] A, int[] B) {
    int i = 0; // A's index
    int j = 0; // B's index
    int droppedValue = -1;

    while (i < A.length)
      if (A[i] == B[j]) {
        ++i;
        ++j;
      } else {
        droppedValue = A[i];
        ++i;
      }

    return j == B.length - 1 && B[j] != droppedValue;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
  def badSensor(self, sensor1: list[int], sensor2: list[int]) -> int:
    # A -> B, so B is defect
    def canReplace(A, B):
      i = 0  # A's index
      j = 0  # B's index
      droppedValue = -1

      while i < len(A):
        if A[i] == B[j]:
          i += 1
          j += 1
        else:
          droppedValue = A[i]
          i += 1

      return j == len(B) - 1 and B[-1] != droppedValue

    oneDefect = canReplace(sensor2, sensor1)
    twoDefect = canReplace(sensor1, sensor2)
    if oneDefect and twoDefect:
      return -1
    if not oneDefect and not twoDefect:
      return -1
    return 1 if oneDefect else 2