LeetCode 1228 - Missing Number In Arithmetic Progression

The problem asks us to find a missing value from an array that originally formed an arithmetic progression (AP). An arithmetic progression is a sequence where the difference between consecutive terms is constant, i.e., arr[i + 1] - arr[i] is the same for every consecutive pair.

leetcodeeasyarraymath

LeetCode Problem 1228

Difficulty: 🟢 Easy
Topics: Array, Math

Solution

Problem Understanding

The problem asks us to find a missing value from an array that originally formed an arithmetic progression (AP). An arithmetic progression is a sequence where the difference between consecutive terms is constant, i.e., arr[i + 1] - arr[i] is the same for every consecutive pair. We are given an array arr where one element has been removed, and importantly, the missing element is not the first or last element.

The input is a list of integers that represents the incomplete AP, and the expected output is the single integer that was removed. Constraints indicate the array has at least three elements and at most 1000, with values ranging from 0 to 100,000. These constraints tell us that an O(n) solution is acceptable and integer arithmetic will safely fit within standard integer types.

Edge cases to be aware of include sequences with decreasing values, sequences with step size greater than one, and arrays where the missing number occurs near the start or end of the original AP but not at the actual array boundaries.

Approaches

The brute-force approach would involve checking every possible number that could exist between the minimum and maximum of the array, constructing a hypothetical complete AP, and comparing it with the given array to find the missing number. This works because an AP is fully defined by its first and last element and its length. However, it is inefficient because it may require constructing and comparing up to O(n) elements unnecessarily.

The optimal approach leverages the fact that the AP has a constant step d and that the missing number can be inferred by examining consecutive differences in the given array. Since only one number is missing, the correct step is the most common difference between consecutive elements. Once d is known, we can iterate through the array to find the first place where the difference is not d. The missing number is simply the previous element plus d.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) O(n) Generate full AP and compare elements
Optimal O(n) O(1) Compute step from first/last elements and detect missing number directly

Algorithm Walkthrough

  1. Identify the first and last elements of the array to compute the expected common difference d. Since one element is missing, the actual step is (last - first) / len(arr).
  2. Iterate through the array from start to second-to-last element.
  3. For each pair of consecutive elements, calculate their difference.
  4. Compare the observed difference with the expected d.
  5. When the observed difference is greater than d, it means the missing number lies between these two elements.
  6. Return the missing number as the previous element plus d.

Why it works: In a valid AP with one missing number, all differences except the one adjacent to the missing number match the common difference. The first pair with a difference greater than d uniquely identifies the location of the missing number. The arithmetic calculation ensures the missing number is reconstructed precisely.

Python Solution

from typing import List

class Solution:
    def missingNumber(self, arr: List[int]) -> int:
        n = len(arr) + 1  # original array length
        d = (arr[-1] - arr[0]) // (n - 1)
        
        for i in range(len(arr) - 1):
            if arr[i + 1] - arr[i] != d:
                return arr[i] + d
        
        # fallback, should not be reached due to problem constraints
        return -1

The Python implementation first computes the correct step d using the first and last elements of the array. It then iterates through consecutive pairs in arr to locate the abnormal difference, which pinpoints the missing number. The calculation arr[i] + d directly reconstructs the missing element.

Go Solution

func missingNumber(arr []int) int {
    n := len(arr) + 1
    d := (arr[len(arr)-1] - arr[0]) / (n - 1)
    
    for i := 0; i < len(arr)-1; i++ {
        if arr[i+1] - arr[i] != d {
            return arr[i] + d
        }
    }
    
    return -1
}

The Go solution mirrors the Python version. We use integer division for computing the step, and the iteration is over slice indices. Go does not need special handling for edge cases here since the constraints guarantee at least three elements and one missing number inside the array.

Worked Examples

Example 1: arr = [5,7,11,13]

Step computation: d = (13 - 5) // 4 = 2

Iteration:

  • 5 -> 7: diff = 2, OK
  • 7 -> 11: diff = 4, mismatch → missing = 7 + 2 = 9

Example 2: arr = [15,13,12]

Step computation: d = (12 - 15) // 3 = -1

Iteration:

  • 15 -> 13: diff = -2, mismatch → missing = 15 + (-1) = 14

Complexity Analysis

Measure Complexity Explanation
Time O(n) Single pass through the array to find the abnormal difference
Space O(1) Only a few integer variables used; no additional data structures

The optimal solution is linear in time and constant in space, making it efficient for the input size up to 1000 elements.

Test Cases

# Provided examples
assert Solution().missingNumber([5,7,11,13]) == 9  # missing middle value
assert Solution().missingNumber([15,13,12]) == 14  # decreasing AP

# Edge tests
assert Solution().missingNumber([1,3,5,9]) == 7  # missing near end
assert Solution().missingNumber([100,200,400]) == 300  # larger step
assert Solution().missingNumber([0,2,4,6,10]) == 8  # missing middle
assert Solution().missingNumber([10,7,4,0]) == 1  # decreasing, negative step
Test Why
[5,7,11,13] Tests basic AP with one missing number
[15,13,12] Tests decreasing AP
[1,3,5,9] Missing number near the end
[100,200,400] Tests large step size
[0,2,4,6,10] Missing number in the middle of positive AP
[10,7,4,0] Decreasing AP with negative step

Edge Cases

Edge Case 1: Decreasing sequence

APs can decrease. If the step is negative, the same logic applies, as differences are correctly compared with d. Our calculation handles negative differences naturally.

Edge Case 2: Missing number near start or end

The missing number is guaranteed not to be the first or last element. The iteration logic checks each consecutive pair; the missing element will be caught as the first abnormal difference.

Edge Case 3: Non-unit step size

APs may have steps larger than one. By computing the step using (arr[-1] - arr[0]) // (n - 1), we correctly infer the common difference regardless of magnitude, ensuring correct reconstruction of the missing number.