Find missing value in sorted consecutive array
Problem Description
Given a sorted array nums of distinct integers. These numbers are expected to form a consecutive sequence starting from an unknown integer start.
- If no number is missing, the sequence would be
start, start+1, start+2, ..., start+n-1, wherenis the length ofnums. - At most one number from this expected sequence may be missing in
nums.
Your task is to return the missing number if one exists. If no number is missing, return null (or -1, ensuring consistency in your chosen return value).
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
- The
startinteger can be any value, including negative numbers. - The input array
numsis guaranteed to be sorted in ascending order and contains no duplicate values.
AI interview prep
Core dilemma
Adapting the binary search algorithm to efficiently locate a single missing element in a sorted, nearly consecutive sequence, rather than a specific target value, while adhering to strict O(log n) time and O(1) space constraints.
3 tradeoffs and 3 stress tests locked
Interview prep
Unlock the interviewer X-Ray rubric, tradeoff matrix, stress tests, clarifying questions, and key concepts.
Find missing value in sorted consecutive array
Problem Description
Given a sorted array nums of distinct integers. These numbers are expected to form a consecutive sequence starting from an unknown integer start.
- If no number is missing, the sequence would be
start, start+1, start+2, ..., start+n-1, wherenis the length ofnums. - At most one number from this expected sequence may be missing in
nums.
Your task is to return the missing number if one exists. If no number is missing, return null (or -1, ensuring consistency in your chosen return value).
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
- The
startinteger can be any value, including negative numbers. - The input array
numsis guaranteed to be sorted in ascending order and contains no duplicate values.