Longest Consecutive Sequence

MediumArray Hash Table

A habit-tracking app stores every day on which a user completed their habit as a day number in nums. Day 0 is the day the account was created, so earlier days are negative. The array is in no particular order, and a day can appear twice when the app syncs the same check-in again.

Return the length of the user's longest streak: the longest run of consecutive day numbers d, d + 1, d + 2, … that are all present in nums. An empty array means a longest streak of 0.

Your algorithm must run in O(n) time.

Example 1

Input: nums = [12,10,-3,11,-2,30,13]
Output: 4

Explanation: Days 10, 11, 12, 13 form a streak of 4. Days -3, -2 form a streak of 2, and day 30 stands alone.

Example 2

Input: nums = [9,7,8,8,20]
Output: 3

Explanation: Day 8 was synced twice but counts once, so days 7, 8, 9 make a streak of 3.

Example 3

Input: nums = []
Output: 0

Constraints

nums has at most 10^5 entries and may be empty.
Each day number lies between -10^9 and 10^9.

💡 Hint 1

Sorting makes the runs easy to see, but it costs O(n log n). What gives you O(1) membership checks instead?

💡 Hint 2

Put every value into a hash set. A run can only start at a value x for which x - 1 is not in the set.

💡 Hint 3

From each run start, count upwards while x + 1, x + 2, … are in the set. Each value is visited by at most one such count, so the total work is O(n).

Try it yourself first ✎

Solutions stick better after a real attempt. Peek when you're ready.

Approach

Load all values into a hash set. A value x begins a run only if x - 1 is absent; for each such start, walk upwards through x + 1, x + 2, … while they are in the set and record the run length. Values that are not run starts are skipped immediately, so every value is stepped over by at most one walk and the whole algorithm is linear. Iterate over the set rather than the array so duplicates do not trigger repeated walks.

Time O(n)Space O(n)

function longestConsecutive(nums) {
  const set = new Set(nums);
  let best = 0;
  for (const x of set) {
    if (set.has(x - 1)) continue;
    let len = 1;
    while (set.has(x + len)) len++;
    best = Math.max(best, len);
  }
  return best;
}

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int x : nums) set.add(x);
        int best = 0;
        for (int x : set) {
            if (set.contains(x - 1)) continue;
            int len = 1;
            while (set.contains(x + len)) len++;
            best = Math.max(best, len);
        }
        return best;
    }
}

/**
 * @param {number[]} nums
 * @return {number}
 */
function longestConsecutive(nums) {

}

Ctrl/⌘ + ' run · Ctrl/⌘ + Enter submit