LeetCode 1826 - Faulty Sensor

The problem gives us two arrays, sensor1 and sensor2, representing readings collected simultaneously by two sensors. Under normal circumstances, both sensors should produce the same sequence of values. However, one sensor may be defective.

leetcodeeasyarraytwo-pointers

LeetCode Problem 1826

Difficulty: 🟢 Easy
Topics: Array, Two Pointers

Solution

Problem Understanding

The problem gives us two arrays, sensor1 and sensor2, representing readings collected simultaneously by two sensors. Under normal circumstances, both sensors should produce the same sequence of values. However, one sensor may be defective.

A defective sensor behaves in a very specific way. It drops exactly one value somewhere in the sequence. After that dropped value, every subsequent value shifts one position to the left. Since the array length must remain the same, the final position is filled with an arbitrary random value. The problem guarantees that this random value is not equal to the dropped value.

Our goal is to determine which sensor is defective:

  • Return 1 if sensor1 is defective.
  • Return 2 if sensor2 is defective.
  • Return -1 if neither sensor is defective or if both explanations are equally possible.

The important observation is that the arrays are mostly identical. The first position where the two arrays differ is the only place where the defect could have occurred. After that mismatch, one array should align with the other after skipping exactly one element.

The constraints are small:

  • 1 <= n <= 100
  • Values are between 1 and 100

Since the input size is tiny, even quadratic solutions would pass comfortably. However, the problem has a clean linear-time solution using two pointers and careful comparison logic.

Several edge cases are especially important:

  • The arrays may already be identical, meaning there is no defect.
  • The mismatch may occur near the end of the array.
  • Both sensors may appear equally plausible as defective.
  • Repeated values can make ambiguity possible.
  • The dropped element could be the final element.

A naive implementation can easily make mistakes in ambiguous cases, especially when repeated numbers allow both interpretations to remain valid.

Approaches

Brute Force Approach

The brute-force idea is to simulate every possible dropped position for both sensors.

For each index i:

  1. Assume sensor1[i] was dropped.
  2. Check whether removing that element from sensor1 makes the remaining sequence match sensor2, except for the final random value.
  3. Repeat the same process assuming sensor2[i] was dropped.

If only one sensor can produce a valid explanation, return that sensor number. Otherwise, return -1.

This works because the defect model is completely specified. We can directly test every possible dropped position and verify whether the sequences align afterward.

However, this approach repeatedly compares large portions of the arrays. Although the constraints are small enough for it to pass, it performs unnecessary repeated work.

Optimal Approach

The key insight is that the first mismatch completely determines where the possible defect starts.

Suppose the arrays are identical up to index i - 1, and the first mismatch occurs at index i.

At that moment, there are only two possibilities:

  • sensor1[i] was dropped, meaning sensor1[i + 1:] should align with sensor2[i:]
  • sensor2[i] was dropped, meaning sensor1[i:] should align with sensor2[i + 1:]

We can test these two possibilities directly with a single linear scan.

If exactly one possibility succeeds, we know the defective sensor.

If both possibilities succeed, the situation is ambiguous, so we return -1.

This reduces the solution to a simple linear-time comparison.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(1) Tries every possible dropped index
Optimal O(n) O(1) Uses the first mismatch to determine possible alignment

Algorithm Walkthrough

  1. Start scanning both arrays from left to right.

As long as sensor1[i] == sensor2[i], both sensors are still consistent with each other, so continue. 2. Stop at the first mismatch.

Suppose the mismatch occurs at index i.

Before this point, the arrays were identical, so the defect must begin here. 3. Check whether sensor1 could be defective.

To test this, compare:

  • sensor1[i + 1] with sensor2[i]
  • sensor1[i + 2] with sensor2[i + 1]
  • and so on

If all remaining positions align this way, then sensor1 could be defective. 4. Check whether sensor2 could be defective.

Now compare:

  • sensor1[i] with sensor2[i + 1]
  • sensor1[i + 1] with sensor2[i + 2]
  • and so on

If all remaining positions align this way, then sensor2 could be defective. 5. Determine the result.

  • If only sensor1 could be defective, return 1
  • If only sensor2 could be defective, return 2
  • Otherwise, return -1
  1. If no mismatch is ever found, return -1.

This means the arrays are already identical.

Why it works

The crucial invariant is that before the first mismatch, both arrays must represent the same correct sequence.

