BinarySearch 0598 Longest Interval Containing One Number

Problem statement

https://binarysearch.com/problems/Longest-Interval-Containing-One-Number/

Solution

What is actually need to be found is gap between two values with distance 2 in sorted array. Also we add sentinels.

Complexity

It is O(n log n) for time and O(n) for space.

Code

class Solution:
    def solve(self, nums):
        nums = sorted(set(nums + [0, 100001]))
        ans = 0
        for i in range(0, len(nums) - 2):
            ans = max(ans, nums[i+2] - nums[i] - 1)
        return ans