tag:blogger.com,1999:blog-8522573717713847738.post8747904349093099329..comments2024-03-28T00:14:29.070-07:00Comments on Yu's Coding Garden : leetcode Question 129: Longest Consecutive SequenceAnonymoushttp://www.blogger.com/profile/00263085222060621782noreply@blogger.comBlogger13125tag:blogger.com,1999:blog-8522573717713847738.post-24497804711908240092016-11-04T08:34:39.366-07:002016-11-04T08:34:39.366-07:00but insertion has worst time complexity of O(size ...but insertion has worst time complexity of O(size of container)...then won't it become O(n^2)Anonymoushttps://www.blogger.com/profile/06774531533313594008noreply@blogger.comtag:blogger.com,1999:blog-8522573717713847738.post-10526246839942124142015-10-13T21:19:48.099-07:002015-10-13T21:19:48.099-07:00what if consecutive length is 1? no elements are c...what if consecutive length is 1? no elements are consecutive in the array, then the map items won't be eliminated, the worst case is still O(n^2). is it? i'm still confused with the O(n) requirement in this question, after reading multiple solutions online, the most straight forward solution to this question is like what you provided here, but i do think the time complexity is O(n^2). if it passed on leetcode, then the question itself is not correct, right? thank you!!Anonymoushttps://www.blogger.com/profile/06033533932916812333noreply@blogger.comtag:blogger.com,1999:blog-8522573717713847738.post-75099404131101992352015-07-31T00:12:53.442-07:002015-07-31T00:12:53.442-07:00I have a solution:
public class Solution {
...I have a solution:<br /><br />public class Solution { <br /> public int longestConsecutive(int[] num) { <br /> int longest = 0; <br /> Map map = new HashMap(); <br /> for(int i = 0; i< num.length; i++){ <br /> map.put(num[i], false); <br /> } <br /> <br /> int l, k; <br /> for(int i = 0;i < num.length;i++){ <br /> <br /> if(map.containsKey(num[i]-1) || map.get(num[i])) continue; <br /> map.put(num[i], true); <br /> l = 0; k = num[i]; <br /> while (map.containsKey(k)){ <br /> l++; <br /> k++; <br /> } <br /> if(longest < l) longest = l; <br /> <br /> } <br /> return longest; <br /> } <br />} <br /><br />There are other solutions here: http://traceformula.blogspot.com/2015/07/longest-consecutive-sequence-some.htmltraceformulahttps://www.blogger.com/profile/07593856187162437549noreply@blogger.comtag:blogger.com,1999:blog-8522573717713847738.post-32672857880468580942015-07-31T00:12:46.106-07:002015-07-31T00:12:46.106-07:00I have a solution:
public class Solution {
...I have a solution:<br /><br />public class Solution { <br /> public int longestConsecutive(int[] num) { <br /> int longest = 0; <br /> Map map = new HashMap(); <br /> for(int i = 0; i< num.length; i++){ <br /> map.put(num[i], false); <br /> } <br /> <br /> int l, k; <br /> for(int i = 0;i < num.length;i++){ <br /> <br /> if(map.containsKey(num[i]-1) || map.get(num[i])) continue; <br /> map.put(num[i], true); <br /> l = 0; k = num[i]; <br /> while (map.containsKey(k)){ <br /> l++; <br /> k++; <br /> } <br /> if(longest < l) longest = l; <br /> <br /> } <br /> return longest; <br /> } <br />} <br /><br />There are other solutions here: http://traceformula.blogspot.com/2015/07/longest-consecutive-sequence-some.htmltraceformulahttps://www.blogger.com/profile/07593856187162437549noreply@blogger.comtag:blogger.com,1999:blog-8522573717713847738.post-57314015574391003872015-04-27T22:14:55.827-07:002015-04-27T22:14:55.827-07:00Use Radix sort O(kN) where k is # of digits in the...Use Radix sort O(kN) where k is # of digits in the max numberMithyahttps://www.blogger.com/profile/00483279902391578030noreply@blogger.comtag:blogger.com,1999:blog-8522573717713847738.post-7184793757278953222014-10-21T22:46:25.569-07:002014-10-21T22:46:25.569-07:00I think in the first piece of code, after line 13,...I think in the first piece of code, after line 13, you can add one more line code<br /><br /> if(mp.find(num[i]) == mp.end()) continue;<br /><br />This will make the code more obviously that the running time is O(n), and more correct.Anonymoushttps://www.blogger.com/profile/04520982579653681599noreply@blogger.comtag:blogger.com,1999:blog-8522573717713847738.post-11144936998924560812014-08-26T11:35:40.612-07:002014-08-26T11:35:40.612-07:00You actually don't need a map here. If you nee...You actually don't need a map here. If you need linear search complexity, use unordered_set will be enough here.Anonymoushttps://www.blogger.com/profile/04744786767863366591noreply@blogger.comtag:blogger.com,1999:blog-8522573717713847738.post-8020516842008527392014-04-15T20:28:46.995-07:002014-04-15T20:28:46.995-07:00Nice code in C#. Complexiety O(n)
http://onestopi...Nice code in C#. Complexiety O(n)<br /><br />http://onestopinterviewprep.blogspot.com/2014/04/longest-consecutive-sequence-of-numbers.htmlAnonymoushttps://www.blogger.com/profile/16589208945112160958noreply@blogger.comtag:blogger.com,1999:blog-8522573717713847738.post-62651167484693420552014-02-17T17:58:44.515-08:002014-02-17T17:58:44.515-08:00Use unordered_set instead of map, that will lead t...Use unordered_set instead of map, that will lead to a O(n) solution.Anonymoushttps://www.blogger.com/profile/16258067420097252750noreply@blogger.comtag:blogger.com,1999:blog-8522573717713847738.post-6149288074363065652013-12-24T00:45:38.342-08:002013-12-24T00:45:38.342-08:00Actually this problem needs some data structure li...Actually this problem needs some data structure like union-find-set. That will led to a O(n) complexity.MatRushhttps://www.blogger.com/profile/15681656757944843231noreply@blogger.comtag:blogger.com,1999:blog-8522573717713847738.post-42367919611153634982013-10-24T11:29:09.342-07:002013-10-24T11:29:09.342-07:00Insertion in map takes O(log n). Since n insertion...Insertion in map takes O(log n). Since n insertions are made, the time complexity is actually O(n log n)Dineshhttps://www.blogger.com/profile/12928811729065399794noreply@blogger.comtag:blogger.com,1999:blog-8522573717713847738.post-15630765681245955752013-06-12T14:18:59.906-07:002013-06-12T14:18:59.906-07:00I think we can understand in this way, every time ...I think we can understand in this way, every time the consecutive element is find, the erase method is performed in the map. e.g. the [100,4,200,1,3,2] sequence, when scanning to "4", 3,2,1 are found in the while loop, and also 3,2,1 are eliminated from the map, thus when for loop goes to 1, or 3, or 2, the while loop actually runs O(1)and the condition fails then skip the while. In this way, the overall complexity is still O(n), isn't it?Anonymoushttps://www.blogger.com/profile/00263085222060621782noreply@blogger.comtag:blogger.com,1999:blog-8522573717713847738.post-40888832741717947362013-06-12T13:59:40.087-07:002013-06-12T13:59:40.087-07:00but i hope the complexity of this algorithm is O(n...but i hope the complexity of this algorithm is O(n^2)... the outer for loop runs 'n' times and inner while loop can run for atmost 'n' times..correct me if i am wronglogic_bomberhttps://www.blogger.com/profile/02704747635992600497noreply@blogger.com