Added 2 new solutions

Meto Trajkovski · Meto Trajkovski · commit 02377945d3ca · 2019-12-12T20:12:14.000+01:00
diff --git a/Backtracking/number_of_islands.py b/Backtracking/number_of_islands.py
@@ -0,0 +1,84 @@
+'''
+Number of Islands
+
+Given a 2d grid map of '1's (land) and '0's (water), count the number of islands.
+An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically.
+You may assume all four edges of the grid are all surrounded by water.
+
+Input:  [
+            ['1','1','1','1','0'],
+            ['1','1','0','1','0'],
+            ['1','1','0','0','0'],
+            ['0','0','0','0','0']
+        ]
+Output: 1
+
+Input:  [
+            ['1','1','0','0','0'],
+            ['1','1','0','0','0'],
+            ['0','0','1','0','0'],
+            ['0','0','0','1','1']
+        ]
+Output: 3
+
+=========================================
+This problem can be solved in several ways (using DFS recursion or using the stack data structure) i'll solve it with BFS using Queue data structure.
+    Time Complexity:    O(M * N)
+    Space Complexity:   O(M * N)
+'''
+
+
+############
+# Solution #
+############
+
+from collections import deque
+
+def num_of_islands(grid):
+    n = len(grid)
+    if n == 0:
+        return 0
+    m = len(grid[0])
+
+    islands = 0
+    queue = deque()
+    directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
+
+    for i in range(n):
+        for j in range(m):
+            # search for an island
+            if grid[i][j] == '1':
+                islands += 1
+                queue.append((i, j))
+
+                # BFS
+                while queue:
+                    coord = queue.popleft()
+                    x, y = coord
+                    
+                    if grid[x][y] != '1':
+                        continue
+                    # delete the island
+                    grid[x][y] = '0'
+
+                    for direction in directions:
+                        # calculate the next position
+                        next_x, next_y = (x + direction[0], y + direction[1])
+                        # check if the next position is valid
+                        if (next_x < 0) or (next_x >= n):
+                            continue
+                        if (next_y < 0) or (next_y >= m):
+                            continue
+                        # save this position
+                        queue.append((next_x, next_y))
+
+    return islands
+
+
+###########
+# Testing #
+###########
+
+# Test 1
+# Correct result => 3
+print(num_of_islands([['1','1','0','0','0'], ['1','1','0','0','0'], ['0','0','1','0','0'], ['0','0','0','1', '1']]))
diff --git a/Lists/merge_intervals.py b/Lists/merge_intervals.py
@@ -1,5 +1,5 @@
 '''
-Find All Intervals
+Merge Intervals
 
 You are given an array of intervals.
 Each interval is defined as: (start, end). e.g. (2, 5)
@@ -20,39 +20,34 @@
 Sort the intervals (using the start), accessing order. After that just iterate the intervals
 and check if the current interval belongs to the last created interval.
     Time Complexity:    O(N LogN)
-    Space Complexity:   O(1)
+    Space Complexity:   O(N)    , for the result
 '''
 
 
 ############
 # Solution #
 ############
 
-def find_all_intervals(intervals):
+def merge_intervals(intervals):
     n = len(intervals)
     if n == 0:
         return []
 
     # sort the intervals
     intervals.sort(key=lambda interval: interval[0])
-    result = []
-    start, end = intervals[0]
+    mergedIntervals = []
+    mergedIntervals.append(intervals[0])
 
     for i in range(1, n):
         # check if this interval belongs to the last created interval
-        if intervals[i][0] <= end + 1:
-            # only the end can be changed (start is min, because array is sorted)
-            end = max(end, intervals[i][1])
+        if intervals[i][0] <= mergedIntervals[-1][1] + 1:
+            # only the end can be changed (just copy start it's min, because the array is sorted)
+            mergedIntervals[-1] = (mergedIntervals[-1][0], max(mergedIntervals[-1][1], intervals[i][1]))
         else:
-            # save this interval
-            result.append((start, end))
             # create a new interval
-            start, end = intervals[i]
+            mergedIntervals.append(intervals[i])
 
-    # add the last interval
-    result.append((start, end))
-
-    return result
+    return mergedIntervals
 
 
 ###########
@@ -61,12 +56,12 @@ def find_all_intervals(intervals):
 
 # Test 1
 # Correct result => [(1, 6)]
-print(find_all_intervals([(1, 5), (2, 6)]))
+print(merge_intervals([(1, 5), (2, 6)]))
 
 # Test 2
 # Correct result => [(2, 8)]
-print(find_all_intervals([(2, 4), (5, 5), (6, 8)]))
+print(merge_intervals([(2, 4), (5, 5), (6, 8)]))
 
 # Test 3
 # Correct result => [(1, 4), (6, 10)]
-print(find_all_intervals([(1, 4), (6, 9), (8, 10)]))
+print(merge_intervals([(1, 4), (6, 9), (8, 10)]))
