Google Problems on LeetCode Flashcards
Time complexity of len() function in Python
Python follows the idea that keeping the length as an attribute is cheap and easy to maintain. len() is actually a function that calls the method ‘__len__()’. This method is defined in the predefined classes of iterable data structures. This method actually acts as a counter, that is automatically incremented as the data is defined and stored. Thus when you call the len() function, you do not give the interpreter the command to find the length by traversing, but rather you ask the interpreter to print a value that is already stored. Hence, len() function in Python runs in O(1) complexity.
Internal working of Python
Refer this wonderful link https://towardsdatascience.com/how-does-python-work-6f21fd197888
Refer this link too : https://opensource.com/article/18/4/introduction-python-bytecode#:~:text=Python%2C%20like%20many%20interpreted%20languages,format%20is%20called%20%22bytecode.%22
Please check the implementation of bytecode present in the above link ( to do in system )..very nice article
Edit : Check this link : it’s amazing
http://www.aosabook.org/en/500L/a-python-interpreter-written-in-python.html
it’s about a python interpreter written in python. CPython interpreter is stack based
- Unique Email Addresses : Easy problem
My code:
class Solution:
def numUniqueEmails(self, emails: List[str]) -> int:
c_emails = []
for stri in emails:
n = len(stri)
ind = stri.find('@')
#print("ind",ind)
local = stri[0:(ind)]
#print(local)
dom = stri[(ind+1):(n)]
#print(dom)
plus_ind = local.find('+')
if plus_ind != -1:
local = local[0:plus_ind]
#print(local)
while(local.find('.') != -1 ):
ln = int(len(local))
l = int(local.find('.'))
local_tmp1 = local[0:(l)]
local_tmp2 = local[(l+1):(ln)]
local = local_tmp1 + local_tmp2
#print(local)
newemail = local + '@' + dom
#print(newemail)
c_emails.append(newemail)
#print(c_emails)
return len(set(c_emails))
Soln mentioned in leetcode:
class Solution(object):
def numUniqueEmails(self, emails):
seen = set()
for email in emails:
local, domain = email.split(‘@’)
if ‘+’ in local:
local = local[:local.index(‘+’)]
seen.add(local.replace(‘.’,’’) + ‘@’ + domain)
return len(seen)
How can we improve the time complexity???
https://www.quora.com/What-is-the-runtime-for-Python-split-built-in-method
License Key Formatting
and find out the time complexity of replace function in python???
My code : referred a soln
class Solution:
def licenseKeyFormatting(self, S: str, K: int) -> str:
temp = S
temp = temp[::-1]
#print(temp)
temp = temp.replace('-','')
#print(temp)
i = 0
l = K
t = ""
x = math.floor(len(temp)/K) - 1
y = len(temp)
count = 0
for ele in temp:
if count == K:
t = t + '-'
count = 0
t = t + ele
count = count + 1
#print(t)
n = len(t)
#if (n > 1):
#t = t[0:(n-1)]
t = t[::-1]
#print(t)
return t.upper()
found the below code in discussion
class Solution:
def licenseKeyFormatting(self, S, K):
“””
:type S: str
:type K: int
:rtype: str
“””
S = S.replace(“-“, “”).upper()[::-1]
return ‘-‘.join(S[i:i+K] for i in range(0, len(S), K))[::-1]
time complexity of replace (ps reasearch more)
searching a substring inside a string can be done in linear time using KMP algorithm which is the most efficient. Replacing in the worst case will take linear time as well.
So overall time complexity: O(n)
Here n is dependent on the string str. In the worst case it will end up traversing the whole string and still not find the searchValue given to the replace function.
- Odd Even Jump
My soln : Brute Force (Time limit exceeded) , but I bet it works -> passed 59/64 cases
Made two improvements
edit : nope this improvement does not work!!
because odda[] gets cleared after filling in..so that continue statee=ment never works because odda will always be empty at that point!!!
-> after finding the path from an earlier starting good index => automatically implies that path exists from alternating indexes
class Solution:
def oddEvenJumps(self, A: List[int]) -> int:
goodind = 1
evena = []
odda = set()
n = len(A)
if(all(A[i] > A[i + 1] for i in range(n-1))):
return 1
else:
for i in range(0,(len(A)-1)):
jump = 0
j = i
if i in odda:
goodind = goodind + 1
continue
while(j<=(n-1) and j!= -1 and j!=(n-1)):
jump = jump + 1
if( jump % 2 == 0 ):
j = evenf(j,A)
else:
j = oddf(j,A)
odda.add(j)
if j == (n-1):
goodind = goodind + 1
odda.clear()
else:
odda.clear()
return goodind
def oddf(start:int,A:List[int]) -> int:
i = start
x = i+1
target_ind = -1
target_val = 100000
for j in range(x,(len(A))):
if A[j] >= A[i] and A[j] < target_val:
target_val = A[j]
target_ind = j
return target_ind
def evenf(start:int,A:List[int]) -> int:
i = start
x = i+1
target_ind = -1
target_val = -1
for j in range(x,len(A)):
if A[j] <= A[i] and A[j] > target_val:
target_val = A[j]
target_ind = j
return target_ind
Please check the official soln
Edit : This is a dynamic programming problem, check nick white’s video on YT
https://www.youtube.com/watch?v=r2I7KIqHTPU
from 16:00
- Odd Even Jump - official soln - 1
class Solution(object):
def oddEvenJumps(self, A):
N = len(A)
def make(B):
ans = [None] * N
stack = [] # invariant: stack is decreasing
for i in B:
while stack and i > stack[-1]: // if the incoming //index i is greater than on that of top of stack => this is //a legal odd jump. The array ans's index is the source //and ans[i] denotes the destination of the legal jump
ans[stack.pop()] = i // popping //the source index
stack.append(i)
return ans
B = sorted(range(N), key = lambda i: A[i]) //the array B will contain indices sorted such that A[i] is sorted
oddnext = make(B)
B.sort(key = lambda i: -A[i]) // sorted indices such //
//that A[I] is in descending order
evennext = make(B)
odd = [False] * N
even = [False] * N
odd[N-1] = even[N-1] = True // even and odd array //implies that the particular index is a good starting //index. The above condition is like the base condition //of 0 jumps from the last index to itself
for i in xrange(N-2, -1, -1):
if oddnext[i] is not None:
odd[i] = even[oddnext[i]] // i -> source index, //oddnext[i] is the destination index and from there even //jump, that's why we refer the even array
if evennext[i] is not None:
even[i] = odd[evennext[i]] // after an even jump //we look to the odd jump, hence the odd array
return sum(odd)
a modification of this question could be –> there’s no restriction that the jump should happen from right to left(like how it is now)
-> if this condition is there, then the logic is caught in a loop.
Check out this one example which I have tracked ( without this modification )
A = [10,13,12,14,15]
[0 ,1, 2, 3,4]
N = len(A) = 5
B = [0,2,1,3,4]
for i in B i = 0::: stack = [0, i = 2::: ans[0] = 2 ::means from ind 0 we can jump to ind 2 stack[2, i = 1::: stack[2,1 i = 3::: ans[1] = 3 ::means from ind 1 we can jump to ind 3 stack[2,3 i = 4::: ans[3] = 4 stack = [2,]
ans[2] = 4
oddnext = [2,3,4,4,None]
then…..
B is sorted in descending
B = [0,2,1,3,4] initially
after sorting ::
-A[i][-10,-12,-13,-14,-15]
=> [-15,-14,-13,-12,-10]
B = [4,3,1,2,0]
make(B) function is called
i = 4:: stack = [] stack = [4,
i = 3:: stack = [4,3
i = 1:: stack = [4,3,1
i = 2::
ans[1] = 2
stack[4,3
i = 0::
stack[4,3,0
evennext = [None,2,None,None,None]
odd = [False,False,False,False,True] even = [False,False,False,False,True]
odd[2] = even[oddnext[2]] odd[2] = even[4] odd[2] = False
odd[1] = even[oddnext[1]]
= even[3]
= False
even[1] = odd[evennext[1]]
= odd[2]
= False
odd[0] = even[oddnext[0]]
= even[2]
= False
A = [10,13,12,14,15]
[0 ,1, 2, 3,4]
odd[3] = even[4] = True
not very clear of why they’ve used stack. Please check again
Fruit into Baskets :
In a row of trees, the i-th tree produces fruit with type tree[i].
You start at any tree of your choice, then repeatedly perform the following steps:
Add one piece of fruit from this tree to your baskets. If you cannot, stop.
Move to the next tree to the right of the current tree. If there is no tree to the right, stop.
Note that you do not have any choice after the initial choice of starting tree: you must perform step 1, then step 2, then back to step 1, then step 2, and so on until you stop.
You have two baskets, and each basket can carry any quantity of fruit, but you want each basket to only carry one type of fruit each.
What is the total amount of fruit you can collect with this procedure?
Example 1:
Input: [1,2,1]
Output: 3
Explanation: We can collect [1,2,1].
Example 2:
Input: [0,1,2,2] Output: 3 Explanation: We can collect [1,2,2]. If we started at the first tree, we would only collect [0, 1]. Example 3:
Input: [1,2,3,2,2] Output: 4 Explanation: We can collect [2,3,2,2]. If we started at the first tree, we would only collect [1, 2]. Example 4:
Input: [3,3,3,1,2,1,1,2,3,3,4]
Output: 5
Explanation: We can collect [1,2,1,1,2].
If we started at the first tree or the eighth tree, we would only collect 4 fruits.
Watched Kevin Naughton Jr's Youtube video for this
class Solution {
public int totalFruit(int[] tree) {
//error handling
if(tree == null || tree.length == 0)
{
return 0;
}
int max = 1; // because atleast one fruit can definitely be collected
int i = 0;
int j = 0;
HashMapmap = new HashMap();
while(j < tree.length)
{
if (map.size() <= 2)
{
map.put(tree[j],j++); //keeps updating the latest index for that tree type
}
if (map.size() > 2)
{
int min = tree.length - 1;
for(int values: map.values())
{
min = Math.min(min,values);
}
i = min + 1;
map.remove(tree[min]);
}
max = Math.max(max,j - i);
}
return max;
} }
basic idea : traverse through the array once, keep two pointers, i and j
This problem boils down to the largest contiguous subarray which has atmax 2 types of trees
i points to the beginning of such a subarray and j to the end of the subarray
to record the highest index of a type of a tree, hash map is used such that it keeps rewriting the index. The key value of this hashmap is the type number and the value contains the largest index of that type. This is useful because as soon as three types are reached, we move the pointer ‘i’ to skip the leftmost type of tree and update i.
edit: why do we consider the minimum of the values in the hashmap???
because our ultimate aim is to maximise the number of fruits. Taking the minimum+1 position for i is the most trivial way for ensuring we still get max while not breaking the rules
Valid Parentheses
Given a string s containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[’ and ‘]’, determine if the input string is valid.
An input string is valid if:
Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Example 1:
Input: s = “()”
Output: true
Example 2:
Input: s = “()[]{}”
Output: true
Example 3:
Input: s = “(]”
Output: false
Example 4:
Input: s = “([)]”
Output: false
Example 5:
Input: s = “{[]}”
Output: true
Constraints:
1 <= s.length <= 104
s consists of parentheses only ‘()[]{}’.
My code is below:: (pls improve)
from collections import deque
class Solution:
def isValid(self, s: str) -> bool:
opp = {'(':')','[':']','{':'}'}
if len(s) == 0:
return True
stack = deque()
for i in s:
if ( i == '(' or i == '[' or i == '{' ):
stack.append(i)
else:
if ( stack and opp[stack.pop()] == i ):
continue
else:
return False
if not stack:
return True
else:
return FalseK Closest Points to Origin
Solution
We have a list of points on the plane. Find the K closest points to the origin (0, 0).
(Here, the distance between two points on a plane is the Euclidean distance.)
You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in.)
Example 1:
Input: points = [[1,3],[-2,2]], K = 1
Output: [[-2,2]]
Explanation:
The distance between (1, 3) and the origin is sqrt(10).
The distance between (-2, 2) and the origin is sqrt(8).
Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin.
We only want the closest K = 1 points from the origin, so the answer is just [[-2,2]].
Example 2:
Input: points = [[3,3],[5,-1],[-2,4]], K = 2
Output: [[3,3],[-2,4]]
(The answer [[-2,4],[3,3]] would also be accepted.)
Note:
1 <= K <= points.length <= 10000
- 10000 < points[i][0] < 10000
- 10000 < points[i][1] < 10000
import math
class Solution:
def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
retlist = []
dict = {}
n = 0
for p in points:
a = p[0]*p[0] + p[1]*p[1]
sqr = math.sqrt(a)
dict[n] = sqr
n = n + 1
B = sorted(range(n), key = lambda i: dict[i])
for i in range(0,K):
retlist.append(points[B[i]])
return retlist
Edit: A dictionary here wasn’t necessary I feel, a normal array in place of that would have sufficed
Edit 2 : Many people have suggested in discussion that this can be solved using heap. Find out how
Kth Largest Element in an Array
Solution
Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.
Example 1:
Input: [3,2,1,5,6,4] and k = 2
Output: 5
Example 2:
Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4
Note:
You may assume k is always valid, 1 ≤ k ≤ array’s length.
This soln uses Heap :
I checked out the basic operations of heaps and their implementation from geeksforgeeks.
My code which worked : but runtime is high
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
# if len(nums) == 0:
# return -1
#B = sorted(nums,key=lambda i:-i)
#print(B)
#return B[k-1]
# 2nd implementation using heap
#heaparr = [None]*(k+1)
# heapi = 0
if sorted(nums, reverse = True) == nums:
return nums[k-1]
heaparr = []
heapsize = 0
if len(nums) == 0:
return -1
for num in nums:
if heapsize <= k:
insert_into_minheap(num,heaparr,heapsize)
heapsize += 1
if heapsize == k+1:
remove_root_minheap(heaparr,heapsize)
heapsize -= 1
return heaparr[0]
def parent(i:int):
return int((i-1/2))
def left(i:int):
return int(2*i+1)
def right(i:int):
return int(2*i+2)
def insert_into_minheap(num:int, heaparr: List[int],hsize:int):
n = len(heaparr)
#heaparr[n] = num
heaparr.append(num)
i = n
while(i!=0 and heaparr[i] < heaparr[parent(i)]):
heaparr[i],heaparr[parent(i)] = heaparr[parent(i)],heaparr[i]
i = parent(i)
def remove_root_minheap(heaparr: List[int],hsize:int):
n = len(heaparr)
heaparr[0] = heaparr[n-1]
#heaparr[n-1] = None
heaparr.pop()
minheapify(heaparr,0,hsize)
def minheapify(heaparr:List[int],index:int,hsize:int):
l = left(index)
r = right(index)
smallest = index
if l < len(heaparr) and heaparr[l] < heaparr[index]:
smallest = l
if r < len(heaparr) and heaparr[r] < heaparr[smallest]:
smallest = r
if smallest != index:
heaparr[index],heaparr[smallest] = heaparr[smallest],heaparr[index]
i = index
while(i!=0 and heaparr[i] < heaparr[parent(i)]):
heaparr[i],heaparr[parent(i)] = heaparr[parent(i)],heaparr[i]
i = parent(i)
minheapify(heaparr,smallest,hsize)
Minimum cost to Hire K workers
class Solution:
def mincostToHireWorkers(self, quality: List[int], wage: List[int], K: int) -> float:
from fractions import Fraction
workers = sorted((Fraction(w, q), q, w)
for q, w in zip(quality, wage))
ans = float('inf')
pool = []
sumq = 0
for ratio, q, w in workers:
heapq.heappush(pool, -q)
sumq += q
if len(pool) > K:
sumq += heapq.heappop(pool)
if len(pool) == K:
ans = min(ans, ratio * sumq)
return float(ans)
MinRewards -> hard -> algoexpert
please check in algoexpert website -> it doesn’t allow me to copy the question here
I was able to solve it -> but not optimally though :)
My Solution’s conceptual understanding ::: the smallest element in the scores list was taken to be the pivot. This pivot will definitely have the minimum reward possible -> which is 1
This kinda divides the array into two parts. we’ll expand from this pivot in both the directions. If it’s increasing, then the current reward = previous reward + 1
if it’s decreasing, we’ll assign reward = 1 for the current score and backtrack until the rewards of two consecutive scores match
Time complexity : O(n2) Space O(n)
Official Solution 1 : they also used backtracking,but no concept of pivot. they just go through the array from left to right in one pass. If the scores are increasing then current reward = pre_reward + 1.
if it’s decreasing , then backtrack till the scores are decreasing -> in the backtracking, we increment the rewards by 1. remember we use max function here => because from the perspective of backtracking from right to left, the current score should have the right index score plus 1, but from the perspective of left to right, the current score should have the left index plus 1. Hence, we should take maximum to satisfy the condition . that’s why they’ve used max function in the code.
Official Solution 2 : this uses the concept of local mins. visualize the scores in a line graph => the valleys are local mins and the peaks are local maxes.
what’s imp to note here is that at all the local mins, the reward will be 1 ( because the score here is lesser than both it’s adjacent scores)
=>find all the local mins ( the valleys ) and then start populating the rewards from these valleys. so we’ll always go upwards from the valleys till we reach a peak. so we expand from the valley in both the directions until we reach peaks. in this case, since valley to peak is increasing, we’ll keep incrementing the rewards.
we have multiple start points here and finally we’re able to cover the entire scores array.
Official solution 3: visualize the points as a line graph. then we have two different persepctives to view the graph. for eg : an increasing graph viewed from left-right is decreasing graph viewed from right-left. This exact property is used in this solution. As a result, they scan the scores array twice, one from left to right and right to left. In both cases, increment of rewards is done for increase in both directions.
note that max function is used for only one of the passes ( from right to left ) => because overwriting the rewards value is possible only here and hence we use the max function. while traversing from left to right, we’ll be filling up the rewards array for the first time and hence max function isnt needed.
Sunset Views : Algoexpert ; pls see the description on the website. It doesn’t let me copy the text
overview
Given : an array representing the length of buildings
and a variable representing the direction faced by ALL the buildings
to return : the list of indices in ascending order => to whom the sunsets are clearly visible\
for a building to see the sunset, all the buildings after that in the specified direction must be strictly lesser in height.
This is a medium problem on algoexpert ( maybe easy by leetcode standards)
I was able to find the optimal solution by myself, so yayy :) and code was submitted successfully
O(n) and 0(n)
My solution :
if the direction is east => then the last building with index n-1 can definitely see the sunset as there is no buildings blocking it
if the direction is west => then the building with the index 0 can definitely see the sunset as there are no buildings blocking it’s view
My solution’s conceptual overview : depending on the direction, start scanning the array from one of the directions.
maintain a variable (max_height) to record the maximum height of the building we have come across till now.
for east, we scan from the last index to the 0th
as we’re moving from left to right by updating max_height. The current building will be able to view the sunset only if it is taller than the value of max_height
similarly for west, but we scan the array from right to left.
Next solution is based on stack
the basic idea of this approach:
at the end of this approach the stack will have all the indices of the buildings which can view the sunsets clearly
if the direction is east, we start scanning from the left ( opposite of what was done in the previous approach)
for i in loop :
while stack and (building[i] > top of stack)
keep popping // because we’ve found a building //greater than the previous ones and they cannot view //the sunset, so pop them out
append(i) to stack
similary for the other direction
even though there’s a for loop and a while loop inside this, the time complexity is not O(n2)
because just observe the while loop : all this while loop does is pop the indices out of the stack
and each index is pushed into the stack only once.
Therefore the maximum amount of times the pop operation can happen in all the passes of the for loop is N
as a result the total time taken will be 2*n which is O(n)
Nth Fibonacci Number : Algoexpert (easy)
The problem is to find out the nth fibonacci number::
I used the normal recursion method -> worked
this method takes O(2^n) time complexity and O(n) space complexity -> because of stacks used in recursion ( mostly )
write this out as a tree, you’ll understand why it’s 2^n(refer one note too)
T(n) = T(n-1) + T(n-2)
The above was soln 1
Solution 2: in soln 1, notice that fibonaaci(i) is repeatedly calculated
for eg : if n = 5, we’ve to calculate fib(3) for n= 5 as well as for fib(4)
to overcome this problem, we save the answers in an array and use it when needed. so repeated calculation of the same will not be necessary
Time = O(n) and space = O(n) beacuse we use another answers array to store the value of each fib(i)
Solution 3:::this is a smart one, which uses O(n) time and O(1) space by not using the array but by just using the last two fib values => because to calulate the nth fibonacci number, all we require is fib(n-1 ) and fib(n-2)
as we progress from 1 to n in the for loop, we keep updating the two varialbels to reflect the last fib and the last but one fib
Monotonic Array : Medium Problem
Honestly -> I thought this is the easy one in terms of LC standard
Got it working in the first go with optimal time and space complexity :)
basic idea was to have two variables each representing if it’s increasing or decreasing. Initially they are None
if consecutive two numbers are increasing, then we set the increasing variable to True
if consecutive two numbers are decreasing, then we set the decreasing varia
ble to False
then we compare these two determine if they are strictly increasing or decreasing
Basically Monotonic means that the array from left to right should only increase or be the same OR
the array from left to right should only decrease or be the same
Visualize the array in terms of line graph to visualize non increasing and non decreasing
Pls go to algoexpert to check the code
