Missing Number In Arithmetic Progression - Video Solutions
1228. Missing Number In Arithmetic Progression (LeetCode)
Missing Number In Arithmetic Progression - Video Solution
Watch 7 video solutions for Missing Number In Arithmetic Progression, a easy level problem involving Array, Math. This walkthrough by hakunamatasq has 790 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
In some array arr, the values were in arithmetic progression: the values arr[i + 1] - arr[i] are all equal for every 0 <= i < arr.length - 1.
A value from arr was removed that was not the first or last value in the array.
Given arr, return the removed value.
Example 1:
Input: arr = [5,7,11,13] Output: 9 Explanation: The previous array was [5,7,9,11,13].
Example 2:
Input: arr = [15,13,12] Output: 14 Explanation: The previous array was [15,14,13,12].
Constraints:
3 <= arr.length <= 10000 <= arr[i] <= 105- The given array is guaranteed to be a valid array.
Approach Overview
Problem Overview: You are given an array that represents an arithmetic progression with exactly one number missing. The array is still sorted and follows the same common difference except for the missing term. Your task is to identify that missing number.
Approach 1: Arithmetic Series Sum Formula (O(n) time, O(1) space)
An arithmetic progression has a predictable total sum based on its first term, last term, and length. The key observation: the full progression should contain n + 1 numbers if the array currently has n. First compute the common difference using (arr[n-1] - arr[0]) / n. With this difference, you can determine what each element of the full sequence should be. Then compute the expected sum of the complete progression and subtract the actual sum of the array to get the missing value.
This approach relies on simple math properties of arithmetic sequences. You iterate once to compute the array sum and use the formula to derive the expected progression. Time complexity is O(n) and space complexity is O(1). It's straightforward and works well when you want a formula-based solution.
Approach 2: Find Common Difference + Traverse (O(n) time, O(1) space)
An arithmetic progression has a constant difference between adjacent elements. Because one number is missing, exactly one adjacent pair will violate this pattern. Start by computing the expected common difference using (arr[n-1] - arr[0]) / n. Then iterate through the array and check the difference between consecutive elements.
If arr[i+1] - arr[i] does not equal the expected difference, the missing value must be arr[i] + diff. This works because the gap appears exactly where the progression skipped a number. The algorithm performs a single linear scan over the array and uses constant extra memory. Time complexity is O(n) and space complexity is O(1).
This method is often easier to reason about because it directly checks the progression property instead of computing sums. It also avoids potential overflow issues that can occur with large arithmetic series sums.
Recommended for interviews: The Find Common Difference + Traverse approach is usually what interviewers expect. It demonstrates understanding of arithmetic progression properties and uses a clean linear scan. The sum formula solution is also valid and shows strong mathematical reasoning, but detecting the broken difference tends to be the most intuitive explanation during interviews.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Arithmetic Series Sum Formula | O(n) | O(1) | When you want a math-based approach using arithmetic progression formulas |
| Find Common Difference + Traverse | O(n) | O(1) | Best when verifying the progression property and detecting the broken gap |