Saturday, December 4, 2021

LeetCode Medium Trick Problem: Longest Consecutive Sequence



Came across this problem on Leetcode, which requires one to focus on optimization.


PROBLEM LINK: https://leetcode.com/problems/longest-consecutive-sequence

TIME COMPLEXITY: O(n) at worst case where n is the number of elements in the input array (precisely the constant factor for n is 2)

APPROACH: The most naive approach to solve this problem would have been to sort the input array using comparison sort in O(n lg n) worst case time complexity and then in single pass find the length of the consecutive sequences in the same, resulting in overall worst case time complexity on O(n lg n).

But, if we notice carefully, we can make use of a trick to solve the problem in O(n) worst case time complexity. The trick makes a space trade off of O(n) and makes use of a HashSet to store the values to quickly check if any number exists in the input array. Then, it checks for all values in input, if it is the start of a consecutive sequence by checking presence of 1 lesser value than that on the number line, in the number Set. If any start-of-consecutive-range is found in the array elements, the length of the range is found by consecutively checking all the numbers in the increasing order on the number line consecutively.

In each such iteration of the numbers in input array, the length of the max-range is updated and the largest value is returned at the end of all iterations.


Here's a sample code for the same:


class Solution {
    
    public int longestConsecutive(int[] nums) {
        Set numberSet = new HashSet ();
        
        // Add numbers to Set while updating length of the longest consecutive elements sequence
        int maxLLCES = 0, currLLCES = 0;
        for (int i=0; i<nums.length; i++) {
            numberSet.add (nums[i]);
        }
        
        for (int i=0; i<nums.length; i++) {
            if (!numberSet.contains(nums[i]-1)) {
                // nums[i] is not a start of a consecutive sequence
                currLLCES = 1;
                int checkNum = nums[i]+1;
                while(numberSet.contains(checkNum)) {
                    currLLCES++;
                    checkNum++;
                }
                maxLLCES = Math.max(maxLLCES, currLLCES);
                // System.out.println("Updated maxLLCES:" + maxLLCES);
            }
        }
        return maxLLCES;
    }
}



Do share your thoughts and feel free to talk about the alternatives/optimisations you feel can be done in the comment section!


Love! ❤️ 
#Lets #Code

Follow us on :

https://twitter.com/ThinkAlgorithms



No comments:

Post a Comment

Featured Post

interviewBit Medium: Palindrome Partitioning II

Problem Name:  Palindrome Partitioning II Problem Description : https://www.interviewbit.com/problems/palindrome-partitioning-ii/ Problem Ap...