Skip to main content

Array, Hash

These are "design a class" problems where the right internal state is a plain list or an index trick rather than anything fancy. Mapping account numbers, car types, or stream keys onto array indices keeps every operation simple and fast.

General​

2043. Simple Bank System​

Medium·
Explanation

The bank state is just a list of balances, where account k maps to index k - 1. Every operation first validates that the account number is in range with is_valid_account, then mutates the corresponding balance.

The edge cases that drive the design are: an invalid account number (any operation returns False), an insufficient balance on withdraw (the withdraw fails without changing state), and a failed transfer. When a transfer withdraws from the source but the deposit to the target fails, the withdrawn money is re-deposited back into the source account so no money is lost.

Analysis
Time
O(1)
  • is_valid_account, deposit, and withdraw each do a single bounds check plus one balance update - O(1).
  • transfer calls withdraw and deposit (and possibly a rollback deposit), a fixed number of O(1) calls.
Space
O(n)
  • self.balance stores one entry per account, where n is the total number of accounts passed to __init__.
FIG. SIMPLE BANK SYSTEM● INTERACTIVE
visualization loads as you reach it
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·
Explanation

A carType can be of three kinds: big, medium, or small, represented by 1, 2, and 3 respectively. By using an array, we can make use of those indices to retrieve the remaining capacity for each car type directly.

The list is built as [None, big, medium, small] so that availability[carType] lines up with the car type without any offset arithmetic. Adding a car succeeds only when that slot still has remaining capacity, decrementing it on success.

Analysis
Time
O(1)
  • __init__() takes O(1)
  • addCar() takes O(1)
Space
O(1)
  • A fixed-size array of four slots is used regardless of input.
FIG. DESIGN PARKING SYSTEM● INTERACTIVE
visualization loads as you reach it
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·
3 Approachesclick to switch
Explanation

The straightforward solution: on every updateSubrectangle() you write newValue into each cell of the given subrectangle, and on getValue() you simply return the stored cell. The matrix always holds the true current state, so reads are trivial but every update touches the whole subrectangle.

Analysis
Time
O(m*n)
  • __init__() is O(1) (just stores the reference).
  • updateSubrectangle() walks every cell of the given subrectangle via iterate_over, up to O(m*n) in the worst case.
  • getValue() is O(1), a direct lookup.
  • Overall bounded by the worst-case update: O(m*n), where m is the number of rows and n is the number of columns.
Space
O(m*n)
  • self.rectangle stores the full grid, O(m*n).
FIG. SUBRECTANGLE QUERIES AS IS● INTERACTIVE
visualization loads as you reach it
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]

1656. Design an Ordered Stream​

Easy·
FIG. DESIGN AN ORDERED STREAM● INTERACTIVE
visualization loads as you reach it
Explanation

The problem asks us to return the longest sorted available slice of the list (a chunk) during each insertion. If there is no chunk available, we return [].

We keep the values in a backing array indexed by idKey - 1, and track the longest contiguous filled prefix from index 0 using a pointer. After inserting a value, we advance the pointer past every consecutive filled slot, then return the slice between the inserted key and the new pointer position - which is exactly the newly available chunk.

Analysis
Time
O(n)
  • __init__() takes O(n)
  • insert() takes O(k)

where:

  • n is the length of the array
  • k is the length of the chunk to be returned
Space
O(n)
  • The backing array of size n is stored.
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]

271. Encode and Decode Strings​

Medium·
3 Approachesclick to switch
Explanation

Pick a delimiter character that can never appear inside any input string, then join on encode and split on decode. Here 'π' stands in for that delimiter, so it only works when the inputs are guaranteed not to contain it - a length-prefix encoding is needed for arbitrary byte strings.

Analysis
Time
O(n)
  • encode() joins all strings in a single pass over their combined length n
  • decode() splits the joined string in a single pass over n
Space
O(n)
  • The encoded string and the decoded list both hold all the original characters
FIG. ENCODE AND DECODE STRINGS● INTERACTIVE
visualization loads as you reach it
class Codec:
def encode(self, strs):
"""Encodes a list of strings to a single string."""
return "π".join(strs)
 
def decode(self, s):
"""Decodes a single string to a list of strings."""
return s.split("π")