# dsa

#dsa#java#tree

Heavy-Light Decomposition in Java: Optimizing Tree Queries

When dealing with large trees, performing path queries (like finding the maximum value on a path between two nodes) or path updates can be slow. A naive approach takes $O(N)$, and while Segment Trees work for arrays, the…

Apr 21, 20263 min read

#dsa#java#tree

Link-Cut Trees in Java: Dynamic Tree Connectivity

While Heavy-Light Decomposition (HLD) is excellent for static trees, it struggles with dynamic trees where edges are frequently added or removed. Link-Cut Trees (LCT) are the solution to this problem, allowing us to main…

Apr 21, 20264 min read

#dsa#java#tree

Suffix Automaton in Java: The Ultimate String Data Structure

When it comes to string processing, the Suffix Automaton (SAM) is often considered the most powerful data structure. It is a minimal Deterministic Finite Automaton (DFA) that recognizes all suffixes of a given string. Wh…

Apr 21, 20263 min read

#dsa#java#string

AVL Trees: Self-Balancing Binary Search Trees

AVL Trees (Self-Balancing BST) An AVL Tree is a self-balancing Binary Search Tree (BST) where the difference between heights of left and right subtrees cannot be more than one for all nodes. This ensures that the tree re…

#dsa#java#avl-trees

Kosaraju's Algorithm for Strongly Connected Components

Kosaraju's Algorithm A Strongly Connected Component (SCC) of a directed graph is a maximal subset of vertices such that for every pair of vertices (u, v) in the subset, there exists a directed path from u to v and a dire…

#dsa#java#graphs

Manacher's Algorithm in Java: Linear Time Palindrome Search

Finding the longest palindromic substring is a classic interview problem. While the naive approach takes $O(N^3)$ and dynamic programming takes $O(N^2)$, Manacher's Algorithm achieves the same result in linear time ($O(N…

#dsa#java#string

Mo's Algorithm: Offline Range Queries

Mo's Algorithm Mo's Algorithm is a powerful offline technique used to solve range query problems. It is particularly effective when the query results can be updated incrementally as we shift the query boundaries [L, R] t…

#dsa#java#mo-algorithm

Red-Black Trees in Java: The Engine Behind TreeMap and HashMap

If you've ever used java.util.TreeMap or java.util.TreeSet, you've already used a Red-Black Tree. It is the most popular self-balancing binary search tree in modern software libraries because it offers a perfect balance…

#dsa#java#binary search tree

Segment Tree Data Structure: Efficient Range Queries

Segment Tree Data Structure A Segment Tree is a versatile data structure used to perform range queries and updates efficiently. It allows us to process operations like Range Sum Query or Range Minimum/Maximum Query in $O…

#dsa#java#segment-tree

Skip Lists in Java: The Probabilistic Alternative to Balanced Trees

A Skip List is a probabilistic data structure that allows for fast search, insertion, and deletion in a sorted list of elements. It is often described as a "multi-layered linked list." While balanced trees like AVL or Re…

#dsa#java#skip list

Tarjan's Algorithm in Java: Finding Strongly Connected Components

In a directed graph, a Strongly Connected Component (SCC) is a maximal subgraph where every node is reachable from every other node. Identifying these components is crucial for solving problems related to dependency anal…

A* Search Algorithm in Java: Heuristic Pathfinding

The A (A-Star) search algorithm is one of the most successful pathfinding algorithms in computer science. It is widely used in video games and robotics because it is both efficient and guaranteed to find the shortest pat…

B-Trees and B+ Trees in Java: The Engines of Modern Databases

While Binary Search Trees (BST) and AVL trees are great for in-memory operations, they perform poorly when data is stored on disk. This is where B-Trees and B+ Trees shine. They are the underlying data structures for alm…

Backtracking Pattern in Java: Permutations and Combinations

Introduction to Backtracking Backtracking is a general algorithmic technique for solving problems that incrementally build candidates to the solutions and abandon a candidate ("backtrack") as soon as it determines that t…

#dsa#java#backtracking

Bellman-Ford Algorithm in Java: Shortest Paths with Negative Weights

Introduction to Bellman-Ford Algorithm Bellman-Ford Algorithm is a single-source shortest path algorithm that works on weighted graphs, including those with negative edge weights. Unlike Dijkstra's algorithm, which fails…

#dsa#java#bellman-ford

Bellman-Ford Algorithm in Java: Shortest Paths with Negative Weights

While Dijkstra's algorithm is faster for most shortest-path problems, it fails when the graph contains negative edge weights. For those scenarios, we use the Bellman-Ford algorithm. Not only does it handle negative weigh…

Bloom Filters in Java: Probabilistic Data Structures

A Bloom Filter is a space-efficient probabilistic data structure used to test whether an element is a member of a set. It is unique because it can give two types of answers: 1. "Possibly in set": The element might be the…

