[LeetCode] Longest Consecutive Sequence

https://leetcode.com/problems/longest-consecutive-sequence/description/

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

You must write an algorithm that runs in O(n) time.

 

Example 1:

Input: nums = [100,4,200,1,3,2]

Output: 4

Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Example 2:

Input: nums = [0,3,7,2,5,8,4,6,0,1]

Output: 9

Example 3:

Input: nums = [1,0,1,2]

Output: 3

 

Constraints:

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109

---

 

The problem is to find the maximum length of consecutive numbers within a given array of integers.
In this problem, the time-complexity requirement was clearly specified.

숫자로 이루어진 주어진 배열 안에서, 연속적으로 나열될 수 있는 숫자의 최대 길이를 구하는 문제.

여기서는 명확하게 시간복잡도에 대한 제시가 있었다. 

 

class Solution {
    public int longestConsecutive(int[] nums) {
         // an array whose size is the maximum value that appears in the input array
         int min = Integer.MAX_VALUE;
         int max = 0;
         for(int num:nums){
            if(num > max){
                max = num;
            }
            if(num < min){
                min = num;
            }
         }
         Integer[] allNumbers = new Integer[max+1]; // including 0
         // Mark each number’s index in that array (duplicates irrelevant)
         for(int num:nums){
            allNumbers[num] = num;
         }

         // Scan the array once to count consecutive numbers
         int result = 0;
         int tmp = 0;
         for(Integer r:allNumbers){
            if(r != null){
                tmp++;
                if(tmp > result){
                    result = tmp;
                }
            }else{
                tmp = 0;
            }
         }
         System.out.println(result);

         return result;
    }
}

 

At first, I considered a solution like the one above,

but it couldn’t handle cases where the minimum value becomes negative.

처음엔 이런 식으로 생각했는데, 최소값이 마이너스가 되는 경우를 커버할 수 없다.

So I changed the approach:

I stored all numbers in a Set and iterated through it to check for consecutive sequences.

방법을 바꿔서, Set 안에다가 배열 속 모든 숫자를 저장하고 이를 순회하는 식으로 진행해 봤다.

class Solution {
    public int longestConsecutive(int[] nums) {
         int result = 1;
         // If array length is 0, return 0
         if(nums.length == 0){
            return 0;
         }

         // Store all numbers in a Set
         Set<Integer> numSet = new HashSet();
         for(int num : nums){
            numSet.add(num);
         }
         // If array length is 1 or only one unique number exists, return 1
         if(nums.length == 1 || numSet.size() == 1){
            return 1;
         }

         // Find min and max values
         int min = Integer.MAX_VALUE;
         int max = Integer.MIN_VALUE;
         for(int num:nums){
            if(num > max){
                max = num;
            }
            if(num < min){
                min = num;
            }
         }
         // Iterate from min to max, updating count if the next number exists
         int tmp = 1;
         for(int i=min; i<=max; i++){
            if(numSet.contains(i) && numSet.contains(i+1)){
                tmp++;
                if(tmp > result){
                    result = tmp;
                }
            }else{
                tmp = 1;
            }
         }

         return result;
    }
}

 

However, this approach wastes time when there are large gaps between numbers.

The array [0,1,2,4,8,5,6,7,9,3,55,88,77,99,999999999] is a particularly troublesome case.
근데 이렇게 하면 당연히, 갑자기 튀는 숫자가 생겼을 때 시간을 쓸데없이 잡아먹게 된다.

[0,1,2,4,8,5,6,7,9,3,55,88,77,99,999999999] 와 같은 배열의 경우 정말 난처하다.

 

Therefore, the iteration should only cover numbers that actually exist in the array.

I modified the logic accordingly, and it successfully passed all tests!

Only the part that actually counts the number of consecutive values was changed.

따라서, 실제로 주어진 배열을 구성하는 숫자 중에서 순회하도록 변경해야 한다.

그래서 아래와 같이 변경했고 무사히 통과됐다!

실제로 연속된 숫자의 수를 세는 부분만 변경해서 통과~

class Solution {
    public int longestConsecutive(int[] nums) {
         ...
         int tmp = 1;
        // 연속된 숫자의 시작이 되는 수는 존재하고, 그보다 작은 수는 존재하지 않아야 함.
        for(int num:numSet){
            if(!numSet.contains(num-1)){
                int currentNum = num;
                tmp = 1;
                while (numSet.contains(currentNum + 1)){
                    tmp++;
                    currentNum++;
                }
                if(tmp > result){
                    result = tmp;
                }
            }
        }

         return result;
    }
}