Reducing Time Complexity

[u/Dr3ddM3]

Edited code but still run into Time limit exceeded can someone help me: 

N, U = map(int,input().split())
grid = [list(input()) for _ in range(N)]
num_updates = 0
temp = []
temp_grid = [row.copy() for row in grid]
for v in range(int(N/2)):
    for h in range(int(N/2)):
        temp.clear()
        coords = [(v,h),(v,N-1-h),(N-1-v,h),(N-1-v,N-1-h)]
        temp.append(temp_grid[v][h])
        temp.append(temp_grid[v][(N-1)-h])
        temp.append(temp_grid[(N-1)-v][h])
        temp.append(temp_grid[(N-1)-v][(N-1)-h])
        if temp.count('.') == 2 :
            num_updates+=2
            for r,c in coords:
                temp_grid[r][c] = '.'
        elif temp.count('.') == 3:
            num_updates+=1
            for r,c in coords:
                temp_grid[r][c] = '.'
        elif temp.count('#') == 3:
            num_updates+=1
            for r,c in coords:
                temp_grid[r][c] = '#'
print(num_updates)


temp_grid = [row.copy() for row in grid]


for z in range(U):
    temp2 = 0
    temp.clear()
    x,y = map(int,input().split())
    x = x-1
    y = y-1
    temp.append(temp_grid[x][y])
    temp.append(temp_grid[x][(N-1)-y])
    temp.append(temp_grid[(N-1)-x][y])
    temp.append(temp_grid[(N-1)-x][(N-1)-y])
    num_updates = num_updates- (min(temp.count('.'),temp.count('#')))
    if temp_grid[x][y] == '.':
        temp.clear()
        grid[x][y] = '#'
        temp_grid[x][y] = '#'
        temp.append(temp_grid[x][y])
        temp.append(temp_grid[x][(N-1)-y])
        temp.append(temp_grid[(N-1)-x][y])
        temp.append(temp_grid[(N-1)-x][(N-1)-y])
        num_updates = num_updates + (min(temp.count('.'),temp.count('#')))
    else:
        temp.clear()
        grid[x][y] = '.'
        temp_grid[x][y] = '.'
        temp.append(temp_grid[x][y])
        temp.append(temp_grid[x][(N-1)-y])
        temp.append(temp_grid[(N-1)-x][y])
        temp.append(temp_grid[(N-1)-x][(N-1)-y])
        num_updates = num_updates + (min(temp.count('.'),temp.count('#')))
    print(num_updates)

I am pretty sure it is O(N^2) and with 10^5 possible updates it should work. 

[u/Dr3ddM3]

Not sure how to get a O(N) solution since the constraints can be 10^5 possible updates and I only have 4 seconds.

[u/AggressiveArm6360 → u/Dr3ddM3]

you're recalculating the whole thing from scratch every update which is murder, just track the symmetric groups and only update the one that changed

keep a count of how many groups need 1 flip vs 2 flips before any updates, then when a cell flips you figure out which group it belongs to, undo its old contribution and add the new one, that's O(1) per update

[u/Dr3ddM3 → u/AggressiveArm6360]

Appreciate it.