-
-
Save shafiemukhre/21dcd6c849974c999b194db580075857 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
from collections import defaultdict | |
class Solution: | |
def __init__(self, columns): | |
# create columns in dict of dict | |
self.columns = columns | |
self.data = defaultdict(dict) | |
for column in self.columns: | |
self.data[column][0] = 0 | |
def set(self, row, column, value): | |
self.data[column][row] = value # O(1) runtime | |
def get(self, row, column): | |
if column not in self.data or row not in self.data[column]: | |
return 0 | |
return self.data[column][row] # O(1) runtime | |
def printFirstNLine(self, n): | |
colRes = "" | |
for column in self.columns: # O(m) | |
colRes += column | |
colRes += " " | |
print(colRes) | |
i = 0 | |
while i < n: # O(n) | |
rowRes = "" | |
for column in self.columns: # O(m) | |
val = self.data[column].get(i, 0) | |
rowRes += str(val) | |
rowRes += " " | |
print(rowRes) | |
i += 1 | |
# Time complexity analysis | |
# initilizing class: O(m) runtime, O(mk) space where k is the amount of .set() being called as self.data grow | |
# set() method: O(1) runtime, O(1) space | |
# get() method: O(1) runtime, O(1) space | |
# printFirstNLine() method: O(mn) runtime, O(1) space if we are not considering printed result as part of extra space | |
spreadSheet = Solution(["fips", "pops", "area"]) | |
spreadSheet.set(0, "fips", 1001) | |
spreadSheet.set(0, "pops", 20000) | |
spreadSheet.set(0, "area", 456) | |
spreadSheet.set(5, "fips", 1002) | |
assert spreadSheet.get(0, "fips") == 1001 | |
assert spreadSheet.get(0, "pops") == 20000 | |
assert spreadSheet.get(1, "area") == 0 | |
assert spreadSheet.get(5, "area") == 0 | |
print(spreadSheet.printFirstNLine(9)) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment