FIND THE LONGEST RUN OF CONSECUTIVE INTEGERS IN AN UNSORTED ARRAY, IN LINEAR TIME. DROP EVERY NUMBER INTO A SET, THEN COUNT FORWARD ONLY FROM THE NUMBERS THAT BEGIN A RUN.
THE LONGEST RUN COULD START ANYWHERE, BUT ONLY A NUMBER WITH NO LEFT NEIGHBOR ACTUALLY BEGINS ONE. COUNT FORWARD ONLY FROM THOSE, AND EVERY NUMBER IS TOUCHED JUST ONCE.
THE TOP ROW IS THE INPUT AND THE CURSOR WALKS IT. EACH RUN START FILLS THE RUN LANE WHILE THE SET CONFIRMS THE NEXT NUMBER. THE GOLD TILES ARE THE LONGEST RUN.
1def longest_consecutive(nums):2 ns = set(nums)3 max_streak = 04 for n in nums:5 if (n - 1) not in ns:6 streak = 17 while n + streak in ns:8 streak += 19 max_streak = max(max_streak, streak)10 return max_streak
ONE PASS BUILDS THE SET. EACH NUMBER IS WALKED AT MOST ONCE, FROM ITS RUN START.
THE SET HOLDS EVERY NUMBER.