Are THESE Better Than Lists?? - The Josephus Permutation 

There may be a caveat here. According to the docs, the time complexity for deque.rotate(k) is O(k). In this case, when k

You have no idea about how helpful and useful you are for people like me. I’m a data analyst who predominantly uses Python and this is super super useful. God bless you ❤

To be pedantic about it, the pythonic "list" in a dynamic array which is also known as a vector. Whereas the deque is a type of doubly linked list which is called "list" for short, compaired to the vector.

You're one of the few programming RU-vidrs I've found that strike the balance of being approachable for beginners and don't gloss over best practices and the relevant CS concepts that people need to grow (time complexity, data structures, etc). Love the content

One of the best videos ever. Instead of a dry approach, you explained Lists, deques AND the Josephus permutation in a fun way where you gradually build upon the solution one step at a time. Seeing the code getting improved was magical and I felt like I learnt something useful that I won't forget. Two thumbs up!

the font is brass mono cozy for those who are wondering

I really enjoy your videos, no useless flashy intro, straight to the point and for me a lot of unique content I didn't see anywhere else. Thank you very much

A while back I derived a formula to find the last guy in this problem after watching a numberphile vid about it. the formula is f(x)= 2(x-2^(floor(log'base2'(x)))) +1. I plotted it in desmos and it looked pretty cool.

I've never heard of deques before but as soon as you explained how they work, I knew you were talking about a linked list! Wonderful video

This video really helped me understand deque. Are you planning to go through the rest of the data structures other than the ones you have covered?

I've watched a few of your videos, and while they were interesting, they were not quite enough to motivate me to give you a subscribe. This one got it. That's incredible.

It’s wonderful to see the deque or linked list being utilized in python!

Hi b001! Your videos are really well made and clear. I wondered what software/tools do you use to create your videos and the animations. Keep up the good work.

Your video is great, as always! I am a huge fan of this type of content.

wow such a great video!! could you please tell me which software or where to edit those array animations you're making in your videos. Thanks in advance :))

You’re explaining, voice and teaching are very helpful and informative, you earned a new subscriber and I’m hoping to see more content like this, I’m gonna start learning python soon and I’m gonna need content like this

Very clever use of Mod Operation

