Table of Contents

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

Note: Check out our Golang Advanced Tutorial. The tutorials in this series are elaborative and we have tried to cover all concepts with examples. This tutorial is for those who are looking to gain expertise and a solid understanding of golang – Golang Advance Tutorial

Also if you are interested in understanding how all design patterns can be implemented in Golang. If yes, then this post is for you – All Design Patterns Golang

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

golang