Overview

An integer array is given. Find the length of the longest consecutive sequence in it. Let’s see an example to understand it

Example 1

Input: [4,7,3,8,2,1]
Output: 4
Reason: The longest consecutive sequence is [1,2,3,4]

Example 2

Input: [4,7,3,8,2,1,9,24,10,11]
Output: 5
Reason: The longest consecutive sequence is [7,8,9,10,11]

The naive idea is to sort the array and return the longest consecutive sequence. But we can do this in O(n) time. Idea is to use a hash here. Below is the idea

• Store each of the numbers in the hash.

• Then starting with each number, find the length of the longest consecutive sequence beginning at that number. So if a number let’s say is n. We try to find n+1, n+2… in the hash and get the length of the longest consecutive sequence  starting from that number

• If the length find in step 2 is greater than the previous longest consecutive sequence found, then update the longest consecutive sequence length

Program

Below is the program for the same

package main

import "fmt"

func longestConsecutive(nums []int) int {
	numsMap := make(map[int]int)

	lenNums := len(nums)

	for i := 0; i < lenNums; i++ {
		numsMap[nums[i]] = 0
	}

	maxLCS := 0
	for i := 0; i < lenNums; i++ {
		currentLen := 1
		counter := 1

		for {
			val, ok := numsMap[nums[i]+counter]
			if ok {
				if val != 0 {
					currentLen += val
					break
				} else {
					currentLen += 1
					counter += 1
				}
			} else {
				break
			}
		}

		if currentLen > maxLCS {
			maxLCS = currentLen
		}
		numsMap[nums[i]] = currentLen
	}

	return maxLCS
}

func main() {
	output := longestConsecutive([]int{4, 7, 3, 8, 2, 1})
	fmt.Println(output)

	output = longestConsecutive([]int{4, 7, 3, 8, 2, 1, 9, 24, 10, 11})
	fmt.Println(output)

}

Output:

4
5

Also, check out our system design tutorial series here – System Design Tutorial Series