One thing to keep in mind, though, is cache invalidation (which granted, if we're using python, it might be the least of our problems). Depending on the sample size of our data, the deque approach might be less efficient than the array one, or vice versa.

Oh wow. Recently discovered your channel through your list comprehension video. Your explanation style amazing! Subbed!

I really enjoy your videos.

List is more of a generalization of a linear structure (specifically Sequences or Tuples), that allows for appending / removing- Queues do this as well, (and are also generalized: as there are different types of queues), but could be represented by a Tree, rather than a Tuple- The tree is a “Fan of degree-1”, for queues and stacks- and is better for appending / removing elements, but removes random access to those elements. The queue gets a reference to a “Head” and “Tail”: tails can only be added to; whereas, heads technically allow removal and adding (in a ~singly directed graph). The stack gets just a “Head” reference instead to add/ remove. For ~doubly directed graphs (some might consider this “undirected”, but I think there’s a difference), then there is more symmetry, and you can add / remove from either side. Also, you can iterate forwards and backwards (instead of just forwards). It uses quite a bit more memory though PS: (Memory optimization idea) Each directed edge is an Object reference can be replaced with an integer reference to a hash-code that will map to a unique object in an outside list (this is exactly how a hashmap works) Technically a hashmap stores Pairs, in a sublist, to avoid “collision” with the hashes- and we should do the same. Cheers

As others noted when using the deque hte complexity becomes O(n*k). The same can be achieved by looping over an array with two indexes, compacting the array while searching it. E. g. for k=3 you would do copy, copy, skip, copy, copy, skip. This should be asymptotically the same but have better constants. For large k a red-black-tree, splay-tree or a skip-list would be much, much faster.

yeah man that presentation is amazing! MANY MANY THANKS

I'd be curious of the memory implications of this. deque sounds like a doubly linked list so rather than working with an array of primitives there is a large number of objects. Now, granted my background is C++/C#/Java so I'm willing to accept that I'm wrong completely in my assumptions, but I would assume that using the code would result in a large number of objects on the heap. Is there a significant difference in memory allocations?

Great video as always! Keep them coming please! Just want to add that from some simple tests I've run, if you only require to pop one (or very few?) items, d = deque(array) takes more time than the popping saves. In other words, the conversion to deque outweighs the benefits of deque popping. However, obviously if you have n popping operations to do, then the conversion time becomes negligible in comparison.

I found your channel and it's one of the best I've ever seen , thank you for your videos i hope you can cover more topics and explain them for beginners like me 🎉

To be honest, I had never considered this Data Structure. Thank you @b001 for the video. Very informative and helpful!

Ok now I’m pretty sure c++ has a completely different implementation of deque that is far more logical to call it a double ended queue. I’ve always thought that they are the same!

These videos make me so excited to start my career

Your videos are very understandable and clear. I suggest you create a full course on Python. Thank you.

I had seen usage of deque in DSA course in the past, but I had trouble understanding why it was used back then. Now it's pretty clear :-) Cheers!

Nice vid, though I wouldn’t say outright better is correct. Like everything, there is a trade off. Lists: O[n] worst case removal, O[1] lookup. Deques: O[1] removal, O[n] worse case lookup. There is also cache coherence to think about, which lists are very good at thanks to be continuous in memory, while deques are very bad thanks to being spread in memory. As usual, the best thing to do is measure, try something different, measure again.

Yo, i really love this CP contents, thank you so much for this. Hope you can do other video relating to standard libraries such as Pandas or Numpy :DDD

Your videos are so good! Are you using a specific textbook to get these information from?

Awesome content and explanation! Thanks!

Not sure how. But somehow i found myself here. And now I have my new favourite coding channel.

This is beautifully done.

Josephus : casually takes out his laptop and codes a python program that takes 2 mins to make sure he survives others : what the hell is he doing b001 : hey would you mind if i barrow that idea for a video?

I know it might not fetch as many views as the simpler, common Videos, but please keep posting about these more advaced topics. Theres enough beginner coding, we need some good stuff :) thank you!

I've used a deque before, but I didn't know about rotate. Looks like the perfect data structure for this problem.

Good stuff! Subbed!

Cool video, bro! What color theme do you use for coding? It looks fire

Instant subscribed

Interesting that popping the array correctly models the problem, which is not immediately obvious from the visual representation.

I'm waiting for the person who always comments a one-liner solution.

Thing is that if i m not wrong, each element of the deck will take way more memory as he has an integer (32 bits), and 2 pointers (128 bits) wich give us 160 bits in emory for one element instead of 32 bits for an array. So as my college teacher says, the perfect algorithm doesn't exists, its just a story of memory cost and temporal cost balance.

This code is relying upon an implementation detail of deque. Deques only guarantees O(1) for push_front() and push_back()--there's no such guarantee for rotate() or arbitrary deletion. A link-list implementation of deque has fast rotation, but another common implementation of an array of dynamic arrays (aka array deques) has very slow rotations.

Love your videos! could you do some custom exception errors, or decorators por functions ?

When you showed the memory operations for deque I realized: Oh thats a doubly linked list, cool

Finding about that new form of linked list tingles my brain 😁😁 BTW, if I wanted to learn python on my own through the official docs, how would I do that ? I mean no offense but python's docs is the _most messiest_ docs I've ever seen, just right after Microsoft's VBA docs. (I guess that's why they implemented it to MSExcel lol)

Amazing.. great job !

The video is so clean. What do you use to create your animation /illustration?

It would be great if there was a playlist for all the data structures that is built-in python.

Hey Your videos are amazing. Can you tell me the theme you are using in your IDE?

