24. Find Longest Consecutive Subsequence

Given an unsorted array of integers, find the length of the longest run of consecutive integers (e.g. 4,5,6,7) that can be formed using elements from the array. Print that length.

Input: The first line contains an integer n. The second line contains n space-separated integers. Output: Print a single integer - the length of the longest run of consecutive integers formable from the array.

1 <= n <= 10^5

Checking for (value - 1) before counting forward is the single trick that prevents the same run from being counted multiple times (once from each of its members) - without it, the algorithm would still be correct but needlessly slow.

Given a jumbled pile of numbers, find the length of the longest unbroken RUN of consecutive integers (like 4, 5, 6, 7) that can be formed using values from the array. Brute force: Sort the array first, then scan for the longest consecutive run in the sorted order - this works correctly but costs O(n log n) due to the sort, when a hash-set approach can do it in true O(n). Optimised: The key trick is only ever starting a 'count forward' scan from values that are genuinely the BEGINNING of a run (where value-1 does NOT exist) - this guarantees every element is examined as part of at most one run-counting scan across the whole algorithm, keeping the total work linear despite looking like nested loops.

Sort the array first, then make a single left-to-right pass comparing each element to the previous one: if it's equal, skip it as a duplicate; if it's exactly one more than the previous, extend the current run; otherwise start a new run. Sorting brings equal and consecutive values physically adjacent, so a single linear scan afterward can measure every consecutive run without any repeated searching, at the cost of the sort itself. Time: O(n log n) Space: O(1) extra (O(n) if sort isn't in-place)

Insert every array element into a hash set, then for each element check whether (element - 1) is also in the set; if it is not, this element must be the start of a run, so count forward through element+1, element+2, and so on for as long as each is present in the set, updating the longest run found. Because every element is only ever extended from when it's a genuine run start, each element is visited a small constant number of times overall across the whole algorithm, giving true linear time without needing to sort at all. Time: O(n) Space: O(n)

For every element in the array, treat it as a potential start of a run and repeatedly check, via a full linear search through the array, whether the next consecutive integer is present, extending the run for as long as it keeps being found, and keep track of the longest run seen. This is correct since it directly tries every possible starting point and follows consecutive values, but every single existence check re-scans the whole array from scratch. Time: O(n^3) worst case Space: O(1)

1. Put every value into a hash set for instant existence checks. 2. For each value, check whether (value - 1) exists in the set - if it does, this value is somewhere in the MIDDLE of a run, so skip it (it'll be counted starting from its run's true beginning). 3. If (value - 1) does NOT exist, this value is the START of a potential run - count forward (value+1, value+2, ...) as long as each next value exists in the set. 4. Track the longest run length found across all such starting points.

Time: O(n) - though it looks like nested loops (an outer scan plus an inner 'count forward' loop), every element is only ever counted forward from ONE true run-start, so the total work across all starts is linear. Space: O(n), for the hash set holding all the array's values.

n = 1 (longest run length is 1); duplicate values that should not inflate the run length; and n = 10^5 (largest, confirming the hash-set based approach is O(n)).

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.