adding LCS problem

rlishtaba · rlishtaba · Dec 11, 2017 · Dec 11, 2017 · Dec 12, 2017 · Dec 11, 2017
commit 14128e53ed819933af563a9ba67b82a42768256e
diff --git a/README.md b/README.md
@@ -80,6 +80,8 @@ $ pip install py-algorithms
       - Weighted Union Find
       - Weighted Union Find with Path Compression
 
+      - Longest Consecutive
+
 ---
 
 ### Dynamic Programing (DP)

diff --git a/py_algorithms/array/longest_consecutive.py b/py_algorithms/array/longest_consecutive.py
@@ -0,0 +1,57 @@
+from typing import List
+
+
+class LongestConsecutive:
+    @staticmethod
+    def apply(nums: List[int]) -> int:
+        return LongestConsecutive.with_sorting(nums)
+
+    @staticmethod
+    def with_sorting(nums: List[int]):
+        if not nums:
+            return 0
+
+        nums = sorted(nums)
+        longest_consecutive = 1
+        current = 1
+
+        for i in range(1, len(nums)):
+            if nums[i] != nums[i - 1]:
+                if nums[i] == nums[i - 1] + 1:
+                    current += 1
+                else:
+                    longest_consecutive = max(current, longest_consecutive)
+                    current = 1
+
+        return max(current, longest_consecutive)
+
+    @staticmethod
+    def brute_force(nums: List[int]):
+        if not nums:
+            return 0
+
+        longest_consecutive = 1
+        for num in nums:
+            current = num
+            current_seq = 1
+
+            while current + 1 in nums:
+                current += 1
+                current_seq += 1
+
+            longest_consecutive = max(longest_consecutive, current_seq)
+        return longest_consecutive
+
+    @staticmethod
+    def with_set(nums):
+        xs = set(nums)
+        known_max = 0
+
+        for p in xs:
+            if p - 1 not in xs:
+                q = p + 1
+                while q in xs:
+                    q += 1
+                known_max = max(known_max, q - p)
+
+        return known_max
diff --git a/py_algorithms/matrix/__init__.py b/py_algorithms/matrix/__init__.py
diff --git a/py_algorithms/strings/path_finder.py → py_algorithms/matrix/path_finder.py b/py_algorithms/strings/path_finder.py → py_algorithms/matrix/path_finder.py
diff --git a/tests/py_algorithms/arrays/longest_consecutive_test.py b/tests/py_algorithms/arrays/longest_consecutive_test.py
@@ -0,0 +1,28 @@
+import pytest
+
+from py_algorithms.array.longest_consecutive import LongestConsecutive
+
+
+def test_case_helper(f, mapping):
+    for x in mapping:
+        payload, expected = x
+        assert expected == f(payload)
+
+
+@pytest.fixture
+def cases():
+    return [
+        ([100, 4, 200, 1, 3, 2], 4),
+        ([], 0),
+        ([2, 1, 1, 3], 3)]
+
+
+class TestLongestConsecutive:
+    def test_apply(self):
+        test_case_helper(LongestConsecutive.with_sorting, cases())
+
+    def test_brute_force(self):
+        test_case_helper(LongestConsecutive.brute_force, cases())
+
+    def test_with_set(self):
+        test_case_helper(LongestConsecutive.with_set, cases())