Given this grid:
grid = [[10,23,16,25,12],
[19,11,8,1,4],
[3,6,9,7,20],
[18,24,4,17,5],
[7,3,4,6,1]]
The sequence with the greatest difference between the sum of its odd rows and the sum of its even rows is the sequence of row 1 to row 3. This is because (10 + 23 + 16 + 25 + 12) - (19 + 11 + 8 + 1 + 4) + (3 + 6 + 9 + 7 + 20) = 88 which is the maximum difference out of all sequences like this.
The sequence should have an even row and an odd row so it must have at least 2 rows. The maximum number of rows depends on the size of the grid.
The problem is I need it to work on an O(log n) time complexity. My idea is to use recursion to divide the grid into 2 and solve it from there. However, it doesn’t work as I wanted to.
This is my whole code:
import math
class Sequence:
def __init__(self,grids):
self.grids = grids
self.calculate_max_difference()
def calculate_max_difference(self):
# Get the odd and even rows using list slicing
odd_rows = self.grids[::2]
even_rows = self.grids[1::2]
odd_sum = 0
even_sum = 0
for odd_lst in odd_rows:
odd_sum += sum(odd_lst)
for even_lst in even_rows:
even_sum += sum(even_lst)
self.diff = odd_sum - even_sum
def consecutive_seq(start,end,max,grids):
middle = math.ceil((start+end)/2)
sequence = []
for row in range(end-start):
sequence.append(grids[start+row])
seq_ins = Sequence(sequence)
if (end-start) <= 3 and (end-start) > 1:
return seq_ins.grids
upper_seq = consecutive_seq(start,middle,seq_ins.diff,seq_ins.grids)
lower_seq = consecutive_seq(middle+1,end,seq_ins.diff,seq_ins.grids)
greater_seq = upper_seq
if upper_seq.diff < lower_seq.diff:
greater_seq = lower_seq
if greater_seq.diff < max:
return seq_ins.grids
# Sample Input
grid = [[10,23,16,25,12],
[19,11,8,1,4],
[3,6,9,7,20],
[18,24,4,17,5],
[7,3,4,6,1]]
n = len(grid)
max_seq = consecutive_seq(0,n-1,0,grid)
print(max_seq)
How should I go about this?
>Solution :
Firstly you don’t really need a 2d array for this. You can sum up all the rows and only store the sums in a 1D array. So for example
grid = [[10,23,16,25,12],
[19,11,8,1,4],
[3,6,9,7,20],
[18,24,4,17,5],
[7,3,4,6,1]]
turns in to
sums = [sum(row) for row in grid] # sums = [86, 43, 45, 68, 21]
Once you have the sums you have to simply invert the signs for odd indices
[86, 43, 45, 68, 21] becomes => [86, -43, 45, -68, 21]
Once you have the data in this format, you can use the algorithm for Finding the largest sum in a contiguous subarray which has a time complexity of O(n). You might have to make a few small tweaks to that to include at least 2 numbers.
Also if you care only about the difference, you will have to run the algorithm again but this time multiply the even indices by -1.
I really don’t think you can solve this in O(log n) time.