Start learning free

LESSON 202 OF 347 · SORTING

Longest Consecutive Sequence in C#: O(n log n) with Sorting

Practice O(n log n) Read the full explanation

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

Example 1:

Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: Longest consecutive sequence is [1, 2, 3, 4].
             Therefore its length is 4.

Example 2:

Input: [0, 2, 0, 1, 2, 3, 1]
Output: 4
Explanation: Longest consecutive sequence is [0, 1, 2, 3].
             Therefore its length is 4.
	     Note that we count each value once, even tho values 0, 1 and 2 appear 2 times each in nums

Note:

For this lesson, your algorithm should run in O(n log n) time and use O(1) extra space.
(There are faster solutions which we will discuss in future lessons)


Hints:

Let's sort the array in non-decreasing order. In this way each consecutive elements sequence is a subarray of the sorted array. Even more, these consecutive elements subarrays will come one after another.

Let's start by finding the first subarray. Its left endpoint is i = 0. We will use another index variable j to find the right endpoint. j is initially equal to 0 and should be incremented for as long as nums[i...j] is a consectuive subarray. But how can we check this?

j is initially equal to 0 and will be incremented as long as nums[j] <= nums[j - 1] + 1. When the condition is not satisfied anymore, we have found the first subarray: nums[i...j-1]. How can we find the second one?

The leftpoint of the second subarray is j. So we can set the index i to j. Then we can continuously increment j as long as our condition is satisfied just like we did for the first subarray. When the condition is not satisfied anymore, we have found the second subarray: nums[i...j-1]. Can we use the same strategy for finding the rest of the subarrays?

Yes, we can. We should design an algorithm that repeats this strategy until we are left with no more subarrays (e.g. i >= n).
  • 1. Initialize i with 0.
  • 2. While i < n:
    • 1. Initialize j with i + 1.
    • 2. While nums[j] <= nums[j - 1] + 1, increment j
    • 3. Set i to j and return to step 1.

STEP 1 OF 11
    Ctrl + Enter to check

    C# · SORTING

    Longest Consecutive Sequence in C#, explained

    Problem overview

    The method LongestConsecutive receives an unsorted int[] and returns the length of the longest run of consecutive integers that can be formed from its values. The run doesn't need to appear in order or in adjacent positions in the input. For [100, 4, 200, 1, 3, 2] the values 1, 2, 3 and 4 form a run of length 4, so the answer is 4.

    Duplicates count only once. In [0, 2, 0, 1, 2, 3, 1] the values 0, 1, 2 and 3 each appear at least once and form a run of length 4, even though 0, 1 and 2 appear twice.

    Approach: sort, then measure each block

    The lesson allows O(n log n) time and O(1) extra space. Checking for every value whether its neighbours exist in the array would need a lot of searching. Sorting makes it easy: each run of consecutive values becomes one contiguous block of the sorted array, and the blocks follow each other.

    For [0, 2, 0, 1, 2, 3, 1] the sorted array is [0, 0, 1, 1, 2, 2, 3]. All seven elements belong to one block, which covers the values 0 to 3. A gap, such as the one between 4 and 100 in the first example, ends a block.

    The scan keeps two indices. i is where the current block starts, and j walks forward as long as the next element is either a duplicate of the block's last value or exactly one larger. The variable currVal tracks the block's last value. When j stops at a gap, the block's length is currVal - nums[i] + 1, and the next block starts at j.

    Step by step

    1. Start result at 1. Any non-empty array contains a run of length 1, and the answer can only grow from there.
    2. Sort the array with Array.Sort(nums), so consecutive and equal values end up together.
    3. Set i = 0 and loop while i < nums.Length. The index i marks where the next block begins. The loop doesn't move it by one; the last line of the body jumps it.
    4. Set currVal = nums[i]. A block initially holds only its first value, which is also its last.
    5. Set j = i + 1, the next element to try adding.
    6. Run an inner loop while j < nums.Length and nums[j] <= currVal + 1. In a sorted array, an element that passes is a duplicate of currVal or the next value. Anything larger means a gap. The length check comes first so that nums[j] is never read past the end.
    7. Extend only on a new value. Inside the inner loop, if nums[j] == currVal + 1, increment currVal. A duplicate fails this test and changes nothing.
    8. Advance j on every pass, whether the element was a duplicate or a new value.
    9. Record the length. After the inner loop, result = Math.Max(result, currVal - nums[i] + 1). A run from a to b holds b - a + 1 values.
    10. Jump to the next block. Set i = j, because everything before j belongs to the block just measured.
    11. Return result after the outer loop.

    The solution in C#

    class Solution {

    public int LongestConsecutive(int[] nums) {
        int result = 1;
        Array.Sort(nums);

        int i = 0;
        while (i < nums.Length) {
            int currVal = nums[i];
            int j = i + 1;
            while (j < nums.Length && nums[j] <= currVal + 1) {
                if (nums[j] == currVal + 1) {
                    currVal++;
                }
                j++;
            }
            result = Math.Max(result, currVal - nums[i] + 1);
            i = j;
        }
        return result;
    }
};

    The C# details to notice:

    • Short-circuit &&. In j < nums.Length && nums[j] <= currVal + 1, the right side runs only when the left side is true. Swapping the two operands would read nums[nums.Length] and throw IndexOutOfRangeException.
    • Math.Max takes two numbers and returns the larger. It lives in the System namespace.
    • Counting by value, not by position. The length is computed as currVal - nums[i] + 1 rather than by counting elements, which is why duplicates don't inflate it.
    • The input array is sorted in place. The caller's array is reordered by the call.

    Complexity

    Time: O(n log n). Sorting costs O(n log n). After that, j moves only forward and each outer iteration starts i where the previous inner loop stopped, so every element is passed over once. The scan is O(n).

    Space: O(1) extra. The array is sorted in place, and the method uses a few integer variables.

    Edge cases and common mistakes

    • Duplicates. In [1, 2, 2, 3] the answer is 3. The duplicate 2 must neither break the run nor be counted twice. Testing nums[j] == currVal + 1 before incrementing handles both.
    • Gaps. [1, 2, 4, 5, 6] has two blocks, of lengths 2 and 3, so the answer is 3.
    • Negative numbers. [-1, 0, 1] works the same way and gives 3.
    • A single element. The inner loop never runs, the block length is 1, and the answer is 1.
    • An empty array. The method returns 1, because result starts at 1 and the loop never runs. The correct answer would be 0, so add a guard if you reuse the code for inputs that may be empty.
    • Forgetting to jump i. Advancing i by one instead of setting it to j re-measures the same block again and again and loses the linear scan.
    • Using nums[j] == currVal + 1 as the loop condition. A duplicate would stop the inner loop early and split one run into pieces.

    Testing

    • [100, 4, 200, 1, 3, 2] gives 4.
    • [0, 2, 0, 1, 2, 3, 1] gives 4.
    • [5] gives 1.
    • [1, 2, 4, 5, 6] gives 3.
    • [-1, 0, 1] gives 3.
    Keep going with C#About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free