List Comprehensions in Python

Ashish Panchal — Sun, 05 Jul 2020 08:53:09 +0000

List comprehensions provide a way to create lists, where each element will be derived from an operation applied to each member of another sequence or iterable or to create another a subsequence with elements that satisfy particular condition.

Use-case 1: Lets calculate squares of all numbers from 1 to 10

Without List Comprehension:

squares = []

for x in range(10):
    squares.append(x**2)

print squares

With List Comprehension:

List comprehension consists of square brackets containing an expression followed by a one or multiple for loops or if clauses. Now, lets calculate squares using list comprehension

squares = [x**2 for x in range(10)]
print squares

Use-case 2: If the resulting data is a tuple, the expression must be parenthesised.

Example: Lets fetch indices of matching elements from two lists. For example:
first_list = [2, 5, 6]
second_list = [5, 6, 1]
Output : [(1, 0), (2, 1)]

Without List Comprehension:

first_list = [2, 5, 6]
second_list = [5, 6, 1]

result = []

for i in range(len(first_list)):
    for j in range(len(second_list)):
        if first_list[i] == second_list[j]:
            result.append((i, j))

print result

With List Comprehension:

first_list = [2, 5, 6]
second_list = [5, 6, 1]

result = [(i, j) for i in range(len(first_list)) for j in range(len(second_list)) if first_list[i] == second_list[j]]

print result

Use-case 3: Nested list comprehension

Nested list comprehension is a list comprehension within another list comprehension just like nested for loops.

Lets take a popular example of flattening a 2D matrix:

matrix = [[1, 2, 3],
[4, 5, 6],
[7, 8, 9]]

Output: [1, 2, 3, 4, 5, 6, 7, 8, 9]

Without List Comprehension:

matrix = [[1, 2, 3], [4, 5], [6, 7, 8, 9]] 
result = []

for row in matrix:
    for val in row:
        result.append(val)

print result

With List Comprehension:

matrix = [[1, 2, 3], [4, 5], [6, 7, 8, 9]]

result = [val for row in matrix for val in row]

print result

We can use multiple for loops or if clauses to achieve any result but list comprehensions make it very concise and readable.

Happy Coding! 👨‍💻

Flood Fill Algorithm

Ashish Panchal — Sat, 23 May 2020 08:26:27 +0000

Description

Flood fill also known as Seed Fill algorithm helps us to find connected area to a node in multi dimensional array. It is popularly known for its use in bucket fill tool of paint program to fill similarly colored area and also used in games like Minesweeper, Go etc.

Following animation shows how flood fill algorithm fills area connected to a node with similar color.

Algorithm

In order to achieve this the algorithm works as follows:

Input parameters: source_node, color_to_replace, new_color

Step 1: If color_to_replace is equal to new_color then return.
Step 2: Else If color of source_node is not equal to color_to_replace then return.
Step 3: Else set the source_node color to new_color.
Step 4: Recursively start performing flood fill on following nodes:

Left node of the source_node, color_to_replace, new_color
Right node of the source_node, color_to_replace, new_color
Upper node of the source_node, color_to_replace, new_color
Node below to the source_node, color_to_replace, new_color

Step 5: return

Implementation

Let's solve a problem to understand it better.

You're given a image represented as 2D array, row and column of source node and new color. You need to color the source node and all its adjacent node which are similarly colored as source node.

Example 1:
Input: [[1,0,1],[1,1,0],[1,1,1]]
source row = 1, source column = 1 and new color = 2
Output: [[2,0,1],[2,2,0],[2,2,2]]

Example 2:
Input: [[0,0,0],[1,1,0],[1,0,1]]
source row = 1, source column = 1 and new color = 2
Output: [[0,0,0],[2,2,0],[2,0,1]]

Note: Try implementing the algorithm on your own before moving to the solution, it'll surely help 🙂

Solution:

class Solution(object):
    def color_it(self, image, sr, sc, new_color):
        """
        :type image: List[List[int]]
        :type sr: int
        :type sc: int
        :type new_color: int
        :rtype: List[List[int]]
        """
        # Initiate an array to keep the track of visited elements
        # and color of the elements
        self.image = []

        for i in range(len(image)):
            self.image.append([])
            for j in range(len(image[i])):
                # Keep the track of color and if the node is already visited
                value = {"color": image[i][j], "visited": False}
                self.image[i].append(value)

        current_color = image[sr][sc]

        self.flood_fill(image, sr, sc, current_color, new_color)

        for i in range(len(image)):
            for j in range(len(image[i])):
                image[i][j] = self.image[i][j]["color"]
        return image

    def flood_fill(self, image, row, col, current_color, new_color):
        if row < 0 or row >= len(image) or col < 0 or col >= len(image[0]):
            return

        if image[row][col] != current_color:
            return
        elif image[row][col] == current_color and self.image[row][col]["visited"]:
            return
        elif image[row][col] == current_color and not self.image[row][col]["visited"]:
            self.image[row][col]["color"] = new_color
            self.image[row][col]["visited"] = True

        # Recursively call flood_fill for adjacent nodes
        self.flood_fill(image, row + 1, col, current_color, new_color)
        self.flood_fill(image, row - 1, col, current_color, new_color)
        self.flood_fill(image, row, col + 1, current_color, new_color)
        self.flood_fill(image, row, col - 1, current_color, new_color)

Forem: Ashish Panchal

List Comprehensions in Python

Use-case 1: Lets calculate squares of all numbers from 1 to 10

Use-case 2: If the resulting data is a tuple, the expression must be parenthesised.

Use-case 3: Nested list comprehension

Flood Fill Algorithm

Description

Algorithm

Implementation