Return Every Integer Whose Neighbors x-1 and x+1 Are Both Absent From the Array
Company: J.P. Morgan
Role: Quantitative Researcher
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given an integer array `nums`, return its lonely values. A value `x` that occurs in `nums` is lonely when neither `x - 1` nor `x + 1` occurs anywhere in `nums`.
The report defines lonely values this way but leaves open how repeated values are handled and in what order the answer is returned; this version fixes both in Rules below.
### Function Signature
```python
def lonely_numbers(nums: list[int]) -> list[int]:
```
### Rules
- A value `x` that occurs in `nums` is lonely when `x - 1` does not occur in `nums` and `x + 1` does not occur in `nums`.
- Other copies of `x` itself do not affect whether `x` is lonely; only `x - 1` and `x + 1` matter. For example, in `[7, 7]` the value 7 is lonely.
- Each lonely value appears in the output exactly once, however many times it occurs in `nums`.
- Return the lonely values in strictly increasing order. If there are none, including when `nums` is empty, return an empty list.
### Constraints
- `0 <= len(nums) <= 10^5`
- `-10^9 <= nums[i] <= 10^9`, so `x - 1` and `x + 1` stay within the 32-bit signed integer range.
- Values may be negative, zero or repeated, and `nums` is in no particular order.
### Examples
**Example 1**
```text
Input: nums = [3, 7, 9, 4]
Output: [7, 9]
```
3 is not lonely because 4 occurs, and 4 is not lonely because 3 occurs. Neither 6 nor 8 occurs, so 7 is lonely; neither 8 nor 10 occurs, so 9 is lonely.
**Example 2**
```text
Input: nums = [20, -3, 8, 9, 2, 20]
Output: [-3, 2, 20]
```
8 and 9 are adjacent, so neither is lonely. -3 (no -4 or -2), 2 (no 1 or 3) and 20 (no 19 or 21) are lonely; 20 occurs twice but is listed once, and the output is in increasing order.
**Example 3**
```text
Input: nums = [1, 2, 3]
Output: []
```
Every value has a neighbor: 1 and 3 each have 2, and 2 has both 1 and 3.
Overview: Given an integer array, return each value x for which neither x - 1 nor x + 1 occurs anywhere in the array, listing each such value once and in increasing order. The task tests precise handling of duplicates, negative numbers and empty input, plus an efficient solution for arrays of up to 100,000 values.
Read the full J.P. Morgan Quantitative Researcher interview experience this question came from