LeetCode/_128_LongestConsecutiveSequence.java at main · SinghAnna/LeetCode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

import java.util.HashSet;
import java.util.Set;


// Time O(nlogn)
// public class _128_LongestConsecutiveSequence {

//     public static int longestConsecutive(int[] nums) {
//         if (nums.length == 0)
//             return 0;

//         Arrays.sort(nums);

//         int curr = 1; // current sequence length
//         int max = 1; // max sequence length

//         for (int i = 1; i < nums.length; i++) {

//             if (nums[i] == nums[i - 1]) {
//                 continue; // duplicate ignore
//             }

//             if (nums[i] - nums[i - 1] == 1) {
//                 curr++;
//             } else {
//                 curr = 1;
//             }

//             max = Math.max(max, curr);
//         }

//         return max;
//     }

    //beat for interview time complexity O(n)

 public class _128_LongestConsecutiveSequence {
    public static int longestConsecutive(int[] nums) {
    Set<Integer> set = new HashSet<>();

    for (int n : nums) {
    set.add(n);
    }

    int longest = 0;

    for (int n : set) {

    // start of sequence
    if (!set.contains(n - 1)) {
    int curr = n;
    int count = 1;

    while (set.contains(curr + 1)) {
    curr++;
    count++;
    }

    longest = Math.max(longest, count);
    }
    }

    return longest;
    }

    public static void main(String[] args) {
        int[] nums = { 100, 4, 200, 1, 3, 2 };
        System.out.println(longestConsecutive(nums)); // ✅ 4
    }
}