jaydave · pull · Feb 15, 2022 · Feb 16, 2022 · Feb 16, 2022 · Feb 24, 2022
diff --git a/.github/workflows/python-app.yml b/.github/workflows/python-app.yml
@@ -0,0 +1,36 @@
+# This workflow will install Python dependencies, run tests and lint with a single version of Python
+# For more information see: https://help.github.com/actions/language-and-framework-guides/using-python-with-github-actions
+
+name: Python application
+
+on:
+  push:
+    branches: [ master ]
+  pull_request:
+    branches: [ master ]
+
+jobs:
+  build:
+
+    runs-on: ubuntu-latest
+
+    steps:
+    - uses: actions/checkout@v2
+    - name: Set up Python 3.10
+      uses: actions/setup-python@v2
+      with:
+        python-version: "3.10"
+    - name: Install dependencies
+      run: |
+        python -m pip install --upgrade pip
+        pip install flake8 pytest
+        if [ -f requirements.txt ]; then pip install -r requirements.txt; fi
+    - name: Lint with flake8
+      run: |
+        # stop the build if there are Python syntax errors or undefined names
+        flake8 . --count --select=E9,F63,F7,F82 --show-source --statistics
+        # exit-zero treats all errors as warnings. The GitHub editor is 127 chars wide
+        flake8 . --count --exit-zero --max-complexity=10 --max-line-length=127 --statistics
+    - name: Test with pytest
+      run: |
+        python -m pytest
diff --git a/CONTRIBUTING.md b/CONTRIBUTING.md
@@ -11,7 +11,7 @@ agree to abide by the [Code of Conduct](CODE_OF_CONDUCT.md).
 
 * After that create a branch for your changes. For example:  
   * add_XXX if you will add new algorithms or data structures.  
-  * fix_XXX if you will fixe a bug on a certain algorithm or data structure.  
+  * fix_XXX if you will fix a bug on a certain algorithm or data structure.  
   * test_XXX if you wrote a test/s.  
   * doc_XXX if you added to or edited documentation.
 

diff --git a/README.md b/README.md
@@ -63,6 +63,7 @@ If you want to uninstall algorithms, it is as simple as:
     - [merge_intervals](algorithms/arrays/merge_intervals.py)
     - [missing_ranges](algorithms/arrays/missing_ranges.py)
     - [plus_one](algorithms/arrays/plus_one.py)
+    - [remove_duplicates](algorithms/arrays/remove_duplicates.py)
     - [rotate](algorithms/arrays/rotate.py)
     - [summarize_ranges](algorithms/arrays/summarize_ranges.py)
     - [three_sum](algorithms/arrays/three_sum.py)
@@ -71,6 +72,8 @@ If you want to uninstall algorithms, it is as simple as:
     - [two_sum](algorithms/arrays/two_sum.py)
     - [move_zeros](algorithms/arrays/move_zeros.py)
     - [n_sum](algorithms/arrays/n_sum.py)
+- [greedy](algorithms/greedy/)
+    - [max_contiguous_subsequence_sum](algorithms/greedy/max_contiguous_subsequence_sum.py)
 - [automata](algorithms/automata)
     - [DFA](algorithms/automata/dfa.py)
 - [backtrack](algorithms/backtrack)
@@ -223,6 +226,7 @@ If you want to uninstall algorithms, it is as simple as:
     - [next_bigger](algorithms/maths/next_bigger.py)
     - [next_perfect_square](algorithms/maths/next_perfect_square.py)
     - [nth_digit](algorithms/maths/nth_digit.py)
+    - [num_perfect_squares](algorithms/maths/num_perfect_squares.py)
     - [polynomial](algorithms/maths/polynomial.py)
     - [power](algorithms/maths/power.py)
     - [prime_check](algorithms/maths/prime_check.py)
@@ -370,7 +374,6 @@ If you want to uninstall algorithms, it is as simple as:
         - [count_left_node](algorithms/tree/bst/count_left_node.py)
         - [num_empty](algorithms/tree/bst/num_empty.py)
         - [height](algorithms/tree/bst/height.py)
-    - [fenwick_tree](algorithms/tree/fenwick_tree]
 	- [fenwick_tree](algorithms/tree/fenwick_tree/fenwick_tree.py)
     - [red_black_tree](algorithms/tree/red_black_tree)
         - [red_black_tree](algorithms/tree/red_black_tree/red_black_tree.py)

diff --git a/algorithms/arrays/__init__.py b/algorithms/arrays/__init__.py
@@ -16,3 +16,4 @@
 from .two_sum import *
 from .limit import *
 from .n_sum import *
