Coding questions · Arista
Find missing value in sorted consecutive array
This question evaluates understanding of array properties and algorithmic complexity, specifically detecting a single missing element in a sorted consecutive sequence within the Coding & Algorithms category.
Given a sorted array nums of distinct integers. The numbers are supposed to form a consecutive sequence starting from some unknown integer start:
- If nothing is missing, the sequence would be:
start, start+1, start+2, ..., start+n-1wheren = len(nums). - But at most one number from this sequence may be missing in
nums.
Return the missing number if one exists; otherwise return null (or -1, but be consistent).
Requirements
- Time complexity must be O(log n).
- Space complexity must be O(1).
Examples
nums = [4,5,6,8,9]→ missing is7nums = [-3,-2,-1,0,1]→ no missing → returnnullnums = [10,11,12,13,15]→ missing is14
Notes
startcan be any integer (including negative).numsis already sorted ascending and contains no duplicates.
Missing Value In Sorted Consecutive Array
Given a sorted distinct array that should be consecutive except for at most one interior missing value, return the missing number or None if no value is missing.
Constraints
- nums is sorted ascending with distinct integers.
- At most one interior value is missing.
- Return None when no missing value is detectable.
Hints
- For a perfect consecutive array, nums[i] - nums[0] equals i.
- Binary search for the first index where that invariant fails.