Golang solution using map with explanation, beats 100% other solutions


  • 0

    Maintain a map whose key is an integer in nums and a value is how many consecutive the number has.
    For example, consider the array below:

    [3, 4, 6, 3, 5]
    

    [0]: map[3] = 1 because 3 is the first value.
    [1]: An element is 4. To have greater consecutive, Adjacent value should exist in the array.
       So search map[3] and map[5].
       map[3] exists and has 1 consecutive, so we can update map[3] = map[4] = 1 + 1 (self) = 2
       because both now has 2 length consecutive.
    [2]: An element is 6. map[5] and map[7] doesn't exist so set map[6] = 1
    [3]: An element is 3, map[3] already exists which means we already examined the value, skip it.
    [4]: Finally we have 5, map[4] = 2 and map[6] = 1, so the length of consecutive becomes 2 + 1 + 1 (self) = 4.
       Then set map[5] = map[3] = map[6] = 4.
       Note that we don't update map[4]. We always have to care about only boundary, which means 4 - 2 + 1 = 3.
       Because we don't revisit values other than the boundary (like we skipped map[3]), no need to update them.

    Finally, we loop through map and return the largest value.

    func longestConsecutive(nums []int) int {
    	nlen := len(nums)
    	if nlen == 0 {
    		return 0
    	}
    
    	m := make(map[int]int)
    	var val1, val2 int
    	var ok1, ok2 bool
    	for i := 0; i < nlen; i++ {
    		val1, val2 = 0, 0
    		ok1, ok2 = false, false
    		num := nums[i]
    
    		if _, ok := m[num]; ok {
    			continue // redundant value
    		}
    
    		val := 1 // self
    		val1, ok1 = m[num+1] // check right side
    		if ok1 {
    			val += val1
    		}
    
    		val2, ok2 = m[num-1] // check left side
    		if ok2 {
    			val += val2
    		}
    
    		m[num] = val
    		if ok1 {
    			m[num+val1] = val // update the right side boundary
    		}
    		if ok2 {
    			m[num-val2] = val // update the left side boundary
    		}
    	}
    
    	max := math.MinInt32
    	for _, v := range m {
    		if v > max {
    			max = v
    		}
    	}
    	return max
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.