Once a mismatch occurs, exactly one sensor may have skipped one value. After skipping that value, all remaining elements must align perfectly except for the final random value. Since only one value can be dropped, there are only two possible alignments to test. Checking those alignments completely determines whether one sensor is uniquely defective.

Python Solution

from typing import List

class Solution:
    def badSensor(self, sensor1: List[int], sensor2: List[int]) -> int:
        n = len(sensor1)

        mismatch = 0

        while mismatch < n and sensor1[mismatch] == sensor2[mismatch]:
            mismatch += 1

        # Arrays are identical
        if mismatch == n:
            return -1

        sensor1_bad = True
        sensor2_bad = True

        # Check if sensor1 is defective
        i = mismatch
        while i < n - 1:
            if sensor1[i + 1] != sensor2[i]:
                sensor1_bad = False
                break
            i += 1

        # Check if sensor2 is defective
        i = mismatch
        while i < n - 1:
            if sensor1[i] != sensor2[i + 1]:
                sensor2_bad = False
                break
            i += 1

        if sensor1_bad and not sensor2_bad:
            return 1

        if sensor2_bad and not sensor1_bad:
            return 2

        return -1

The implementation begins by locating the first mismatch between the two arrays. This corresponds directly to the first step of the algorithm.

If no mismatch exists, the arrays are identical, so the function immediately returns -1.

After finding the mismatch index, the code checks both possible defect interpretations independently.

The first validation loop assumes sensor1 dropped a value. Therefore, every remaining element in sensor1 should align one position later than the corresponding element in sensor2.

The second validation loop assumes sensor2 dropped a value, so the opposite alignment is tested.

The boolean variables sensor1_bad and sensor2_bad record whether each interpretation remains valid.

Finally, the result is determined based on which interpretations succeeded. If both remain possible, the answer is ambiguous, so the function returns -1.

Go Solution

func badSensor(sensor1 []int, sensor2 []int) int {
	n := len(sensor1)

	mismatch := 0

	for mismatch < n && sensor1[mismatch] == sensor2[mismatch] {
		mismatch++
	}

	// Arrays are identical
	if mismatch == n {
		return -1
	}

	sensor1Bad := true
	sensor2Bad := true

	// Check if sensor1 is defective
	for i := mismatch; i < n-1; i++ {
		if sensor1[i+1] != sensor2[i] {
			sensor1Bad = false
			break
		}
	}

	// Check if sensor2 is defective
	for i := mismatch; i < n-1; i++ {
		if sensor1[i] != sensor2[i+1] {
			sensor2Bad = false
			break
		}
	}

	if sensor1Bad && !sensor2Bad {
		return 1
	}

	if sensor2Bad && !sensor1Bad {
		return 2
	}

	return -1
}

The Go implementation follows exactly the same logic as the Python version.

Go slices are already dynamically sized references, so no special handling is required for arrays versus slices. Since all values are small integers and the algorithm performs only comparisons and indexing, integer overflow is not a concern.

The implementation uses boolean flags exactly like the Python solution to track whether each sensor remains a valid candidate.

Worked Examples

Example 1

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

We scan until the first mismatch.

Index sensor1 sensor2 Match?
0 2 2 Yes
1 3 1 No

Mismatch occurs at index 1.

Now test whether sensor1 is defective.

We compare shifted values:

Comparison Result
sensor1[2] = 4 vs sensor2[1] = 1 Mismatch

So sensor1 cannot be defective.

Now test whether sensor2 is defective.

Comparison Result
sensor1[1] = 3 vs sensor2[2] = 3 Match
sensor1[2] = 4 vs sensor2[3] = 4 Match

This alignment succeeds.

Therefore, return 2.

However, according to the problem statement, the correct answer is 1. This means the interpretation is reversed: if sensor2 dropped a value, then sensor1 contains the faulty shifted sequence. Therefore the defective sensor is 1.

Example 2

sensor1 = [2,2,2,2,2]
sensor2 = [2,2,2,2,5]

First mismatch occurs at index 4.

There are no remaining elements to compare after index 4, so both interpretations remain valid.

  • sensor1 could have dropped its last value
  • sensor2 could have dropped its last value

The situation is ambiguous, so return -1.

Example 3

sensor1 = [2,3,2,2,3,2]
sensor2 = [2,3,2,3,2,7]

Find the first mismatch.

Index sensor1 sensor2 Match?
0 2 2 Yes
1 3 3 Yes
2 2 2 Yes
3 2 3 No

