Length of the Longest Run of Consecutive Numbers

Medium20–25 min

Topics

ArrayHashing

Companies

AmazonMicrosoftGoogleFacebook

Given an unsorted array nums, return the length of the longest run of consecutive integers that all appear somewhere in the array. The numbers don't need to be next to each other in the array itself — for [100, 4, 200, 1, 3, 2], the values 1, 2, 3, 4 are each present somewhere, forming a run of length 4. Checking "is the next number present?" by re-scanning the array every time works, but it's wasteful — the same values get searched for again and again from different starting points. Putting every number into a hash set turns each membership check into O(1). The remaining trick is to only start counting from numbers that are genuine sequence starts — where num - 1 is NOT in the set — so every number in the array is ever counted at most once, keeping the whole algorithm at O(n).

Test Case 1:

Input:nums = [100, 4, 200, 1, 3, 2]

Output:4

Explanation:The numbers 1, 2, 3, 4 each appear somewhere in the array — that's a run of length 4.

Test Case 2:

Input:nums = [0, 3, 7, 2, 5, 8, 4, 6, 0, 1]

Output:9

Explanation:Every number from 0 to 8 appears somewhere — a run of length 9, even with a duplicate 0 present.

Test Case 3:

Input:nums = [1, 2, 0, 1]

Output:3

Explanation:Duplicates don't extend a run — the numbers present are just {0, 1, 2}, a run of length 3.

Constraints

◆0 ≤ nums.length ≤ 10⁵
◆-10⁹ ≤ nums[i] ≤ 10⁹

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

🧪Try your own test case

nums (comma-separated) — 4-9 integers, -200 to 200

1	class Solution {
2	public int longestConsecutiveSequence(int[] nums) {
3	Set<Integer> numSet = new HashSet<>();
4	for (int num : nums) numSet.add(num);
5	int longest = 0;
6	for (int num : numSet) {
7	if (!numSet.contains(num - 1)) {
8	int current = num;
9	int length = 1;
10	while (numSet.contains(current + 1)) {
11	current++;
12	length++;
13	}
14	longest = Math.max(longest, length);
15	}
16	}
17	return longest;
18	}
19	}
20

Array

100

200

HashMap

100→100

4→4

200→200

1→1

3→3

2→2

Variables

setSize6

INITIALIZE

Put every number into a hash set once: 6 distinct values. Membership checks against this set are O(1).

Step 1 / 17

Approach & Solutions

Brute Force

Brute

For every number in the array, repeatedly check whether the next consecutive number also appears — by scanning the WHOLE array again for each check. Correct, but the same values get re-scanned for over and over, from every possible starting point.

TimeO(n²) to O(n³)

SpaceO(1)

Java

Try it out

class Solution {
    public int longestConsecutiveSequence(int[] nums) {
        int longest = 0;
        for (int num : nums) {
            int current = num;
            int length = 1;
            while (contains(nums, current + 1)) {
                current++;
                length++;
            }
            longest = Math.max(longest, length);
        }
        return longest;
    }

    private boolean contains(int[] nums, int target) {
        for (int n : nums) {
            if (n == target) return true;
        }
        return false;
    }
}

Optimal — Hash Set

Optimal

Put every number into a hash set once — membership checks become O(1). Then only start counting from numbers that ARE a sequence start (num - 1 is not in the set); every other number will already get counted while extending some earlier run, so skipping them is what keeps the total work at O(n) instead of O(n²).

TimeO(n)

SpaceO(n)