Longest Consecutive Sequence


For the approach #3, personally, maybe we can reduce a little bit time complexity.
when jump out from while loop and before the next for loop, we might check whether now the longest_streak has been longer than nums.length/2+1. If it is, I thought there might not exist another longer subsequence...

@CodingFisher Yep! That would be a good constant optimization to include (that didn't occur to me). However, it is important to note that such an optimization would never improve the asymptotic time complexity beyond linear  there are still cases where you need to examine every element.

@RK21 This problem doesn't care about duplicates, so
unordered_set
should do what you want it to. All we need to know is whether a particular number appears or not, which we can accomplish without tracking duplicate numbers. If we had to deal with duplicates, I would suggest using a hash table that maps list elements to counts.

@li.xiong.391 It appears that the expected answer (according to the judge's solution) is 2, but I agree that it should be 1. The constraints are not specified very clearly for this problem, so I guess this might fall under the umbrella of "illdefined behavior".

@littlefinzer Duplicates don't actually affect this problem, so using a TreeSet would just unnecessarily increase our time complexity to O(nlgn).

@emptyset You're right, I was a little careless there to overlook the O(n) requirement; Will redo it

class Solution {
public int longestConsecutive(int[] nums) {
final HashSet<Integer> mySet = new HashSet<Integer>();
for (int i : nums) mySet.add(i);int longest = 0; for (int i : nums) { int length = 1; for (int j = i  1; mySet.contains(j); j) { mySet.remove(j); ++length; } for (int j = i + 1; mySet.contains(j); ++j) { mySet.remove(j); ++length; } longest = Math.max(longest, length); } return longest; }
}
This shit worked and i still confuse.

@anmingyu11 This is a creative solution. How it works is: because all numbers were preput into the mySet set, imagine if they're all sorted, you can see all the range present from left to right. Example:
nums = [1, 3, 11, 8, 2, 7]
mySet = [1,2,3, 11, 7,8] (anyway to look at mySet since it's a set, order does not matter)the "for (int i : nums)" picks any number, expand left and right from that number. This eventually scan 1 complete range and count length at the same time. Order of ranges being scanned is: (1,2,3), (7,8), then (11)

@littlefinzer i know how it works, but, which i confused is Can anyone give a mathmatic prove that element in Hashset can be removed ? i'm not so good at english, don't know my discription is accurate enough.

I got the point "Because the while loop is reached only when currentNum marks the beginning of a sequence (i.e. currentNum1 is not present in nums),", but still can not understand why "the while loop can only run for n iterations throughout the entire runtime of the algorithm". Could you please explain a little bit more detail?

@cdt This is because
current_num
is never assigned to the same number twice during the entire execution of the algorithm (lemma). By the pigeonhole principle, the lemma implies thatcurrent_num
can be assigned no more thann
times. Additionally, because the (overall) number ofwhile
loop iterations is linearly proportional to the (overall) number ofcurrent_num
assignments, the algorithm runs in linear time.A proof of lemma 1 by contradiction:
Assume that
current_num
is assigned to some numberp
multiple times during the algorithm's execution. During a single iteration of thefor
loop, it is obvious that this is impossible, ascurrent_num
is assigned tonum
and incremented some number of times. Therefore,current_num
must be assigned top
during multiple differentfor
loop iterations. This is impossible viacurrent_num = num
, as the numbers are drawn from aSet
(which does not allow for duplicates). This means that that,current_num
is assigned top
during one iteration of thefor
loop, and during another iteration it is assigned to a numberq
(such thatq < p
and all integers on the interval[q .. p]
are innums
). Given that all integers betweenq
andp
are innums
, thewhile
loop will bringcurrent_num
fromq
top
. This is where the contradiction appears, ascurrent_num
would never have been assigned top
in the first place ifp1
was innums
. QED.

I think, using a HashSet is a bit confusing in terms of the time complexity. For many people (and to myself in particular) it wasn't obvious that we spend O(n).
I prefer using a HashMap here in the following way:
Firstly, put every element in a HashMap and mark it as unexplored.

Then iterate through the array of numbers and "explore" every number up and down, remembering the longest subsequence length.

If item has already been explored  it'll be skipped.
Thus, every item will be processed only once  so we get O(n) time complexity, what satisfies the requirements.
public int longestConsecutive(int[] nums) {
Map<Integer, Boolean> mapExplored = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
mapExplored.put(nums[i], false);
}
int maxCounter = 0;
for (int i = 0; i < nums.length; i++) {
if (mapExplored.get(nums[i])) {
continue;
}int counter = 1; int startPos = nums[i]  1; while (mapExplored.containsKey(startPos) && !mapExplored.get(startPos)) { counter += 1; mapExplored.put(startPos, true); startPos; } startPos = nums[i] + 1; while (mapExplored.containsKey(startPos) && !mapExplored.get(startPos)) { counter += 1; mapExplored.put(startPos, true); startPos++; } if (maxCounter < counter) { maxCounter = counter; } mapExplored.put(nums[i], true); } return maxCounter;
}


@emptyset
I think the complexity is O(nn) because the 'in' operator in python is of complexity O(n)
'in' operator inside of for loop would give complexity to be O(nn)

@shlok.gandhi, the
in
operator is overloaded, so it functions different depending on what container is used. For alist
, the complexity is O(n), but we are using aset
here (which has O(1) complexity).