-
Notifications
You must be signed in to change notification settings - Fork 228
/
apartment-hunting.py
67 lines (59 loc) · 2.01 KB
/
apartment-hunting.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
# APARTMENT HUNTING
# O(b^2 * r) time and O(1) space
def apartmentHunting(blocks, reqs):
# Write your code here.
minDistance, index = float('inf'), None
for idx in range(len(blocks)):
getDistance = findMinDistanceFromBlock(blocks, reqs, idx)
print(idx,getDistance)
if getDistance < minDistance:
minDistance = getDistance
index = idx
return index
def findMinDistanceFromBlock(blocks, reqs, blockIdx):
minDistance = 0
for req in reqs:
block = blocks[blockIdx]
minForReq = float('inf')
for idx, currentBlock in enumerate(blocks):
if currentBlock[req]:
minForReq = min(minForReq, abs(blockIdx - idx))
if minForReq == float('inf'):
return float('inf')
minDistance = max(minDistance, minForReq)
return minDistance
# O(br) time and space
def apartmentHunting(blocks, reqs):
# Write your code here.
minDistancesFromBlocks = list(map(lambda req: getMinDistances(blocks, req), reqs))
maxDistancesAtBlocks = getMaxDistancesAtBlocks(blocks, minDistancesFromBlocks)
return getIdxAtMinValue(maxDistancesAtBlocks)
def getMinDistances(blocks, req):
minDistances = [0 for block in blocks]
closestReqIdx = float("inf")
for i in range(len(blocks)):
if blocks[i][req]:
closestReqIdx = i
minDistances[i] = distanceBetween(i, closestReqIdx)
for i in reversed(range(len(blocks))):
if blocks[i][req]:
closestReqIdx = i
minDistances[i] = min(minDistances[i], distanceBetween(i, closestReqIdx))
return minDistances
def getMaxDistancesAtBlocks(blocks, minDistancesFromBlocks):
maxDistancesAtBlocks = [0 for block in blocks]
for i in range(len(blocks)):
minDistancesAtBlock = list(map(lambda distances: distances[i], minDistancesFromBlocks))
maxDistancesAtBlocks[i] = max(minDistancesAtBlock)
return maxDistancesAtBlocks
def getIdxAtMinValue(array):
idxAtMinValue = 0
minValue = float("inf")
for i in range(len(array)):
currentValue = array[i]
if currentValue < minValue:
minValue = currentValue
idxAtMinValue = i
return idxAtMinValue
def distanceBetween(a, b):
return abs(a - b)