ac solution code


  • 0
        /*
         Solution1. DP/HashMap - time = O(n); space = O(n)     
         1) DP[i]: length of the longest consecutive sequence with boundary at i
         2) Update length of left/right boundary(s) accordingly
         */
        func longestConsecutive(_ nums: [Int]) -> Int {
            var res = 0
            var DP = [Int: Int]() // DP[i]: longest consecutive sequence ends at i
            for i in nums {
                if DP[i] != nil { continue }            // Visited
                let leftLen = DP[i - 1] ?? 0            // Length of left(i-1) boundary
                let rightLen = DP[i + 1] ?? 0           // Length of right(i+1) boundary
                let totalLen = leftLen + rightLen + 1   // totalLen: +1 = i
                DP[i] = totalLen                        // Save totalLen to DP[i]
                
                res = Swift.max(res, totalLen)          // keep track of the max length
    
                // Update length of left/right boundary(s) to avoid duplicate check
                DP[i - leftLen] = totalLen
                DP[i + rightLen] = totalLen
            }
            return res
        }
    
    

Log in to reply
 

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