标签：#datastructures

The Quest Begins (The "Why") I still remember the first time I stared at a LeetCode problem that asked me to count the number of islands in a grid. My initial instinct? Run a BFS/DFS from every unvisited land cell, mark everything reachable, and repeat. It worked, but each query felt like I was re‑exploring the same territory over and over again—like walking the same hallway in a dungeon every time I wanted to open a new door. Then a friend tossed me another problem: “Given a list of friendships, tell me if two people are in the same social circle.” Again, the naive solution was to rebuild the whole graph for every query. I felt like I was stuck in a grind‑fest, repeating the same low‑level work while the real challenge—understanding the structure of the connections—remain. That frustration sparked a question: Is there a way to remember what we’ve already discovered about connectivity, so future queries are instant? The answer, as many of you have guessed, lives in a humble but mighty data structure called Union‑Find (also known as Disjoint Set Union, DSU). The Revelation (The Insight) At its core, Union‑Find is about two simple ideas : Each element starts in its own set – think of every person as a lone adventurer. When we learn that two elements belong together, we merge their sets – we call that a union . The magic isn’t just in merging; it’s in how we find the representative (or “root”) of a set later on. If we naïvely walked up a chain of parents every time, we could end up with O(n) per find—still a grind. Two optimizations turn this into near‑constant time: Union by rank (or size) – always attach the smaller tree under the root of the larger one. This keeps the overall tree shallow, guaranteeing that the height never exceeds log n. Path compression – during a find operation, we make every node we pass point directly to the root. It’s like handing every traveler a map that instantly shows the shortest route to the campfire, so next time they don’t need to trek

JavaScript ships with Array , Set , and Map — but nothing that keeps its elements sorted as you insert. If you've ever built a leaderboard, an order book, or anything that answers "give me the items between X and Y", you know the workaround: push into an array and .sort() after every insertion. It works, until scale punishes you — you're paying O(n log n) over and over for data that was already 99.9% sorted. Python solved this years ago with sortedcontainers , built on an elegant "list of lists" design instead of balanced trees. I just published sorted-collections , which brings that idea to TypeScript — with full credit to the original as its inspiration. What you get SortedList, SortedSet, SortedMap — always sorted, no manual re-sorting, range queries built in. O(log n) insertions, O(√n) positional access via sqrt-decomposition into buckets. Zero runtime dependencies , ~2KB gzip, types included, dual ESM/CJS. Package quality gated in CI with publint , arethetypeswrong , and size-limit . The API in 30 seconds import { SortedList , SortedSet , SortedMap } from " sorted-collections " ; // SortedList: stays sorted on every insert const list = new SortedList ([ 5 , 1 , 4 , 2 , 3 ]); list . add ( 0 ); console . log ([... list ]); // [0, 1, 2, 3, 4, 5] console . log ( list . at ( 2 )); // 2 — positional access on sorted order // SortedSet: no duplicates, plus set algebra const a = new SortedSet ([ 1 , 2 , 3 , 4 ]); const b = new SortedSet ([ 3 , 4 , 5 ]); console . log ([... a . intersection ( b )]); // [3, 4] // SortedMap: keys always in order, range queries built in const prices = new SortedMap < number , string > ([ [ 104.5 , " order-3 " ], [ 99.2 , " order-1 " ], [ 101.0 , " order-2 " ], ]); for ( const [ price , id ] of prices . irange ( 100 , 105 )) { console . log ( price , id ); // 101.0 order-2, then 104.5 order-3 } Custom comparators are fully typed: number and string get natural ordering for free; for your own types, TypeScript requires a comparator at compile

The Quest Begins (The "Why") I still remember the first time I faced a problem that asked for the sum of numbers in a sub‑array, over and over again, with updates sprinkled in between. It felt like I was stuck in a never‑ending loop of for i in range(l, r+1): total += arr[i] – O(n) per query, and with up to 10⁵ queries the solution timed out every single time. I was staring at the screen, thinking, “There has to be a smarter way to answer these range questions without scanning the whole array each time.” That moment was my dragon: a seemingly simple problem that kept biting me because I kept reaching for the brute‑force sword. I needed a data structure that could give me the answer in logarithmic time while still supporting point updates. Enter the segment tree – the tool that turned my O(n·q) nightmare into an O((n+q)·log n) victory. The Revelation (The Insight) So why does a segment tree work? Imagine you have an array and you want to know the sum of any interval [l, r] . If you could break that interval into a handful of pre‑computed chunks, you’d only need to add those chunk values together instead of touching every element. A segment tree is exactly that: a binary tree where each node stores the aggregate (sum, min, max, etc.) of a segment of the original array. The root covers the whole array [0, n‑1] . Its two children cover the left half and the right half, and this keeps splitting until the leaves represent single elements. The magic lies in two facts: Every node’s value is a function of its children. If you know the sum of the left child and the sum of the right child, the parent’s sum is just their addition. This means we can build the tree bottom‑up in O(n) time. Any interval can be represented as O(log n) disjoint nodes. When you walk down the tree to answer [l, r] , you either take a whole node (if its segment lies completely inside the query) or you recurse further. Because the tree’s height is log₂n, you’ll visit at most 2·log₂n nodes. Thus, building

