LeetCode 220: Contains Duplicate III - Interview Prep Ep 47

LeetCode 220. Contains Duplicate III: https://leetcode.com/problems/contains-duplicate-iii/

⭐ Support my channel and connect with me:
https://www.youtube.com/channel/UCPL5uAbYQ40HwAdOe4ikI0w/join

Solution explained:
1. We'll need a data structure that could give us efficient access for operations like: get, insert, delete for a given size of k elements, we want it better than a linear time complexity - a self balancing binary search tree comes into picture;
2. We'll still use a set to find the duplicate, and the set size will be k as well, however, each time:
a. we'll quickly peek the maximum element in the set that is smaller than the current element that we are iterating on, check if their difference is smaller than or equal to t, if so, then we could happily return true, if not,
b. then we check the minimum element in this given set that is bigger than the current element that we are iterating on, check if their difference is smaller than or equal to t, if so, then we could happily return true, if not,
c. we'll add this element into the set;
d. then we'll do a check to make sure the size of the set is still within k, if not, we'll remove the oldest element from this set.

Time complexity: O(nlog(min(n, k)))
Space complexity: O(min(n, k))

// TOOLS THAT I USE:
○ Memory Foam Set Keyboard Wrist Rest Pad - https://amzn.to/3cOGOAj
○ Electric Height Adjustable Standing Desk - https://amzn.to/2S9YexJ
○ Apple Magic Keyboard (Wireless, Rechargable) - https://amzn.to/36gy5FJ
○ Apple Magic Trackpad 2 (Wireless, Rechargable) - https://amzn.to/36ltimu
○ Apple MacBook Pro - https://amzn.to/30iSvKE
○ All-In One Printer - https://amzn.to/34etmSi
○ Apple AirPods Pro - https://amzn.to/2GpVYQf
○ My new favorite Apple Watch - https://amzn.to/2EIIUFd

// MY FAVORITE BOOKS:
○ Introduction to Algorithms - https://amzn.to/36hxHXD
○ Designing Data-Intensive Applications - https://amzn.to/2S7snOg
○ Head First Java - https://amzn.to/2ScLDKa
○ Design Patterns - https://amzn.to/2SaGeU2
Follow me on Github for complete LeetCode solutions: https://github.com/fishercoder1534/Leetcode

Support me on Patreon: https://www.patreon.com/fishercoder

My ENTIRE Programming Equipment and Computer Science Bookshelf:
https://www.amazon.com/shop/fishercoder

And make sure you subscribe to my channel!

Your comments/thoughts/questions/advice will be greatly appreciated!

#softwareengineering #leetcode #algorithms #coding #interview #SDE #SWE #SiliconValley #programming #datastructures

Видео LeetCode 220: Contains Duplicate III - Interview Prep Ep 47 канала Fisher Coder