+from .remove_duplicates import *
diff --git a/algorithms/arrays/josephus.py b/algorithms/arrays/josephus.py
@@ -9,7 +9,6 @@
 Output: 369485271
 """
 
-
 def josephus(int_list, skip):
     skip = skip - 1                     # list starts with 0 index
     idx = 0

diff --git a/algorithms/arrays/limit.py b/algorithms/arrays/limit.py
@@ -14,4 +14,12 @@
 
 # tl:dr -- array slicing by value
 def limit(arr, min_lim=None, max_lim=None):
+    if len(arr) == 0:
+        return arr
+
+    if min_lim is None:
+        min_lim = min(arr)
+    if max_lim is None:
+        max_lim = max(arr)
+
     return list(filter(lambda x: (min_lim <= x <= max_lim), arr))
diff --git a/algorithms/arrays/longest_non_repeat.py b/algorithms/arrays/longest_non_repeat.py
@@ -88,4 +88,22 @@ def get_longest_non_repeat_v2(string):
                 max_len = index - start + 1
                 sub_string = string[start: index + 1]
         used_char[char] = index
-    return max_len, sub_string
+    return max_len, sub_string
+
+def get_longest_non_repeat_v3(string):
+    """
+    Find the length of the longest substring
+    without repeating characters.
+    Uses window sliding approach.
+    Return max_len and the substring as a tuple
+    """
+    longest_substring = ''
+    seen = set()
+    start_idx = 0
+    for i in range(len(string)):
+        while string[i] in seen:
+            seen.remove(string[start_idx])
+            start_idx += 1
+        seen.add(string[i])
+        longest_substring = max(longest_substring, string[start_idx: i+1], key=len)
+    return len(longest_substring), longest_substring
diff --git a/algorithms/arrays/remove_duplicates.py b/algorithms/arrays/remove_duplicates.py
@@ -0,0 +1,30 @@
+"""
+This algorithm removes any duplicates from an array and returns a new array with those duplicates
+removed.
+
+For example:
+
+Input: [1, 1 ,1 ,2 ,2 ,3 ,4 ,4 ,"hey", "hey", "hello", True, True]
+Output: [1, 2, 3, 4, 'hey', 'hello']
+
+Time Complexity: O(n) for hashable items, O(n²) worst case for unhashable items
+Space Complexity: O(n) for the seen set and result array
+"""
+
+from collections.abc import Hashable
+
+
+def remove_duplicates(array):
+    seen = set()
+    new_array = []
+
+    for item in array:
+        if isinstance(item, Hashable):
+            if item not in seen:
+                seen.add(item)
+                new_array.append(item)
+        else:
+            if item not in new_array:
+                new_array.append(item)
+
+    return new_array
diff --git a/algorithms/arrays/summarize_ranges.py b/algorithms/arrays/summarize_ranges.py
@@ -5,23 +5,22 @@
 For example, given [0, 1, 2, 4, 5, 7], return [(0, 2), (4, 5), (7, 7)].
 """
 
+from typing import List, Tuple
 
-def summarize_ranges(array):
-    """
-    :type array: List[int]
-    :rtype: List[]
-    """
+
+def summarize_ranges(array: List[int]) -> List[Tuple[int, ...]]:
     res = []
+    if len(array) == 0:
+        return []
     if len(array) == 1:
-        return [str(array[0])]
-    i = 0
-    while i < len(array):
-        num = array[i]
-        while i + 1 < len(array) and array[i + 1] - array[i] == 1:
-            i += 1
-        if array[i] != num:
-            res.append((num, array[i]))
+        return [(array[0], array[0])]
+    it = iter(array)
+    start = end = next(it)
+    for num in it:
+        if num - end == 1:
+            end = num
         else:
-            res.append((num, num))
-        i += 1
+            res.append((start, end))
+            start = end = num
+    res.append((start, end))
     return res
diff --git a/algorithms/compression/elias.py b/algorithms/compression/elias.py
@@ -1,17 +1,20 @@
 """
-Elias γ code or Elias gamma code is a universal code encoding positive integers.
-It is used most commonly when coding integers whose upper-bound cannot be determined beforehand.
-Elias δ code or Elias delta code is a universal code encoding the positive integers,
+Elias γ code or Elias gamma code is a universal code
+encoding positive integers.
+It is used most commonly when coding integers whose
+upper-bound cannot be determined beforehand.
+Elias δ code or Elias delta code is a universal code
+ encoding the positive integers,
 that includes Elias γ code when calculating.
 Both were developed by Peter Elias.
 
 """
-from math import log,ceil
+from math import log
 
-log2 = lambda x: log(x,2)
+log2 = lambda x: log(x, 2)
 
 # Calculates the binary number
-def binary(x,l=1):
+def binary(x, l=1):
 	fmt = '{0:0%db}' % l
 	return fmt.format(x)
 
@@ -21,20 +24,21 @@ def unary(x):
 
 def elias_generic(lencoding, x):
 	"""
-	The compressed data is calculated in two parts. 
-	The first part is the unary number of 1 + ⌊log2(x)⌋. 
+	The compressed data is calculated in two parts.
+	The first part is the unary number of 1 + ⌊log2(x)⌋.
 	The second part is the binary number of x - 2^(⌊log2(x)⌋).
 	For the final result we add these two parts.
 	"""
