Share my BFS solution based on HashSet. It's slow(21ms), though easy to come with.


  • 0
    Z
    public class Solution {
        public int longestConsecutive(int[] nums) {
            if (nums.length <= 1) {
                return nums.length;
            }
            
            HashSet<Integer> set = new HashSet<>();
            for (int num : nums) {
                if (!set.contains(num)) {
                    set.add(num);
                }
            }
            
            int max = 1;
            for (int num : nums) {
                if (!set.contains(num)) {
                    continue;
                }
                Queue<Integer> queue = new LinkedList<>();
                queue.offer(num);
                int localMax = 1;
                set.remove(num);
                while (!queue.isEmpty()) {
                    int cur = queue.poll();
                    // check the neighbours
                    if (set.contains(cur - 1)) {
                        ++localMax;
                        set.remove(cur - 1);
                        queue.offer(cur - 1);
                    }
                    if (set.contains(cur + 1)) {
                        ++localMax;
                        set.remove(cur + 1);
                        queue.offer(cur + 1);
                    }
                }
                max = Math.max(max, localMax);
            }
            return max;
        }
    }

  • 0

    Nice solution, very similar to mine


Log in to reply
 

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