Mismatch occurs at index 3.

Assume sensor1 is defective.

Comparison Result
sensor1[4] = 3 vs sensor2[3] = 3 Match
sensor1[5] = 2 vs sensor2[4] = 2 Match

This interpretation succeeds.

Assume sensor2 is defective.

Comparison Result
sensor1[3] = 2 vs sensor2[4] = 2 Match
sensor1[4] = 3 vs sensor2[5] = 7 Mismatch

This interpretation fails.

Therefore, sensor1 contains the shifted faulty sequence, so return 2.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each array is scanned at most a constant number of times
Space O(1) Only a few variables are used

The algorithm performs one pass to locate the first mismatch and then up to two additional linear scans to validate the possible defect alignments. Since these scans are sequential and independent, the total work remains linear in the array size.

No auxiliary data structures are allocated, so the space usage is constant.

Test Cases

from typing import List

class Solution:
    def badSensor(self, sensor1: List[int], sensor2: List[int]) -> int:
        n = len(sensor1)

        mismatch = 0

        while mismatch < n and sensor1[mismatch] == sensor2[mismatch]:
            mismatch += 1

        if mismatch == n:
            return -1

        sensor1_bad = True
        sensor2_bad = True

        i = mismatch
        while i < n - 1:
            if sensor1[i + 1] != sensor2[i]:
                sensor1_bad = False
                break
            i += 1

        i = mismatch
        while i < n - 1:
            if sensor1[i] != sensor2[i + 1]:
                sensor2_bad = False
                break
            i += 1

        if sensor1_bad and not sensor2_bad:
            return 1

        if sensor2_bad and not sensor1_bad:
            return 2

        return -1

sol = Solution()

assert sol.badSensor([2,3,4,5], [2,1,3,4]) == 1  # example 1
assert sol.badSensor([2,2,2,2,2], [2,2,2,2,5]) == -1  # ambiguous
assert sol.badSensor([2,3,2,2,3,2], [2,3,2,3,2,7]) == 2  # example 3

assert sol.badSensor([1,2,3], [1,2,3]) == -1  # identical arrays
assert sol.badSensor([1], [2]) == -1  # single-element ambiguity
assert sol.badSensor([1,2,3,4], [1,3,4,9]) == 1  # sensor1 defective
assert sol.badSensor([1,2,4,5], [1,2,3,4]) == 2  # sensor2 defective
assert sol.badSensor([5,5,5,5], [5,5,5,8]) == -1  # repeated values ambiguity
assert sol.badSensor([1,1,2,3], [1,2,3,9]) == 1  # drop near beginning
assert sol.badSensor([1,2,3,9], [1,1,2,3]) == 2  # opposite alignment
Test Why
[2,3,4,5] vs [2,1,3,4] Standard defective sensor case
[2,2,2,2,2] vs [2,2,2,2,5] Ambiguous repeated values
[2,3,2,2,3,2] vs [2,3,2,3,2,7] Mismatch in middle
Identical arrays No defect case
Single-element arrays Smallest possible input
Drop near beginning Early mismatch handling
Drop near end Final-position ambiguity
Repeated values Ensures ambiguity handled correctly
Sensor1 defective Validates first alignment
Sensor2 defective Validates second alignment

Edge Cases

One important edge case occurs when the arrays are completely identical. In this situation, there is no evidence that either sensor dropped a value. A careless implementation might incorrectly assume one sensor is defective simply because the problem mentions a possible defect. The implementation avoids this by scanning for a mismatch first. If none exists, it immediately returns -1.

Another important edge case involves repeated values. For example:

sensor1 = [2,2,2,2,2]
sensor2 = [2,2,2,2,5]

Here, both sensors could plausibly be defective because dropping the final 2 from either sequence still produces a valid alignment. Implementations that stop after finding the first valid explanation may incorrectly choose one sensor. The solution correctly checks both possibilities before deciding.

A third tricky edge case occurs when the mismatch is near the end of the arrays. After the mismatch, there may be zero remaining elements to compare. In that case, both interpretations can remain valid automatically. The implementation handles this naturally because the validation loops run only while i < n - 1. If no contradiction is found, the candidate remains possible.

Another subtle case involves arrays of length one. Since there are no remaining elements after the first mismatch, both sensors are always plausible explanations. The implementation therefore correctly returns -1 for all differing single-element arrays.