Introduction

By definition, a factorial is the product of a positive integer and all the positive integers that are less than or equal to the given number. In other words, getting a factorial of a number means to multiply all whole numbers from that number, down to 1.

0! equals 1 as well, by convention.

A factorial is denoted by the integer and followed by an exclamation mark.

5! denotes a factorial of five.

And to calculate that factorial, we multiply the number with every whole number smaller than it, until we reach 1:

5! = 5 * 4 * 3 * 2 * 1
5! = 120

Keeping these rules in mind, in this tutorial, we will learn how to calculate the factorial of an integer with Python, using loops and recursion. Let's start with calculating the factorial using loops.

Calculating Factorial Using Loops

We can calculate factorials using both the while loop and the for loop. The general process is pretty similar for both. All we need is a parameter as input and a counter.

Let's start with the for loop:

def get_factorial_for_loop(n):
    result = 1
    if n > 1:
        for i in range(1, n+1):
            result = result * i
        return result
    else:
        return 'n has to be positive'

You may have noticed that we are counting starting from 1 to the n, whilst the definition of factorial was from the given number down to 1. But mathematically:

1∗2∗3∗4...∗n=n∗(n−1)∗(n−2)∗(n−3)∗(n−4)...∗(n−(n−1))1∗2∗3∗4...∗n=n∗(n−1)∗(n−2)∗(n−3)∗(n−4)...∗(n−(n−1))

To simplify, (n - (n-1)) will always be equal to 1.

That means that it doesn't matter in which direction we're counting. It can start from 1 and increase towards the n, or it can start from n and decrease towards 1. Now that's clarified, let's start breaking down the function we've just wrote.

Our function takes in a parameter n which denotes the number we're calculating a factorial for. First, we define a variable named result and assign 1 as a value to it.

Why assign 1 and not 0 you ask?

Because if we were to assign 0 to it then all the following multiplications with 0, naturally would result in a huge 0.

Then we start our for loop in the range from 1 to n+1. Remember, the Python range will stop before the second argument. To include the last number as well, we simply add an additional 1.

Inside the for loop, we multiply the current value of result with the current value of our index i.

Finally, we return the final value of the result. Let's test our function print out the result:

inp = input("Enter a number: ")
inp = int(inp)

print(f"The result is: {get_factorial_for_loop(inp)}")

If you'd like to read more about how to get user input, read our Getting User Input in Python.

It will prompt the user to give input. We'll try it with 4:

Enter a number: 4
The result is: 24

You can use a calculator to verify the result:

4! is 4 * 3 * 2 * 1, which results 24.

Now let's see how we can calculate factorial using the while loop. Here's our modified function:

def get_factorial_while_loop(n):
    result = 1
    while n > 1:
        result = result * n
        n -= 1
    return result

This is pretty similar to the for loop. Except for this time we're moving from n towards the 1, closer to the mathematical definition. Let's test our function:

inp = input("Enter a number: ")
inp = int(inp)

print(f"The result is: {get_factorial_while_loop(inp)}")

We'll enter 4 as an input once more:

Enter a number: 4
The result is: 24

Although the calculation was 4 * 3 * 2 * 1 the final result is the same as before.

Calculating factorials using loops was easy. Now let's take a look at how to calculate the factorial using a recursive function.

Calculating Factorial Using Recursion

A recursive function is a function that calls itself. It may sound a bit intimidating at first but bear with us and you'll see that recursive functions are easy to understand.

In general, every recursive function has two main components: a base case and a recursive step.

Base cases are the smallest instances of the problem. Also a break, a case that will return a value and will get out of the recursion. In terms of factorial functions, the base case is when we return the final element of the factorial, which is 1.

Without a base case or with an incorrect base case, your recursive function can run infinitely, causing an overflow.

Recursive steps - as the name implies- are the recursive part of the function, where the whole problem is transformed into something smaller. If the recursive step fails to shrink the problem, then again recursion can run infinitely.

Consider the recurring part of the factorials:

• 5! is 5 * 4 * 3 * 2 * 1.

But we also know that:

• 4 * 3 * 2 * 1 is 4!.

In other words 5! is 5 * 4!, and 4! is 4 * 3! and so on.

So we can say that n! = n * (n-1)!. This will be the recursive step of our factorial!

A factorial recursion ends when it hits 1. This will be our base case. We will return 1 if n is 1 or less, covering the zero input.

Let's take a look at our recursive factorial function:

def get_factorial_recursively(n):
    if n <= 1:
        return 1
    else:
        return n * get_factorial_recursively(n-1)

As you see the if block embodies our base case, while the else block covers the recursive step.

Let's test our function:

inp = input("Enter a number: ")
inp = int(inp)

print(f"The result is: {get_factorial_recursively(inp)}")

We will enter 3 as input this time:

Enter a number:3
The result is: 6

We get the same result. But this time, what goes under the hood is rather interesting:

You see, when we enter the input, the function will check with the if block, and since 3 is greater than 1, it will skip to the else block. In this block, we see the line return n * get_factorial_recursively(n-1).

We know the current value of n for the moment, it's 3, but get_factorial_recursively(n-1) is still to be calculated.

Then the program calls the same function once more, but this time our function takes 2 as the parameter. It checks the if block and skips to the else block and again encounters with the last line. Now, the current value of the n is 2 but the program still must calculate the get_factorial_recursively(n-1).

