# Apartment hunting

user_1884715
python
13 days ago
2.2 kB
3
Indexable
Never
```#O(N) time, O(N*R) space
def apartmentHunting(blocks, reqs):
n = len(blocks)
r = len(reqs)
INF = float('inf')
lastReqIdxFromLeft = generateLeftClosestReq(blocks, reqs)
lastReqIdxFromRight = generateRightClosestReq(blocks, reqs)
optimalBuildingIdx = 0
maxWalkFromOptimalBuilding = INF
for i in range(n):
maxWalkFromIthBlock = maxWalkFromBlock(i, lastReqIdxFromLeft[i], lastReqIdxFromRight[i], reqs)
if maxWalkFromIthBlock < maxWalkFromOptimalBuilding:
optimalBuildingIdx = i
maxWalkFromOptimalBuilding = maxWalkFromIthBlock
return optimalBuildingIdx

def generateLeftClosestReq(blocks, reqs):
n = len(blocks)
r = len(reqs)
INF = float('inf')
lastReqIdxFromLeft = [{req: INF for req in reqs} for i in range(n)]
for i, block in enumerate(blocks):
for req in reqs:
if block[req] == True:
lastReqIdxFromLeft[i][req] = i
elif i > 0:
lastReqIdxFromLeft[i][req] = lastReqIdxFromLeft[i-1][req]
return lastReqIdxFromLeft

def generateRightClosestReq(blocks, reqs):
n = len(blocks)
r = len(reqs)
INF = float('inf')
lastReqIdxFromRight = [{req: INF for req in reqs} for i in range(n)]
for i in range(n-1, -1, -1):
for req in reqs:
if blocks[i][req] == True:
lastReqIdxFromRight[i][req] = i
elif i < n-1:
lastReqIdxFromRight[i][req] = lastReqIdxFromRight[i+1][req]
return lastReqIdxFromRight

def maxWalkFromBlock(i, lastReqIdxFromLeft, lastReqIdxFromRight, reqs):
INF = float('inf')
maxWalkFromIthBlock = 0
for req in reqs:
leftClosestIdx, rightClosestIdx = lastReqIdxFromLeft[req], lastReqIdxFromRight[req]
walkForReq = INF
if leftClosestIdx != INF:
leftWalk = i - leftClosestIdx
walkForReq = min(walkForReq, leftWalk)
if rightClosestIdx != INF:
rightWalk = rightClosestIdx - i
walkForReq = min(walkForReq, rightWalk)
maxWalkFromIthBlock = max(maxWalkFromIthBlock, walkForReq)
return maxWalkFromIthBlock```