Boyer-Moore Voting Algorithm in Java: Finding the Majority Element

Finding the "majority element" in an array (an element that appears more than $n/2$ times) is a classic interview problem. While you could solve it with a Hash Map in $O(n)$ time and $O(n)$ space, the Boyer-Moore Voting…

Dijkstra's Algorithm in Java: Finding the Shortest Path

Dijkstra's algorithm is the industry standard for finding the shortest path from a starting node to all other nodes in a graph with non-negative edge weights. Whether you are building a navigation system like Google Maps…

Deep DiveDSA Mastery

Fenwick Trees (Binary Indexed Trees) in Java

The Fenwick Tree, also known as a Binary Indexed Tree (BIT), is a compact data structure that provides efficient methods for calculation and manipulation of the prefix sums of an array of values. It is more space-efficie…

#dsa#java#fenwick tree

Floyd-Warshall Algorithm in Java: All-Pairs Shortest Paths

While Dijkstra's algorithm finds the shortest path from a single source to all other nodes, the Floyd-Warshall algorithm finds the shortest paths between all pairs of vertices in a weighted graph. It is a classic example…

Huffman Coding in Java: Lossless Data Compression

Huffman Coding is a classic greedy algorithm used for lossless data compression. It assigns variable-length codes to input characters, with shorter codes assigned to more frequent characters. This is the foundation of ma…

Kadane's Algorithm in Java: Maximum Sum Subarray

Finding the Maximum Sum Subarray is a classic problem that can be solved in $O(n^2)$ using brute force. However, Kadane's Algorithm allows us to solve it in a single pass ($O(n)$ time and $O(1)$ space). It is a beautiful…

Apr 19, 20262 min read

Kruskal's Algorithm in Java: Finding the Minimum Spanning Tree

Kruskal's algorithm is a famous greedy algorithm used to find the Minimum Spanning Tree (MST) of a connected, weighted, and undirected graph. An MST is a subset of edges that connects all vertices together, without any c…

Longest Common Subsequence (LCS) in Java: Dynamic Programming Guide

The Longest Common Subsequence (LCS) problem is a foundation of many string comparison tools, including git diff and bioinformatics software. A subsequence is a sequence that appears in the same relative order, but not n…

Lowest Common Ancestor (LCA) in Java: Binary Trees and DAGs

Introduction to Lowest Common Ancestor (LCA) The Lowest Common Ancestor (LCA) of two nodes p and q in a tree (or a Directed Acyclic Graph - DAG) is the lowest (i.e., deepest) node that has both p and q as descendants. A…

#dsa#java#lca

LRU Cache Implementation in Java: $O(1)$ Strategy

The LRU (Least Recently Used) Cache is one of the most popular interview questions because it tests your ability to design a custom data structure. It requires you to maintain a fixed-size cache and, when full, evict the…

#dsa#java#cache

Matrix Traversal in Java: Spiral, Diagonal, and Flood Fill

Introduction to Matrix Traversal Matrices (or 2D arrays) are fundamental data structures used to represent grids, images, game boards, and various other tabular data. Matrix traversal refers to the process of visiting ea…

Apr 19, 202613 min read

#dsa#java#matrix

N-Queens Problem in Java: Solving Constraints with Backtracking

Introduction to the N-Queens Problem The N-Queens puzzle is the problem of placing N non-attacking queens on an N×N chessboard. A queen can attack horizontally, vertically, and diagonally. The goal is to find all distinc…

#dsa#java#backtracking

Prim's Algorithm in Java: Minimum Spanning Tree via Greedy Growth

While Kruskal's algorithm focuses on edges, Prim's algorithm takes a vertex-centric approach to finding the Minimum Spanning Tree (MST). It starts from an arbitrary node and "grows" the tree by always adding the cheapest…

Rabin-Karp Algorithm in Java: Efficient String Searching with Hashing

The Rabin-Karp algorithm is a powerful string searching algorithm that uses hashing to find any one of a set of pattern strings in a text. While brute-force matching takes $O(n \cdot m)$ time, Rabin-Karp achieves an aver…

Apr 19, 20264 min read

Sudoku Solver in Java: Efficient Backtracking and Pruning