So it calls the function once again, but this time the if block, or rather, the base class succeeds to return 1 and breaks out from the recursion.

Following the same pattern to upwards, it returns each function result, multiplying the current result with the previous n and returning it for the previous function call. In other words, our program first gets to the bottom of the factorial (which is 1), then builds its way up, while multiplying on each step.

Also removing the function from the call stack one by one, up until the final result of the n * (n-1) is returned.

This is generally how recursive functions work. Some more complicated problems may require deeper recursions with more than one base case or more than one recursive step. But for now, this simple recursion is good enough to solve our factorial problem!

Introduction

Dijkstra's algorithm is an algorithm which finds the shortest paths between nodes in a graph. It was designed by a Dutch computer scientist Edsger Wybe Dijkstra in 1956, when he thought about how he might calculate the shortest route from Rotterdam to Groningen. It was published three years later.

In computer science (as well as in our everyday life), there are a lot of problems that require finding the shortest path between two points. We encounter problems such as:

• Finding the shortest path from our house to our school or workplace

• Finding the quickest way to get to a gas station while traveling

• Finding a list of friends that a particular user on social network may know

These are just a few of the many "shortest path problems" we see daily. Dijkstra's algorithm is one of the most well known shortest path algorithms because of it's efficiency and simplicity.

Graphs and Types of Graphs

Dijkstra's algorithm works on undirected, connected, weighted graphs. Before we get into it, let's explain what an undirected, connected, and weighed graph actually is.

A graph is a data structure represented by two things:

• Vertices: Groups of certain objects or data (also known as a "node")

• Edges: Links that connect those groups of objects or data

Let's explain this with an example: We want to represent a country with a graph. That country is made out of cities of different sizes and characteristics. Those cities would be represented by vertices. Between some of those cities, there are roads that connect them. Those roads would be represented by edges.

One more example of a graph can be a circle route of a train: the train stations are represented by vertices, and the rails between them are represented by the edges of a graph.

A graph can even be as abstract as a representation of human relationships: We can represent each person in a group of people as vertices in a graph, and if they know each other, we connect them with an edge.

Graphs can be divided based on the types of their edges or based on the number of components that represent them.

When it comes to their edges, graphs can be:

• Directed

• Undirected

A directed graph is a graph in which the edges have orientations. A second example mentioned above is an example of a directed graph: the train goes from one station to the other, but it can't go in reverse.

An undirected graph is a graph in which the edges do not have orientations (therefore, all edges in an undirected graph are considered to be bidirectional). An example of an undirected graph can be the third example mentioned above: It's impossible for person A to know person B without person B knowing the person A back.

Another division by the edges in a graph can be:

• Weighted

• Unweighted

A weighted graph is a graph whose edges have a certain numerical value joined to them: their weight. For example, if we knew the lengths of every road between each pair of cities in a country, we could assign them to the edges in a graph representation of a country and create a weighted graph. i.e. the weigth or "cost" of an edge is the distance between the cities.

An unweighted graph is a graph whose edges don't have weights, like the forementioned graph of relationships between people - we can't assign a numerical value to "knowing a person"!

Based on the number of components that represent them, graphs can be:

• Connected

• Disconnected

A connected graph is a graph that only consists of one component - every vertex inside of it has a path to every other vertex. If we were at a party, and every person there knew the host, that would be represented with a connected graph - everyone could meet anyone they want via the host.

A disconnected graph is a graph that consists of more than one component. Using the same example, if somehow an outsider who doesn't know anyone ended up at the party, the graph of all people at the party and their relationships, it would now be disconnected, because there is one vertex with no edges to connect it to the other vertices present.

Dijkstra's Algorithm

The original Dijkstra's algorithm finds the shortest path between two nodes in a graph. Another, more common variation of this algorithm finds the shortest path between the first vertex and all of the other vertices in a graph. In this article, we will focus on this variation.

We will now go over this algorithm step by step:

1. First, we will create a set of visited vertices, to keep track of all of the vertices that have been assigned their correct shortest path.

   We will also need to set "costs" of all vertices in the graph (lengths of the current shortest path that leads to it). All of the costs will be set to 'infinity' at the begining, to make sure that every other cost we may compare it to would be smaller than the starting one. The only exception is the cost of the first, starting vertex - this vertex will have a cost of 0, because it has no path to itself.

2. As long as there are vertices without the shortest path assigned to them, we do the following:

   • We pick a vertex with the shortest current cost, visit it, and add it to the visited vertices set

   • We update the costs of all its adjacent vertices that are not visited yet. We do this by comparing its current (old) cost, and the sum of the parent's cost and the edge between the parent (current node) and the adjacent node in question.

Let's explain this a bit better using an example:

Let's say the vertex 0 is our starting point. We are going to set the initial costs of vertices in this graph like this:

We pick the vertex with a minimum cost - that vertex is 0. We will mark it as visited and add it to our set of visited vertices. The visited nodes will be marked with green color in the images:

Then, we will update the cost of adjacent vertices (1 and 6).

Since 0 + 4 < infinity and 0 + 7 < infinity, the new costs will be the following (the numbers in bold will be visited vertices):

Now we visit the next smallest cost node, which is 1.

