Missing Values Inside a Retained Range
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Other
### Problem
An integer array `nums` contains distinct values left over from an original inclusive range of consecutive integers. Some values may be missing, but the smallest and largest values of that original range are still present.
Return all missing integers from the original range in increasing order. Return an empty list if the range is complete. The input array itself is not necessarily sorted.
```cpp
class Solution {
public:
vector<int> findMissingElements(vector<int>& nums);
};
```
### Examples
**Example 1:**
```text
Input: nums = [9,3,6]
Output: [4,5,7,8]
Explanation: The original range is [3,9]. Its retained values are 3,6,9, so the four listed integers are missing.
```
**Example 2:**
```text
Input: nums = [4,2,3]
Output: []
Explanation: Every integer from the retained minimum 2 through the retained maximum 4 is already present.
```
### Constraints
- `2 <= nums.length <= 100`.
- `1 <= nums[i] <= 100`.
- All elements of `nums` are unique.
- The original range's two endpoints are present in `nums`.
### Clarifying Questions
- Is the input order meaningful? No; the original interval and missing values are the requirements.
- Should values outside the retained minimum and maximum be returned? No; they are outside the original range.
- Is the result the completed range? No; return only the missing values.
- Is output order arbitrary? No; return the missing values in increasing order.
### What a Strong Answer Covers
- The endpoint-preservation promise and the original range it identifies.
- Every missing value exactly once, with no retained or outside-range values.
- Unsorted input, consecutive retained values, and an empty result.
- A completeness argument and resource bounds using the stated limits.
### Follow-up Questions
- What information would be needed if the original endpoints could also be missing?
- How would returning the completed interval change the required output?
```hint Use the retained endpoints
Find the minimum and maximum retained values. Check each integer in that inclusive interval for membership and append only absent values, in increasing order. The small value bound permits a simple presence table.
```
Overview: Find the missing integers inside a range whose endpoints remain present. Includes sorted-output examples, a completeness proof, bounds, and a C++ solution.