nicolarusso
BAN USERWe can achieve this with Time Complexity O(n) and Auxiliary Space O(1)
def findLastIndex(arr: [int]) -> int:
last_index = -1
for i in range(len(arr)-1):
if arr[i] == arr[i + 1]:
last_index = arr[i + 1]
return last_index
If the input is not sorted, we can still achieve this with Time Complexity O(n) and Auxiliary Space O(n).
def findLastNotOrdered(arr: [int]) -> int:
elem_map = {}
max_index = -1
for i in range(len(arr)):
if arr[i] in elem_map:
elem_map[arr[i]].append(i)
if len(elem_map[arr[i]]) > 1:
max_index = i
else:
elem_map[arr[i]] = [i]
return max_index
Naive solution with Time Complexity O(n**2), Auxiliary Space O(1). Can't figure out a linear solution
def hasSubSum(arr: [int], k: int) -> bool:
for i in range(len(arr) - 1):
sum = arr[i]
for j in range(i + 1, len(arr)):
sum += arr[j]
if sum % k == 0:
return True
return False
This should do the job in O(row * column) = O(tot_element) using BFS
def get_max_shapes(grid: [[str]]) -> int:
seen = set()
max_shapes = 0
for row_index in range(len(grid)):
for shape_index in range(len(grid[row_index])):
if grid[row_index][shape_index] == 'X' and (row_index, shape_index) not in seen:
queue = collections.deque([[(row_index, shape_index)]])
seen.add((row_index, shape_index))
path_shapes = 0
while queue:
path = queue.popleft()
i, j = path[-1]
path_shapes += 1
cand_moves = ((i - 1, j), (i + 1, j), (i, j + 1), (i, j - 1))
for can in cand_moves:
if can not in seen and -1 < can[1] < len(grid[i]) and -1 < can[0] < len(grid):
if grid[can[0]][can[1]] == 'X':
queue.append(path + [can])
seen.add(can)
if path_shapes > max_shapes:
max_shapes = path_shapes
return max_shapes
Assuming array not sorted, with duplicates. Time complexity: O(n**2), Space Complexity: O(1) + input
def count_subsets(arr: [int], k: int) -> int:
count = 0
for i in range(len(arr)): O(n)
if arr[i] <= k:
count += 1
j = i+1
min = arr[i]
max = arr[i]
while j < len(arr): # O(n)
if arr[j] < min:
min = arr[j]
if arr[j] > max:
max = arr[j]
if min + max <= k:
count += 1
j += 1
return count
Time complexity O(min(n, m))
def extra_char(s1: str, s2:str) -> str:
max = s1
min = s2
if len(s2) > len(max):
max = s2
min = s1
for c1, c2 in zip(max, min): # O(min(n, m))
if c1 != c2:
return c1
return max[-1]
Assumptions:
1. Names are unique keys in a chart. The 'updateEntity' method should have been 'updateEntities' if a single name (as for signature of that method) may refer to more than one Entity.
2. The 'updateEntity' method is used to increment the score of 1 unit.
Given this, the design is really driven by the more often used operation. Let's say, if we need to do a lot of updates and rarely need to get_from_rank then the following solution is optimal. Viceversa, we could order and store the dictionary at every update_entity.
class ScorerChart:
def __init__(self, name, score):
self.chart = {name: score}
def add(self, name, score):
self.chart[name] = score
def update_entity(self, name):
self.chart[name] += 1 # O(1)
def get_entity_from_rank(self, rank):
sorted_chart = sorted(self.chart.items(), key=lambda e: e[1], reverse=True) # O(n log n)
return sorted_chart[rank - 1] # O(1)
if __name__ == "__main__":
c = ScorerChart("Carl", 74)
c.add("Alex", 55)
c.add("Isla", 40)
c.add("Tom", 5)
c.add("Michael", 32)
c.add("Nigel", 75)
c.add("Greg", 15)
assert c.get_entity_from_rank(1) == ("Nigel", 75)
c.update_entity("Carl")
c.update_entity("Carl")
assert c.get_entity_from_rank(1) == ("Carl", 76)
# Randomly assuming that target is calculated (once reached) as target = target[x]* 7, target[y]* 7
def move(start, target):
queue = collections.deque([[start]])
seen = {start}
while queue:
path = queue.popLeft()
x, y = path[-1]
if x, y == target:
return move((x, y), (target[0] * 7, target[1] * 7))
candidates = {(x + 1, y + 1), (x - 1, y + 1), (x - 1, y - 1), (x + 1, y - 1)}
forbidden_l = get_forbidden_cells()
for can in candidates:
if can not in forbidden_l and can not in seen:
queue.append(path + [can])
seen.add(can)
def get_forbidden_cells():
# not relevant, probably O(1)
Here a solution that doesn't sort the array.
def countSubset(arr, target):
r = []
count = 0
for element in arr: # O(n)
if element < target:
temp_r = []
for r_set in r: # O(m)
curr_set = r_set.copy() # O(len(r_set))
curr_set.add(element)
sorted_set = sorted(curr_set) # O(len(curr_set) * log len(curr_set))
max = sorted_set[-1]
min = sorted_set[0]
if max + min < target:
temp_r.append(set(sorted_set))
count += 1
temp_r.append({element})
count += 1
r.extend(temp_r) # O(len(temp_r))
return count
def top10(videos):
v_dict = {}
for video in videos: # O(v)
if video[0] in v_dict:
v_dict[video[0]] += video[1]
else:
v_dict[video[0]] = video[1]
sorted_v = sorted(v_dict.items(), key=lambda x: x[1], reverse=True)[:10] # O(n log(n))
result = [(k, v) for k, v in sorted_v]
return result
# With `r` = number of rules in `table` and `sr` = number of rules that contain at least one `*`:
# Time complexity = O(r) + O(r * sr)
def isAmbiguous(table):
seen = {}
starred_rules = {}
is_amb = False
for rule in table: # O(r)
val = rule.pop()
curr_rule = tuple(rule)
if '*' in rule:
if curr_rule in starred_rules and starred_rules[curr_rule] != val: # worst case: O(s) - assuming robust hash function with no collisions: O(1)
is_amb = True
break
starred_rules[curr_rule] = val
else:
if curr_rule in seen and seen[curr_rule] != val: # worst case: O(se) - assuming robust hash function with no collisions: O(1)
is_amb = True
break
seen[curr_rule] = val
if not is_amb and bool(starred_rules):
for star_rule in starred_rules: # O(sr)
for rule in seen: # O(r)
if len(set(star_rule) - set(rule)) < 2:
return True
return is_amb
# This solution supports negative integers and elements duplication (e.g. [3, 5, 2, -4, 8, -4, 11, 11]).
# With `n` = number of elements in arr and `m` = number of indices of a certain complement
# Time complexity = O(n * m)
# Space complexity = O(n * m)
def twoSum(arr, sum):
compl = {}
result = []
for i in range(len(arr)): # O(n)
n = arr[i]
if sum-n in compl:
for j in compl[sum-n]: # O(m)
result.append([arr[j], n])
if n in compl:
compl[n].append(i)
else:
compl[n] = [i]
return result
# With `n` = number of words in the dictionary and `m` = number of chars of a certain (current) word:
# Time complexity = O(n * m)
# Space complexity = O(n * m)
def compare(dict, w):
found = False
for eng_w in dict: # O(n)
if len(w) == len(eng_w):
count = 0
for char_x, char_y in zip(w, eng_w): # O(m)
if char_x != char_y:
count += 1
if count > 1:
break
if count < 2:
found = True
break
return found
Sliding window - O(n)
- nicolarusso May 17, 2020