Not a member of GistPad yet?
Sign Up,
it unlocks many cool features!
- class Solution {
- /**
- 1. Store all elements in a HashSet, This allows O(1) lookup for checking if a number exists.
- 2. Only start building a sequence from numbers that are the beginning
- - number is the start if, set does not contains (element-1)
- - count (currentLength) how long the sequence goes, so Expand forward (ele + 1, ele + 2, …)
- - once you found the current length of sequence, Track the maximum length
- 3. repeat step-2 for all the array elements
- 4. return the max length
- */
- public int longestConsecutive(int[] nums) {
- if(nums.length == 0)
- return 0;
- // to remove duplicates
- HashSet<Integer> set = new HashSet<>();
- for(int ele : nums)
- set.add(ele);
- int maxLength = 0;
- for(int ele : nums)
- {
- // find the start of sequence
- if(set.contains(ele - 1) == false) // this is not the start
- {
- int length = 1;
- while(set.contains(ele + 1))
- {
- ele++;
- length++;
- }
- }
- }
- return maxLength;
- }
- }
RAW Paste Data
Copied
