Array, Hash¶
General¶
2043. Simple Bank System (Medium)¶
Solution
Edge cases:
invalid account number
insufficient amount for withdraw
retransfer (deposit back) the withdrawn amount on failure
Analysis
Time Complexity: \(\mathcal{O}(1)\)
__init__()takes \(\mathcal{O}(1)\)withdraw()takes \(\mathcal{O}(1)\)deposit()takes \(\mathcal{O}(1)\)transfer()takes \(\mathcal{O}(1)\)
Space Complexity: \(\mathcal{O}(n)\)
where:
\(n\) is the total number of accounts
class Bank:
def __init__(self, balance: List[int]):
self.balance = balance
def transfer(self, account1: int, account2: int, money: int) -> bool:
if self.withdraw(account1, money):
if self.deposit(account2, money):
return True
self.deposit(account1, money)
return False
def deposit(self, account: int, money: int) -> bool:
if self.is_valid_account(account):
self.balance[account - 1] += money
return True
return False
def withdraw(self, account: int, money: int) -> bool:
if self.is_valid_account(account) and self.balance[account - 1] >= money:
self.balance[account - 1] -= money
return True
return False
def is_valid_account(self, account: int) -> bool:
return 1 <= account <= len(self.balance)
1603. Design Parking System (Easy)¶
Solution
carType can be of three kinds: big, medium, or small, which are represented
by 1, 2 and 3 respectively. By using array, we can make
use of indices to retrieve carType.
Analysis
Time Complexity: \(\mathcal{O}(1)\)
__init__()takes \(\mathcal{O}(1)\)addCar()takes \(\mathcal{O}(1)\)
Space Complexity: \(\mathcal{O}(1)\)
class ParkingSystem:
def __init__(self, big: int, medium: int, small: int):
self.availability = [None, big, medium, small]
def addCar(self, carType: int) -> bool:
if self.availability[carType] > 0:
self.availability[carType] -= 1
return True
return False
1476. Subrectangle Queries (Medium)¶
Solution
Straightforward solution where you can update the matrix for every updateSubrectangle()
and return the actual value during getValue()
Analysis
Time Complexity: \(\mathcal{O}(m\cdot n)\)
__init__()takes \(\mathcal{O}(m\cdot n)\)updateSubrectangle()takes \(\mathcal{O}(m\cdot n)\)getValue()takes \(\mathcal{O}(1)\)
where:
\(m\) is the number of rows
\(n\) is the number of columns
Space Complexity: \(\mathcal{O}(m\cdot n)\)
class SubrectangleQueries:
def __init__(self, rectangle: List[List[int]]):
self.rectangle = rectangle
def iterate_over(
self, row1: int, col1: int, row2: int, col2: int
) -> Tuple[int, int]:
for r in range(row1, row2 + 1):
for c in range(col1, col2 + 1):
yield r, c
def updateSubrectangle(
self, row1: int, col1: int, row2: int, col2: int, newValue: int
) -> None:
for row, col in self.iterate_over(row1, col1, row2, col2):
self.rectangle[row][col] = newValue
def getValue(self, row: int, col: int) -> int:
if 0 <= row < len(self.rectangle) and 0 <= col < len(self.rectangle[0]):
return self.rectangle[row][col]
Solution
Instead of updating the matrix for every updateSubrectangle(), we can cache
the update request and never update the matrix.
Analysis
Time Complexity: \(\mathcal{O}(m\cdot n)\)
__init__()takes \(\mathcal{O}(m\cdot n)\)updateSubrectangle()takes \(\mathcal{O}(1)\)getValue()takes \(\mathcal{O}(k)\)
where:
\(m\) is the number of rows
\(n\) is the number of columns
\(k\) is the number of cached operations. Cache is never flushed here.
Space Complexity: \(\mathcal{O}(m\cdot n)\)
class SubrectangleQueries:
def __init__(self, rectangle: List[List[int]]):
self.rectangle = rectangle
self.update_cache = []
def updateSubrectangle(
self, row1: int, col1: int, row2: int, col2: int, newValue: int
) -> None:
self.update_cache.append([row1, col1, row2, col2, newValue])
def getValue(self, row: int, col: int) -> int:
for op in reversed(self.update_cache):
row1, col1, row2, col2, newValue = op
if row1 <= row <= row2 and col1 <= col <= col2:
return newValue
return self.rectangle[row][col]
Solution
Extension of Track Updates solution, useful when you have to
save the updates to rectangle matrix.
Instead of updating the matrix for every updateSubrectangle(), we can cache
the update request and the update the matrix periodically. Here, we can update when
getValue() is called.
This approach is life-saving is updating a cell in a rectangle is a costly operation. This is inspired by the idea “Write Coalescing os SSD.” (google for more :p)
Analysis
Time Complexity: \(\mathcal{O}(m\cdot n)\)
__init__()takes \(\mathcal{O}(2\cdot m\cdot n)\)updateSubrectangle()takes \(\mathcal{O}(1)\)getValue()takes \(\mathcal{O}(k\cdot m\cdot n)\)
where:
\(m\) is the number of rows
\(n\) is the number of columns
\(k\) is the number of cached operations. Cache is flushed for every
coalesce()orgetValue()
Space Complexity: \(\mathcal{O}(2\cdot m\cdot n)\)
class SubrectangleQueries:
def __init__(self, rectangle: List[List[int]]):
self.rectangle = rectangle
self.update_cache = []
self.isupdated = self.get_fresh_isupdated()
def get_fresh_isupdated(self):
return [[False] * len(self.rectangle[0]) for _ in range(len(self.rectangle))]
def iterate_over(
self, row1: int, col1: int, row2: int, col2: int
) -> Tuple[int, int]:
for r in range(row1, row2 + 1):
for c in range(col1, col2 + 1):
if self.isupdated[r][c] == False:
yield r, c
self.isupdated[r][c] = True
def updateSubrectangle(
self, row1: int, col1: int, row2: int, col2: int, newValue: int
) -> None:
self.update_cache.append([row1, col1, row2, col2, newValue])
def coalesce(self):
while self.update_cache:
op = self.update_cache.pop()
for r, c in self.iterate_over(*op[:4]):
self.rectangle[r][c] = op[4]
self.isupdated = self.get_fresh_isupdated()
def getValue(self, row: int, col: int) -> int:
self.coalesce()
if 0 <= row < len(self.rectangle) and 0 <= col < len(self.rectangle[0]):
return self.rectangle[row][col]
1656. Design an Ordered Stream (Easy)¶
Solution
Question states that we need to return longest sorted available slice of list (chunk)
during each insertion. If there is no chunk available, return [].
Keeping track of longest available slice from the beginning index == 0 using
pointer will help us to return the chunk.
Analysis
Time Complexity: \(\mathcal{O}(n)\)
__init__()takes \(\mathcal{O}(n)\)insert()takes \(\mathcal{O}(k)\)
where:
\(n\) is the length of the array
\(k\) is the length of the chunk to be returned
Space Complexity: \(\mathcal{O}(n)\)
class OrderedStream:
def __init__(self, n: int):
self.pointer = 0
self.data = [None for i in range(n)]
self.n = n
def insert(self, idKey: int, value: str) -> List[str]:
idKey = idKey - 1 # 0-indexing
self.data[idKey] = value
while self.pointer < self.n and self.data[self.pointer]:
self.pointer += 1
return self.data[idKey : self.pointer]