Manipulating Lists in Python 3 for Competitive Programming

Introduction

A couple of months ago, I was preparing for the ECPC Qualifications and I knew that we can't use any external libraries like Numpy in the competition, so I tried to figure out some alternative methods to manipulate lists, and today, I want to share it with you!

We will discuss four techniques:

• Performing Multiple Swaps on Rows and columns Efficiently

• Initializing a 2D Matrix

• Deleting an Element from a List That You’re Iterating Upon

• Getting the Transpose of a Matrix

Performing Multiple Swaps on Rows and columns Efficiently

Steps:

• Store the matrix in a list of lists

• Create two dictionaries, one for the rows (that has size equal to the number of rows), and another for the columns (has size equal to the number of columns)

• Both keys and values are initialized to the initial indexing of the matrix

• The keys for those dictionaries are the original value for the indices of the matrix, the values are the indices after all swap operations

• We will access matrix elements using those dictionaries only

Sample Code:

matrix = [[1, 2, 3], [4, 5, 6]]

col = {i : i for i in range (3)} # creating columns map
row = {i : i for i in range (2)} # creating rows map

# I will perform three swaps, but you could extend to way more than that!
col[0], col[1] = col[1], col[0] # first swap
row[0], row[1] = row[1], row[0] # second swap
col[2], col[0] = col[0], col[2] # third swap

for i in matrix : # printing the original matrix before the swaps
    print (i)
'''
output:
[1, 2, 3]
[4, 5, 6]
'''

# printing the matrix after the swaps
for i in range (2) : # iterate through the whole matrix
    for j in range (3) :
        print (matrix [row[i]][col[j]], end = ' ') # accessing the matrix using the two maps
    print ()
'''
output:
6 4 5 
3 1 2 
'''

Initializing a 2D Matrix

It seems like an easy topic, but there is a trick that a lot of people don’t get at the first glance

I will show you the wrong way that many got mistaken over, then I will show you the correct method of doing it

The Wrong Method

• This method will create four references, all to the same 1-D list

• If you changed any element in the first 1-D list, it will affect the rest of the lists (will affect all elements with the same index as in the first list)

• This is because the reference of the first list is the same reference to the rest of the list

Sample Code:

# The WRONG way
# DO NOT DO THIS!
matrix = [[0] * 3] * 4 # initialization
matrix[0][0] = 1 # change
for i in matrix :
    print (i)
'''
output:

[1, 0, 0]
[1, 0, 0]
[1, 0, 0]
[1, 0, 0]
[1, 0, 0]
'''

The Right Method

• We will use a for loop, It's equivalent to writing multiple statements
• This will create multiple references, one for each row (1-D list)

Sample Code:

matrix = [[0] * 3 for _ in range (4)] # initialization
matrix[0][0] = 1 # change
for i in matrix :
    print (i)
'''
output:

[1, 0, 0]
[0, 0, 0]
[0, 0, 0]
[0, 0, 0]
'''

Deleting an Element from a List That You’re Iterating Upon

• If we deleted some elements from a list while iterating over it, we will get the following error:

IndexError: list index out of range

Steps of deleting elements from a list while iterating over it correctly:

• Let's call the array that we want to delete elements from (arr)

• Make a new boolean array, and we called it (isDeleted)

• If the current element should be deleted, then make the corresponding element in the boolean array = 1

Note that: In the boolean array, the value of one means that the elements should be deleted, value of zero means otherwise

• Make a third array, we called it (LAfterDeletion), that will take the elements from arr that correspond to elements in the boolean array with a value of 0

Sample Code:

L = [1, 2, 3, 5, 66, 7, 8, 4, 23, 12] # making a list

isDeleted = [0] * len (L) # creating the boolean array
LAfterDeletion = [] # create the final array, that will take values after deletion

# Delete the elements that are larger than 5!
for i in range (len (L)) :
    if L[i] > 5 :
        isDeleted[i] = 1
for i in range (len (isDeleted)) :
    if isDeleted[i] == 0:
        LAfterDeletion.append(L[i])
print (LAfterDeletion) # [1, 2, 3, 5, 4]

Getting the Transpose of a Matrix

• The main idea is based on using the zip function

• Zip () function takes multiple iterables and returns a generator that contains a series of tuples, where each tuple contains a series of elements, one from each iterable

• We could cast this generator to a list

Sample Code:

lis = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] # declaring the original list
for i in lis :
    print (i)
'''
output:

[1, 2, 3]
[4, 5, 6]
[7, 8, 9]
'''
lis = list (zip (*lis)) # first rotation (replacing rows with columns)
# *lis is used to unpack the list of lists to multiple lists, equivalent to: lis[0], lis[1], lis[2]
for i in lis :
    print (i)
'''
output:
(1, 4, 7)
(2, 5, 8)
(3, 6, 9)
'''

That's it! I hope you learned from it. Happy coding!