This is the simplest approach: def largestRange(array): main_rng=[] for i in range(len(array)): rng=[] a=array[i] while a in array: rng.append(a) a=a+1 if len(main_rng)
I just started to learn Python by myself (by watching videos, researching, etc), and these kind of "tutorials" make me fall even deeper in love with coding. I want to work something like machine learning combining with complex and very humanoid prosthesis (legs or arms for example). Thank you for your videos, Tim!
it's actually good. machine-learning growing up recently and i have been learning it for about 1 year now and i love it so much it;s not that hard but needs time and focusing on it.
Birreliant and a very efficient solution. However, for the case where the longest sequence is 1, this would still be O(n*n), so it's only O(kn) or O(n) if it is guaranteed that k
Small optimization: we could use Hashset instead of Hashmap and delete seen values from there. We also could declare set capacity to avoid Hashset resizes during population and optimize performance: public int[] longestRange(int[] arr) { // Declare a hashset capacity of 125% mof arr.length to avoid hashset resizes and optimize performance Set set = new HashSet((int) (arr.length / 0.75) + 1); // Populate hashset for(int element : arr) { set.add(element); } int left = 0; int right = 0; for(int element : arr) { if(!set.contains(element)) { continue; } int leftElement = element; int rightElement = element; while (set.contains(leftElement - 1)) { set.remove(leftElement); leftElement--; } while (set.contains(rightElement + 1)) { set.remove(rightElement); rightElement++; } set.remove(element); if(rightElement - leftElement > right - left) { left = leftElement; right = rightElement; } } return new int[]{ left, right }; }
This is what I got: 6 array = [1,5,8,5,9,3,2,7,3,10] 7 sorted_array = [] 8 - for i in range(len(array)): 9 value = min(array) 10 sorted_array.append(value) 11 array.remove(value) 12 13 print(sorted_array)
Alternative x = [1,11,3,0,15,5,2,4,10,7,12,6,16,17] result = [] all_range = [] strt = min(x) fin = max(x)+2 for num in range(strt,fin): if num in x: result.append(num) else: if len(result)>1: all_range.append(result) result = [] continue a = [] for i in all_range: if len(i)>len(a): a=i print(a)
Starting with the dictionary comprehension makes it a 2n solution. I think it's possible to keep it just n. Start by initializing an empty dictionary. For each integer in the array, look above and below in the dictionary. If neither exists, add n to the dict with a key of 0. If a number exists below with a value of 0, change that value to 1 and insert n into the dictionary with a value of -1. You get the idea there. Same with above, or with above and below if it joins two previously separate segments. Of course, keep track of the max in a separate integer variable as you go so that you don't have to iterate through the dictionary after you're done. def find_max_consecutive_length(array): coords = dict() current_max = 0 for n in array: if n - 1 in coords: min_value = (n - 1) + coords[n - 1] del coords[n - 1] else: min_value = n if n + 1 in coords: max_value = (n + 1) + coords[n + 1] del coords[n + 1] else: max_value = n current_max = max(current_max, max_value - min_value + 1) coords[min_value] = max_value - min_value coords[max_value] = min_value - max_value return current_max
This code is simpler than the explained one.. def largestRange(array): main_rng=[] for i in range(len(array)): rng=[] a=array[i] while a in array: rng.append(a) a=a+1 if len(main_rng)
a in array is an O(n) check (arrays are not sets!), and the loop on i is O(n) as well, so this is at least O(n^2) which is worse than sorting and much worse than the explanation in the video.
Your code looks Beautiful dude! ❤ I have just started programming and following in my code with I think worst Time Complexity, I tried to solve it before watching the solution, I just watched the problem and it took me a day to solve this, and when I watched your solution, I mean like it was so beautiful, thank you so much for providing these videos. t = int(input()) #no of test cases for _ in range(t): array = list(map(int, input().split())) sorted_array = [] while len(array): sorted_array.append(min(array)) array.remove(min(array)) range_dict = {} length = len(sorted_array) i = 0 j = i + 1 while j < len(sorted_array): range_list = [] while j = 2: range_create = [range_list[0],range_list[-1]] diff = range_create[-1] - range_create[0] range_dict[diff] = list(range_create) print(range_dict[max(range_dict)])
Here's another linear approach in JS. It works in one pass (no pre-initialization of a hash table), but it keeps more information in the table. It's a simplified union-find function largestRange(arr) { if (arr.length === 0) return [] const rangeMap = {} // { num => [lo, hi] } let largestRange = [arr[0], arr[0]] for (num of arr) { if (rangeMap[num]) continue; rangeMap[num] = [num,num] // init with default range if (rangeMap[num-1]) largestRange = union(num, num-1, rangeMap, largestRange) // union num with left if (rangeMap[num+1]) largestRange = union(num, num+1, rangeMap, largestRange) // union num with right } return largestRange } function union(x, y, map, range) { let newLo = Math.min(map[x][0], map[y][0]) let newHi = Math.max(map[x][1], map[y][1]) map[newLo] = [newLo, newHi] // keep endpoints of ranges up to date in map map[newHi] = [newLo, newHi] return newHi-newLo > range[1]-range[0] ? [newLo,newHi] : range // return newLargestRange }
You can save the +=1 and -=1 outside the loop (4 lines ) by doing while(left_count-1) in numbers: and reversing the lines inside the loop. But maybe it is less readable.. so whatever. nice solution and explanation :)
important thing with this solution is that we are making use of extra information which is specific to numbers i.e. x-1, x, x+1 and not really present in the input data
Hi, Great Content: Think you might be hashing again to 1 when you process key 4. Sorry for all the output: easiest way to explain. {11: 0, 7: 0, 3: 0, 4: 0, 2: 0, 1: 0, 0: 0} PROCESSING NUMBER 11 FOR HASH 0 number= {11: 0, 7: 0, 3: 0, 4: 0, 2: 0, 1: 0, 0: 0},ONE LEFT left_counter=10,ONE RIGHT right_counter=12 ----LEFT COUNTER INCREMENTED TO =11 PROCESSING NUMBER 7 FOR HASH 0 number= {11: 0, 7: 0, 3: 0, 4: 0, 2: 0, 1: 0, 0: 0},ONE LEFT left_counter=6,ONE RIGHT right_counter=8 ----LEFT COUNTER INCREMENTED TO =7 PROCESSING NUMBER 3 FOR HASH 0 number= {11: 0, 7: 0, 3: 0, 4: 0, 2: 0, 1: 0, 0: 0},ONE LEFT left_counter=2,ONE RIGHT right_counter=4 ------------ONE LEFT left_counter=2 FOUND IN ARRAY ------------ONE LEFT left_counter=2 FOUND IN ARRAY AND MARKED AS PROCESSED number= {11: 0, 7: 0, 3: 0, 4: 0, 2: 1, 1: 0, 0: 0} ------------LEFT COUNTER DECREMENTED TO =1 ------------ONE LEFT left_counter=1 FOUND IN ARRAY ------------ONE LEFT left_counter=1 FOUND IN ARRAY AND MARKED AS PROCESSED number= {11: 0, 7: 0, 3: 0, 4: 0, 2: 1, 1: 1, 0: 0} ------------LEFT COUNTER DECREMENTED TO =0 ------------ONE LEFT left_counter=0 FOUND IN ARRAY ------------ONE LEFT left_counter=0 FOUND IN ARRAY AND MARKED AS PROCESSED number= {11: 0, 7: 0, 3: 0, 4: 0, 2: 1, 1: 1, 0: 1} ------------LEFT COUNTER DECREMENTED TO =-1 ----LEFT COUNTER INCREMENTED TO =0 PROCESSING NUMBER 4 FOR HASH 0 number= {11: 0, 7: 0, 3: 0, 4: 0, 2: 1, 1: 1, 0: 1},ONE LEFT left_counter=3,ONE RIGHT right_counter=5 ------------ONE LEFT left_counter=3 FOUND IN ARRAY ------------ONE LEFT left_counter=3 FOUND IN ARRAY AND MARKED AS PROCESSED number= {11: 0, 7: 0, 3: 1, 4: 0, 2: 1, 1: 1, 0: 1} ------------LEFT COUNTER DECREMENTED TO =2 ------------ONE LEFT left_counter=2 FOUND IN ARRAY ------------ONE LEFT left_counter=2 FOUND IN ARRAY AND MARKED AS PROCESSED number= {11: 0, 7: 0, 3: 1, 4: 0, 2: 1, 1: 1, 0: 1} ------------LEFT COUNTER DECREMENTED TO =1 ------------ONE LEFT left_counter=1 FOUND IN ARRAY ------------ONE LEFT left_counter=1 FOUND IN ARRAY AND MARKED AS PROCESSED number= {11: 0, 7: 0, 3: 1, 4: 0, 2: 1, 1: 1, 0: 1} ------------LEFT COUNTER DECREMENTED TO =0 ------------ONE LEFT left_counter=0 FOUND IN ARRAY ------------ONE LEFT left_counter=0 FOUND IN ARRAY AND MARKED AS PROCESSED number= {11: 0, 7: 0, 3: 1, 4: 0, 2: 1, 1: 1, 0: 1} ------------LEFT COUNTER DECREMENTED TO =-1 ----LEFT COUNTER INCREMENTED TO =0
Hey Tim, your video was very good with the code and explanation I just tried this one myself and got the code much easier 😄 It's working perfectly😁 Here's the code: def LongestRange(arr): num = arr[0] longwidth = 0 for i in arr: width = 0 while width+i+1 in arr: width+=1 if width > longwidth: longwidth = width num = i return [num,num+longwidth] Did i miss something?🤔
@Tech With Tim Building a hash table that ensures O(1) lookup (worst case) with n Elements is not possible in O(n) worst case time. The complete Algorithm does not run in O(n) worst case!
Simplest approach def largestRange(array): main_rng=[] for i in range(len(array)): rng=[] a=array[i] while a in array: rng.append(a) a=a+1 if len(main_rng)
Thank you for the content! I think I just found one of the most easy to understand explanations. Love the idea with drawing on the board. Thanks again!
The trivial solution is O(n) in space (the input array) and O(n*log n) in time by sorting (O(n*log n)) the list and then simply scanning it once while remembering the longest sequence seen so far. The fancy alternative would use a hash table of all sequences seen so far, indexed by the beginning of each sequence. The top of each sequence is also indexed, with the negative length of the sequence. This is also O(n) space but should approach O(n) in time since it can be done with a single streaming pass over the input. It is similar to how I merge contour line segments generated from a triangulated lidar point cloud.
But why can't I use some sorting of O(n). ? Since I can find the range by first finding the max value there are sorting algos of O(n) this way I can use first approach as well in o(n
just use sort.... u have a nested loop which makes ur program n^2 if im not mistaken. u can do this by sorting and then a single for loop to keep it at nlogn instead of n^2
it doesnt make it n^2 because the nested loop only iterates through the length of the range not the length of the array. if the range contained every item in the array then all array items would receive a 1 in the hashmap, meaning that the while loop wouldn't be called again.
I think the variable name left_count and right_count should be better named left_local, right_local. Strictly speaking, they are not counts, they are values.
I just started learning Python and thought I was making good progress until I watched this video. I never even heard of a hashtable. Man I feel so far away from even being remotely close to being in a position to apply for a job. How can people pick all this up from zero to hero in less than 6 months all while not even studying 8+ hours a day, everyday? Maybe I should just be a cop or something, idk, this is pretty depressing.
This was wonderful and entertaining to watch. I learned something new (that hashtables search for keys in O (1), but I don't get the difference between array and hashtable search, considering that the underlying search function probably still has to iterate to find that key, same as with array). You made a more difficult problem easier to understand and solve.
Hash tables don’t store elements using index’s in an order. They use a hash function, I don’t know enough to explain the lower level concepts but it allows a look up to happen in an average time o(1), look up how they work! They’re pretty interesting
Can anyone explain how the search for left and right is in O(1)? It's a while loop which in the worst case would have to go through every item. I understand that checking for a specific number is O(1), but if one exists it has to keep going up to n times doesn't it?
What is first number (or numbers in the lists) is the list is very huge like [999999999999, 1, 20]? how many iteration it is going to take in first the while loop of your code?
hey Tim, how about this code? will it work for all the corner cases? a = sorted(map(int, input('Num list: ').split())) Clist = [] for num in a: cons_list = [] while num+1 in a: cons_list.append(num) num += 1 else: if len(cons_list) >= len(Clist): Clist = cons_list print(Clist)
The only thing this doesnt solve is if you have the same range for various numbers, like if you have -3,-4,-5 and 6,7,8 in the same list, technically they're the same, but I guess the lists they give don't specifically have lists with this kind of issue built in....otherwise I guess you could technically make another dictionary that specifies each range and return all of them with the largest range, but that's kind of an extra step and challenge
Wouldn't it be easier to just loop over the list verifying whether the next number is consecutive to the current one (having 2 branches for ascending and descending) and when we reach one that doesn't comply, we mark the end of sequence we save it and compute it's length, then go over the rest of the list and save other start and end point only if the distance is greater. Basic algorithm from 10th grade.
Will that run In O(n)? Also the next number in the sequence doesn’t need to be adjacent. If you think you can do it that way send me your solution I’d like to see it!
@@TechWithTim Oh, I see, thought it had to be adjacent, should've read the description not only listen. Keep doing what you're doing, you're doing great.
Would this not work: def largestRange(l): largerange = [] for i in l: if i+1 in l: largerange.append(i)
return [min(largerange), max(largerange)+1] Furthermore, the question doesn't ask us to use linear time or space complexity; therefore, I believe that we allowed to use different complexities of time and space.
No that won't work. Say you have [2,3,5,6,7,9,10]. Your solution would see 2 and check if 3 is in the list, which it is, so you would have largerange = [2]. Then it will see 3 and check if 4 is in the list, which it's not, so nothing happens. This continues as 5, 6, and 9 are added so you have [2,5,6,9], which gives you the return value of [2,10] instead of the correct [5,7]. In addition, your code runs in O(n^2) time because checking if something is in a list is O(n), and that's happening inside a loop through the list which is also O(n). While the question doesn't explicity state a required efficiency, even a correct O(n^2) solution to this problem would likely fail an interview, as well as on e.g. leetcode, where large datasets are tested and timed.
Hi Tech With Tim, thank you for this very thoughtful tutorial! I noticed that after the two while loops (on lines 11 and 16 respectively) you did not check to see if you had already visited the adjacent numbers ("continue"-ing if so). Does this mean that an O(n^2) solution can pass all test cases as well? Do correct me if I am mistaken, as I am not a Python user.
I think doing ‘number in dictionary’ is same as ‘number in dictionary.keys()’ which is just a list of keys and in worst case it can be in the last position… I’m not sure cuz I’m new to coding but isn’t that O(n^2) itself? I understand that lookup is O(1) ie dictionary[key] but yh… idk man this doesn’t seem like a ‘clean’ O(n) solution. Btw when I say dictionary I mean hashmap
The exercises look great but they are not Python specific, those could be implemented with any programming languages. But, for example, "Implement a cache mechanism with decorators" is a direct Python question. The question is , does Algoexpert have questions that really are Python specific?
@@TechWithTim Thank you for the link. Does this package offer teaching or also problems like Leetcode. I just checked it and it does not look like they have problems, just questions and teaching... Of course thsi was just first look on their page. DO you know if they have Python problems and how many included in that $78 package?
Can anyone pls explain me how the program is taking input. Because it not taking list input from the user. I have tried running this code my computer but it do not work. please help, I am new to the programming.
I don't really like this solution due to corner cases. You can't just do: left_count += 1 and assume that your previous check was good. It might've failed on the first check. I wrote a soln that creates a left/right candidate initialized as the item in the array then checks neighbors def check_neighbor(item, the_dict, direction): print(f'
Entered check_neighbor item: {item}\t direction: {direction}') # print(f'target dict: {the_dict}') cand = item + direction ret_val = None while True: if the_dict.get(cand) is not None: print(f'yup {cand} is in the dict') the_dict[cand] = 1 ret_val = cand cand = cand + direction continue else: print(f'cand: {cand} is not in direction: {direction}') return ret_val
Done with lists and range: l = [0,2,3,4,6,7,8,9,10,12,13] # can ask user input for list too def largestRange(l): ranges=[] temp = [] l.sort() # here l is manually given and sorted start = False for i in range(len(l)-1): if l[i+1]-l[i]==1: if start==False: start=True temp.append(l[i]) temp.append(l[i+1]) else: temp.append(l[i+1]) elif l[i+1]-l[i]!=1 and start==True: start=False ranges.append(temp) temp = [] ranges.append(temp) ranges.sort(key=len) xyz=[] xyz.append(ranges[-1][0]) xyz.append(ranges[-1][-1]) print(xyz)
couldn't we start from the smallest number (using min(array)) in the list and keep removing the elements as they are counted,it might get the program more easy (i guess)
Im starting with developing, can someone confirm if i understood the problem at all and if my code is doing what he supposed to do? problem = [1,11,3,0,15,5,2,4,10,7,12,6] answer, contador = 0 placar =[] def llist(number): global contador, placar, answer for num in number: for nume in number: if nume-7
im a bit confused about the whole left and right thing. lets say we have the list [3 7 8 2 4]. if we go right in the list then yes we find 4, but how does going left find the 2? does it loop until its the starting point?
it finds 2 because it looks in the hash map/dict. we aren't looking in the list for the left right elements, we are looking in the hash-table to see if they exist. we don't care about their position.
at 18:50 you change the less than to less than equal - you never give the explanation for it, and actually it's not needed. Other than that - excellent lecture! :-)
I dont know, in my opinion premature optimisation is root of all evil. You need to ask yourself how much time does a reader of your code take to understand your code. So if you do not know beforehand that this is a bottleneck in performance, I'd rather go simple.
That's right, but you should still be able to write the most efficient solution. In an interview, you would generally write out the simpler but not optimal solution (sorting, in this case), and then write the optimal solution. Then you could discuss the pros and cons of each solution in a practical setting. In the end, you will sometimes be in situations where you need to write optimal code, so they expect you to demonstrate that.
I'm not trying to sound cocky, but this looks really simple, i learned about ranges and that stuff in year 6 and could do this question in my sleep(I have not learned coding but I know a lot about coding and how the languages function, the main part of this question is learning the names of the expressions used to write the algorithm) Someone please confirm if I'm correct? Just saying the algorithm for this question would be easy????
O(n) solution written in Python using set: gist.github.com/AvihayShahar/33e993fe698ba0d3683522cd59d64789 I am poping a number off a set and checking left and right of it in a function. If the range that was found is greater than current, update current and store the range array. Please rate it!
@@TechWithTim Yes I did complicate it a lot I guess XD. I also think that removing items from a set while iterating it is bad programming generally so I guess my solution sucks.
@@TechWithTim I meant there is optional value in range,where you specify steps. so range(0,11) = 0,1,2,3,4,5,6,7,8,9,10 but range(0,11,2) = 0,2,4,6,8,10 and so on.
Tha's cool but are other free methods that are just as good for those who can't afford the $85 plan Project Euler and Leet Code are good free alternatives
If you want access to all the questions on the site use the code "techwithtim" for 15% off. algoexpert.io/techwithtim
This is the simplest approach:
def largestRange(array):
main_rng=[]
for i in range(len(array)):
rng=[]
a=array[i]
while a in array:
rng.append(a)
a=a+1
if len(main_rng)
I just started to learn Python by myself (by watching videos, researching, etc), and these kind of "tutorials" make me fall even deeper in love with coding. I want to work something like machine learning combining with complex and very humanoid prosthesis (legs or arms for example). Thank you for your videos, Tim!
it's actually good. machine-learning growing up recently and i have been learning it for about 1 year now and i love it so much it;s not that hard but needs time and focusing on it.
Is machine learning interesting?
Birreliant and a very efficient solution. However, for the case where the longest sequence is 1, this would still be O(n*n), so it's only O(kn) or O(n) if it is guaranteed that k
Please more of these. This was absolutely amazing!
I want more pls keep uploading this kinda content..
Small optimization: we could use Hashset instead of Hashmap and delete seen values from there. We also could declare set capacity to avoid Hashset resizes during population and optimize performance:
public int[] longestRange(int[] arr) {
// Declare a hashset capacity of 125% mof arr.length to avoid hashset resizes and optimize performance
Set set = new HashSet((int) (arr.length / 0.75) + 1);
// Populate hashset
for(int element : arr) {
set.add(element);
}
int left = 0;
int right = 0;
for(int element : arr) {
if(!set.contains(element)) {
continue;
}
int leftElement = element;
int rightElement = element;
while (set.contains(leftElement - 1)) {
set.remove(leftElement);
leftElement--;
}
while (set.contains(rightElement + 1)) {
set.remove(rightElement);
rightElement++;
}
set.remove(element);
if(rightElement - leftElement > right - left) {
left = leftElement;
right = rightElement;
}
}
return new int[]{
left,
right
};
}
This is what I got:
6 array = [1,5,8,5,9,3,2,7,3,10]
7 sorted_array = []
8 - for i in range(len(array)):
9
value = min(array)
10
sorted_array.append(value)
11
array.remove(value)
12
13 print(sorted_array)
Alternative
x = [1,11,3,0,15,5,2,4,10,7,12,6,16,17]
result = []
all_range = []
strt = min(x)
fin = max(x)+2
for num in range(strt,fin):
if num in x:
result.append(num)
else:
if len(result)>1:
all_range.append(result)
result = []
continue
a = []
for i in all_range:
if len(i)>len(a):
a=i
print(a)
Starting with the dictionary comprehension makes it a 2n solution. I think it's possible to keep it just n.
Start by initializing an empty dictionary. For each integer in the array, look above and below in the dictionary. If neither exists, add n to the dict with a key of 0. If a number exists below with a value of 0, change that value to 1 and insert n into the dictionary with a value of -1. You get the idea there. Same with above, or with above and below if it joins two previously separate segments. Of course, keep track of the max in a separate integer variable as you go so that you don't have to iterate through the dictionary after you're done.
def find_max_consecutive_length(array):
coords = dict()
current_max = 0
for n in array:
if n - 1 in coords:
min_value = (n - 1) + coords[n - 1]
del coords[n - 1]
else:
min_value = n
if n + 1 in coords:
max_value = (n + 1) + coords[n + 1]
del coords[n + 1]
else:
max_value = n
current_max = max(current_max, max_value - min_value + 1)
coords[min_value] = max_value - min_value
coords[max_value] = min_value - max_value
return current_max
Doesn't work
Initially insert 4,3 into hash, then insert 2.
H(2)=0
H(3)=1
H(4)=1
0(2n) is the same as a 0(n)
one of the best videos on this subject. Congratulations!
This code is simpler than the explained one..
def largestRange(array):
main_rng=[]
for i in range(len(array)):
rng=[]
a=array[i]
while a in array:
rng.append(a)
a=a+1
if len(main_rng)
a in array is an O(n) check (arrays are not sets!), and the loop on i is O(n) as well, so this is at least O(n^2) which is worse than sorting and much worse than the explanation in the video.
Your code looks Beautiful dude! ❤
I have just started programming and following in my code with I think worst Time Complexity, I tried to solve it before watching the solution, I just watched the problem and it took me a day to solve this, and when I watched your solution, I mean like it was so beautiful, thank you so much for providing these videos.
t = int(input()) #no of test cases
for _ in range(t):
array = list(map(int, input().split()))
sorted_array = []
while len(array):
sorted_array.append(min(array))
array.remove(min(array))
range_dict = {}
length = len(sorted_array)
i = 0
j = i + 1
while j < len(sorted_array):
range_list = []
while j = 2:
range_create = [range_list[0],range_list[-1]]
diff = range_create[-1] - range_create[0]
range_dict[diff] = list(range_create)
print(range_dict[max(range_dict)])
Here's another linear approach in JS. It works in one pass (no pre-initialization of a hash table), but it keeps more information in the table. It's a simplified union-find
function largestRange(arr) {
if (arr.length === 0) return []
const rangeMap = {} // { num => [lo, hi] }
let largestRange = [arr[0], arr[0]]
for (num of arr) {
if (rangeMap[num]) continue;
rangeMap[num] = [num,num] // init with default range
if (rangeMap[num-1]) largestRange = union(num, num-1, rangeMap, largestRange) // union num with left
if (rangeMap[num+1]) largestRange = union(num, num+1, rangeMap, largestRange) // union num with right
}
return largestRange
}
function union(x, y, map, range) {
let newLo = Math.min(map[x][0], map[y][0])
let newHi = Math.max(map[x][1], map[y][1])
map[newLo] = [newLo, newHi] // keep endpoints of ranges up to date in map
map[newHi] = [newLo, newHi]
return newHi-newLo > range[1]-range[0] ? [newLo,newHi] : range // return newLargestRange
}
You can save the +=1 and -=1 outside the loop (4 lines ) by doing while(left_count-1) in numbers: and reversing the lines inside the loop. But maybe it is less readable.. so whatever. nice solution and explanation :)
wish there were more of these Difficulty:Hard solutions. 10/10 video 👍
11:53
TH-cam algorithm: Demonetized it is
important thing with this solution is that we are making use of extra information which is specific to numbers i.e. x-1, x, x+1 and not really present in the input data
Hi, Great Content: Think you might be hashing again to 1 when you process key 4. Sorry for all the output: easiest way to explain.
{11: 0, 7: 0, 3: 0, 4: 0, 2: 0, 1: 0, 0: 0}
PROCESSING NUMBER 11 FOR HASH 0 number= {11: 0, 7: 0, 3: 0, 4: 0, 2: 0, 1: 0, 0: 0},ONE LEFT left_counter=10,ONE RIGHT right_counter=12
----LEFT COUNTER INCREMENTED TO =11
PROCESSING NUMBER 7 FOR HASH 0 number= {11: 0, 7: 0, 3: 0, 4: 0, 2: 0, 1: 0, 0: 0},ONE LEFT left_counter=6,ONE RIGHT right_counter=8
----LEFT COUNTER INCREMENTED TO =7
PROCESSING NUMBER 3 FOR HASH 0 number= {11: 0, 7: 0, 3: 0, 4: 0, 2: 0, 1: 0, 0: 0},ONE LEFT left_counter=2,ONE RIGHT right_counter=4
------------ONE LEFT left_counter=2 FOUND IN ARRAY
------------ONE LEFT left_counter=2 FOUND IN ARRAY AND MARKED AS PROCESSED
number= {11: 0, 7: 0, 3: 0, 4: 0, 2: 1, 1: 0, 0: 0}
------------LEFT COUNTER DECREMENTED TO =1
------------ONE LEFT left_counter=1 FOUND IN ARRAY
------------ONE LEFT left_counter=1 FOUND IN ARRAY AND MARKED AS PROCESSED
number= {11: 0, 7: 0, 3: 0, 4: 0, 2: 1, 1: 1, 0: 0}
------------LEFT COUNTER DECREMENTED TO =0
------------ONE LEFT left_counter=0 FOUND IN ARRAY
------------ONE LEFT left_counter=0 FOUND IN ARRAY AND MARKED AS PROCESSED
number= {11: 0, 7: 0, 3: 0, 4: 0, 2: 1, 1: 1, 0: 1}
------------LEFT COUNTER DECREMENTED TO =-1
----LEFT COUNTER INCREMENTED TO =0
PROCESSING NUMBER 4 FOR HASH 0 number= {11: 0, 7: 0, 3: 0, 4: 0, 2: 1, 1: 1, 0: 1},ONE LEFT left_counter=3,ONE RIGHT right_counter=5
------------ONE LEFT left_counter=3 FOUND IN ARRAY
------------ONE LEFT left_counter=3 FOUND IN ARRAY AND MARKED AS PROCESSED
number= {11: 0, 7: 0, 3: 1, 4: 0, 2: 1, 1: 1, 0: 1}
------------LEFT COUNTER DECREMENTED TO =2
------------ONE LEFT left_counter=2 FOUND IN ARRAY
------------ONE LEFT left_counter=2 FOUND IN ARRAY AND MARKED AS PROCESSED
number= {11: 0, 7: 0, 3: 1, 4: 0, 2: 1, 1: 1, 0: 1}
------------LEFT COUNTER DECREMENTED TO =1
------------ONE LEFT left_counter=1 FOUND IN ARRAY
------------ONE LEFT left_counter=1 FOUND IN ARRAY AND MARKED AS PROCESSED
number= {11: 0, 7: 0, 3: 1, 4: 0, 2: 1, 1: 1, 0: 1}
------------LEFT COUNTER DECREMENTED TO =0
------------ONE LEFT left_counter=0 FOUND IN ARRAY
------------ONE LEFT left_counter=0 FOUND IN ARRAY AND MARKED AS PROCESSED
number= {11: 0, 7: 0, 3: 1, 4: 0, 2: 1, 1: 1, 0: 1}
------------LEFT COUNTER DECREMENTED TO =-1
----LEFT COUNTER INCREMENTED TO =0
Hey Tim,
your video was very good with the code and explanation
I just tried this one myself and got the code much easier 😄
It's working perfectly😁
Here's the code:
def LongestRange(arr):
num = arr[0]
longwidth = 0
for i in arr:
width = 0
while width+i+1 in arr:
width+=1
if width > longwidth:
longwidth = width
num = i
return [num,num+longwidth]
Did i miss something?🤔
Great video, well explained. I like the way you break down these problems.
@Tech With Tim Building a hash table that ensures O(1) lookup (worst case) with n Elements is not possible in O(n) worst case time. The complete Algorithm does not run in O(n) worst case!
Oops! Should have said a average time!
Simplest approach
def largestRange(array):
main_rng=[]
for i in range(len(array)):
rng=[]
a=array[i]
while a in array:
rng.append(a)
a=a+1
if len(main_rng)
Thank you for the content! I think I just found one of the most easy to understand explanations. Love the idea with drawing on the board. Thanks again!
The trivial solution is O(n) in space (the input array) and O(n*log n) in time by sorting (O(n*log n)) the list and then simply scanning it once while remembering the longest sequence seen so far. The fancy alternative would use a hash table of all sequences seen so far, indexed by the beginning of each sequence. The top of each sequence is also indexed, with the negative length of the sequence. This is also O(n) space but should approach O(n) in time since it can be done with a single streaming pass over the input. It is similar to how I merge contour line segments generated from a triangulated lidar point cloud.
But why can't I use some sorting of O(n). ? Since I can find the range by first finding the max value there are sorting algos of O(n) this way I can use first approach as well in o(n
just use sort.... u have a nested loop which makes ur program n^2 if im not mistaken. u can do this by sorting and then a single for loop to keep it at nlogn instead of n^2
it doesnt make it n^2 because the nested loop only iterates through the length of the range not the length of the array. if the range contained every item in the array then all array items would receive a 1 in the hashmap, meaning that the while loop wouldn't be called again.
Nice logic, I solved it using an alternate approach using disjoint set technique
I think the variable name left_count and right_count should be better named left_local, right_local. Strictly speaking, they are not counts, they are values.
what should this return print(largestRange([8, 9, 3, 5, 4, 7]))? [3,5] or [7,9]? they both have the largest range. Above returns [3,5].
what an elegant solution!
I just started learning Python and thought I was making good progress until I watched this video. I never even heard of a hashtable. Man I feel so far away from even being remotely close to being in a position to apply for a job. How can people pick all this up from zero to hero in less than 6 months all while not even studying 8+ hours a day, everyday? Maybe I should just be a cop or something, idk, this is pretty depressing.
holy moly man, you really impressed me with this solution, greetings
That Tim Stuff..... always cool
Tim you are the best. Thanks dude
This was wonderful and entertaining to watch. I learned something new (that hashtables search for keys in O (1), but I don't get the difference between array and hashtable search, considering that the underlying search function probably still has to iterate to find that key, same as with array). You made a more difficult problem easier to understand and solve.
Hash tables don’t store elements using index’s in an order. They use a hash function, I don’t know enough to explain the lower level concepts but it allows a look up to happen in an average time o(1), look up how they work! They’re pretty interesting
Can anyone explain how the search for left and right is in O(1)? It's a while loop which in the worst case would have to go through every item. I understand that checking for a specific number is O(1), but if one exists it has to keep going up to n times doesn't it?
Bro which compiler you are using
More of these please
What is first number (or numbers in the lists) is the list is very huge like [999999999999, 1, 20]? how many iteration it is going to take in first the while loop of your code?
hey Tim, how about this code? will it work for all the corner cases?
a = sorted(map(int, input('Num list: ').split()))
Clist = []
for num in a:
cons_list = []
while num+1 in a:
cons_list.append(num)
num += 1
else:
if len(cons_list) >= len(Clist):
Clist = cons_list
print(Clist)
It's crazy that people are using apps like Coding Interview Champ to solve these LeetCode interview problems during the coding interview
The only thing this doesnt solve is if you have the same range for various numbers, like if you have -3,-4,-5 and 6,7,8 in the same list, technically they're the same, but I guess the lists they give don't specifically have lists with this kind of issue built in....otherwise I guess you could technically make another dictionary that specifies each range and return all of them with the largest range, but that's kind of an extra step and challenge
Love your walkthroughs Tim
Hey, your solution is much better than algo expert's one, better you start a new webpage I will defenitely subscribe your webpage.
doesn't seems you need variable left and right, you can just use right_count - left_count
You have to return the range, therefore you have to store that somewhere.
Great Video, Great Solution, Great Explanation.
if your right is 4 and left is 0, then 4-0 = 4 but it needs to be 5 as 0,1,2,3,4
Great explanation!
Thank you for explanation
Thank you for your valuble video ! I think the cost of your solution is O(2n), isn't it ?
Wouldn't it be easier to just loop over the list verifying whether the next number is consecutive to the current one (having 2 branches for ascending and descending) and when we reach one that doesn't comply, we mark the end of sequence we save it and compute it's length, then go over the rest of the list and save other start and end point only if the distance is greater. Basic algorithm from 10th grade.
Will that run In O(n)? Also the next number in the sequence doesn’t need to be adjacent. If you think you can do it that way send me your solution I’d like to see it!
@@TechWithTim Oh, I see, thought it had to be adjacent, should've read the description not only listen.
Keep doing what you're doing, you're doing great.
Would this not work:
def largestRange(l):
largerange = []
for i in l:
if i+1 in l:
largerange.append(i)
return [min(largerange), max(largerange)+1]
Furthermore, the question doesn't ask us to use linear time or space complexity; therefore, I believe that we allowed to use different complexities of time and space.
No that won't work. Say you have [2,3,5,6,7,9,10]. Your solution would see 2 and check if 3 is in the list, which it is, so you would have largerange = [2]. Then it will see 3 and check if 4 is in the list, which it's not, so nothing happens. This continues as 5, 6, and 9 are added so you have [2,5,6,9], which gives you the return value of [2,10] instead of the correct [5,7]. In addition, your code runs in O(n^2) time because checking if something is in a list is O(n), and that's happening inside a loop through the list which is also O(n). While the question doesn't explicity state a required efficiency, even a correct O(n^2) solution to this problem would likely fail an interview, as well as on e.g. leetcode, where large datasets are tested and timed.
great video. thank you
learnt more in 22:04 mins than i did during my whole time in college .
Thanks a lot , luved this solution .
I want more of these videos
Hi Tech With Tim, thank you for this very thoughtful tutorial! I noticed that after the two while loops (on lines 11 and 16 respectively) you did not check to see if you had already visited the adjacent numbers ("continue"-ing if so). Does this mean that an O(n^2) solution can pass all test cases as well? Do correct me if I am mistaken, as I am not a Python user.
I think doing ‘number in dictionary’ is same as ‘number in dictionary.keys()’ which is just a list of keys and in worst case it can be in the last position… I’m not sure cuz I’m new to coding but isn’t that O(n^2) itself? I understand that lookup is O(1) ie dictionary[key] but yh… idk man this doesn’t seem like a ‘clean’ O(n) solution. Btw when I say dictionary I mean hashmap
if I will use python for the contest, Will I face any problems? Please answer me.
More videos of this kind
Why even with sorting cant i do it in On. Since i can find the max value in On and then use some sorting of On since the range is known
Great job
Why not dynamic programming ?
The exercises look great but they are not Python specific, those could be implemented with any programming languages.
But, for example, "Implement a cache mechanism with decorators" is a direct Python question.
The question is , does Algoexpert have questions that really are Python specific?
No, but programmingexpert.io does!
@@TechWithTim Thank you for the link. Does this package offer teaching or also problems like Leetcode. I just checked it and it does not look like they have problems, just questions and teaching... Of course thsi was just first look on their page. DO you know if they have Python problems and how many included in that $78 package?
Can anyone pls explain me how the program is taking input. Because it not taking list input from the user. I have tried running this code my computer but it do not work. please help, I am new to the programming.
Loved it 🙏🏻
I don't really like this solution due to corner cases.
You can't just do:
left_count += 1
and assume that your previous check was good. It might've failed on the first check.
I wrote a soln that creates a left/right candidate initialized as the item in the array then checks neighbors
def check_neighbor(item, the_dict, direction):
print(f'
Entered check_neighbor item: {item}\t direction: {direction}')
# print(f'target dict: {the_dict}')
cand = item + direction
ret_val = None
while True:
if the_dict.get(cand) is not None:
print(f'yup {cand} is in the dict')
the_dict[cand] = 1
ret_val = cand
cand = cand + direction
continue
else:
print(f'cand: {cand} is not in direction: {direction}')
return ret_val
Done with lists and range:
l = [0,2,3,4,6,7,8,9,10,12,13] # can ask user input for list too
def largestRange(l):
ranges=[]
temp = []
l.sort() # here l is manually given and sorted
start = False
for i in range(len(l)-1):
if l[i+1]-l[i]==1:
if start==False:
start=True
temp.append(l[i])
temp.append(l[i+1])
else:
temp.append(l[i+1])
elif l[i+1]-l[i]!=1 and start==True:
start=False
ranges.append(temp)
temp = []
ranges.append(temp)
ranges.sort(key=len)
xyz=[]
xyz.append(ranges[-1][0])
xyz.append(ranges[-1][-1])
print(xyz)
largestRange(l)
Actually this one is just dfs for next and previous then mark it visited and count
How is algoexpert better than leetcode?
Make more video like this pls
couldn't we start from the smallest number (using min(array)) in the list and keep removing the elements as they are counted,it might get the program more easy (i guess)
It doesn't work if the largest number on the list is in index 0.
this is great content, thanks alot man
Is this similar to codewars?
Im starting with developing, can someone confirm if i understood the problem at all and if my code is doing what he supposed to do?
problem = [1,11,3,0,15,5,2,4,10,7,12,6]
answer, contador = 0
placar =[]
def llist(number):
global contador, placar, answer
for num in number:
for nume in number:
if nume-7
I WISH THERE WAS AN OPTION TO GIVE AS MANY LIKE AS POSSIBLE
im a bit confused about the whole left and right thing. lets say we have the list [3 7 8 2 4]. if we go right in the list then yes we find 4, but how does going left find the 2? does it loop until its the starting point?
it finds 2 because it looks in the hash map/dict. we aren't looking in the list for the left right elements, we are looking in the hash-table to see if they exist. we don't care about their position.
left_count and right_count is bad naming. You should have used left_num ...
Bro, I will learn English to watch your videos
i like your videos. keep going!
Can i shine in competitive programming Contest by using python? 🙃
at 18:50 you change the less than to less than equal - you never give the explanation for it, and actually it's not needed. Other than that - excellent lecture! :-)
You caught me! My bad, must have forgotten :)
Please make more..
thank you
Subscribed!
I dont know, in my opinion premature optimisation is root of all evil. You need to ask yourself how much time does a reader of your code take to understand your code. So if you do not know beforehand that this is a bottleneck in performance, I'd rather go simple.
That's right, but you should still be able to write the most efficient solution. In an interview, you would generally write out the simpler but not optimal solution (sorting, in this case), and then write the optimal solution. Then you could discuss the pros and cons of each solution in a practical setting. In the end, you will sometimes be in situations where you need to write optimal code, so they expect you to demonstrate that.
Please make more
Please upload more questions and approach used to solve them sir
I'm not trying to sound cocky, but this looks really simple, i learned about ranges and that stuff in year 6 and could do this question in my sleep(I have not learned coding but I know a lot about coding and how the languages function, the main part of this question is learning the names of the expressions used to write the algorithm) Someone please confirm if I'm correct? Just saying the algorithm for this question would be easy????
Hii Tim add more functionality to the voice assistant
Can you please tell when you will you add more features of voice assistant so that I can add more features to my project
O(n) solution written in Python using set: gist.github.com/AvihayShahar/33e993fe698ba0d3683522cd59d64789
I am poping a number off a set and checking left and right of it in a function.
If the range that was found is greater than current, update current and store the range array.
Please rate it!
It’s somewhat similar to my solution, but you just made it more complicated! Good solution but the level of complexity is not necessary
@@TechWithTim Yes I did complicate it a lot I guess XD. I also think that removing items from a set while iterating it is bad programming generally so I guess my solution sucks.
AlgoExpert, sounds like what we had in the old days where the nerd wrote our term papers for us.
This guy is doing alot of commercials. He is more like a marketing guy
Awesome
I don't want to sound smart,but how about 3rd value in range?
I don’t understand the your comment
@@TechWithTim I meant there is optional value in range,where you specify steps.
so range(0,11) = 0,1,2,3,4,5,6,7,8,9,10
but range(0,11,2) = 0,2,4,6,8,10
and so on.
@@TechWithTim aww, it was specified to return "array of length 2" .. nevermind, I missed that
Consecutive is the word you missed.
@@keshavnemeli no,that array length is more precise for that.
Tha's cool but are other free methods that are just as good for those who can't afford the $85 plan
Project Euler and Leet Code are good free alternatives
For sure, I personally like the structure of this but there is obviously some great free alternatives!
Calvo
Poto calvo
Instructions unclear
list.sort() go BRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR
Damn man I feel so lost
I am 14 years old and I solved it in an hour. It's not hard, it's medium.
I have heavy brain promblems
Wow Thats sick bro!
Thanks
Yeah gotr my skolership yesterday
Sick bro!
You should drink sometimes.