Hellp guys!

It’s Day 11 of #100DaysofCode. Here’s a summary of what I did today. Mostly it’s leetcode problems.

Asteroid collision – stack approach – Append to stack if no collision (i.e both asteroids in the same direction or different directions in opposite ways). Otherwise keep popping from the stack until no collision happens. Time complexity – O(n) and space complexity O(n).

Number of ships in a rectangle – this one’s a weird problem. Here we keep dividing the problem until our square becomes a point and if that point has a ship we return 1 otherwise 0. We make mid points to form 4 new rectangles and call functions on them. Here the time complexity will be O(n) if n is the number of ships it has or O(k^2) where k is the top right point coordinates where we can have maximum of k^2 points.

Gas Station – we use greedy approach here – We check each position as starting but if the fuel is not enough to go to next station we start from this next index. Once we find the starting index we return it. Here we check any index i till N only not from N to i again because we can say intuitively that it will work for circular case. Time complexity – O(N), space Complexity O(1)

Two City Scheduling – This is also greedy but the values are not sorted. So we sort the values according to abs(a-b). Because we want to select city a where the loss for company is minimal that is where we know a is lesser by a great margin to b. So once we sort, we pick all a’s till N and then we pick all city b’s. This will be the optimal solution. Time complexity O(nlogn), space complexity O(1).

Vertical order binary tree traversal – Here we traverse the tree in DFS approach and store the values in a dictionary. The x values are the keys and tuple of y value and node value as values in the dictionary. Later we will sort using lambda function according to the given requirements. Time complexity – O(nlogn) for sorting and O(n) for space.

Binary Tree Vertical order Traversal – A slight modification to the previous problem. Here we need to return values from left to right in case of same level. So we use a BFS approach to save sorting time. We use a queue and traverse the tree by level. Simultaneously, we add the pairs to the dictionary with x column as key and node value list as value. We keep track of min_columns and max_columns to retrieve the values later without having to sort by cols. The time complexity is O(n) to traverse all the n nodes and space is O(n) to store them.

Insert Delete get Random O(1) – here we use dictionary to store the values. This gives us O(1) insert and delete times. To get random without having to convert keys of dictionary every time into a list we define a list and add values to it every time we insert into the dictionary. Here the tricky part is to delete from the list in O(1) time. What we can do is while storing val as key in the dictionary we store the values as it’s index. When deleting a value we get it’s index and replace that element in the list with the last element and pop the last one. All these operations are in constant time. Space is O(n)

Insert Delete get Random O(1) Duplicates allowed – Modification to above problem where duplicates are allowed. Here in the dictionary we store the values with set of all indexes for the occurence of that character. And a list with all the values inserted. While deleting we pop the index from the set for that key and do the same replace operations as before. One more thing to take care of is since we are moving the last element to another place we should remove it’s index from the set in the dictionary. I learnt a new operator discard which does this for the set. Then we add the new index to that set. All these operations are O(1)

Phew!! These are all the problems that i did today. I am thinking I should revisit all the problems I have done some time this week. Later I watched a video about NoSQL databases. Next I started the one with MongoDB and python and watched only a few minutes. In that video the instructor is going to build air bnb clone app using MongoDB but for snakes. I think I will rename it for all pets. I just installed mongoDB in my system. I will complete the rest tomorrow. It’s been a long day today. I will catch you in tomorrow’s blog.

Bye!!!