We mark it as visited, and then update the adjacent vertices: 2, 6, and 7:

• Since 4 + 9 < infinity, new cost of vertex 2 will be 13

• Since 4 + 11 > 7, the cost of vertex 6 will remain 7

• Since 4 + 20 < infinity, new cost of vertex 7 will be 24

These are our new costs:

The next vertex we're going to visit is vertex 6. We mark it as visited and update its adjacent vertices' costs:

Since 7 + 1 < 24, the new cost for vertex 7 will be 8.

These are our new costs:

The next vertex we are going to visit is vertex 7:

Now we're going to update the adjacent vertices: vertices 4 and 8.

• Since 8 + 1 < infinity, the new cost of vertex 4 is 9

• Since 8 + 3 < infinity, the new cost of vertex 8 is 11

These are the new costs:

The next vertex we'll visit is vertex 4:

Free eBook: Git Essentials

Check out our hands-on, practical guide to learning Git, with best-practices, industry-accepted standards, and included cheat sheet. Stop Googling Git commands and actually learn it!Download the eBook

• Since 9 + 2 < 13, the new cost of vertex 2 is 11

• Since 9 + 10 < infinity, the new cost of vertex 3 is 19

• Since 9 + 15 < infinity, the new cost of vertex 5 is 24

• Since 9 + 5 > 11, the cost of vertex 8 remains 11

The new costs are:

The next vertex we are going to visit is vertex 2:

The only vertex we're going to update is vertex 3:

• Since 11 + 6 > 19, the cost of vertex 3 stays the same

Therefore, the current costs for all nodes will stay the same as before.

The next vertex we are going to visit is vertex 8:

We are updating the vertex 5:

• Since 11 + 12 < 24, the new cost of vertex 5 is going to be 23

The costs of vertices right now are:

The next vertex we are going to visit is vertex 3.

We are updating the remaining adjacent vertex - vertex 5.

• Since 19 + 5 > 23, the cost of vertex 5 remains the same

The final vertex we are going to visit is vertex 5:

There are no more unvisited vertices that may need an update.

Our final costs represents the shortest paths from node 0 to every other node in the graph:

Implementation

Now that we've gone over an example, let's see how we can implement Dijkstra's algorithm in Python!

Before we start, we are first going to have to import a priority queue:

from queue import PriorityQueue

We will use a priority queue to easily sort the vertices we haven't visited yet, which will more easily allow us to choose the one of shortest current cost.

Now, we'll implement a constructor for a class called Graph:

class Graph:

    def __init__(self, num_of_vertices):
        self.v = num_of_vertices
        self.edges = [[-1 for i in range(num_of_vertices)] for j in range(num_of_vertices)]
        self.visited = []

In this simple parametrized constructor, we provided the number of vertices in the graph as an argument, and we initialized three fields:

• v: Represents the number of vertices in the graph

• edges: Represents the list of edges in the form of a matrix. For nodes u and v, self.edges[u][v] = weight of the edge

• visited: A set which will contain the visited vertices

Now, let's define a function which is going to add an edge to a graph:

    def add_edge(self, u, v, weight):
        self.edges[u][v] = weight
        self.edges[v][u] = weight

Now, let's write the function for Dijkstra's algorithm:

    def dijkstra(self, start_vertex):
        D = {v:float('inf') for v in range(self.v)}
        D[start_vertex] = 0

        pq = PriorityQueue()
        pq.put((0, start_vertex))

        while not pq.empty():
            (dist, current_vertex) = pq.get()
            self.visited.append(current_vertex)

            for neighbor in range(self.v):
                if self.edges[current_vertex][neighbor] != -1:
                    distance = self.edges[current_vertex][neighbor]
                    if neighbor not in self.visited:
                        old_cost = D[neighbor]
                        new_cost = D[current_vertex] + distance
                        if new_cost < old_cost:
                            pq.put((new_cost, neighbor))
                            D[neighbor] = new_cost
        return D

In this code, we first created a list D of the size v. The entire list is initialized to infinity. This is going to be a list where we keep the shortest paths from start_vertex to all of the other nodes.

We set the value of the start vertex to 0, since that is its distance from itself.

Then, we initialize a priority queue, which we will use to quickly sort the vertices from the least to most distant. We put the start vertex in the priority queue.

Now, for each vertex in the priority queue, we will first mark them as visited, and then we will iterate through their neighbors.

If the neighbor is not visited, we will compare its old cost and its new cost.

The old cost is the current value of the shortest path from the start vertex to the neighbor, while the new cost is the value of the sum of the shortest path from the start vertex to the current vertex and the distance between the current vertex and the neighbor.

If the new cost is lower than the old cost, we put the neighbor and its cost to the priority queue, and update the list where we keep the shortest paths accordingly.

Finally, after all of the vertices are visited and the priority queue is empty, we return the list D. Our function is done!

Let's put the graph we used in the example above as the input of our implemented algorithm:

from .all_factors import *
from .count_islands import *
from .pacific_atlantic import *
from .sudoku_solver import *
from .walls_and_gates import *
from .maze_search import *