Introduction to the Sudoku Solver Problem The Sudoku puzzle is a classic number-placement puzzle. The objective is to fill a 9x9 grid with digits so that each column, each row, and each of the nine 3x3 subgrids (also cal…

Apr 19, 202611 min read

#dsa#java#backtracking

Suffix Arrays and Suffix Trees in Java: Advanced String Structures

When it comes to advanced string processing, Suffix Trees and Suffix Arrays are the heavy hitters. They allow you to answer complex queries about a string—like "What is the longest repeated substring?" or "How many times…

Z-Algorithm in Java: Linear Time String Matching

The Z-Algorithm is an efficient string matching algorithm that finds all occurrences of a pattern $P$ in a text $T$ in linear time $O(n + m)$. While many developers learn KMP (Knuth-Morris-Pratt), the Z-Algorithm is ofte…

BFS (Breadth First Search) in Java: Level-Order and Shortest Path

Introduction to Breadth First Search (BFS) Breadth First Search (BFS) is a fundamental algorithm for traversing or searching tree or graph data structures. Unlike DFS, which explores as deeply as possible along each bran…

#dsa#java#bfs

Big-O Notation in Java: Time and Space Complexity for Interview Problem Solving

Big-O notation scares a lot of people because it often gets explained as math first and problem solving second. In interviews, that is backward. You do not need to sound like a theoretician. You need to look at code, est…

#dsa#java#big-o

Binary Search Pattern in Java: Efficiently Searching Sorted Data

Introduction to the Binary Search Pattern The Binary Search pattern is a highly efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing in half the portion of the list that co…

Deep DiveDSA Mastery

#dsa#java#binary search

DFS (Depth First Search) in Java: Tree and Graph Traversals

Introduction to Depth First Search (DFS) Depth First Search (DFS) is a fundamental algorithm for traversing or searching tree or graph data structures. It explores as far as possible along each branch before backtracking…

#dsa#java#dfs

Dutch National Flag Pattern in Java: Efficient Three-Way Partitioning

Introduction to the Dutch National Flag (DNF) Pattern The Dutch National Flag (DNF) pattern, also known as three-way partitioning, is an algorithm for sorting an array containing three distinct values (or elements that c…

Apr 18, 20268 min read

#dsa#java#dutch national flag

Fast & Slow Pointers in Java: Detecting Cycles and Finding Middle Elements

Introduction to the Fast & Slow Pointers Pattern The Fast & Slow Pointers pattern, also known as the Hare and Tortoise algorithm, is a powerful and elegant technique used primarily in problems involving linked lists and…

#dsa#java#fast slow pointers

In-place Reversal of a Linked List in Java: Efficient Memory Management

Introduction to In-place Linked List Reversal Reversing a linked list is a fundamental operation in Data Structures and Algorithms (DSA) that frequently appears in technical interviews. The in-place reversal technique is…

#dsa#java#linked list

Monotonic Queue Pattern in Java: Efficiently Solving Sliding Window Maximum

Introduction to the Monotonic Queue Pattern The Monotonic Queue pattern, often implemented using a Deque (double-ended queue), is a specialized data structure technique used to efficiently solve problems involving slidin…

#dsa#java#monotonic queue

Monotonic Stack Pattern in Java: Efficiently Finding Next Greater/Smaller Elements

Introduction to the Monotonic Stack Pattern The Monotonic Stack pattern is a specialized application of the stack data structure where the elements within the stack are always kept in a specific order (either strictly in…

#dsa#java#monotonic stack

Prefix Sum Pattern in Java: Efficiently Calculate Range Sums and Subarray Properties

Introduction to the Prefix Sum Pattern The Prefix Sum pattern is a fundamental technique in Data Structures and Algorithms (DSA) used to efficiently answer queries about the sum (or other aggregate properties) of element…

#dsa#java#prefix sum

Sliding Window Pattern in Java: Efficiently Solve Array and String Subarray Problems

Introduction to the Sliding Window Pattern The Sliding Window pattern is a powerful technique used to solve problems that involve finding a subarray, subsegment, or substring in a given array or string that satisfies a c…

#dsa#java#sliding window

Sorting Algorithms in Java: QuickSort, MergeSort, and HeapSort Explained

Introduction to Sorting Algorithms Sorting is one of the most fundamental and widely studied problems in computer science. It involves arranging elements of a list or array in a specific order (e.g., numerical, lexicogra…

#dsa#java#sorting algorithms

Topological Sort in Java: Handling Dependencies with Kahn's Algorithm

Introduction to Topological Sort Topological Sort (or Topological Ordering) is an algorithm for ordering the vertices of a Directed Acyclic Graph (DAG) such that for every directed edge u -> v, vertex u comes before vert…

#dsa#java#topological sort

Two Pointers Pattern in Java: Solve Array and String Problems Efficiently

The two pointers pattern is one of the fastest ways to turn a slow nested-loop solution into a clean linear-time solution. It shows up everywhere: - sorted arrays - palindrome problems - deduplication - partitioning - li…

#dsa#java#two pointers

Union Find (DSU) in Java: Connectivity and Cycle Detection

Introduction to Union Find (Disjoint Set Union) The Union Find data structure, also known as Disjoint Set Union (DSU), is a powerful and efficient data structure that keeps track of a set of elements partitioned into a n…

Apr 18, 202610 min read