The Quest Begins (The "Why") Honestly, I still remember the first time I stared at the Daily Temperatures problem on LeetCode and felt like I was trying to crack a vault with a toothpick. The brute‑force solution — two nested loops, checking every future day for a warmer temperature — was simple to write, but it timed out on the larger test cases. I spent an hour tweaking loops, adding early breaks, and even trying to memoize results, only to watch the same red “Time Limit Exceeded” banner flash again. I was frustrated, but more than that, I was curious. Why did this problem feel so repetitive ? Every element seemed to be asking the same question: “What’s the next greater value to my right?” If I could answer that for each index in a single pass, the whole thing would collapse into O(n). That’s when I remembered a weird little data structure I’d seen in a textbook — the monotonic stack — and realized it might be the magic wand I needed. The Revelation (The Insight) Here’s the thing: a monotonic stack isn’t just a stack with a funny name; it’s a way to capture relationships between elements without ever looking backward more than once . Imagine you’re walking through a line of people sorted by height, and you want to know, for each person, who is the first taller person standing ahead of them. If you keep a stack of people whose heights are strictly decreasing as you move from left to right, then whenever you see a new person taller than the one on top of the stack, you’ve just found the answer for that stacked person: the current person is their “next greater.” You pop them off, record the distance, and keep going. Because each index is pushed once and popped at most once , the total work is linear. The same idea works for “next smaller,” “previous greater,” or any problem where you need the nearest element that satisfies a monotonic condition. The stack does the heavy lifting of remembering candidates that could still be relevant, discarding the ones that are alrea

[While preparing for interviews, I realized I had a strange habit. I would solve a problem, get stuck, open the solution, understand it, and move on feeling productive. A few days later, I couldn’t solve a similar problem on my own. The issue wasn’t lack of practice. The issue was that I was consuming solutions faster than I was developing problem-solving skills. So I changed my approach. Instead of looking for answers, I started forcing myself to think longer, write down my ideas, identify where I was stuck, and only then seek guidance. That worked much better. But I couldn’t find a tool that supported this style of learning. Most platforms either: Give you the answer. Give you the editorial. Give you AI that writes the code for you. So I started building my own. The goal was simple: An AI coach that guides the thought process instead of generating the solution. Over time I added: DSA practice System Design preparation Low-Level Design preparation Company-wise interview questions Topic-wise strength and weakness analysis Personalized revision lists The interesting part wasn’t building it. The interesting part was realizing that interview preparation is less about collecting solutions and more about training how you think. What has helped you improve more during interview prep? Reading solutions? Or struggling with the problem first? Sde vault - https://sdevaultweb.onrender.com/

A linked list is an ordered linear data structure where elements are not stored in sequential memory locations, instead they are stored in nodes that are linked together by a pointers. Linked list are used in data intensive application because linked list offer specific benefits for high frequency data manipulation, this benefits include: Efficient insertion and deletion Adding and removing elements from a linked list is highly efficient, unlike arrays which requires shifting all subsequent elements to maintain indexing. A linked list only requires updating the pointer. Dynamic sizing: linked list can grow or shrink during runtime without needing to pre-allocate memory. Memory management: Nodes in a linked list are only allocated when needed which prevents memory wastage. Flexible Traversal: Doubly and circular list allow you to move forward or backward, which makes them helpful for complex navigation The first node in a linked list is called the head which signifies the start of the list, while the last node is called the tail and has a pointer of null except in a circular linked list. Each node in a linked list has two things which are: the actual data the pointer or reference There are three main types of linked list: Singly linked list Doubly linked list Circular linked list Singly Linked List: Singly linked list are lists where each node has a next pointer that points to the next node. Doubly Linked List: Doubly linked list are list where each node has a next and previous pointer that points to the previous and next node. Circular Linked List: Circular linked list are list where the last node points back to the first node, forming a circle. Table of Contents create node class create linked list class isEmpty and getSize Methods prepend and append Method removeHead and removeTail Methods insert and search Methods getIndex and removeIndex Methods clear and print Methods create node class First let's open our code editor and create a new file called singlyLinkedLi