You are given a mn grid. You are asked to generate k mines on this grid randomly. Each cell should have equal probability of k / mn of being chosen. Your algorithm should run in O(m) time.

The traditional resevoir sampling does not work due to the time complexity constraint
def insert(h,w,m):
position = [None]m
lut = {}
for i in range(m):
pos = randint(0,hw-i-1)
if pos in lut:
position[i] = lut[pos]
else:
position[i] = pos
lut[pos] = h*w-i-1