That's so interesting. I didn't know you could find the closest elements this way if the value being searched for doesn't exist in a binary search. Never would have thought of that.
Instead of setting res in every step; if the element not found in the search loop, you can also return the element that "r" points to. Explanation: In the last step of the loop, all l,m,r pointers will be showing the same position. If the target is bigger than m, then r is the biggest element that is less than target. If target is less than m, then r will be pointed m-1 and r is the biggest element that is less than target. resulting code: def get(self, key: str, timestamp: int) -> str: values = self.keyStore.get(key, []) l, r = 0, len(values) - 1 while l timestamp: r = m - 1 else: return values[m][0] if r!=-1: return values[r][0] return ""
For anyone who may experience the TLE in C++, swift, when you do vector vals = map[key], basically you're copying everything from map to vals, which is O(n). This is language-specific, some languages would return the vector result as a reference while others might return it as value(copy).
As soon as he read the fine print at the end of the problem it was just so clear and I didn't have to watch the rest to solve it. Thanks for being a good explanator hahah
I was racking my brain with this, didn't read or realize that timestamp was in increasing order, I even implement a sort method in the set so that the array was sorted and the get could be done in log n time, but it wasn't enough some test failed because the time keep running out, then I saw that part of the video expecting some fancy algorithm and was like ._. oh? it's already sorted.
in this case I think you can use a priority queue implemented with a binary search tree. you would be able to have get in O(logn) and insert in O(logn)
"Questions to ask in real interviews" - I'd love if you share thoughts on this topic on other problems too! In my experience, it makes a big difference, especially if you can't solve a problem during the interview.
one small mem optimization i ended up making was just replacing the timestamp at the end of backing store if added item was same. so [ add(a,b,1), add(a,b,2) , add(a,b,3) ] in sequence ended with { a : (b,3) } if self.store[key][1] == value: self.store[key][0] = timestamp
@@frankl1 Dict is ordered, but you aren't supposed to rely on that. It used to be unordered, and OrderedDict exists for ordered dictionaries. It was a later patch which changes how dicts are implemented in Python and now they are ordered by default sort of by accident. I recommend the talk "Modern Dictionaries" by Raymond Hettinger.
there seems to be a problem in your get function, you missed to check if the given key actually exists in the map or not here, have a look at my code which is almost similar to yours but with the check void set(string key, string value, int timestamp) { mp[key].push_back(make_pair(value,timestamp)); }
string get(string key, int timestamp) { // run binary search on the value list if(mp.find(key)==mp.end())return "";
This video help me how to find optimal solution. What is my first solution: Implement binary search and if value is not finded just go from the end of array,becouse last element is with highest timestamp and check if we can find value < then timestamp. So now you can see this is time compl of O(n) + O(log n) but O(n) is dominant then time complexity in worst case will be O(n),but in general they will be better but we are looking for worst case.
I recently took a CodeSignal online assessment that contained this problem but with additional method compare_and_set which checks if the current value stored at key equals expected_value, and if that condition is true only then do we update the key to store new_value. Man I wish I had seen this video a week before. Oh well, you live and you learn.
So we assume the input timestamp(s) are always ascending for each key/value? For example they cannot give you ["foo", "bar", 4] then ["foo", "bar", 1]?
Why did you choose to save the zeroth element of the value dictionary and not the 1st which satisfied the condition of time stamp being less than or equal to queried time stamp?
Well, think of this way. The goal of this problem is to find the value that matches the given timestamp. If that given timstamp doesn't exit in the hashMap's key, then the closest one. You can write it your way: if values[mid][1] < timestamp: res = values[mid][0] l = m + 1 elif values[mid][1] < timestamp: r = m -1 else: res = values[mid][0] break Or you can do it NeetCode's way: if values[mid][1]
of course for lists that are much much bigger in size the binary search option is still better with a time complexity of O(log n), but i feel like there's a much simpler approach that is O(n) at worst. since the timestamps are always in increasing order, we can iterate through the timestamps backwards and return the value whose timestamp is less than or equal to the input timestamp, otherwise return an empty string. class TimeMap: def __init__(self): self.pairs = {} def set(self, key: str, value: str, timestamp: int) -> None: if key in self.pairs: self.pairs[key].append((value, timestamp)) else: self.pairs[key] = [(value, timestamp)] def get(self, key: str, timestamp: int) -> str: if key not in self.pairs: return "" else: for values in reversed(self.pairs[key]): if values[1]
I am getting TLE for same solution in Swift, anyone can help ? I have written down the solution below. class TimeMap { private var dictionary = [String: [(Int,String)]]() init(){} func set(_ key: String, _ value: String, _ timestamp: Int) { var list = dictionary[key] ?? [] list.append((timestamp, value)) dictionary[key] = list } func get(_ key: String, _ timestamp: Int) -> String { var result = "" let array = dictionary[key, default: []] var left = 0, right = array.count-1 while left
I think there is no need to use binary search because according to the condition, the timestamps are strictly set in increasing order, so the right most index has the max timestamp which you can compare it with the current timestamp, so you could condense the get function like: def get(self, key, timestamp): res = " " values = self.store.get(key, []) if values[-1][1]
the whole point of binary search is to continually search for the nearest smallest value, if the given timestamp is smaller does that mean the nearest smallest value cannot be found? I don't think so.
@@jointcc2 oh yeah i though that the gets operations where going to ask for time values in increasing order as the example but in reality it could ask for any time value
this is the answer that chatgpt gave me, and its shorter and 95% faster than every other answer... import bisect from collections import defaultdict class TimeMap: def __init__(self): self.data = defaultdict(list) def set(self, key, value, timestamp): self.data[key].append((timestamp, value)) def get(self, key, timestamp): values = self.data[key] index = bisect.bisect_right(values, (timestamp, chr(127))) if index: return values[index - 1][1] return "" edit: I understand why he didnt do it this way now, he said "he didnt want to abuse java" and wanted it to be more similar to other languages
At first I thought of a TreeMap. Then I saw your video and thought otherwise. Then I realized I discarded my initial idea just because I thought that to be something like a brute force solution. Taking advantage of the fact that TreeMap implements NavigableMap I used floorEntry() to spare myself all that binary search clutter.
That's so interesting. I didn't know you could find the closest elements this way if the value being searched for doesn't exist in a binary search. Never would have thought of that.
Instead of setting res in every step; if the element not found in the search loop, you can also return the element that "r" points to. Explanation: In the last step of the loop, all l,m,r pointers will be showing the same position. If the target is bigger than m, then r is the biggest element that is less than target. If target is less than m, then r will be pointed m-1 and r is the biggest element that is less than target.
resulting code:
def get(self, key: str, timestamp: int) -> str:
values = self.keyStore.get(key, [])
l, r = 0, len(values) - 1
while l timestamp:
r = m - 1
else:
return values[m][0]
if r!=-1:
return values[r][0]
return ""
I watched the video for this one specifically because I wanted to see a nicer way of finding a close value! Gotta love this guy.
Exactly. There are 2 types of Binary Search, one is to find the element and the other is to find the range (like here, range (
For anyone who may experience the TLE in C++, swift, when you do vector vals = map[key], basically you're copying everything from map to vals, which is O(n). This is language-specific,
some languages would return the vector result as a reference while others might return it as value(copy).
Thank you for this comment! I got it working when I used - vector& vals = map[key]
thanks bro
i hated this problem but ur explanation made it less complicated ty
As soon as he read the fine print at the end of the problem it was just so clear and I didn't have to watch the rest to solve it.
Thanks for being a good explanator hahah
you are a leetcode legend!...i have watched a couple of your leetcode videos solution
Thanks :)
Damn I love this problem and your explaination, thank you man!
Liked again and commenting to support!
Huge thanks!! That 'strictly increasing' is killing me!! LOL
13:49 i've forgot `left
Nice. And for binary search, could just use right pointer at end of loop -- as that should be the closest value less than target
13:18 In line 13. I couldn't get it, the function should call itself infinite times. How?
Very concise solution and easy to understand. Thank you!
I was racking my brain with this, didn't read or realize that timestamp was in increasing order, I even implement a sort method in the set so that the array was sorted and the get could be done in log n time, but it wasn't enough some test failed because the time keep running out, then I saw that part of the video expecting some fancy algorithm and was like ._. oh? it's already sorted.
yea me2 lol i tried sorting it
same, i also failed after 44/53 test cases because of sorting
in this case I think you can use a priority queue implemented with a binary search tree. you would be able to have get in O(logn) and insert in O(logn)
"Questions to ask in real interviews" - I'd love if you share thoughts on this topic on other problems too! In my experience, it makes a big difference, especially if you can't solve a problem during the interview.
Yes much needed. Questions to ask during interview
I got this problem on an interview, if only I was subscribed to you back then.
for real? can you share which company?
@@nguyentuan1990 it was for soti
which company plz
It was Soti
one small mem optimization i ended up making was just replacing the timestamp at the end of backing store if added item was same. so [ add(a,b,1), add(a,b,2) , add(a,b,3) ] in sequence ended with { a : (b,3) }
if self.store[key][1] == value:
self.store[key][0] = timestamp
Any one know how did he condense that line at 11:11?
i don't understand why the nested part can't be another hashmap like a nested dictionary. in the nested dictionary, timestamp is a string
It's because a dictionary is unordered, and you need an ordered data structure in order to apply binary search
@@frankl1 some languages dict is ordered ie python3
@@enterprisecloudnative8757 I didn't know that, do you have any reference to share ?
@@frankl1 Dict is ordered, but you aren't supposed to rely on that. It used to be unordered, and OrderedDict exists for ordered dictionaries. It was a later patch which changes how dicts are implemented in Python and now they are ordered by default sort of by accident. I recommend the talk "Modern Dictionaries" by Raymond Hettinger.
Thanks neetcode , Presentation is really good
mapmp;
void set(string key, string value, int timestamp) {
mp[key].push_back({value,timestamp});
}
string get(string key, int timestamp) {
auto it=mp[key];
int high=it.size()-1;
int low=0;
string ans="";
while(low
there seems to be a problem in your get function, you missed to check if the given key actually exists in the map or not
here, have a look at my code which is almost similar to yours but with the check
void set(string key, string value, int timestamp) {
mp[key].push_back(make_pair(value,timestamp));
}
string get(string key, int timestamp) {
// run binary search on the value list
if(mp.find(key)==mp.end())return "";
string res="";
int l=0,h=mp[key].size()-1;
while(l
This video help me how to find optimal solution.
What is my first solution:
Implement binary search and if value is not finded just go from the end of array,becouse last element is with highest timestamp and check if we can find value < then timestamp.
So now you can see this is time compl of O(n) + O(log n) but O(n) is dominant then time complexity in worst case will be O(n),but in general they will be better but we are looking for worst case.
I don't wanna abuse Python too much to make everything so easy. lol
I really love your videos! Could you upload a video for "843. Guess the Word"? (Top google question)
I recently took a CodeSignal online assessment that contained this problem but with additional method compare_and_set which checks if the current value stored at key equals expected_value, and if that condition is true only then do we update the key to store new_value. Man I wish I had seen this video a week before. Oh well, you live and you learn.
So we assume the input timestamp(s) are always ascending for each key/value? For example they cannot give you ["foo", "bar", 4] then ["foo", "bar", 1]?
No its always ascending, as mentioned in the question.
Great explanation, thank you!
love this question!
Why did you choose to save the zeroth element of the value dictionary and not the 1st which satisfied the condition of time stamp being less than or equal to queried time stamp?
The 0th element is the value that you return but the 1st value is the timestamp
I am getting time limit exceeded with this solution or it is just me? thanks
Same time limit exceeded
Thank you very much man
Nice solution. Can you please do a video on 68. Text Justification from leetcode?
Sure, will try to do it this week
@@NeetCode have you given text justification a try haha
what is the justification for this request? :P
This problem statement is really badly written
Awesome explanation
Can anyone explain why we write the binary search that way? I usually have 3 conditions in my binary search
Well, think of this way.
The goal of this problem is to find the value that matches the given timestamp. If that given timstamp doesn't exit in the hashMap's key, then the closest one.
You can write it your way:
if values[mid][1] < timestamp:
res = values[mid][0]
l = m + 1
elif values[mid][1] < timestamp:
r = m -1
else:
res = values[mid][0]
break
Or you can do it NeetCode's way:
if values[mid][1]
yeah i was able to solve this myself once i saw that constraint.
Thank you!! :)
Bisect Right. Nice.
if I write values =self.store[key] instead of self.store.get(keys,[]), the run time difference is huge, why is get() so much faster ??
leetcode run time is not precise. Did you run it multiple times and its really different? It doesnt make much sense
The answer will be wrong if I gave
while (l
it will be wrong in the case where the exact value doesn't exist. You seem to never return the closest value below as the problem desires.
Thanks
The goat fr
bro I didn't even know it was a binary search
What about java code...?
"I don't want to make it too easy"
I'm getting a TLE for this solution
understood
of course for lists that are much much bigger in size the binary search option is still better with a time complexity of O(log n), but i feel like there's a much simpler approach that is O(n) at worst. since the timestamps are always in increasing order, we can iterate through the timestamps backwards and return the value whose timestamp is less than or equal to the input timestamp, otherwise return an empty string.
class TimeMap:
def __init__(self):
self.pairs = {}
def set(self, key: str, value: str, timestamp: int) -> None:
if key in self.pairs:
self.pairs[key].append((value, timestamp))
else:
self.pairs[key] = [(value, timestamp)]
def get(self, key: str, timestamp: int) -> str:
if key not in self.pairs:
return ""
else:
for values in reversed(self.pairs[key]):
if values[1]
wouldn' t it be easier to use a TreeMap as the Values method?
So something like Map.
You have access to "lowerKey" method as well.
thats what i was thinking but insertion is nLogn
nice bro
I am getting TLE for same solution in Swift, anyone can help ? I have written down the solution below.
class TimeMap {
private var dictionary = [String: [(Int,String)]]()
init(){}
func set(_ key: String, _ value: String, _ timestamp: Int) {
var list = dictionary[key] ?? []
list.append((timestamp, value))
dictionary[key] = list
}
func get(_ key: String, _ timestamp: Int) -> String {
var result = ""
let array = dictionary[key, default: []]
var left = 0, right = array.count-1
while left
Your language could be the hurdle, change your language to some mainstreams language
I think that problem should be easy
I think there is no need to use binary search because according to the condition, the timestamps are strictly set in increasing order, so the right most index has the max timestamp which you can compare it with the current timestamp, so you could condense the get function like:
def get(self, key, timestamp):
res = " "
values = self.store.get(key, [])
if values[-1][1]
the whole point of binary search is to continually search for the nearest smallest value, if the given timestamp is smaller does that mean the nearest smallest value cannot be found? I don't think so.
@@jointcc2 oh yeah i though that the gets operations where going to ask for time values in increasing order as the example but in reality it could ask for any time value
Time Limit Exceeded with same solution
I dont get it
Hash map to store all the values for a key and binary search to find time stamp as list is sorted
@@dev_among_men still dont get it
Try to do this question, Find index of element in sorted array if not present get index of the number just smaller than it.
@@masternobody1896 would help if you mentioned which aspect you didn't get.
@@hemantkarasala5767 i guess i need to do some basic leetcode to understand
this is the answer that chatgpt gave me, and its shorter and 95% faster than every other answer...
import bisect
from collections import defaultdict
class TimeMap:
def __init__(self):
self.data = defaultdict(list)
def set(self, key, value, timestamp):
self.data[key].append((timestamp, value))
def get(self, key, timestamp):
values = self.data[key]
index = bisect.bisect_right(values, (timestamp, chr(127)))
if index:
return values[index - 1][1]
return ""
edit: I understand why he didnt do it this way now, he said "he didnt want to abuse java" and wanted it to be more similar to other languages
At first I thought of a TreeMap. Then I saw your video and thought otherwise. Then I realized I discarded my initial idea just because I thought that to be something like a brute force solution. Taking advantage of the fact that TreeMap implements NavigableMap I used floorEntry() to spare myself all that binary search clutter.