// @Override // public String toString() { // String p = prev == null ? "NULL" : prev.val + ""; // String n = next == null ? "NULL" : next.val + ""; // return p + " <- " + val + " -> " + n; // } }
public int longestConsecutive(final List<Integer> A) { // [100, 4, 200, 1, 3, 2] Map<Integer, Node> map = new HashMap<>(); for (Integer i : A) { if (map.containsKey(i)) continue; Node node = new Node(i); // System.out.print(i + ": "); if (map.containsKey(i + 1)) { Node next = map.get(i + 1); node.next = next; next.prev = node; } if (map.containsKey(i - 1)) { Node prev = map.get(i - 1); node.prev = prev; prev.next = node; } map.put(i, node); // System.out.println(map); }
int max = 0; for (Map.Entry<Integer, Node> entry : map.entrySet()) { Integer i = entry.getKey(); Node node = entry.getValue(); int val = 1; if (!node.visited) { Node prev = node.prev; while (prev != null && !prev.visited) { val ++; prev.visited = true; prev = prev.prev; } Node next = node.next; while (next != null && !next.visited) { val ++; next.visited = true; next = next.next; } } node.visited = true; max = Math.max(max, val); } return max; } }
Method 2:
Use a set
Solution 2:
Time: O(n) Space: O(n)
public class Solution { // DO NOT MODIFY THE LIST. IT IS READ ONLY public int longestConsecutive(final List<Integer> A) { Set<Integer> set = new HashSet<>(); for (int i : A) { set.add(i); } int max = 0; for (int i : A) { if (set.contains(i - 1)) { continue; } else { int cur = 0; int val = i; while (set.contains(val)) { cur ++; val ++; } max = Math.max(max, cur); } } return max; } }
class Solution { public int longestConsecutive(int[] nums) { Set<Integer> set = new HashSet<>(); for (int val : nums) { set.add(val); } int max = 0; for (int val : nums) { if (set.contains(val - 1)) { continue; } if (set.contains(val)) { int curLen = 0; while (set.contains(val)) { curLen ++; max = Math.max(max, curLen); val ++; } } } return max; } }