"""
Numbers can be regarded as product of its factors. For example,
8 = 2 x 2 x 2;
  = 2 x 4.


Write a function that takes an integer n and return all possible combinations
of its factors.Numbers can be regarded as product of its factors. For example,
8 = 2 x 2 x 2;
  = 2 x 4.

Examples:
input: 1
output:
[]


input: 37
output:
[]

input: 32
output:
[
  [2, 16],
  [2, 2, 8],
  [2, 2, 2, 4],
  [2, 2, 2, 2, 2],
"""


def get_factors(n):
    """[summary]
    
    Arguments:
        n {[int]} -- [to analysed number]
    
    Returns:
        [list of lists] -- [all factors of the number n]
    """

    def factor(n, i, combi, res):
        """[summary]
        helper function

        Arguments:
            n {[int]} -- [number]
            i {[int]} -- [to tested divisor]
            combi {[list]} -- [catch divisors]
            res {[list]} -- [all factors of the number n]
        
        Returns:
            [list] -- [res]
        """

        while i * i <= n:
            if n % i == 0:
                res += (combi + [i, int(n / i)],)
                factor(n / i, i, combi + [i], res)
            i += 1
        return res

    return factor(n, 2, [], [])


def get_factors_iterative1(n):
    """[summary]
    Computes all factors of n.
    Translated the function get_factors(...) in
    a call-stack modell.

    Arguments:
        n {[int]} -- [to analysed number]
    
    Returns:
        [list of lists] -- [all factors]
    """

    todo, res = [(n, 2, [])], []
    while todo:
        n, i, combi = todo.pop()
        while i * i <= n:
            if n % i == 0:
                res += (combi + [i, n // i],)
                todo.append((n // i, i, combi + [i])),
            i += 1
    return res


def get_factors_iterative2(n):
    """[summary]
    analog as above

    Arguments:
        n {[int]} -- [description]
    
    Returns:
        [list of lists] -- [all factors of n]
    """

    ans, stack, x = [], [], 2
    while True:
        if x > n // x:
            if not stack:
                return ans
            ans.append(stack + [n])
            x = stack.pop()
            n *= x
            x += 1
        elif n % x == 0:
            stack.append(x)
            n //= x
        else:
            x += 1

"""
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.

Example 1:

11110
11010
11000
00000
Answer: 1

Example 2:

11000
11000
00100
00011
Answer: 3
"""


def num_islands(grid):
    count = 0
    for i in range(len(grid)):
        for j, col in enumerate(grid[i]):
            if col == 1:
                dfs(grid, i, j)
                count += 1
    return count


def dfs(grid, i, j):
    if (i < 0 or i >= len(grid)) or (j < 0 or j >= len(grid[0])):
        return
    if grid[i][j] != 1:
        return
    grid[i][j] = 0
    dfs(grid, i + 1, j)
    dfs(grid, i - 1, j)
    dfs(grid, i, j + 1)
    dfs(grid, i, j - 1)

"""
Find shortest path from top left column to the right lowest column using DFS.
only step on the columns whose value is 1
if there is no path, it returns -1
(The first column(top left column) is not included in the answer.)

Ex 1)
If maze is
[[1,0,1,1,1,1],
 [1,0,1,0,1,0],
 [1,0,1,0,1,1],
 [1,1,1,0,1,1]],
the answer is: 14

Ex 2)
If maze is
[[1,0,0],
 [0,1,1],
 [0,1,1]],
the answer is: -1
"""


def find_path(maze):
    cnt = dfs(maze, 0, 0, 0, -1)
    return cnt


def dfs(maze, i, j, depth, cnt):
    directions = [(0, -1), (0, 1), (-1, 0), (1, 0)]

    row = len(maze)
    col = len(maze[0])

    if i == row - 1 and j == col - 1:
        if cnt == -1:
            cnt = depth
        else:
            if cnt > depth:
                cnt = depth
        return cnt

    maze[i][j] = 0

    for k in range(len(directions)):
        nx_i = i + directions[k][0]
        nx_j = j + directions[k][1]

        if nx_i >= 0 and nx_i < row and nx_j >= 0 and nx_j < col:
            if maze[nx_i][nx_j] == 1:
                cnt = dfs(maze, nx_i, nx_j, depth + 1, cnt)

    maze[i][j] = 1

    return cnt

# Given an m x n matrix of non-negative integers representing
# the height of each unit cell in a continent,
# the "Pacific ocean" touches the left and top edges of the matrix
# and the "Atlantic ocean" touches the right and bottom edges.

# Water can only flow in four directions (up, down, left, or right)
# from a cell to another one with height equal or lower.

# Find the list of grid coordinates where water can flow to both the
# Pacific and Atlantic ocean.

# Note:
# The order of returned grid coordinates does not matter.
# Both m and n are less than 150.
# Example:

# Given the following 5x5 matrix:

# Pacific ~   ~   ~   ~   ~
# ~  1   2   2   3  (5) *
# ~  3   2   3  (4) (4) *
# ~  2   4  (5)  3   1  *
# ~ (6) (7)  1   4   5  *
# ~ (5)  1   1   2   4  *
# *   *   *   *   * Atlantic

# Return:

# [[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]]
# (positions with parentheses in above matrix).


def pacific_atlantic(matrix):
    """
    :type matrix: List[List[int]]
    :rtype: List[List[int]]
    """
    n = len(matrix)
    if not n:
        return []
    m = len(matrix[0])
    if not m:
        return []
    res = []
    atlantic = [[False for _ in range(n)] for _ in range(m)]
    pacific = [[False for _ in range(n)] for _ in range(m)]
    for i in range(n):
        dfs(pacific, matrix, float("-inf"), i, 0)
        dfs(atlantic, matrix, float("-inf"), i, m - 1)
    for i in range(m):
        dfs(pacific, matrix, float("-inf"), 0, i)
        dfs(atlantic, matrix, float("-inf"), n - 1, i)
    for i in range(n):
        for j in range(m):
            if pacific[i][j] and atlantic[i][j]:
                res.append([i, j])
    return res


def dfs(grid, matrix, height, i, j):
    if i < 0 or i >= len(matrix) or j < 0 or j >= len(matrix[0]):
        return
    if grid[i][j] or matrix[i][j] < height:
        return
    grid[i][j] = True
    dfs(grid, matrix, matrix[i][j], i - 1, j)
    dfs(grid, matrix, matrix[i][j], i + 1, j)
    dfs(grid, matrix, matrix[i][j], i, j - 1)
    dfs(grid, matrix, matrix[i][j], i, j + 1)

"""
It's similar to how human solve Sudoku.

create a hash table (dictionary) val to store possible values in every location.
Each time, start from the location with fewest possible values, choose one value
from it and then update the board and possible values at other locations.
If this update is valid, keep solving (DFS). If this update is invalid (leaving
zero possible values at some locations) or this value doesn't lead to the
solution, undo the updates and then choose the next value.
Since we calculated val at the beginning and start filling the board from the
location with fewest possible values, the amount of calculation and thus the
runtime can be significantly reduced:


The run time is 48-68 ms on LeetCode OJ, which seems to be among the fastest
python solutions here.


The PossibleVals function may be further simplified/optimized, but it works just
fine for now. (it would look less lengthy if we are allowed to use numpy array
for the board lol).
"""


class Sudoku:
    def __init__(self, board, row, col):
        self.board = board
        self.row = row
        self.col = col
        self.val = self.possible_values()

    def possible_values(self):
        a = "123456789"
        d, val = {}, {}
        for i in range(self.row):
            for j in range(self.col):
                ele = self.board[i][j]
                if ele != ".":
                    d[("r", i)] = d.get(("r", i), []) + [ele]
                    d[("c", j)] = d.get(("c", j), []) + [ele]
                    d[(i // 3, j // 3)] = d.get((i // 3, j // 3), []) + [ele]
                else:
                    val[(i, j)] = []
        for (i, j) in val.keys():
            inval = (
                d.get(("r", i), []) + d.get(("c", j), []) + d.get((i / 3, j / 3), [])
            )
            val[(i, j)] = [n for n in a if n not in inval]
        return val

    def solve(self):
        if len(self.val) == 0:
            return True
        kee = min(self.val.keys(), key=lambda x: len(self.val[x]))
        nums = self.val[kee]
        for n in nums:
            update = {kee: self.val[kee]}
            if self.valid_one(n, kee, update):  # valid choice
                if self.solve():  # keep solving
                    return True
            self.undo(kee, update)  # invalid choice or didn't solve it => undo
        return False

    def valid_one(self, n, kee, update):
        self.board[kee[0]][kee[1]] = n
        del self.val[kee]
        i, j = kee
        for ind in self.val.keys():
            if n in self.val[ind]:
                if (
                    ind[0] == i
                    or ind[1] == j
                    or (ind[0] / 3, ind[1] / 3) == (i / 3, j / 3)
                ):
                    update[ind] = n
                    self.val[ind].remove(n)
                    if len(self.val[ind]) == 0:
                        return False
        return True

    def undo(self, kee, update):
        self.board[kee[0]][kee[1]] = "."
        for k in update:
            if k not in self.val:
                self.val[k] = update[k]
            else:
                self.val[k].append(update[k])
        return None

    def __str__(self):
        """[summary]
        Generates a board representation as string.

        Returns:
            [str] -- [board representation]
        """

        resp = ""
        for i in range(self.row):
            for j in range(self.col):
                resp += " {0} ".format(self.board[i][j])
            resp += "\n"
        return resp

"""
You are given a m x n 2D grid initialized with these three possible values:
    -1: A wall or an obstacle.
    0: A gate.
    INF: Infinity means an empty room. We use the value 2^31 - 1 = 2147483647 to represent INF 
         as you may assume that the distance to a gate is less than 2147483647.
Fill the empty room with distance to its nearest gate.
If it is impossible to reach a gate, it should be filled with INF.

For example, given the 2D grid:
    INF -1  0   INF
    INF INF INF -1
    INF -1  INF -1
    0   -1  INF INF
After running your function, the 2D grid should be:
    3   -1  0   1
    2   2   1   -1
    1   -1  2   -1
    0   -1  3   4
"""


def walls_and_gates(rooms):
    for i in range(len(rooms)):
        for j in range(len(rooms[0])):
            if rooms[i][j] == 0:
                dfs(rooms, i, j, 0)


def dfs(rooms, i, j, depth):
    if (i < 0 or i >= len(rooms)) or (j < 0 or j >= len(rooms[0])):
        return  # out of bounds
    if rooms[i][j] < depth:
        return  # crossed
    rooms[i][j] = depth
    dfs(rooms, i + 1, j, depth + 1)
    dfs(rooms, i - 1, j, depth + 1)
    dfs(rooms, i, j + 1, depth + 1)
    dfs(rooms, i, j - 1, depth + 1)

Introduction

Originating from mathematics, graphs are now widely used data structures in Computer Science. One of the first problems we encounter when constructing any algorithm regarding Graph processing or traversal, is how we represent the graph and then, how to traverse that representation.

Graph traversal is not a trivial problem, and given the difficulty of the task - many algorithms have been devised for efficient (yet not perfect) graph traversal.

In this guide, we'll take a look at one of the two fundamental and simplest algorithms for Graph traversal - Depth-First Search (DFS). It's the most commonly used algorithm alongside the related Breadth-First Search (BFS) given their simplicity. After going over the main idea used for DFS, we'll implement it in Python on a Graph representation - an adjacency list.

Depth-First Search - Theory

Depth-First Search (DFS) is an algorithm used to traverse or locate a target node in a graph or tree data structure. It priorities depth and searches along one branch, as far as it can go - until the end of that branch. Once there, it backtracks to the first possible divergence from that branch, and searches until the end of that branch, repeating the process.

Given the nature of the algorithm, you can easily implement it recursively - and you can always implement a recursive algorithm iteratively as well:

The start node is the root node for tree data structures, while with more generic graphs - it can be any node.

DFS is widely-used as a part of many other algorithms that resolve graph-represented problems. From cycle searches, path finding, topological sorting, to finding articulation points and strongly connected components. The reason behind this widespread use of the DFS algorithm lays in its overall simplicity and easy recursive implementation.

The DFS Algorithm

The DFS algorithm is pretty simple and consists of the following steps:

1. Mark the current node as visited.

2. Traverse the neighbouring nodes that aren't visited and recursively call the DFS function for that node.

The algorithm stops either when the target node is found, or the whole graph has been traversed (all nodes are visited).

Since graphs can have cycles, we'll need a system to avoid them so we don't fall into infinity loops. That's why we "mark" every node we pass as visited by adding them to a Set containing only unique entries.

By marking nodes as "visited", if we ever encounter that node again - we're in a loop! Endless computational power and time has been wasted on loops, lost in the aether.

Pseudocode

Given these steps, we can summarize DFS in pseudocode:

DFS(G, u):
    # Input processing
    u.visited = true
    for each v in G.adj[u]:
        if !v.visited:
            DFS(G, v)
            # Output processing

Input and output processing are performed depending on the purpose of the graph search. Our input processing for DFS will be checking if the current node is equal to the target node.

With this view, you can really start to appreciate just how simple yet useful this algorithm is.

Depth-First Search - Implementation

Depth-First Search implementation is usually recursive in code given how natural of a pair that is, but it can also be easily implemented non-recursively. We'll be using the recursive method as it's simpler and more fitting:

def dfs(adj_list, start, target, path, visited = set()):
    path.append(start)
    visited.add(start)
    if start == target:
        return path
    for neighbour in adj_list[start]:
        if neighbour not in visited:
            result = dfs(adj_list, neighbour, target, path, visited)
            if result is not None:
                return result
	  path.pop()
    return None

We added the start node to the beginning of our traversal path and marked it as visited by adding it to a set of visited nodes. Then, we traversed the start node's neighbours that aren't already visited and called the function recursively for each of them. Recursive calls result in going as deep as we can along one "branch".

We saved the recursion result in a variable - in the case it returns None that means that the target node was not found in this branch and that we should try another. If the recursive call, in fact, does not return None, that means we have found our target node and we return the traversal path as result.

In the end, if we find ourselves outside of the for loop, it means that all the neighbour branches of the current node have been visited and none of them lead to our target node. So, we remove the current node from the path, and return None as result.

Running DFS

Let's illustrate how the code works through an example. We'll be using a Python dictionary to represent the graph as an adjacency list. Here's the graph we'll be using in the following example:

adj_list = {
    0 : [1, 2],
    1 : [0, 3],
    2 : [0, 3],
    3 : [1, 2, 4],
    4 : [3]
}

An adjacency list is a type of graph representation in code, it consists of keys which represent each node, and a list of values for each of them containing nodes that are connected to the key node with an edge.

Using a dictionary for this is the easiest way to quickly represent a graph in Python, though you could also define your own Node classes and add them to a Graph instance.

Here's what our example graph looks like:

We're searching for a path from node 0 to node 3, if it exists, the path will be saved into a set of visited nodes, called traversal_path so we can reconstruct it for printing:

traversal_path = []

traversal_path = dfs(adj_list, 0, 3, traversal_path)
print(traversal_path)

The steps our algorithm will take are as follows:

• Add node 0 to the traversal path and mark it as visited. Check if node 0 is equal to target node 3, since it's not, continue and traverse it's neighbours (1 and 2).

• Is neighbour 1 visited? - No. Then, the algorithm calls the function recursively for that node.

  • Recursive call for node 1: Add node 1 to the traversal path and mark it as visited, . Is 1 equal to our target node 3? - No, continue and traverse it's neighbours (0 and 3).

  • Is neighbour 0 visited? - Yes, move onto the next one.

  • Is neighbour 3 visited? - No, call the function recursively for this node.

    • Recursive call for node 3: Add node 3 to the traversal path and mark it as visited. Is 3 equal to our target node 3? - Yes, target node has been found, return the traversal path.

The algorithm stops and our program prints out the resulting traversal path from node 0 to node 3:

[0, 1, 3]

After the search, the marked nodes on the graph represent the path we took to get to the target node:

In case there was no path between the start and target node, the traversal path would be empty.

Note: Graphs can also be disconnected, meaning that there are at least two nodes that cannot be connected by a path. In this case, DFS would ignore the nodes that it can't get to:

For example in this graph, if we were to start DFS from node 0 to node 4, there would be no such path because it has no way of getting to the target node.

Conclusion

In this article we've explained the theory behind the Depth-First Search algorithm. We've depicted the widely-used recursive Python implementation, and went over the borderline cases for which the algorithm will not work properly.

Data Structures & Algorithms Resource List Part 1

Guess the author of the following quotes:

Data Structures & Algorithms Resource List Part 1

Guess the author of the following quotes:

Talk is cheap. Show me the code.

Software is like sex: it’s better when it’s free.

Microsoft isn’t evil, they just make really crappy operating systems.

Here’s some more:

• The Framework for Learning Algorithms and intense problem solving exercises

• Algs4: Recommended book for Learning Algorithms and Data Structures

• An analysis of Dynamic Programming

• Dynamic Programming Q&A — What is Optimal Substructure

• The Framework for Backtracking Algorithm

• Binary Search in Detail: I wrote a Poem

• The Sliding Window Technique

• Difference Between Process and Thread in Linux

• Some Good Online Practice Platforms

• Dynamic Programming in Details

• Dynamic Programming Q&A — What is Optimal Substructure

• Classic DP: Longest Common Subsequence

• Classic DP: Edit Distance

• Classic DP: Super Egg

• Classic DP: Super Egg (Advanced Solution)

• The Strategies of Subsequence Problem

• Classic DP: Game Problems

• Greedy: Interval Scheduling

• KMP Algorithm In Detail

• A solution to all Buy Time to Buy and Sell Stock Problems

• A solution to all House Robber Problems

• 4 Keys Keyboard

• Regular Expression

• Longest Increasing Subsequence

• The Framework for Learning Algorithms and intense problem solving exercises

• Algs4: Recommended book for Learning Algorithms and Data Structures

• Binary Heap and Priority Queue

• LRU Cache Strategy in Detail

• Collections of Binary Search Operations

• Special Data Structure: Monotonic Stack

• Special Data Structure: Monotonic Stack

• Design Twitter

• Reverse Part of Linked List via Recursion

• Queue Implement Stack/Stack implement Queue

• My Way to Learn Algorithm

• The Framework of Backtracking Algorithm

• Binary Search in Detail

• Backtracking Solve Subset/Permutation/Combination

• Diving into the technical parts of Double Pointers

• Sliding Window Technique

• The Core Concept of TwoSum Problems

• Common Bit Manipulations

• Breaking down a Complicated Problem: Implement a Calculator

• Pancake Sorting Algorithm

• Prefix Sum: Intro and Concept

• String Multiplication

• FloodFill Algorithm in Detail

• Interval Scheduling: Interval Merging

• Interval Scheduling: Intersections of Intervals

• Russian Doll Envelopes Problem

• A collection of counter-intuitive Probability Problems

• Shuffle Algorithm

• Recursion In Detail

• How to Implement LRU Cache

• How to Find Prime Number Efficiently

• How to Calculate Minimium Edit Distance

• How to use Binary Search

• How to efficiently solve Trapping Rain Water Problem

• How to Remove Duplicates From Sorted Array

• How to Find Longest Palindromic Substring

• How to Reverse Linked List in K Group

• How to Check the Validation of Parenthesis

• How to Find Missing Element

• How to Find Duplicates and Missing Elements

• How to Check Palindromic LinkedList

• How to Pick Elements From an Infinite Arbitrary Sequence

• How to Schedule Seats for Students

• Union-Find Algorithm in Detail

• Union-Find Application

• Problems that can be solved in one line

• Find Subsequence With Binary Search

• Difference Between Process and Thread in Linux

• You Must Know About Linux Shell

• You Must Know About Cookie and Session

• Cryptology Algorithm

• Some Good Online Practice Platforms

Algorithms:

• 100 days of algorithms

• Algorithms — Solved algorithms and data structures problems in many languages.

• Algorithms by Jeff Erickson (Code) (HN)

• Top algos/DS to learn

• Some neat algorithms

• Mathematical Proof of Algorithm Correctness and Efficiency (2019)

• Algorithm Visualizer — Interactive online platform that visualizes algorithms from code.

• Algorithms for Optimization book

• Collaborative book on algorithms (Code)

• Algorithms in C by Robert Sedgewick

• Algorithm Design Manual

• MIT Introduction to Algorithms course (2011)

• How to implement an algorithm from a scientific paper (2012)

• Quadsort — Stable non-recursive merge sort named quadsort.

• System design algorithms — Algorithms you should know before system design.

• Algorithms Design book

• Think Complexity

• All Algorithms implemented in Rust

• Solutions to Introduction to Algorithms book (Code)

• Maze Algorithms (2011) (HN)

• Algorithmic Design Paradigms book (Code)

• Words and buttons Online Blog (Code)

• Algorithms animated

• Cache Oblivious Algorithms (2020) (HN)

• You could have invented fractional cascading (2012)

• Guide to learning algorithms through LeetCode (Code) (HN)

• How hard is unshuffling a string?

• Optimization Algorithms on Matrix Manifolds

• Problem Solving with Algorithms and Data Structures (HN) (PDF)

• Algorithms implemented in Python

• Algorithms implemented in JavaScript

• Algorithms & Data Structures in Java

• Wolfsort — Stable adaptive hybrid radix / merge sort.

• Evolutionary Computation Bestiary — Bestiary of evolutionary, swarm and other metaphor-based algorithms.

• Elements of Programming book — Decomposing programs into a system of algorithmic components. (Review) (HN) (Lobsters)

• Competitive Programming Algorithms

• CPP/C — C/C++ algorithms/DS problems.

• How to design an algorithm (2018)

• CSE 373 — Introduction to Algorithms, by Steven Skiena (2020)

• Computer Algorithms II course (2020)

• Improving Binary Search by Guessing (2019)

• The case for a learned sorting algorithm (2020) (HN)

• Elementary Algorithms — Introduces elementary algorithms and data structures. Includes side-by-side comparisons of purely functional realization and their imperative counterpart.

• Combinatorics Algorithms for Coding Interviews (2018)

• Algorithms written in different programming languages (Web)

• Solving the Sequence Alignment problem in Python (2020)

• The Sound of Sorting — Visualization and “Audibilization” of Sorting Algorithms. (Web)

• Miniselect: Practical and Generic Selection Algorithms (2020)

• The Slowest Quicksort (2019)

• Functional Algorithm Design (2020)

• Algorithms To Live By — Book Notes

• Numerical Algorithms (2015)

• Using approximate nearest neighbor search in real world applications (2020)

• In search of the fastest concurrent Union-Find algorithm (2019)

• Computer Science 521 Advanced Algorithm Design

• Data Structures and Algorithms implementation in Go

• Which algorithms/data structures should I “recognize” and know by name?

• Dictionary of Algorithms and Data Structures

• Phil’s Data Structure Zoo

• The Periodic Table of Data Structures (HN)

• Data Structure Visualizations (HN)

• Data structures to name-drop when you want to sound smart in an interview

• On lists, cache, algorithms, and microarchitecture (2019)

• Topics in Advanced Data Structures (2019) (HN)

• CS166 Advanced DS Course (2019)

• Advanced Data Structures (2017) (HN)

• Write a hash table in C

• Python Data Structures and Algorithms

• HAMTs from Scratch (2018)

• JavaScript Data Structures and Algorithms

• Implementing a Key-Value Store series

• Open Data Structures — Provide a high-quality open content data structures textbook that is both mathematically rigorous and provides complete implementations. (Code)

• A new analysis of the false positive rate of a Bloom filter (2009)

• Ideal Hash Trees

• RRB-Trees: Efficient Immutable Vectors

• Some data structures and algorithms written in OCaml

• Let’s Invent B(+)-Trees (HN)

• Anna — Low-latency, cloud-native KVS.

• Persistent data structures thanks to recursive type aliases (2019)

• Log-Structured Merge-Trees (2020)

• Bloom Filters for the Perplexed (2017)

• Understanding Bloom Filters (2020)

• Dense vs. Sparse Indexes (2020)

• Data Structures and Algorithms Problems

• Data Structures & Algorithms I Actually Used Working at Tech Companies (2020) (Lobsters) (HN)

• Let’s implement a Bloom Filter (2020) (HN)

• Data Structures Part 1: Bulk Data (2019) (Lobsters)

• Data Structures Explained

• Introduction to Cache-Oblivious Data Structures (2018)

• The Daily Coding newsletter — Master JavaScript and Data Structures.

• Lectures Note for Data Structures and Algorithms (2019)

• Mechanically Deriving Binary Tree Iterators with Continuation Defunctionalization (2020)

• Segment Tree data structure

• Structure of a binary state tree (2020)

• Introductory data structures and algorithms

• Applying Textbook Data Structures for Real Life Wins (2020) (HN)

• Michael Scott — Nonblocking data structures lectures (2020) — Nonblocking concurrent data structures are an increasingly valuable tool for shared-memory parallel programming.

• Scal — High-performance multicore-scalable data structures and benchmarks. (Web)

• Hyperbolic embedding implementations

• Morphisms of Computational Constructs — Visual catalogue + story of morphisms displayed across computational structures.

• What is key-value store? (build-your-own-x) (2020)

• Lesser Known but Useful Data Structures

• Using Bloom filters to efficiently synchronize hash graphs (2020)

• Bloom Filters by Example (Code)

• Binary Decision Diagrams (HN)

• 3 Steps to Designing Better Data Structures (2020)

• Sparse Matrices (2019) (HN)

• Algorithms & Data Structures in C++

• Fancy Tree Traversals (2019)

• The Robson Tree Traversal (2019)

• Data structures and program structures

• cdb — Fast, reliable, simple package for creating and reading constant databases.

• PGM-index — Learned indexes that match B-tree performance with 83x less space. (HN) (Code)

• Structural and pure attributes

• Cache-Tries: O(1) Concurrent Lock-Free Hash Tries (2018)