9/30/25, 2:10 AM DSA-Lecture2-R14
In [1]: from itertools import chain
In [2]: #Creating pascals triangle
answer = []
firstrow = [1]
[Link](firstrow)
print(answer)
n_rows = 5
middle_element = 0
for i in range(1,n_rows):
print(f"row: {i}")
print(f"No of middle elements: {middle_element}")
current_row = []
# add start element 1
current_row.append(1)
# add middle elements
for j in range(1,middle_element+1):
new_element = answer[(i-1)][j] + answer[(i-1)][(j-1)]
current_row.append(new_element)
# add end element 1
current_row.append(1)
[Link](current_row)
print(f"Answer: {answer}")
middle_element+=1
print(f"\n\nFinal answer: {answer}")
[[1]]
row: 1
No of middle elements: 0
Answer: [[1], [1, 1]]
row: 2
No of middle elements: 1
Answer: [[1], [1, 1], [1, 2, 1]]
row: 3
No of middle elements: 2
Answer: [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1]]
row: 4
No of middle elements: 3
Answer: [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]
Final answer: [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]
In [3]: # zigzag conversion
string_ = "PAYPALISHIRING"
# expected output string with n_row = 3 is "PAHNAPLSIIGYIR"
n_rows = 3
def zigzag(string_, n_rows):
if n_rows == 1:
return string_
[Link] 1/4
9/30/25, 2:10 AM DSA-Lecture2-R14
answer = [[] for _ in range(n_rows)] # created [[], [], []]
row_index = 0
turn = -1
for i,letter in enumerate(string_):
print(f"i:{i} letter:{letter} turn:{turn} row_index:{row_index}")
answer[row_index].append(letter)
print(answer)
if row_index==(n_rows-1) or (row_index==0):
turn = -turn
row_index+=turn
return answer
answer = zigzag(string_, n_rows)
print(f"\n\nInput string: {string_} with n_rows:{n_rows}")
print(f"\nExpected Output: {''.join(chain(*answer))}")
i:0 letter:P turn:-1 row_index:0
[['P'], [], []]
i:1 letter:A turn:1 row_index:1
[['P'], ['A'], []]
i:2 letter:Y turn:1 row_index:2
[['P'], ['A'], ['Y']]
i:3 letter:P turn:-1 row_index:1
[['P'], ['A', 'P'], ['Y']]
i:4 letter:A turn:-1 row_index:0
[['P', 'A'], ['A', 'P'], ['Y']]
i:5 letter:L turn:1 row_index:1
[['P', 'A'], ['A', 'P', 'L'], ['Y']]
i:6 letter:I turn:1 row_index:2
[['P', 'A'], ['A', 'P', 'L'], ['Y', 'I']]
i:7 letter:S turn:-1 row_index:1
[['P', 'A'], ['A', 'P', 'L', 'S'], ['Y', 'I']]
i:8 letter:H turn:-1 row_index:0
[['P', 'A', 'H'], ['A', 'P', 'L', 'S'], ['Y', 'I']]
i:9 letter:I turn:1 row_index:1
[['P', 'A', 'H'], ['A', 'P', 'L', 'S', 'I'], ['Y', 'I']]
i:10 letter:R turn:1 row_index:2
[['P', 'A', 'H'], ['A', 'P', 'L', 'S', 'I'], ['Y', 'I', 'R']]
i:11 letter:I turn:-1 row_index:1
[['P', 'A', 'H'], ['A', 'P', 'L', 'S', 'I', 'I'], ['Y', 'I', 'R']]
i:12 letter:N turn:-1 row_index:0
[['P', 'A', 'H', 'N'], ['A', 'P', 'L', 'S', 'I', 'I'], ['Y', 'I', 'R']]
i:13 letter:G turn:1 row_index:1
[['P', 'A', 'H', 'N'], ['A', 'P', 'L', 'S', 'I', 'I', 'G'], ['Y', 'I', 'R']]
Input string: PAYPALISHIRING with n_rows:3
Expected Output: PAHNAPLSIIGYIR
In [4]: # moore's voting algorithm
num_list = [1,4,5,6,6,6,7,6,6]
# num_list = [1,2,3,2,2,4,5]
# return majority number which appears > n/2 else return -1
[Link] 2/4
9/30/25, 2:10 AM DSA-Lecture2-R14
def majority_num(num_list):
count = 0
number = -1
for i, num in enumerate(num_list):
if count == 0:
count+=1
number = num
else:
if number == num:
count+=1
else:
count-=1
votes=0
for _,num in enumerate(num_list):
if (num == number):
votes += 1
if (votes > len(num_list) // 2):
return number
else:
return -1
return number
print("Majority number is ", majority_num(num_list))
Majority number is 6
In [5]: #Maximum consecutive ones
# input_list = [0,1,1,1,0,1,1,0,0,0,1,0,0,1]
# input_list = [1,0,1,1,0]
# input_list = [0,0,0,0]
input_list = [1,1]
def max_consecutive_repeats(input_list, n):
max_repeated = 0
sum_=0
for i in range(len(input_list)):
if input_list[i]==n:
sum_+=1
else:
sum_=0
if sum_>max_repeated:
max_repeated = sum_
return max_repeated
max_consecutive_repeats(input_list,1)
Out[5]: 2
In [6]: #Kadane's Algorithm
#Determine max sum possible for a subarray in an array (can have negative elemen
# input_list = [2,3,1,-7,8,1,2,-9]
# input_list = [-2, -4] # -2 expected output
input_list = [2, 3, -8, 7, -1, 2, 3] # 11 expected output
max_sum = input_list[0]
for i, num in enumerate(input_list):
[Link] 3/4
9/30/25, 2:10 AM DSA-Lecture2-R14
if i == 0:
current_sum = num
else:
current_sum = max(num, current_sum+num)
if current_sum > max_sum:
max_sum = current_sum
print(max_sum)
11
Thank you!
[Link] 4/4