Isn't the time complexity O(N/2) when going through a doubly link list/deque, there by making the time complexity O(N*(N/2)) and not O(n)? And the gains come from not having to shift all the data in memory and instead just having to change a single pointer? Or am I thinking wrong somehow?

Hi! I quickly want to ask what vs code theme you're using as I realy like the coloring.

What vs code theme are you using? I really love the look of the syntac highlighting and vibrancy. Also, nice video about deque :D

Thanks man

What's the name of the monospace font you use? Looks pretty clean.

very helpful !

Yeah you can't sort deques in O(nlogn). You also can't search a sorted deque in O(logn).The continuous memory list is pretty handy for this. You should add this caution at the end in my opinion.

Might be a bit of a meme question but what VSCode theme are you using? It kinda looks like Tomorrow Night Blue

So why not just use a linked list?

Good information

May I ask how did you do this animation?

So instead of O(n^2) it’s O(n*k), for n rotate operations which take (I think) k time to complete?

Question about list example, I have 2 lists, arr1 is numbers, arr2 is chars arr1 = [1, 2, 3, 3.14, 4, 5] arr2 = ["a", "b", "c", "d", "e"] I want to combine them, but... Should I user rr3 = arr1 + arr2 or? arr3 = arr1.copy() + arr2.copy() which one is better?

Naming this data structure deque is really confusing to me, because it is essentially a double linked list. In C++ for example deque is implemented using a dynamic array and it allows for element access in constant time as well as appending and popping from both sides. So to compare time complexity (C++ vs python): Append/pop (any side): O(1) (amortized I believe) vs O(1) Remove given element: O(n) vs O(1) Access random index: O(1) vs O(n) So it's a completely different structure. Really weird naming decision.

When seeing the rotation, my first thought is just why is traversing through pointers until the head is at the right one any faster than o(n), making it still overall o(n^2)?

Why is your code terminal so cool ?

there is a way to crunch this algorithm down to 1 line

tanks

Nice video, brow!

more videos likes this please

I am still confused why you are rotating elements in deque? It is a double ended queue, why bring the element in head to delete it? Just traverse to the element and remove it from there. I am confused, is there a difference in this or something? I haven't used queues and stacks in python, so..

why would you need memory structures for this at all? simple iterative function mod highest number and loop highest number times in total

here is my solution using lists :) it is 4x faster from time import perf_counter def solution(array,n): result=[] offset=n-1 while l: offsetneu=(offset-len(l))%n result.extend(l[offset::n]) del l[offset::n] offset=offsetneu return result k=1000000 n=3 l=list(range(1,k+1)) start=perf_counter() sol=solution(l,n) print(perf_counter()-start) print(sol[-100:])

I hope one day I’ll be this good in algorithms😢

I never though yet another data structure existed in python Is there more unknown data structure in python hidden from us like that ?

Rotate the deque like a DJ on the decks, scratchin’ left or right for the choice cuts

For the array why not just use the range function?

I just watched class in 1 minute and I like how u explain class function can u do python for beginners

Wouldn't rotate be O(n) now?

Keep up 👏

What theme and font is this?

Whats the font being used anyone aware.. I find it pretty cool...

what is the theme you use? it isn't synthwave

holllly molly WTF......., this really helped me while True: print("thank you")

which font do you use brother?

It's another year of AOC, the deque is so helpful if you want to get to the leader board

This "deque" is almost like a doubly linked list!

why not show how deque performs with a million soldiers compared to lists?

I hope Josephus knew about deques as well

what is your vscode theme

Nice vid lol 🎉

Cool but that actually leads to the complexity of O(n * k) which is terrible when k = n. There actually is a data structure that can solve the problem in O(n * log(n)) which is Binary Indexed Tree or Fenwick Tree. I wish you could make a video on solving this problem using those proposed data structure, that would be super cool 😎😎.

do more of solving a problem to teach a concept

Even though this video's intention is to show deques, it is definitely not the most efficient / optimised way to solve this problem :)

it is definately link list in C++, isn't it

That solution is still really slow. Rotating deque still takes O(n).