Longest Consecutive Sequence

Given an array of n integers that may contain duplicates, find the length of the longest run of consecutive integers (for example 4, 5, 6, 7) such that every integer in the run appears at least once somewhere in the array. The elements of the run do not need to be contiguous within the array itself.

Input: The first line contains a single integer n. The second line contains n space-separated integers. Output: A single integer: the length of the longest run of consecutive integers present in the array.

1 <= n <= 10^5. -10^9 <= arr[i] <= 10^9. The array may contain duplicate values.

The 'check if x-1 is absent before counting forward' trick is the single detail that prevents the same run from being recounted from every one of its members - without it, the algorithm would still be correct but needlessly slow.

Given a jumbled array of numbers, find the length of the longest run of consecutive integers that could be formed using values from the array. Brute force: Sort the array first, then scan for the longest consecutive run in sorted order - this works correctly but costs O(n log n) for the sort, when a hash-set approach achieves true O(n). Optimised: Checking that (x-1) is ABSENT before starting a forward count guarantees every element is only ever counted forward from the ONE true beginning of its run - despite looking like it could be O(n²) (an outer scan plus an inner counting loop), every element across the WHOLE array is examined as part of at most one run-counting scan, keeping the total work genuinely linear.

1. Put every number into a hash set first, so membership can be checked in O(1). 2. Only START counting a run from a number x when (x - 1) is NOT in the set - this guarantees x is the true beginning of its run, so each run gets counted exactly once. 3. From each such starting point, count forward (x+1, x+2, ...) as long as each next value exists in the set, tracking the longest run found.

Time: O(n) - though it looks like nested loops, every element is only ever counted forward from its run's true start exactly once across the entire algorithm. Space: O(n), for the hash set holding all the array's values.

When n = 1, the answer is always 1. Duplicate values do not extend the length of a run - a value appearing multiple times still counts once.

Be ready to justify explicitly why the overall time stays O(n) despite the nested-looking structure - interviewers often push on this exact point, since it looks like O(n²) at first glance without the 'only start from a true run beginning' insight.