81. Neighbourly Subsequence
A bakery records the weight in grams of every loaf of a batch in the array nums. A tray is called neighbourly if the heaviest loaf on it and the lightest loaf on it differ by exactly 1 gram. A tray is made by picking any chosen loaves from the batch while keeping their original relative order (a subsequence), although the order does not affect whether the tray is neighbourly.
Return the largest number of loaves that can be placed on a neighbourly tray, or 0 if no neighbourly tray can be formed.
Example 1
- Input:
- nums = [3,4,4,9,3,5]
- Output:
- 4
- Explanation:
Take the loaves 3, 4, 4, 3: the lightest is 3 and the heaviest is 4, giving a tray of 4 loaves.
Example 2
- Input:
- nums = [1,1,1,1]
- Output:
- 0
- Explanation:
All weights are equal, so no tray has a spread of exactly 1 and the answer is 0.
Example 3
- Input:
- nums = [2,5,6,6,5,7]
- Output:
- 4
- Explanation:
The loaves 5, 6, 6, 5 form the largest neighbourly tray, with 4 loaves.
Constraints
1 ≤ nums.length ≤ 105
-109 ≤ nums[i] ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n)
- Space
- O(n)