-	if x == 0: return '0'
+	if x == 0:
+		return '0'
 
 	first_part = 1 + int(log2(x))
 
 	a = x - 2**(int(log2(x)))
 
 	k = int(log2(x))
 
-	return lencoding(first_part) + binary(a,k)
+	return lencoding(first_part) + binary(a, k)
 
 def elias_gamma(x):
 	"""
@@ -46,4 +50,4 @@ def elias_delta(x):
 	"""
 	For the first part we put the elias_g of the number.
 	"""
-	return elias_generic(elias_gamma,x)
+	return elias_generic(elias_gamma, x)
diff --git a/algorithms/dp/__init__.py b/algorithms/dp/__init__.py
@@ -20,4 +20,4 @@
 from .word_break import *
 from .int_divide import *
 from .k_factor import *
-from .planting_trees import *
+from .planting_trees import *
diff --git a/algorithms/dp/climbing_stairs.py b/algorithms/dp/climbing_stairs.py
@@ -1,32 +1,36 @@
 """
 You are climbing a stair case.
-It takes n steps to reach to the top.
+It takes `steps` number of steps to reach to the top.
 
 Each time you can either climb 1 or 2 steps.
 In how many distinct ways can you climb to the top?
 
-Note: Given n will be a positive integer.
+Note: Given argument `steps` will be a positive integer.
 """
 
 
 # O(n) space
 
-def climb_stairs(n):
+def climb_stairs(steps):
     """
-    :type n: int
+    :type steps: int
     :rtype: int
     """
     arr = [1, 1]
-    for _ in range(1, n):
+    for _ in range(1, steps):
         arr.append(arr[-1] + arr[-2])
     return arr[-1]
 
 
 # the above function can be optimized as:
 # O(1) space
 
-def climb_stairs_optimized(n):
-    a = b = 1
-    for _ in range(n):
-        a, b = b, a + b
-    return a
+def climb_stairs_optimized(steps):
+    """
+    :type steps: int
+    :rtype: int
+    """
+    a_steps = b_steps = 1
+    for _ in range(steps):
+        a_steps, b_steps = b_steps, a_steps + b_steps
+    return a_steps
diff --git a/algorithms/dp/coin_change.py b/algorithms/dp/coin_change.py
@@ -1,28 +1,34 @@
 """
 Problem
-Given a value n, if we want to make change for N cents, and we have infinite supply of each of 
-coins = {S1, S2, .. , Sm} valued coins, how many ways can we make the change? 
-The order of coins doesn't matter.
-For example, for n = 4 and coins = [1, 2, 3], there are four solutions: 
-[1, 1, 1, 1], [1, 1, 2], [2, 2], [1, 3]. 
-So output should be 4. 
+Given a value `value`, if we want to make change for `value` cents, and we have infinite
+supply of each of coins = {S1, S2, .. , Sm} valued `coins`, how many ways can we make the change?
+The order of `coins` doesn't matter.
+For example, for `value` = 4 and `coins` = [1, 2, 3], there are four solutions:
+[1, 1, 1, 1], [1, 1, 2], [2, 2], [1, 3].
+So output should be 4.
 
-For n = 10 and coins = [2, 5, 3, 6], there are five solutions: 
-[2, 2, 2, 2, 2], [2, 2, 3, 3], [2, 2, 6], [2, 3, 5] and [5, 5]. 
+For `value` = 10 and `coins` = [2, 5, 3, 6], there are five solutions:
+
+[2, 2, 2, 2, 2], [2, 2, 3, 3], [2, 2, 6], [2, 3, 5] and [5, 5].
 So the output should be 5.
 
-Time complexity: O(n * m) where n is the value and m is the number of coins
+Time complexity: O(n * m) where n is the `value` and m is the number of `coins`
 Space complexity: O(n)
 """
 
-def count(coins, n):
+def count(coins, value):
+    """ Find number of combination of `coins` that adds upp to `value`
+
+    Keyword arguments:
+    coins -- int[]
+    value -- int
+    """
     # initialize dp array and set base case as 1
-    dp = [1] + [0] * n
- 
+    dp_array = [1] + [0] * value
+
     # fill dp in a bottom up manner
     for coin in coins:
-        for i in range(coin, n+1):
-            dp[i] += dp[i-coin]
-
-    return dp[n]
+        for i in range(coin, value+1):
+            dp_array[i] += dp_array[i-coin]
 
+    return dp_array[value]
-Original file line number
+Diff line change
@@ Expand Up / @@ -9,7 +9,6 @@ @@
     Output: 369485271
     """
     def josephus(int_list, skip):
         skip = skip - 1                     # list starts with 0 index
         idx = 0
@@ Expand Down @@