Search Blogs

Showing results for "Classes"

Found 50 results

OOPs in Java - Complete Guide With Simple Examples

IntroductionObject Oriented Programming — or OOPs — is the foundation of Java. Almost every Java program you will ever write or read is built around OOPs concepts. The good news is these concepts are not complicated at all. They are actually modeled after how we think about real life things.By the end of this article you will understand every core OOPs concept clearly — not just enough to answer interview questions, but enough to actually use them confidently in your code.What Is Object Oriented Programming?Before OOPs, programmers wrote procedural code — a long sequence of instructions executed top to bottom. As programs grew bigger, this became a nightmare to manage. You could not organize related data and behavior together, reuse code cleanly, or model real world things naturally.OOPs solved this by organizing code around objects — just like the real world is organized around things. A car, a person, a bank account — each is a thing with properties and behaviors. OOPs lets you model these things directly in code.Java is a purely object oriented language (almost everything in Java is an object). That is why understanding OOPs is not optional in Java — it is essential.Class — The BlueprintA class is a blueprint or template. It defines what properties and behaviors an object of that type will have. The class itself is not an actual thing — it is just the design.Think of a class like an architectural blueprint of a house. The blueprint is not a house. But from one blueprint you can build many houses.class Car { // properties (what a car HAS) String brand; String color; int speed; // behaviors (what a car DOES) void accelerate() { System.out.println(brand + " is speeding up!"); } void brake() { System.out.println(brand + " is slowing down!"); }}Car is the blueprint. It defines that every car has a brand, color, speed, and can accelerate and brake. No actual car exists yet — this is just the design.Object — The Real ThingAn object is an actual instance created from a class. When you create an object, you are building a real house from the blueprint.public class Main { public static void main(String[] args) { // creating objects from the Car class Car car1 = new Car(); car1.brand = "Toyota"; car1.color = "Red"; car1.speed = 120; Car car2 = new Car(); car2.brand = "BMW"; car2.color = "Black"; car2.speed = 200; car1.accelerate(); // Toyota is speeding up! car2.brake(); // BMW is slowing down! }}car1 and car2 are two different objects from the same Car blueprint. Each has its own data but shares the same structure and behaviors.Constructor — The Object InitializerA constructor is a special method that runs automatically when an object is created. It is used to set initial values.class Car { String brand; String color; int speed; // constructor — same name as class, no return type Car(String brand, String color, int speed) { this.brand = brand; this.color = color; this.speed = speed; } void accelerate() { System.out.println(brand + " is speeding up!"); }}// Now creating objects is cleanerCar car1 = new Car("Toyota", "Red", 120);Car car2 = new Car("BMW", "Black", 200);The this keyword refers to the current object — it distinguishes between the parameter brand and the object's field brand.The Four Pillars of OOPsEverything in OOPs builds on four core concepts. These are what interviewers ask about and what real code is organized around.Pillar 1: Encapsulation — Wrapping and Protecting DataEncapsulation means bundling data (fields) and the methods that work on that data together in one class — and controlling access from outside.Think of a capsule pill. The medicine inside is protected by the outer shell. You do not mess with the medicine directly — you just swallow the capsule.In Java, encapsulation is achieved using access modifiers (private, public) and getters/setters.class BankAccount { private double balance; // private — no direct access from outside private String owner; BankAccount(String owner, double initialBalance) { this.owner = owner; this.balance = initialBalance; } // getter — read the balance public double getBalance() { return balance; } // setter with validation — controlled access public void deposit(double amount) { if (amount > 0) { balance += amount; System.out.println("Deposited: " + amount); } else { System.out.println("Invalid amount!"); } } public void withdraw(double amount) { if (amount > 0 && amount <= balance) { balance -= amount; } else { System.out.println("Insufficient funds!"); } }}BankAccount account = new BankAccount("Alice", 1000);// account.balance = -5000; // ERROR — private, cannot access directlyaccount.deposit(500); // controlled access through methodSystem.out.println(account.getBalance()); // 1500.0Why encapsulation matters: Without it, anyone could set balance = -999999 directly. With it, you control exactly how data can be changed — protecting your object's integrity.Pillar 2: Inheritance — Reusing Code Through Parent-Child RelationshipInheritance allows one class to acquire the properties and behaviors of another class. The child class gets everything the parent has and can add its own things on top.Think of it like genetics. A child inherits traits from their parents but also develops their own unique characteristics.In Java, inheritance uses the extends keyword.// Parent classclass Animal { String name; Animal(String name) { this.name = name; } void eat() { System.out.println(name + " is eating."); } void sleep() { System.out.println(name + " is sleeping."); }}// Child class inherits from Animalclass Dog extends Animal { String breed; Dog(String name, String breed) { super(name); // calls Animal's constructor this.breed = breed; } // Dog's own behavior void bark() { System.out.println(name + " says: Woof!"); }}class Cat extends Animal { Cat(String name) { super(name); } void meow() { System.out.println(name + " says: Meow!"); }}Dog dog = new Dog("Buddy", "Labrador");dog.eat(); // inherited from Animal — Buddy is eating.dog.sleep(); // inherited from Animal — Buddy is sleeping.dog.bark(); // Dog's own method — Buddy says: Woof!Cat cat = new Cat("Whiskers");cat.eat(); // inherited — Whiskers is eating.cat.meow(); // Cat's own — Whiskers says: Meow!super() calls the parent class constructor. super.methodName() calls a parent class method.Why inheritance matters: You write eat() and sleep() once in Animal and every animal class gets them for free. No repetition, clean organization.Pillar 3: Polymorphism — One Interface, Many FormsPolymorphism means the same method name behaves differently depending on the object calling it. It comes in two flavors.The word itself means "many forms" — same action, different results based on who is doing it.Think of a "speak" command given to different animals. You tell a dog to speak — it barks. You tell a cat to speak — it meows. Same command, different behavior.Method Overriding (Runtime Polymorphism)A child class provides its own version of a method already defined in the parent class.class Animal { String name; Animal(String name) { this.name = name; } void makeSound() { System.out.println(name + " makes a sound."); }}class Dog extends Animal { Dog(String name) { super(name); } @Override void makeSound() { System.out.println(name + " says: Woof!"); }}class Cat extends Animal { Cat(String name) { super(name); } @Override void makeSound() { System.out.println(name + " says: Meow!"); }}class Cow extends Animal { Cow(String name) { super(name); } @Override void makeSound() { System.out.println(name + " says: Moo!"); }}Animal[] animals = { new Dog("Buddy"), new Cat("Whiskers"), new Cow("Bella")};for (Animal a : animals) { a.makeSound(); // different behavior for each!}// Buddy says: Woof!// Whiskers says: Meow!// Bella says: Moo!Same makeSound() call on an Animal reference — but the actual behavior depends on what the object really is at runtime. That is runtime polymorphism.Method Overloading (Compile-Time Polymorphism)Same method name, different parameters in the same class.class Calculator { int add(int a, int b) { return a + b; } double add(double a, double b) { return a + b; } int add(int a, int b, int c) { return a + b + c; }}Calculator calc = new Calculator();calc.add(2, 3); // calls first method — 5calc.add(2.5, 3.5); // calls second method — 6.0calc.add(1, 2, 3); // calls third method — 6Java decides which version to call at compile time based on the argument types and count.Pillar 4: Abstraction — Hiding Complexity, Showing EssentialsAbstraction means showing only the necessary details to the user and hiding the internal complexity. You expose what something does, not how it does it.Think of driving a car. You know the steering wheel turns the car and the pedal accelerates it. You do not need to know how the engine combustion works internally. The complexity is hidden — only what you need to use is exposed.Java achieves abstraction through abstract classes and interfaces.Abstract ClassAn abstract class cannot be instantiated directly. It can have abstract methods (no body — child must implement) and regular methods (with body).abstract class Shape { String color; Shape(String color) { this.color = color; } // abstract method — no body, child MUST implement abstract double calculateArea(); // regular method — shared behavior void displayColor() { System.out.println("Color: " + color); }}class Circle extends Shape { double radius; Circle(String color, double radius) { super(color); this.radius = radius; } @Override double calculateArea() { return Math.PI * radius * radius; }}class Rectangle extends Shape { double width, height; Rectangle(String color, double width, double height) { super(color); this.width = width; this.height = height; } @Override double calculateArea() { return width * height; }}Shape circle = new Circle("Red", 5);Shape rect = new Rectangle("Blue", 4, 6);circle.displayColor(); // Color: RedSystem.out.println(circle.calculateArea()); // 78.53...System.out.println(rect.calculateArea()); // 24.0InterfaceAn interface is a 100% abstract contract — it only defines what methods a class must have, with no implementation (in older Java). A class can implement multiple interfaces.interface Flyable { void fly(); // every class implementing this MUST define fly()}interface Swimmable { void swim();}class Duck implements Flyable, Swimmable { @Override public void fly() { System.out.println("Duck is flying!"); } @Override public void swim() { System.out.println("Duck is swimming!"); }}Duck duck = new Duck();duck.fly(); // Duck is flying!duck.swim(); // Duck is swimming!Key difference between abstract class and interface:A class can extend only one abstract class but can implement multiple interfaces. Use abstract class when classes share common code. Use interface when you want to define a contract that unrelated classes can follow.Access Modifiers — Quick ReferenceAccess modifiers control who can access your class members:ModifierSame ClassSame PackageSubclassEverywhereprivate✅❌❌❌default✅✅❌❌protected✅✅✅❌public✅✅✅✅General rule — make fields private, make methods public unless there is a reason not to. This is encapsulation in practice.Quick Summary — All OOPs Concepts in One PlaceClass — Blueprint/template that defines structure and behaviorObject — Real instance created from a class using newConstructor — Special method that initializes an object when createdEncapsulation — Bundle data and methods together, control access with private/publicInheritance — Child class gets parent's properties and behaviors using extendsPolymorphism — Same method name behaves differently (overriding = runtime, overloading = compile time)Abstraction — Hide complexity, show only essentials using abstract class or interfaceFAQs — People Also AskQ1. What is the difference between a class and an object in Java? A class is the blueprint — it defines structure but does not exist in memory as a usable thing. An object is a real instance created from that blueprint using new. You can create many objects from one class, just like building many houses from one blueprint.Q2. What is the difference between abstract class and interface in Java? An abstract class can have both abstract (no body) and concrete (with body) methods, and a class can extend only one. An interface traditionally has only abstract methods and a class can implement multiple interfaces. Use abstract class for shared code, interface for defining contracts.Q3. What is the difference between method overriding and overloading? Overriding happens in a parent-child relationship — the child redefines a parent method with the same name and parameters. Overloading happens in the same class — same method name but different parameters. Overriding is resolved at runtime, overloading at compile time.Q4. Why is OOPs important in Java? Java is built entirely around OOPs. Every piece of Java code lives inside a class. OOPs enables code reuse through inheritance, data protection through encapsulation, flexibility through polymorphism, and simplicity through abstraction — all essential for building large, maintainable applications.ConclusionOOPs in Java is not a collection of confusing terms — it is a natural way of thinking about and organizing code. Classes are blueprints, objects are real things, encapsulation protects data, inheritance reuses code, polymorphism provides flexibility, and abstraction hides complexity.Once these four pillars feel natural, you will start seeing them everywhere — in every Java library, every framework, every codebase. That is when Java truly starts to click.

OOPsJavaClassesObjectsInheritancePolymorphismEncapsulationAbstraction

Stack Data Structure in Java: The Complete In-Depth Guide

1. What Is a Stack?A Stack is a linear data structure that stores elements in a sequential order, but with one strict rule — you can only insert or remove elements from one end, called the top.It is one of the simplest yet most powerful data structures in computer science. Its strength comes from its constraint. Because everything happens at one end, the behavior of a stack is completely predictable.The formal definition: A Stack is a linear data structure that follows the Last In, First Out (LIFO) principle — the element inserted last is the first one to be removed.Here is what a stack looks like visually: ┌──────────┐ │ 50 │ ← TOP (last inserted, first removed) ├──────────┤ │ 40 │ ├──────────┤ │ 30 │ ├──────────┤ │ 20 │ ├──────────┤ │ 10 │ ← BOTTOM (first inserted, last removed) └──────────┘When you push 60 onto this stack, it goes on top. When you pop, 60 comes out first. That is LIFO.2. Real-World AnalogiesBefore writing a single line of code, it helps to see stacks in the real world. These analogies will make the concept permanently stick.A Pile of Plates In a cafeteria, clean plates are stacked on top of each other. You always pick the top plate. You always place a new plate on top. You never reach into the middle. This is a stack.Browser Back Button Every time you visit a new webpage, it gets pushed onto a history stack. When you press the Back button, the browser pops the most recent page off the stack and takes you there. The page you visited first is at the bottom — you only reach it after going back through everything else.Undo Feature in Text Editors When you type in a document and press Ctrl+Z, the most recent action is undone first. That is because every action you perform is pushed onto a stack. Undo simply pops from that stack.Call Stack in Programming When a function calls another function, the current function's state is pushed onto the call stack. When the inner function finishes, it is popped off and execution returns to the outer function. This is the literal stack your programs run on.A Stack of Books Put five books on a table, one on top of another. You can only take the top book without knocking the pile over. That is a stack.3. The LIFO Principle ExplainedLIFO stands for Last In, First Out.It means whatever you put in last is the first thing to come out. This is the exact opposite of a Queue (which is FIFO — First In, First Out).Let us trace through an example step by step:Start: Stack is empty → []Push 10 → [10] (10 is at the top)Push 20 → [10, 20] (20 is at the top)Push 30 → [10, 20, 30] (30 is at the top)Pop → returns 30 (30 was last in, first out) Stack: [10, 20]Pop → returns 20 Stack: [10]Peek → returns 10 (just looks, does not remove) Stack: [10]Pop → returns 10 Stack: [] (stack is now empty)Every single operation happens only at the top. The bottom of the stack is never directly accessible.4. Stack Operations & Time ComplexityA stack supports the following core operations:OperationDescriptionTime Complexitypush(x)Insert element x onto the top of the stackO(1)pop()Remove and return the top elementO(1)peek() / top()Return the top element without removing itO(1)isEmpty()Check if the stack has no elementsO(1)isFull()Check if the stack has reached its capacity (Array only)O(1)size()Return the number of elements in the stackO(1)search(x)Find position of element from top (Java built-in only)O(n)All primary stack operations — push, pop, peek, isEmpty — run in O(1) constant time. This is what makes the stack so efficient. It does not matter whether the stack has 10 elements or 10 million — these operations are always instant.Space complexity for a stack holding n elements is O(n).5. Implementation 1 — Using a Static ArrayThis is the most fundamental way to implement a stack. We use a fixed-size array and a variable called top to track where the top of the stack currently is.How it works:top starts at -1 (stack is empty)On push: increment top, then place the element at arr[top]On pop: return arr[top], then decrement topOn peek: return arr[top] without changing it// StackUsingArray.javapublic class StackUsingArray { private int[] arr; private int top; private int capacity; // Constructor — initialize with a fixed capacity public StackUsingArray(int capacity) { this.capacity = capacity; arr = new int[capacity]; top = -1; } // Push: add element to the top public void push(int value) { if (isFull()) { System.out.println("Stack Overflow! Cannot push " + value); return; } arr[++top] = value; System.out.println("Pushed: " + value); } // Pop: remove and return top element public int pop() { if (isEmpty()) { System.out.println("Stack Underflow! Stack is empty."); return -1; } return arr[top--]; } // Peek: view the top element without removing public int peek() { if (isEmpty()) { System.out.println("Stack is empty."); return -1; } return arr[top]; } // Check if stack is empty public boolean isEmpty() { return top == -1; } // Check if stack is full public boolean isFull() { return top == capacity - 1; } // Return current size public int size() { return top + 1; } // Display all elements public void display() { if (isEmpty()) { System.out.println("Stack is empty."); return; } System.out.print("Stack (top → bottom): "); for (int i = top; i >= 0; i--) { System.out.print(arr[i] + " "); } System.out.println(); } // Main method to test public static void main(String[] args) { StackUsingArray stack = new StackUsingArray(5); stack.push(10); stack.push(20); stack.push(30); stack.push(40); stack.push(50); stack.push(60); // This will trigger Stack Overflow stack.display(); System.out.println("Peek: " + stack.peek()); System.out.println("Pop: " + stack.pop()); System.out.println("Pop: " + stack.pop()); stack.display(); System.out.println("Size: " + stack.size()); }}```**Output:**```Pushed: 10Pushed: 20Pushed: 30Pushed: 40Pushed: 50Stack Overflow! Cannot push 60Stack (top → bottom): 50 40 30 20 10Peek: 50Pop: 50Pop: 40Stack (top → bottom): 30 20 10Size: 3Key Points about Array Implementation:Fixed size — you must declare capacity upfrontVery fast — direct array index accessStack Overflow is possible if capacity is exceededMemory is pre-allocated even if stack is not full6. Implementation 2 — Using an ArrayListAn ArrayList-based stack removes the fixed-size limitation. The ArrayList grows dynamically, so you never have to worry about stack overflow due to capacity.How it works:The end of the ArrayList acts as the topadd() is used for pushremove(size - 1) is used for popget(size - 1) is used for peek// StackUsingArrayList.javaimport java.util.ArrayList;public class StackUsingArrayList { private ArrayList<Integer> list; // Constructor public StackUsingArrayList() { list = new ArrayList<>(); } // Push: add to the end (which is our top) public void push(int value) { list.add(value); System.out.println("Pushed: " + value); } // Pop: remove and return the last element public int pop() { if (isEmpty()) { System.out.println("Stack Underflow! Stack is empty."); return -1; } int top = list.get(list.size() - 1); list.remove(list.size() - 1); return top; } // Peek: view the last element public int peek() { if (isEmpty()) { System.out.println("Stack is empty."); return -1; } return list.get(list.size() - 1); } // Check if stack is empty public boolean isEmpty() { return list.isEmpty(); } // Return size public int size() { return list.size(); } // Display elements from top to bottom public void display() { if (isEmpty()) { System.out.println("Stack is empty."); return; } System.out.print("Stack (top → bottom): "); for (int i = list.size() - 1; i >= 0; i--) { System.out.print(list.get(i) + " "); } System.out.println(); } // Main method to test public static void main(String[] args) { StackUsingArrayList stack = new StackUsingArrayList(); stack.push(5); stack.push(15); stack.push(25); stack.push(35); stack.display(); System.out.println("Peek: " + stack.peek()); System.out.println("Pop: " + stack.pop()); System.out.println("Pop: " + stack.pop()); stack.display(); System.out.println("Is Empty: " + stack.isEmpty()); System.out.println("Size: " + stack.size()); }}```**Output:**```Pushed: 5Pushed: 15Pushed: 25Pushed: 35Stack (top → bottom): 35 25 15 5Peek: 35Pop: 35Pop: 25Stack (top → bottom): 15 5Is Empty: falseSize: 2Key Points about ArrayList Implementation:Dynamic size — grows automatically as neededNo overflow riskSlight overhead compared to raw array due to ArrayList internalsExcellent for most practical use cases7. Implementation 3 — Using a LinkedListA LinkedList-based stack is the most memory-efficient approach when you do not know the stack size in advance. Each element (node) holds data and a pointer to the next node. The head of the LinkedList acts as the top of the stack.How it works:Each node stores a value and a reference to the node below itPush creates a new node and makes it the new headPop removes the head node and returns its valuePeek returns the head node's value without removing it// StackUsingLinkedList.javapublic class StackUsingLinkedList { // Inner Node class private static class Node { int data; Node next; Node(int data) { this.data = data; this.next = null; } } private Node top; // Head of the linked list = top of stack private int size; // Constructor public StackUsingLinkedList() { top = null; size = 0; } // Push: create new node and link it to top public void push(int value) { Node newNode = new Node(value); newNode.next = top; // new node points to current top top = newNode; // new node becomes the new top size++; System.out.println("Pushed: " + value); } // Pop: remove and return top node's data public int pop() { if (isEmpty()) { System.out.println("Stack Underflow! Stack is empty."); return -1; } int value = top.data; top = top.next; // move top pointer to next node size--; return value; } // Peek: return top node's data without removing public int peek() { if (isEmpty()) { System.out.println("Stack is empty."); return -1; } return top.data; } // Check if empty public boolean isEmpty() { return top == null; } // Return size public int size() { return size; } // Display elements from top to bottom public void display() { if (isEmpty()) { System.out.println("Stack is empty."); return; } System.out.print("Stack (top → bottom): "); Node current = top; while (current != null) { System.out.print(current.data + " "); current = current.next; } System.out.println(); } // Main method to test public static void main(String[] args) { StackUsingLinkedList stack = new StackUsingLinkedList(); stack.push(100); stack.push(200); stack.push(300); stack.push(400); stack.display(); System.out.println("Peek: " + stack.peek()); System.out.println("Pop: " + stack.pop()); System.out.println("Pop: " + stack.pop()); stack.display(); System.out.println("Size: " + stack.size()); }}```**Output:**```Pushed: 100Pushed: 200Pushed: 300Pushed: 400Stack (top → bottom): 400 300 200 100Peek: 400Pop: 400Pop: 300Stack (top → bottom): 200 100Size: 2Key Points about LinkedList Implementation:Truly dynamic — each node allocated only when neededNo wasted memory from pre-allocationSlightly more memory per element (each node carries a pointer)Ideal for stacks where size is completely unknown8. Java's Built-in Stack ClassJava provides a ready-made Stack class inside java.util. It extends Vector and is thread-safe by default.// JavaBuiltinStack.javaimport java.util.Stack;public class JavaBuiltinStack { public static void main(String[] args) { Stack<Integer> stack = new Stack<>(); // Push elements stack.push(10); stack.push(20); stack.push(30); stack.push(40); System.out.println("Stack: " + stack); // Peek — look at top without removing System.out.println("Peek: " + stack.peek()); // Pop — remove top System.out.println("Pop: " + stack.pop()); System.out.println("After pop: " + stack); // Search — returns 1-based position from top System.out.println("Search 20: position " + stack.search(20)); // isEmpty System.out.println("Is Empty: " + stack.isEmpty()); // Size System.out.println("Size: " + stack.size()); }}```**Output:**```Stack: [10, 20, 30, 40]Peek: 40Pop: 40After pop: [10, 20, 30]Search 20: position 2Is Empty: falseSize: 3Important Note: In modern Java development, it is often recommended to use Deque (specifically ArrayDeque) instead of Stack for better performance, since Stack is synchronized and carries the overhead of Vector.// Using ArrayDeque as a stack (modern preferred approach)import java.util.ArrayDeque;import java.util.Deque;public class ModernStack { public static void main(String[] args) { Deque<Integer> stack = new ArrayDeque<>(); stack.push(10); // pushes to front stack.push(20); stack.push(30); System.out.println("Top: " + stack.peek()); System.out.println("Pop: " + stack.pop()); System.out.println("Stack: " + stack); }}9. Comparison of All ImplementationsFeatureArrayArrayListLinkedListJava StackArrayDequeSizeFixedDynamicDynamicDynamicDynamicStack Overflow RiskYesNoNoNoNoMemory UsagePre-allocatedAuto-growsPer-node overheadAuto-growsAuto-growsPush TimeO(1)O(1) amortizedO(1)O(1)O(1)Pop TimeO(1)O(1)O(1)O(1)O(1)Peek TimeO(1)O(1)O(1)O(1)O(1)Thread SafeNoNoNoYesNoBest ForKnown size, max speedGeneral useUnknown/huge sizeLegacy codeModern Java10. Advantages & DisadvantagesAdvantagesAdvantageExplanationSimple to implementVery few rules and operations to worry aboutO(1) operationsPush, pop, and peek are all constant timeMemory efficientNo extra pointers needed (array-based)Supports recursionThe call stack is itself a stackEasy undo/redoNatural fit for reversible action trackingBacktrackingPerfectly suited for maze, puzzle, and game solvingExpression evaluationPowers compilers and calculatorsDisadvantagesDisadvantageExplanationLimited accessCannot access elements in the middle directlyFixed size (array)Array-based stacks overflow if size is exceededNo random accessYou cannot do stack[2] — only top is accessibleMemory waste (array)Pre-allocated array wastes space if underusedNot suitable for all problemsMany problems need queues, trees, or graphs insteadStack overflow in recursionVery deep recursion can overflow the JVM call stack11. Real-World Use Cases of StackUnderstanding when to use a stack is just as important as knowing how to implement one. Here is where stacks show up in real software:Function Call Management (Call Stack) Every time your Java program calls a method, the JVM pushes that method's frame onto the call stack. When the method returns, the frame is popped. This is why you see "StackOverflowError" when you write infinite recursion.Undo and Redo Operations Text editors, image editors (Photoshop), and IDEs use two stacks — one for undo history and one for redo history. Every action pushes onto the undo stack. Ctrl+Z pops from it and pushes to the redo stack.Browser Navigation Your browser maintains a back-stack and a forward-stack. Visiting a new page pushes to the back-stack. Pressing Back pops from it and pushes to the forward-stack.Expression Evaluation and Conversion Compilers use stacks to evaluate arithmetic expressions and convert between infix, prefix, and postfix notations. For example: 3 + 4 * 2 must be evaluated considering operator precedence — this is done with a stack.Balanced Parentheses Checking Linters, compilers, and IDEs use stacks to check if brackets are balanced: {[()]} is valid, {[(])} is not.Backtracking Algorithms Maze solving, N-Queens, Sudoku solvers, and depth-first search all use stacks (explicitly or via recursion) to backtrack to previous states when a path fails.Syntax Parsing Compilers parse source code using stacks to match opening and closing constructs like if/else, try/catch, { and }.12. Practice Problems with Full SolutionsHere is where things get really interesting. These problems will sharpen your stack intuition and prepare you for coding interviews.Problem 1 — Reverse a String Using a StackDifficulty: EasyProblem: Write a Java program to reverse a string using a Stack.Approach: Push every character of the string onto a stack, then pop them all. Since LIFO reverses the order, the characters come out reversed.// ReverseString.javaimport java.util.Stack;public class ReverseString { public static String reverse(String str) { Stack<Character> stack = new Stack<>(); // Push all characters for (char c : str.toCharArray()) { stack.push(c); } // Pop all characters to build reversed string StringBuilder reversed = new StringBuilder(); while (!stack.isEmpty()) { reversed.append(stack.pop()); } return reversed.toString(); } public static void main(String[] args) { System.out.println(reverse("hello")); // olleh System.out.println(reverse("java")); // avaj System.out.println(reverse("racecar")); // racecar (palindrome) System.out.println(reverse("datastructure")); // erutcurtasatad }}Problem 2 — Check Balanced ParenthesesDifficulty: Easy–MediumProblem: Given a string containing (, ), {, }, [, ], determine if the brackets are balanced.Approach: Push every opening bracket onto the stack. When you see a closing bracket, check if it matches the top of the stack. If it does, pop. If it does not, the string is unbalanced.// BalancedParentheses.javaimport java.util.Stack;public class BalancedParentheses { public static boolean isBalanced(String expr) { Stack<Character> stack = new Stack<>(); for (char c : expr.toCharArray()) { // Push all opening brackets if (c == '(' || c == '{' || c == '[') { stack.push(c); } // For closing brackets, check the top of stack else if (c == ')' || c == '}' || c == ']') { if (stack.isEmpty()) return false; char top = stack.pop(); if (c == ')' && top != '(') return false; if (c == '}' && top != '{') return false; if (c == ']' && top != '[') return false; } } // Stack must be empty at the end for a balanced expression return stack.isEmpty(); } public static void main(String[] args) { System.out.println(isBalanced("{[()]}")); // true System.out.println(isBalanced("{[(])}")); // false System.out.println(isBalanced("((()))")); // true System.out.println(isBalanced("{]")); // false System.out.println(isBalanced("")); // true (empty is balanced) }}Problem 3 — Reverse a Stack (Without Extra Data Structure)Difficulty: Medium–HardProblem: Reverse all elements of a stack using only recursion — no array or extra stack allowed.Approach: This is a classic recursion problem. You need two recursive functions:insertAtBottom(stack, item) — inserts an element at the very bottom of the stackreverseStack(stack) — pops all elements, reverses, and uses insertAtBottom to rebuild// ReverseStack.javaimport java.util.Stack;public class ReverseStack { // Insert an element at the bottom of the stack public static void insertAtBottom(Stack<Integer> stack, int item) { if (stack.isEmpty()) { stack.push(item); return; } int top = stack.pop(); insertAtBottom(stack, item); stack.push(top); } // Reverse the stack using insertAtBottom public static void reverseStack(Stack<Integer> stack) { if (stack.isEmpty()) return; int top = stack.pop(); reverseStack(stack); // reverse the remaining stack insertAtBottom(stack, top); // insert popped element at bottom } public static void main(String[] args) { Stack<Integer> stack = new Stack<>(); stack.push(1); stack.push(2); stack.push(3); stack.push(4); stack.push(5); System.out.println("Before: " + stack); // [1, 2, 3, 4, 5] reverseStack(stack); System.out.println("After: " + stack); // [5, 4, 3, 2, 1] }}Problem 4 — Evaluate a Postfix ExpressionDifficulty: MediumProblem: Evaluate a postfix (Reverse Polish Notation) expression. Example: "2 3 4 * +" should return 14 because it is 2 + (3 * 4).Approach: Scan left to right. If you see a number, push it. If you see an operator, pop two numbers, apply the operator, and push the result.// PostfixEvaluation.javaimport java.util.Stack;public class PostfixEvaluation { public static int evaluate(String expression) { Stack<Integer> stack = new Stack<>(); String[] tokens = expression.split(" "); for (String token : tokens) { // If it's a number, push it if (token.matches("-?\\d+")) { stack.push(Integer.parseInt(token)); } // If it's an operator, pop two and apply else { int b = stack.pop(); // second operand int a = stack.pop(); // first operand switch (token) { case "+": stack.push(a + b); break; case "-": stack.push(a - b); break; case "*": stack.push(a * b); break; case "/": stack.push(a / b); break; } } } return stack.pop(); } public static void main(String[] args) { System.out.println(evaluate("2 3 4 * +")); // 14 → 2 + (3*4) System.out.println(evaluate("5 1 2 + 4 * + 3 -")); // 14 → 5+((1+2)*4)-3 System.out.println(evaluate("3 4 +")); // 7 }}Problem 5 — Next Greater ElementDifficulty: MediumProblem: For each element in an array, find the next greater element to its right. If none exists, output -1.Example: Input: [4, 5, 2, 10, 8] → Output: [5, 10, 10, -1, -1]Approach: Iterate right to left. Maintain a stack of candidates. For each element, pop all stack elements that are smaller than or equal to it — they can never be the answer for any element to the left. The top of the stack (if not empty) is the next greater element.// NextGreaterElement.javaimport java.util.Stack;import java.util.Arrays;public class NextGreaterElement { public static int[] nextGreater(int[] arr) { int n = arr.length; int[] result = new int[n]; Stack<Integer> stack = new Stack<>(); // stores elements, not indices // Traverse from right to left for (int i = n - 1; i >= 0; i--) { // Pop elements smaller than or equal to current while (!stack.isEmpty() && stack.peek() <= arr[i]) { stack.pop(); } // Next greater element result[i] = stack.isEmpty() ? -1 : stack.peek(); // Push current element for future comparisons stack.push(arr[i]); } return result; } public static void main(String[] args) { int[] arr1 = {4, 5, 2, 10, 8}; System.out.println(Arrays.toString(nextGreater(arr1))); // [5, 10, 10, -1, -1] int[] arr2 = {1, 3, 2, 4}; System.out.println(Arrays.toString(nextGreater(arr2))); // [3, 4, 4, -1] int[] arr3 = {5, 4, 3, 2, 1}; System.out.println(Arrays.toString(nextGreater(arr3))); // [-1, -1, -1, -1, -1] }}Problem 6 — Sort a Stack Using RecursionDifficulty: HardProblem: Sort a stack in ascending order (smallest on top) using only recursion — no loops, no extra data structure.// SortStack.javaimport java.util.Stack;public class SortStack { // Insert element in correct sorted position public static void sortedInsert(Stack<Integer> stack, int item) { if (stack.isEmpty() || item > stack.peek()) { stack.push(item); return; } int top = stack.pop(); sortedInsert(stack, item); stack.push(top); } // Sort the stack public static void sortStack(Stack<Integer> stack) { if (stack.isEmpty()) return; int top = stack.pop(); sortStack(stack); // sort remaining sortedInsert(stack, top); // insert top in sorted position } public static void main(String[] args) { Stack<Integer> stack = new Stack<>(); stack.push(34); stack.push(3); stack.push(31); stack.push(98); stack.push(92); stack.push(23); System.out.println("Before sort: " + stack); sortStack(stack); System.out.println("After sort: " + stack); // smallest on top }}13. Summary & Key TakeawaysA stack is a simple, elegant, and powerful data structure. Here is everything in one place:What it is: A linear data structure that follows LIFO — Last In, First Out.Core operations: push (add to top), pop (remove from top), peek (view top), isEmpty — all in O(1) time.Three ways to implement it in Java:Array-based: fast, fixed size, risk of overflowArrayList-based: dynamic, easy, slightly more overheadLinkedList-based: truly dynamic, memory-efficient per-element, best for unknown sizesWhen to use it:Undo/redo systemsBrowser navigationBalancing brackets and parenthesesEvaluating mathematical expressionsBacktracking problemsManaging recursive function callsDepth-first searchWhen NOT to use it:When you need random access to elementsWhen insertion/deletion is needed from both ends (use Deque)When you need to search efficiently (use HashMap or BST)Modern Java recommendation: Prefer ArrayDeque over the legacy Stack class for non-thread-safe scenarios. Use Stack only when you need synchronized access.The stack is one of those data structures that once you truly understand, you start seeing it everywhere — in your browser, in your IDE, in recursive algorithms, and deep within the operating system itself.This article covered everything from the fundamentals of the Stack data structure to multiple Java implementations, time complexity analysis, real-world applications, and six practice problems of increasing difficulty. Bookmark it as a reference and revisit the practice problems regularly — they are the real test of your understanding.

DataStructuresJavaStackDataStructureLIFO

What Is Dynamic Programming? Origin Story, Real-Life Uses, LeetCode Problems & Complete Beginner Guide

Introduction — Why Dynamic Programming Feels Hard (And Why It Isn't)If you've ever stared at a LeetCode problem, read the solution, understood every single line, and still had absolutely no idea how someone arrived at it — welcome. You've just experienced the classic Dynamic Programming (DP) confusion.DP has a reputation. People treat it like some dark art reserved for competitive programmers or Google engineers. The truth? Dynamic Programming is one of the most logical, learnable, and satisfying techniques in all of computer science. Once it clicks, it really clicks.This guide will take you from zero to genuinely confident. We'll cover where DP came from, how it works, what patterns to learn, how to recognize DP problems, real-world places it shows up, LeetCode problems to practice, time complexity analysis, and the mistakes that trip up even experienced developers.Let's go.The Origin Story — Who Invented Dynamic Programming and Why?The term "Dynamic Programming" was coined by Richard Bellman in the early 1950s while working at RAND Corporation. Here's the funny part: the name was deliberately chosen to sound impressive and vague.Bellman was doing mathematical research that his employer — the US Secretary of Defense, Charles Wilson — would have found difficult to fund if described accurately. Wilson had a well-known distaste for the word "research." So Bellman invented a name that sounded suitably grand and mathematical: Dynamic Programming.In his autobiography, Bellman wrote that he picked the word "dynamic" because it had a precise technical meaning and was also impossible to use negatively. "Programming" referred to the mathematical sense — planning and decision-making — not computer programming.The underlying idea? Break a complex problem into overlapping subproblems, solve each subproblem once, and store the result so you never solve it twice.Bellman's foundational contribution was the Bellman Equation, which underpins not just algorithms but also economics, operations research, and modern reinforcement learning.So the next time DP feels frustrating, remember — even its inventor named it specifically to confuse people. You're in good company.What Is Dynamic Programming? (Simple Definition)Dynamic Programming is an algorithmic technique used to solve problems by:Breaking them down into smaller overlapping subproblemsSolving each subproblem only onceStoring the result (memoization or tabulation)Building up the final solution from those stored resultsThe key insight is overlapping subproblems + optimal substructure.Overlapping subproblems means the same smaller problems come up again and again. Instead of solving them every time (like plain recursion does), DP solves them once and caches the answer.Optimal substructure means the optimal solution to the whole problem can be built from optimal solutions to its subproblems.If a problem has both these properties — it's a DP problem.The Two Approaches to Dynamic Programming1. Top-Down with Memoization (Recursive + Cache)You write a recursive solution exactly as you would naturally, but add a cache (usually a dictionary or array) to store results you've already computed.fib(n):if n in cache: return cache[n]if n <= 1: return ncache[n] = fib(n-1) + fib(n-2)return cache[n]This is called memoization — remember what you computed so you don't repeat yourself.Pros: Natural to write, mirrors the recursive thinking, easy to reason about. Cons: Stack overhead from recursion, risk of stack overflow on large inputs.2. Bottom-Up with Tabulation (Iterative)You figure out the order in which subproblems need to be solved, then solve them iteratively from the smallest up, filling a table.fib(n):dp = [0, 1]for i from 2 to n:dp[i] = dp[i-1] + dp[i-2]return dp[n]This is called tabulation — fill a table, cell by cell, bottom to top.Pros: No recursion overhead, usually faster in practice, easier to optimize space. Cons: Requires thinking about the order of computation upfront.🧩 Dynamic Programming Template CodeBefore diving into how to recognize DP problems, here are ready-to-use Java templates for every major DP pattern. Think of these as your reusable blueprints — every DP problem you ever solve will fit into one of these structures. Just define your state, plug in your recurrence relation, and you are good to go.Template 1 — Top-Down (Memoization)import java.util.HashMap;import java.util.Map;public class TopDownDP {Map<Integer, Integer> memo = new HashMap<>();public int solve(int n) {// Base caseif (n <= 1) return n;// Check cacheif (memo.containsKey(n)) return memo.get(n);// Recurrence relation — change this part for your problemint result = solve(n - 1) + solve(n - 2);// Store in cachememo.put(n, result);return result;}}Template 2 — Bottom-Up (Tabulation)public class BottomUpDP {public int solve(int n) {// Create DP tableint[] dp = new int[n + 1];// Base casesdp[0] = 0;dp[1] = 1;// Fill the table bottom-upfor (int i = 2; i <= n; i++) {// Recurrence relation — change this part for your problemdp[i] = dp[i - 1] + dp[i - 2];}return dp[n];}}Template 3 — Bottom-Up with Space Optimizationpublic class SpaceOptimizedDP {public int solve(int n) {// Only keep last two values instead of full tableint prev2 = 0;int prev1 = 1;for (int i = 2; i <= n; i++) {// Recurrence relation — change this part for your problemint curr = prev1 + prev2;prev2 = prev1;prev1 = curr;}return prev1;}}Template 4 — 2D DP (Two Sequences or Grid)public class TwoDimensionalDP {public int solve(String s1, String s2) {int m = s1.length();int n = s2.length();// Create 2D DP tableint[][] dp = new int[m + 1][n + 1];// Base cases — first row and columnfor (int i = 0; i <= m; i++) dp[i][0] = i;for (int j = 0; j <= n; j++) dp[0][j] = j;// Fill table cell by cellfor (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {// Recurrence relation — change this part for your problemif (s1.charAt(i - 1) == s2.charAt(j - 1)) {dp[i][j] = dp[i - 1][j - 1];} else {dp[i][j] = 1 + Math.min(dp[i - 1][j],Math.min(dp[i][j - 1], dp[i - 1][j - 1]));}}}return dp[m][n];}}Template 5 — Knapsack Patternpublic class KnapsackDP {public int solve(int[] weights, int[] values, int capacity) {int n = weights.length;// dp[i][w] = max value using first i items with capacity wint[][] dp = new int[n + 1][capacity + 1];for (int i = 1; i <= n; i++) {for (int w = 0; w <= capacity; w++) {// Don't take item idp[i][w] = dp[i - 1][w];// Take item i if it fitsif (weights[i - 1] <= w) {dp[i][w] = Math.max(dp[i][w],values[i - 1] + dp[i - 1][w - weights[i - 1]]);}}}return dp[n][capacity];}}💡 How to use these templates:Step 1 — Identify which pattern your problem fits into. Step 2 — Define what dp[i] or dp[i][j] means in plain English before writing any code. Step 3 — Write your recurrence relation on paper first. Step 4 — Plug it into the matching template above. Step 5 — Handle your specific base cases carefully.🎥 Visual Learning Resource — Watch This Before Moving ForwardIf you prefer learning by watching before reading, this free full-length course by freeCodeCamp is one of the best Dynamic Programming resources on the internet. Watch it alongside this guide for maximum understanding.Credit: freeCodeCamp — a free, nonprofit coding education platform.How to Recognize a Dynamic Programming ProblemAsk yourself these four questions:1. Can I define the problem in terms of smaller versions of itself? If you can write a recursive formula (recurrence relation), DP might apply.2. Do the subproblems overlap? If a naive recursive solution would recompute the same thing many times, DP is the right tool.3. Is there an optimal substructure? Is the best answer to the big problem made up of best answers to smaller problems?4. Are you looking for a count, minimum, maximum, or yes/no answer? DP problems often ask: "What is the minimum cost?", "How many ways?", "Can we achieve X?"Red flag words in problem statements: minimum, maximum, shortest, longest, count the number of ways, can we reach, is it possible, fewest steps.The Core DP Patterns You Must LearnMastering DP is really about recognizing patterns. Here are the most important ones:Pattern 1 — 1D DP (Linear) Problems where the state depends on previous elements in a single sequence. Examples: Fibonacci, Climbing Stairs, House Robber.Pattern 2 — 2D DP (Grid / Two-sequence) Problems with two dimensions of state, often grids or two strings. Examples: Longest Common Subsequence, Edit Distance, Unique Paths.Pattern 3 — Interval DP You consider all possible intervals or subarrays and build solutions from them. Examples: Matrix Chain Multiplication, Burst Balloons, Palindrome Partitioning.Pattern 4 — Knapsack DP (0/1 and Unbounded) You decide whether to include or exclude items under a capacity constraint. Examples: 0/1 Knapsack, Coin Change, Partition Equal Subset Sum.Pattern 5 — DP on Trees State is defined per node; you combine results from children. Examples: Diameter of Binary Tree, House Robber III, Maximum Path Sum.Pattern 6 — DP on Subsets / Bitmask DP State includes a bitmask representing which elements have been chosen. Examples: Travelling Salesman Problem, Shortest Superstring.Pattern 7 — DP on Strings Matching, editing, or counting arrangements within strings. Examples: Longest Palindromic Subsequence, Regular Expression Matching, Wildcard Matching.Top LeetCode Problems to Practice Dynamic Programming (With Links)Here are the essential problems, organized by difficulty and pattern. Solve them in this order.Beginner — Warm UpProblemPatternLinkClimbing Stairs1D DPhttps://leetcode.com/problems/climbing-stairs/Fibonacci Number1D DPhttps://leetcode.com/problems/fibonacci-number/House Robber1D DPhttps://leetcode.com/problems/house-robber/Min Cost Climbing Stairs1D DPhttps://leetcode.com/problems/min-cost-climbing-stairs/Best Time to Buy and Sell Stock1D DPhttps://leetcode.com/problems/best-time-to-buy-and-sell-stock/Intermediate — Core PatternsProblemPatternLinkCoin ChangeKnapsackhttps://leetcode.com/problems/coin-change/Longest Increasing Subsequence1D DPhttps://leetcode.com/problems/longest-increasing-subsequence/Longest Common Subsequence2D DPhttps://leetcode.com/problems/longest-common-subsequence/0/1 Knapsack (via Subset Sum)Knapsackhttps://leetcode.com/problems/partition-equal-subset-sum/Unique Paths2D Grid DPhttps://leetcode.com/problems/unique-paths/Jump Game1D DP / Greedyhttps://leetcode.com/problems/jump-game/Word BreakString DPhttps://leetcode.com/problems/word-break/Decode Ways1D DPhttps://leetcode.com/problems/decode-ways/Edit Distance2D String DPhttps://leetcode.com/problems/edit-distance/Triangle2D DPhttps://leetcode.com/problems/triangle/Advanced — Interview LevelProblemPatternLinkBurst BalloonsInterval DPhttps://leetcode.com/problems/burst-balloons/Regular Expression MatchingString DPhttps://leetcode.com/problems/regular-expression-matching/Wildcard MatchingString DPhttps://leetcode.com/problems/wildcard-matching/Palindrome Partitioning IIInterval DPhttps://leetcode.com/problems/palindrome-partitioning-ii/Maximum Profit in Job SchedulingDP + Binary Searchhttps://leetcode.com/problems/maximum-profit-in-job-scheduling/Distinct Subsequences2D DPhttps://leetcode.com/problems/distinct-subsequences/Cherry Pickup3D DPhttps://leetcode.com/problems/cherry-pickup/Real-World Use Cases of Dynamic ProgrammingDP is not just for coding interviews. It is deeply embedded in the technology you use every day.1. Google Maps & Navigation (Shortest Path) The routing engines behind GPS apps use DP-based algorithms like Dijkstra and Bellman-Ford to find the shortest or fastest path between two points across millions of nodes.2. Spell Checkers & Autocorrect (Edit Distance) When your phone corrects "teh" to "the," it is computing Edit Distance — a classic DP problem — between what you typed and every word in the dictionary.3. DNA Sequence Alignment (Bioinformatics) Researchers use the Needleman-Wunsch and Smith-Waterman algorithms — both DP — to align DNA and protein sequences and find similarities between species or identify mutations.4. Video Compression (MPEG, H.264) Modern video codecs use DP to determine the most efficient way to encode video frames, deciding which frames to store as full images and which to store as differences from the previous frame.5. Financial Portfolio Optimization Investment algorithms use DP to find the optimal allocation of assets under risk constraints — essentially a variant of the knapsack problem.6. Natural Language Processing (NLP) The Viterbi algorithm — used in speech recognition, part-of-speech tagging, and machine translation — is a DP algorithm. Every time Siri or Google Assistant understands your sentence, DP played a role.7. Game AI (Chess, Checkers) Game trees and minimax algorithms with memoization use DP to evaluate board positions and find the best move without recomputing already-seen positions.8. Compiler Optimization Compilers use DP to decide the optimal order of operations and instruction scheduling to generate the most efficient machine code.9. Text Justification (Word Processors) Microsoft Word and LaTeX use DP to optimally break paragraphs into lines — minimizing raggedness and maximizing visual appeal.10. Resource Scheduling in Cloud Computing AWS, Google Cloud, and Azure use DP-based scheduling to assign computational tasks to servers in the most cost-efficient way possible.Time Complexity Analysis of Common DP ProblemsUnderstanding the time complexity of DP is critical for interviews and for building scalable systems.ProblemTime ComplexitySpace ComplexityNotesFibonacci (naive recursion)O(2ⁿ)O(n)Exponential — terribleFibonacci (DP)O(n)O(1) with optimizationLinear — excellentLongest Common SubsequenceO(m × n)O(m × n)m, n = lengths of two stringsEdit DistanceO(m × n)O(m × n)Can optimize space to O(n)0/1 KnapsackO(n × W)O(n × W)n = items, W = capacityCoin ChangeO(n × amount)O(amount)Classic tabulationLongest Increasing SubsequenceO(n²) or O(n log n)O(n)Binary search version is fasterMatrix Chain MultiplicationO(n³)O(n²)Interval DPTravelling Salesman (bitmask)O(2ⁿ × n²)O(2ⁿ × n)Still exponential but manageable for small nThe general rule: DP trades time for space. You use memory to avoid recomputation. The time complexity equals the number of unique states multiplied by the work done per state.How to Learn and Master Dynamic Programming — Step by StepHere is an honest, structured path to mastery:Step 1 — Get recursion absolutely solid first. DP is memoized recursion at its core. If you cannot write clean recursive solutions confidently, DP will remain confusing. Practice at least 20 pure recursion problems first.Step 2 — Start with the classics. Fibonacci → Climbing Stairs → House Robber → Coin Change. These teach you the core pattern of defining state and transition without overwhelming you.Step 3 — Learn to define state explicitly. Before writing any code, ask: "What does dp[i] represent?" Write it in plain English. "dp[i] = the minimum cost to reach step i." This single habit separates good DP thinkers from struggling ones.Step 4 — Write the recurrence relation before coding. On paper or in a comment. Example: dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]). If you can write the recurrence, the code writes itself.Step 5 — Master one pattern at a time. Don't jump between knapsack and interval DP in the same week. Spend a few days on each pattern until it feels intuitive.Step 6 — Solve the same problem both ways. Top-down and bottom-up. This builds deep understanding of what DP is actually doing.Step 7 — Optimize space after getting correctness. Many 2D DP solutions can use a single row instead of a full matrix. Learn this optimization after you understand the full solution.Step 8 — Do timed practice under interview conditions. Give yourself 35 minutes per problem. Review what you got wrong. DP is a muscle — it builds with reps.Common Mistakes in Dynamic Programming (And How to Avoid Them)Mistake 1 — Jumping to code before defining state. The most common DP error. Always define what dp[i] or dp[i][j] means before writing a single line of code.Mistake 2 — Wrong base cases. A single wrong base case corrupts every answer built on top of it. Trace through your base cases manually on a tiny example before running code.Mistake 3 — Off-by-one errors in indexing. Whether your dp array is 0-indexed or 1-indexed must be 100% consistent throughout. This causes more bugs in DP than almost anything else.Mistake 4 — Confusing top-down with bottom-up state order. In bottom-up DP, you must ensure that when you compute dp[i], all values it depends on are already filled. If you compute in the wrong order, you get garbage answers.Mistake 5 — Memoizing in the wrong dimension. In 2D problems, some people cache only one dimension when the state actually requires two. Always identify all variables that affect the outcome.Mistake 6 — Using global mutable state in recursion. If you use a shared array and don't clear it between test cases, you'll get wrong answers on subsequent inputs. Always scope your cache correctly.Mistake 7 — Not considering the full state space. In problems like Knapsack, forgetting that the state is (item index, remaining capacity) — not just item index — leads to fundamentally wrong solutions.Mistake 8 — Giving up after not recognizing the pattern immediately. DP problems don't announce themselves. The skill is learning to ask "is there overlapping subproblems here?" on every problem. This takes time. Don't mistake unfamiliarity for inability.Frequently Asked Questions About Dynamic ProgrammingQ: Is Dynamic Programming the same as recursion? Not exactly. Recursion is a technique for breaking problems into smaller pieces. DP is recursion plus memoization — or iterative tabulation. All DP can be written recursively, but not all recursion is DP.Q: What is the difference between DP and Divide and Conquer? Divide and Conquer (like Merge Sort) breaks problems into non-overlapping subproblems. DP is used when subproblems overlap — meaning the same subproblem is solved multiple times in a naive approach.Q: How do I know when NOT to use DP? If the subproblems don't overlap (no repeated computation), greedy or divide-and-conquer may be better. If the problem has no optimal substructure, DP won't give a correct answer.Q: Do I need to memorize DP solutions for interviews? No. You need to recognize patterns and be able to derive the recurrence relation. Memorizing solutions without understanding them will fail you in interviews. Focus on the thinking process.Q: How long does it take to get good at DP? Most people start to feel genuinely comfortable after solving 40–60 varied DP problems with deliberate practice. The first 10 feel impossible. The next 20 feel hard. After 50, patterns start feeling obvious.Q: What programming language is best for DP? Any language works. Python is often used for learning because its dictionaries make memoization trivial. C++ is preferred in competitive programming for its speed. For interviews, use whatever language you're most comfortable in.Q: What is space optimization in DP? Many DP problems only look back one or two rows to compute the current row. In those cases, you can replace an n×m table with just two arrays (or even one), reducing space complexity from O(n×m) to O(m). This is called space optimization or rolling array technique.Q: Can DP be applied to graph problems? Absolutely. Shortest path algorithms like Bellman-Ford are DP. Longest path in a DAG is DP. DP on trees is a rich subfield. Anywhere you have states and transitions, DP can potentially apply.Q: Is Greedy a type of Dynamic Programming? Greedy is related but distinct. Greedy makes locally optimal choices without reconsidering. DP considers all choices and picks the globally optimal one. Some DP solutions reduce to greedy when the structure allows, but they are different techniques.Q: What resources should I use to learn DP? For structured learning: Neetcode.io (organized problem list), Striver's DP Series on YouTube, and the book "Introduction to Algorithms" (CLRS) for theoretical depth. For practice: LeetCode's Dynamic Programming study plan and Codeforces for competitive DP.Final Thoughts — Dynamic Programming Is a SuperpowerDynamic Programming is genuinely one of the most powerful ideas in computer science. It shows up in your GPS, your autocorrect, your streaming video, your bank's risk models, and the AI assistants you talk to daily.The path to mastering it is not memorization. It is developing the habit of asking: can I break this into smaller problems that overlap? And then learning to define state clearly, write the recurrence, and trust the process.Start with Climbing Stairs. Write dp[i] in plain English before every problem. Solve everything twice — top-down and bottom-up. Do 50 problems with genuine reflection, not just accepted solutions.The click moment will come. And when it does, you'll wonder why it ever felt hard.

Dynamic ProgrammingMemoizationTabulationJavaOrigin StoryRichard Bellman

Climbing Stairs Problem (LeetCode 70) – Complete Guide with Optimized Solutions

IntroductionThe Climbing Stairs problem is one of the most commonly asked coding interview questions for beginners. It is a perfect example to understand recursion, memoization, and dynamic programming (DP).In this article, we will break down the problem step by step and explore multiple approaches—from brute force recursion to an optimized space-efficient solution.Link of Problem: LeetCode – Climbing StairsProblem StatementYou are climbing a staircase that has n steps.Each time, you can either climb 1 step or 2 steps.The goal is to calculate the total number of distinct ways to reach the top.ExampleInput:n = 2Output:2Explanation:1 + 12Input:n = 3Output:3Explanation:1 + 1 + 11 + 22 + 1Key InsightTo reach step n, there are only two possibilities:From step n-1 (taking 1 step)From step n-2 (taking 2 steps)So, the recurrence relation becomes:ways(n) = ways(n-1) + ways(n-2)This is identical to the Fibonacci sequence, making this problem a classic DP question.Approach 1: Recursive Solution (Brute Force)IdeaBreak the problem into smaller subproblems:Count ways to reach n-1Count ways to reach n-2Add both resultsCodeclass Solution { public int climbStairs(int n) { if(n == 0) return 1; if(n < 0) return 0; return climbStairs(n-1) + climbStairs(n-2); }}ComplexityTime Complexity: O(2^n)Space Complexity: O(n)DrawbackThis solution recalculates the same subproblems multiple times, leading to Time Limit Exceeded (TLE) for larger values.Approach 2: Recursion with Memoization (Top-Down DP)IdeaTo optimize recursion, store already computed results using a HashMap.Avoid repeated calculationsConvert exponential time into linear timeCodeimport java.util.HashMap;class Solution { private HashMap<Integer, Integer> memo = new HashMap<>(); public int climbStairs(int n) { if(n == 0) return 1; if(n < 0) return 0; if(memo.containsKey(n)) { return memo.get(n); } int result = climbStairs(n-1) + climbStairs(n-2); memo.put(n, result); return result; }}ComplexityTime Complexity: O(n)Space Complexity: O(n)Why It WorksMemoization ensures each subproblem is solved only once, making recursion efficient and practical.Approach 3: Dynamic Programming (Bottom-Up)IdeaInstead of recursion, build the solution iteratively:Use an array dp[]Store results for each stepBuild from smaller values to larger onesCodeclass Solution { public int climbStairs(int n) { if(n == 1) return n; if(n == 2) return n; if(n == 3) return n; int dp[] = new int[n+1]; dp[0] = 0; dp[1] = 1; dp[2] = 2; for(int i = 3; i <= n; i++) { dp[i] = dp[i-1] + dp[i-2]; } return dp[n]; }}ComplexityTime Complexity: O(n)Space Complexity: O(n)Approach 4: Optimal Solution (Space Optimized)IdeaWe only need the last two values instead of the whole array.Codeclass Solution { public int climbStairs(int n) { if(n <= 2) return n; int prev1 = 1; int prev2 = 2; for(int i = 3; i <= n; i++) { int current = prev1 + prev2; prev1 = prev2; prev2 = current; } return prev2; }}ComplexityTime Complexity: O(n)Space Complexity: O(1)Key TakeawaysThe problem follows a Fibonacci-like patternBrute force recursion is simple but inefficientMemoization converts recursion into an efficient solutionDynamic programming avoids recursion completelySpace optimization reduces memory usage to constant spaceWhen This Problem Is AskedThis question is frequently asked in:Coding interviews (product-based companies)Data Structures & Algorithms examsOnline coding platformsIt evaluates:Problem-solving abilityUnderstanding of recursionOptimization skillsConclusionThe Climbing Stairs problem is a foundational example for learning dynamic programming. Starting with recursion and improving it using memoization and iterative DP demonstrates how to optimize algorithms effectively.Understanding this pattern will help solve many similar problems related to sequences and decision-making.Frequently Asked Questions (FAQs)1. Is this problem related to Fibonacci?Yes, the recurrence relation is exactly the same as the Fibonacci sequence.2. Why does recursion fail for large inputs?Because it recalculates the same values repeatedly, leading to exponential time complexity.3. What is the best approach?The space-optimized approach is the most efficient with O(n) time and O(1) space.

EasyJavaLeetCodeRecursionMemoization

Stack Problems Explained: NGR, NGL, NSR, NSL — The Four-Problem Family You Must Master

IntroductionAmong all the problems built around the Stack data structure, four stand out as a family — they appear repeatedly in coding interviews, competitive programming, and real-world software systems. These four are the Next Greater to the Right (NGR), Next Greater to the Left (NGL), Next Smaller to the Right (NSR), and Next Smaller to the Left (NSL).What makes them special is not just their individual solutions — it is the fact that all four are solved by a single elegant technique called the Monotonic Stack. Learn the pattern once, and you have all four in your toolkit permanently.This guide breaks down each problem with a full solution, step-by-step dry run, edge cases, and the exact reasoning behind every decision in the code. Whether you are preparing for a technical interview or simply want to deeply understand this pattern — you are in the right place.The Story That Makes This ClickBefore any code, let us understand this family of problems with one real-world story.Imagine you are standing in a queue at a cricket stadium. Everyone in the queue has a different height. You are standing somewhere in the middle. You look to your right and ask — who is the first person taller than me? That is your Next Greater Element to the Right (NGR).Now you look to your left — who is the first person taller than me on this side? That is your Next Greater to the Left (NGL).Now instead of taller, you ask shorter — who is the first shorter person to my right? That is Next Smaller to the Right (NSR).And shorter to your left? That is Next Smaller to the Left (NSL).Same queue. Same people. Four different questions. Four different answers. This is exactly what these four problems are about — and they all share the same solution pattern.What Is a Monotonic Stack?A monotonic stack is just a regular stack with one rule — elements inside it are always maintained in a specific order, either always increasing or always decreasing from bottom to top.You never enforce this rule explicitly. It happens naturally as you pop elements that violate the order before pushing a new one. This popping step is the key insight — the moment you pop an element, you have found its answer for the current element being processed.This one pattern solves all four problems. Only two small details change between them — the direction of traversal and the comparison condition inside the while loop.The Four Problems — Quick ReferenceProblemDirectionWhat You WantProblem LinksNGRTraverse Right to LeftFirst greater on right"Next Greater Element GFG"NGLTraverse Left to RightFirst greater on left"Previous Greater Element GFG"NSRTraverse Right to LeftFirst smaller on right"Next Smaller Element GFG"NSLTraverse Left to RightFirst smaller on left"Previous Smaller Element GFG"Problem 1 — Next Greater Element to Right (NGR)GFG Problem: Search "Next Greater Element" on GeeksForGeeks Difficulty: Medium | Accuracy: 32.95% | Submissions: 515K+The QuestionFor each element in the array, find the first element to its right that is strictly greater than it. If none exists, return -1.Input: [1, 3, 2, 4] Output: [3, 4, 4, -1]Input: [6, 8, 0, 1, 3] Output: [8, -1, 1, 3, -1]Real World ExampleThink of the stock market. You have daily closing prices: [1, 3, 2, 4]. For each day, you want to know — on which future day will the price first exceed today's price? Day 1 has price 1, first exceeded on Day 2 with price 3. Day 2 has price 3, first exceeded on Day 4 with price 4. Day 3 has price 2, also first exceeded on Day 4 with price 4. Day 4 has no future day, so -1. This is exactly NGR — and it is literally used in financial software to detect price breakout points.The IntuitionThe brute force is obvious — for every element, scan everything to its right and find the first greater one. That works but it is O(n²). For an array of 10⁶ elements that becomes 10¹² operations. It will time out on any large input.The stack insight is this — traverse right to left. As you move left, the stack always holds elements you have already seen on the right side. These are the candidates for being the next greater element. Before pushing the current element, pop all stack elements that are smaller than or equal to it. Why? Because the current element is blocking them — for any future element to the left, the current element will always be encountered first, so those smaller popped elements can never be an answer for anything. Whatever remains on top of the stack after popping is the answer for the current element.Step-by-Step Dry RunArray: [1, 3, 2, 4], traversing right to left.i=3, element is 4. Stack is empty. Answer for index 3 is -1. Push 4. Stack: [4]i=2, element is 2. Top of stack is 4, which is greater than 2. Answer for index 2 is 4. Push 2. Stack: [4, 2]i=1, element is 3. Top of stack is 2, which is not greater than 3. Pop 2. Top is now 4, which is greater than 3. Answer for index 1 is 4. Push 3. Stack: [4, 3]i=0, element is 1. Top of stack is 3, which is greater than 1. Answer for index 0 is 3. Push 1. Stack: [4, 3, 1]Answers collected right to left: [-1, 4, 4, 3] After Collections.reverse(): [3, 4, 4, -1] ✓The Code// NGR — Next Greater Element to Rightclass Solution {public ArrayList<Integer> nextLargerElement(int[] arr) {ArrayList<Integer> result = new ArrayList<>();Stack<Integer> st = new Stack<>();// Traverse from RIGHT to LEFTfor (int i = arr.length - 1; i >= 0; i--) {// Pop all elements smaller than or equal to current// They can never be the answer for any element to the leftwhile (!st.empty() && arr[i] >= st.peek()) {st.pop();}// Whatever is on top now is the next greater elementif (st.empty()) {result.add(-1);} else {result.add(st.peek());}// Push current — it is a candidate for elements to the leftst.push(arr[i]);}// Collected answers right to left, so reverse before returningCollections.reverse(result);return result;}}Edge CasesAll elements decreasing — Input: [5, 4, 3, 2, 1] Output: [-1, -1, -1, -1, -1] Every element has no greater element to its right. Traversing right to left, each new element is larger than everything already in the stack, so the stack gets cleared and the answer is always -1.All elements increasing — Input: [1, 2, 3, 4, 5] Output: [2, 3, 4, 5, -1] Each element's next greater is simply the next element in the array. The last element always gets -1 since nothing exists to its right.All elements equal — Input: [3, 3, 3, 3] Output: [-1, -1, -1, -1] Equal elements do not count as greater. The pop condition uses >= so equals get removed from the stack, ensuring duplicates never answer each other.Single element — Input: [7] Output: [-1] Nothing to the right, always -1.Why only 32.95% accuracy on GFG? Most people either forget to reverse the result at the end, use the wrong comparison in the while loop, or submit a brute force O(n²) solution that times out on large inputs.Problem 2 — Next Greater Element to Left / Previous Greater Element (NGL)GFG Problem: Search "Previous Greater Element" on GeeksForGeeks Difficulty: Medium | Accuracy: 68.93% | Submissions: 7K+The QuestionFor each element in the array, find the first element to its left that is strictly greater than it. If none exists, return -1.Input: [10, 4, 2, 20, 40, 12, 30] Output: [-1, 10, 4, -1, -1, 40, 40]Real World ExampleImagine you are a junior employee at a company. For each person in the office, you want to know — who is the first senior person sitting to their left who earns more? This is NGL. It is used in organizational hierarchy systems, salary band analysis tools, and even in database query optimizers to find the nearest dominant record on the left side.The IntuitionThis is the mirror image of NGR. Instead of traversing right to left, we traverse left to right. The stack holds elements we have already seen from the left side — these are candidates for being the previous greater element. For each new element, pop everything from the stack that is smaller than or equal to it. Whatever remains on top is the first greater element to its left. Then push the current element for future use.No reverse is needed here because we are already going left to right and building the result in order.Step-by-Step Dry RunArray: [10, 4, 2, 20, 40, 12, 30], traversing left to right.i=0, element is 10. Stack is empty. Answer is -1. Push 10. Stack: [10]i=1, element is 4. Top is 10, greater than 4. Answer is 10. Push 4. Stack: [10, 4]i=2, element is 2. Top is 4, greater than 2. Answer is 4. Push 2. Stack: [10, 4, 2]i=3, element is 20. Top is 2, not greater than 20. Pop 2. Top is 4, not greater. Pop 4. Top is 10, not greater. Pop 10. Stack is empty. Answer is -1. Push 20. Stack: [20]i=4, element is 40. Top is 20, not greater. Pop 20. Stack empty. Answer is -1. Push 40. Stack: [40]i=5, element is 12. Top is 40, greater than 12. Answer is 40. Push 12. Stack: [40, 12]i=6, element is 30. Top is 12, not greater than 30. Pop 12. Top is 40, greater than 30. Answer is 40. Push 30. Stack: [40, 30]Result: [-1, 10, 4, -1, -1, 40, 40] ✓ No reverse needed.The Code// NGL — Next Greater Element to Left (Previous Greater Element)class Solution {static ArrayList<Integer> preGreaterEle(int[] arr) {Stack<Integer> st = new Stack<>();ArrayList<Integer> result = new ArrayList<>();// Traverse LEFT to RIGHT — no reverse neededfor (int i = 0; i <= arr.length - 1; i++) {// Pop all elements smaller than or equal to currentwhile (!st.empty() && arr[i] >= st.peek()) {st.pop();}// Top of stack is the previous greater elementif (!st.empty() && st.peek() > arr[i]) {result.add(st.peek());} else {result.add(-1);}// Push current for future elementsst.push(arr[i]);}return result;}}Edge CasesStrictly increasing array — Input: [10, 20, 30, 40] Output: [-1, -1, -1, -1] Each new element is larger than everything before it, so the stack always gets fully cleared. No previous greater exists for any element.First element is always -1 — regardless of its value, the first element has nothing to its left. The stack is empty at i=0, so the answer is always -1 for index 0. This is guaranteed by the logic.Duplicate values — Input: [5, 5, 5] Output: [-1, -1, -1] Equal elements do not qualify as greater. The pop condition uses >= so duplicates get removed from the stack and never answer each other.Problem 3 — Next Smaller Element to Right (NSR)GFG Problem: Search "Next Smaller Element" on GeeksForGeeks Difficulty: Medium | Accuracy: 36.26% | Submissions: 225K+The QuestionFor each element in the array, find the first element to its right that is strictly smaller than it. If none exists, return -1.Input: [4, 8, 5, 2, 25] Output: [2, 5, 2, -1, -1]Input: [13, 7, 6, 12] Output: [7, 6, -1, -1]Real World ExampleYou work at a warehouse. Shelves have items of weights: [4, 8, 5, 2, 25] kg. For each item, the system needs to find the first lighter item sitting to its right on the shelf — this is used to optimize load balancing and shelf arrangement algorithms. Item of 4 kg — first lighter to the right is 2 kg. Item of 8 kg — first lighter is 5 kg. Item of 5 kg — first lighter is 2 kg. Items of 2 kg and 25 kg have no lighter item to their right, so -1.The IntuitionNSR is structurally identical to NGR — we traverse right to left and collect answers, then reverse. The only change is the pop condition. In NGR we popped elements smaller than or equal to current because we wanted greater. Here we want smaller, so we pop elements greater than or equal to current. After popping, whatever remains on top is the first smaller element to the right.Step-by-Step Dry RunArray: [4, 8, 5, 2, 25], traversing right to left.i=4, element is 25. Stack is empty. Answer is -1. Push 25. Stack: [25]i=3, element is 2. Top is 25, which is greater than or equal to 2. Pop 25. Stack is empty. Answer is -1. Push 2. Stack: [2]i=2, element is 5. Top is 2, which is less than 5. Answer is 2. Push 5. Stack: [2, 5]i=1, element is 8. Top is 5, which is less than 8. Answer is 5. Push 8. Stack: [2, 5, 8]i=0, element is 4. Top is 8, which is greater than or equal to 4. Pop 8. Top is 5, which is greater than or equal to 4. Pop 5. Top is 2, which is less than 4. Answer is 2. Push 4. Stack: [2, 4]Answers collected right to left: [-1, -1, 2, 5, 2] After Collections.reverse(): [2, 5, 2, -1, -1] ✓The Code// NSR — Next Smaller Element to Rightclass Solution {static ArrayList<Integer> nextSmallerEle(int[] arr) {Stack<Integer> st = new Stack<>();ArrayList<Integer> result = new ArrayList<>();// Traverse RIGHT to LEFTfor (int i = arr.length - 1; i >= 0; i--) {// Pop elements greater than or equal to current// Opposite of NGR — we want smaller, so clear the bigger oneswhile (!st.empty() && arr[i] <= st.peek()) {st.pop();}// Top is now the next smaller elementif (!st.empty() && st.peek() < arr[i]) {result.add(st.peek());} else {result.add(-1);}st.push(arr[i]);}Collections.reverse(result);return result;}}Edge CasesStrictly decreasing array — Input: [5, 4, 3, 2, 1] Output: [4, 3, 2, 1, -1] Each element's next smaller is simply the next element in the array. Last element is always -1.Strictly increasing array — Input: [1, 2, 3, 4, 5] Output: [-1, -1, -1, -1, -1] No element has a smaller element to its right since the array only grows.Last element is always -1 — nothing exists to its right regardless of its value.Single element — Input: [42] Output: [-1]Why 36.26% accuracy on GFG? The most common mistake is keeping the NGR pop condition (arr[i] >= st.peek()) and only changing the problem description in your head. The pop condition must flip to arr[i] <= st.peek() for NSR. Forgetting this gives completely wrong answers that look plausible, which makes the bug hard to spot.Problem 4 — Next Smaller Element to Left / Previous Smaller Element (NSL)GFG Problem: Search "Previous Smaller Element" on GeeksForGeeksThe QuestionFor each element in the array, find the first element to its left that is strictly smaller than it. If none exists, return -1.Input: [4, 8, 5, 2, 25] Output: [-1, 4, 4, -1, 2]Real World ExampleSame warehouse. Now the system looks left instead of right. For the item weighing 8 kg, the first lighter item to its left is 4 kg. For 25 kg, the first lighter to its left is 2 kg. For 4 kg, nothing lighter exists to its left so -1. For 2 kg, nothing lighter to its left so -1. This kind of lookback query appears in time-series analysis, price history tracking, and sensor data processing.The IntuitionNSL is the mirror of NSR, exactly as NGL was the mirror of NGR. We traverse left to right (no reverse needed). We maintain a stack of candidates from the left. For each element, pop all elements greater than or equal to it — they cannot be the answer since they are not smaller. Whatever remains on top is the first smaller element to the left. Push current and move on.Step-by-Step Dry RunArray: [4, 8, 5, 2, 25], traversing left to right.i=0, element is 4. Stack is empty. Answer is -1. Push 4. Stack: [4]i=1, element is 8. Top is 4, which is less than 8. Answer is 4. Push 8. Stack: [4, 8]i=2, element is 5. Top is 8, which is greater than or equal to 5. Pop 8. Top is 4, which is less than 5. Answer is 4. Push 5. Stack: [4, 5]i=3, element is 2. Top is 5, greater than or equal to 2. Pop 5. Top is 4, greater than or equal to 2. Pop 4. Stack is empty. Answer is -1. Push 2. Stack: [2]i=4, element is 25. Top is 2, which is less than 25. Answer is 2. Push 25. Stack: [2, 25]Result: [-1, 4, 4, -1, 2] ✓ No reverse needed.The Code// NSL — Next Smaller Element to Left (Previous Smaller Element)class Solution {static ArrayList<Integer> prevSmallerEle(int[] arr) {Stack<Integer> st = new Stack<>();ArrayList<Integer> result = new ArrayList<>();// Traverse LEFT to RIGHT — no reverse neededfor (int i = 0; i < arr.length; i++) {// Pop elements greater than or equal to currentwhile (!st.empty() && arr[i] <= st.peek()) {st.pop();}// Top is the previous smaller elementif (!st.empty() && st.peek() < arr[i]) {result.add(st.peek());} else {result.add(-1);}st.push(arr[i]);}return result;}}Edge CasesFirst element is always -1 — nothing exists to its left. Stack is empty at i=0 every time.All same elements — Input: [5, 5, 5, 5] Output: [-1, -1, -1, -1] Equal elements do not qualify as smaller. The condition arr[i] <= st.peek() ensures equals are popped and never answer each other.Single element — Input: [9] Output: [-1]The Master Cheat SheetThis is the one table to save and refer to whenever you encounter any of these four problems.VariantTraverse DirectionPop ConditionReverse Result?NGR — Next Greater RightRight to Leftarr[i] >= st.peek()YesNGL — Next Greater LeftLeft to Rightarr[i] >= st.peek()NoNSR — Next Smaller RightRight to Leftarr[i] <= st.peek()YesNSL — Next Smaller LeftLeft to Rightarr[i] <= st.peek()NoTwo rules to remember forever:Rule 1 — Direction. If you are looking to the right, traverse right to left and reverse at the end. If you are looking to the left, traverse left to right and no reverse is needed.Rule 2 — Pop Condition. If you want a greater element, pop when arr[i] >= st.peek() to clear out smaller useless candidates. If you want a smaller element, pop when arr[i] <= st.peek() to clear out bigger useless candidates.Mix these two rules and you derive all four variants instantly without memorizing anything separately.Common Mistakes to AvoidWrong pop condition — Using > instead of >= in the while loop. This causes duplicate values to wrongly answer each other. Always use >= for greater problems and <= for smaller problems inside the while loop.Forgetting to reverse — For right-to-left traversals (NGR and NSR), you collect answers from right to left. You must call Collections.reverse() before returning. Skipping this is the single most common reason for wrong answers on these problems.Not checking empty stack before peek — Always check !st.empty() before calling st.peek(). An empty stack peek throws EmptyStackException at runtime and will crash your solution.Wrong if-condition after the while loop — After the while loop, the if-condition must use strict comparison. For NGR use st.peek() > arr[i]. For NSR use st.peek() < arr[i]. These must be strict — no equals sign here.Confusing traversal direction with answer direction — You traverse right to left for NGR but the answer array is filled left to right. The reverse at the end handles this. Do not try to index directly into the result array to compensate — just use reverse.Time and Space ComplexityAll four problems run in O(n) time and use O(n) space.Even though there is a while loop nested inside the for loop, each element is pushed into the stack exactly once and popped from the stack at most once. So across the entire traversal, the total number of push and pop operations combined is at most 2n — which gives O(n) overall. This is the beauty of the monotonic stack.Why These Four Problems Matter Beyond GFGThese four patterns are not just textbook exercises. They appear as the hidden sub-problem inside some of the hardest stack questions:-Largest Rectangle in Histogram uses NSR and NSL to find the left and right boundaries of each bar.Trapping Rain Water uses NGR and NGL to determine the water level above each position.Stock Span Problem is literally NGL applied directly to stock prices.Sum of Subarray Minimums uses NSR and NSL together to count contributions of each element.Once you master these four patterns deeply, a whole family of hard problems that previously seemed unapproachable suddenly becomes a matter of recognizing the pattern and applying it.Also on This BlogIf you are building your stack foundation from scratch, check out the complete deep-dive here → Stack Data Structure in Java: The Complete Guide — covering everything from what a stack is, LIFO principle, all three implementations, every operation with code, and six practice problems.

MonotonicStackNextGreaterElementStackProblemsJavaGeeksForGeeksStackPattern

LeetCode 123 — Best Time to Buy and Sell Stock III | At Most Two Transactions Explained

🚀 Try This Problem First!Before reading the solution, attempt it yourself on LeetCode — you will learn much more that way.🔗 Problem Link: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/What Is the Problem Asking?You have a list of stock prices, one for each day. You are allowed to buy and sell the stock, but with one important restriction — you can make at most two transactions in total. A transaction means one buy followed by one sell.You cannot hold two stocks at the same time, meaning you must sell whatever you are holding before you buy again.Your job is to find the maximum profit you can make by doing at most two transactions. If there is no way to make any profit, return 0.Example to build intuition: prices = [3, 3, 5, 0, 0, 3, 1, 4]If you buy on day 4 (price 0) and sell on day 6 (price 3), profit = 3. Then buy on day 7 (price 1) and sell on day 8 (price 4), profit = 3. Total profit = 6. That is the best you can do.Constraints:1 ≤ prices.length ≤ 10⁵0 ≤ prices[i] ≤ 10⁵Why Is This Harder Than the Previous Stock Problems?In LeetCode 121, you could only make one transaction — so you just found the best single buy-sell pair.In LeetCode 122, you could make unlimited transactions — so you greedily collected every upward price movement.Here, you are limited to exactly two transactions. Greedy does not work anymore because sometimes skipping a small profit early on allows you to make a much bigger combined profit across two trades. You need a smarter strategy.The Big Idea Behind the SolutionHere is a simple way to think about it.If you are allowed two transactions, you can imagine drawing a dividing line somewhere in the price array. The first transaction happens entirely on the left side of that line. The second transaction happens entirely on the right side.So the problem becomes:For every possible dividing position, find the best profit on the left side and the best profit on the right side.Add them together.The maximum sum across all dividing positions is your answer.The challenge is doing this efficiently without checking every position with a nested loop, which would be O(N²) and too slow.Approach 1 — Left-Right Prefix DPThe idea:Instead of trying every split point from scratch, precompute the answers in advance.Build a leftProfit array where leftProfit[i] stores the best single transaction profit you can make using prices from day 0 to day i.Build a rightProfit array where rightProfit[i] stores the best single transaction profit you can make using prices from day i to the last day.Then for every index i, the answer if you split at i is simply leftProfit[i] + rightProfit[i]. Take the maximum across all indices.How to build leftProfit:Go left to right. Keep track of the minimum price seen so far. At each day i, the best profit you could make ending at or before day i is either the same as the day before, or selling today at today's price minus the minimum price seen so far. Take whichever is larger.How to build rightProfit:Go right to left. Keep track of the maximum price seen so far from the right. At each day i, the best profit you could make starting at or after day i is either the same as the day after, or buying today at today's price and selling at the maximum price seen to the right. Take whichever is larger.Dry Run — prices = [3, 3, 5, 0, 0, 3, 1, 4]Building leftProfit left to right, tracking minimum price seen:Day 0 → min=3, leftProfit[0] = 0 (nothing to compare yet) Day 1 → min=3, best profit = 3-3 = 0, leftProfit[1] = max(0, 0) = 0 Day 2 → min=3, best profit = 5-3 = 2, leftProfit[2] = max(0, 2) = 2 Day 3 → min=0, best profit = 0-0 = 0, leftProfit[3] = max(2, 0) = 2 Day 4 → min=0, best profit = 0-0 = 0, leftProfit[4] = max(2, 0) = 2 Day 5 → min=0, best profit = 3-0 = 3, leftProfit[5] = max(2, 3) = 3 Day 6 → min=0, best profit = 1-0 = 1, leftProfit[6] = max(3, 1) = 3 Day 7 → min=0, best profit = 4-0 = 4, leftProfit[7] = max(3, 4) = 4leftProfit = [0, 0, 2, 2, 2, 3, 3, 4]Building rightProfit right to left, tracking maximum price seen:Day 7 → max=4, rightProfit[7] = 0 (nothing to compare yet) Day 6 → max=4, best profit = 4-1 = 3, rightProfit[6] = max(0, 3) = 3 Day 5 → max=4, best profit = 4-3 = 1, rightProfit[5] = max(3, 1) = 3 Day 4 → max=4, best profit = 4-0 = 4, rightProfit[4] = max(3, 4) = 4 Day 3 → max=4, best profit = 4-0 = 4, rightProfit[3] = max(4, 4) = 4 Day 2 → max=5, best profit = 5-5 = 0, rightProfit[2] = max(4, 0) = 4 Day 1 → max=5, best profit = 5-3 = 2, rightProfit[1] = max(4, 2) = 4 Day 0 → max=5, best profit = 5-3 = 2, rightProfit[0] = max(4, 2) = 4rightProfit = [4, 4, 4, 4, 4, 3, 3, 0]Combining at each index: Index 0 → 0 + 4 = 4 Index 1 → 0 + 4 = 4 Index 2 → 2 + 4 = 6 Index 3 → 2 + 4 = 6 Index 4 → 2 + 4 = 6 Index 5 → 3 + 3 = 6 Index 6 → 3 + 3 = 6 Index 7 → 4 + 0 = 4Maximum = 6 ✅Implementation code:class Solution { public int maxProfit(int[] prices) { int lefProf[] = new int[prices.length]; int rigProf[] = new int[prices.length]; int j = 1; int i = 0; int coL = 1; while (i < j && j < prices.length) { if (prices[i] > prices[j]) { i = j; if (coL - 1 != -1) { lefProf[coL] = lefProf[coL - 1]; } coL++; } else { int max = prices[j] - prices[i]; if (coL - 1 != -1) { lefProf[coL] = Math.max(lefProf[coL - 1], max); coL++; } else { lefProf[coL] = max; coL++; } } j++; } int ii = prices.length - 2; int jj = prices.length - 1; int coR = prices.length - 2; while (ii >= 0) { if (prices[ii] > prices[jj]) { jj = ii; if (coR + 1 < prices.length) { rigProf[coR] = rigProf[coR + 1]; } coR--; } else { int max = prices[jj] - prices[ii]; if (coR + 1 < prices.length) { rigProf[coR] = Math.max(rigProf[coR + 1], max); coR--; } else { rigProf[coR] = max; coR--; } } ii--; } int maxAns = 0; for (int k = 0; k < lefProf.length; k++) { maxAns = Math.max(maxAns, lefProf[k] + rigProf[k]); } return maxAns; }}The approach here is exactly right. You are building the left and right profit arrays using a two pointer scanning technique — the same idea as LeetCode 121 but applied twice, once going forward and once going backward. The manual counters coL and coR make it a bit harder to follow, but the logic underneath is solid.Here is the same approach written in a cleaner way so it is easier to read and debug:class Solution { public int maxProfit(int[] prices) { int n = prices.length; int[] leftProfit = new int[n]; int[] rightProfit = new int[n]; int minPrice = prices[0]; for (int i = 1; i < n; i++) { minPrice = Math.min(minPrice, prices[i]); leftProfit[i] = Math.max(leftProfit[i - 1], prices[i] - minPrice); } int maxPrice = prices[n - 1]; for (int i = n - 2; i >= 0; i--) { maxPrice = Math.max(maxPrice, prices[i]); rightProfit[i] = Math.max(rightProfit[i + 1], maxPrice - prices[i]); } int maxProfit = 0; for (int i = 0; i < n; i++) { maxProfit = Math.max(maxProfit, leftProfit[i] + rightProfit[i]); } return maxProfit; }}Time Complexity: O(N) — three separate linear passes through the array. Space Complexity: O(N) — two extra arrays of size N.Approach 2 — Four Variable State Machine DPThe idea:Instead of building arrays, what if you could track everything in just four variables and solve it in a single pass?Think about what is happening at any point in time as you go through the prices. You are always in one of these situations:You have bought your first stock and are currently holding it. You have sold your first stock and are sitting on that profit. You have bought your second stock (using the profit from the first sale) and are holding it. You have sold your second stock and collected your total profit.These four situations are your four states. For each one, you always want to know — what is the best possible profit I could have in this state up to today?Here is how each state updates as you look at a new price:buy1 — This represents the best outcome after buying the first stock. Buying costs money, so this is negative. As you see each new price, you ask: is it better to have bought on some earlier day, or to buy today? You keep whichever gives you the least cost, which means the highest value of negative price.sell1 — This represents the best profit after completing the first transaction. As you see each new price, you ask: is it better to have sold on some earlier day, or to sell today using the best buy1 we have? Selling today means adding today's price on top of buy1.buy2 — This represents the best outcome after buying the second stock. The key insight here is that you are not starting from zero — you already have the profit from the first transaction in your pocket. So buying the second stock costs today's price but you subtract it from sell1. As you see each new price, you ask: is it better to have bought the second stock earlier, or to buy today using the profit from sell1?sell2 — This is your final answer. It represents the best total profit after completing both transactions. As you see each new price, you ask: is it better to have completed both transactions earlier, or to sell the second stock today using the best buy2 we have?The beautiful thing is that all four updates happen in order on every single day, in one pass through the array. Each variable feeds into the next — buy1 feeds sell1, sell1 feeds buy2, buy2 feeds sell2.Dry Run — prices = [3, 3, 5, 0, 0, 3, 1, 4]We start with buy1 and buy2 as very negative (not yet bought anything) and sell1 and sell2 as 0 (no profit yet).Day 0, price = 3: buy1 = max(-∞, -3) = -3. Best cost to buy first stock is spending 3. sell1 = max(0, -3+3) = 0. Selling immediately gives no profit. buy2 = max(-∞, 0-3) = -3. Best cost to buy second stock after first sale is 3. sell2 = max(0, -3+3) = 0. No total profit yet.Day 1, price = 3: Nothing changes — same price as day 0.Day 2, price = 5: buy1 = max(-3, -5) = -3. Still best to have bought at price 3. sell1 = max(0, -3+5) = 2. Selling today at 5 after buying at 3 gives profit 2. buy2 = max(-3, 2-5) = -3. Buying second stock today costs too much relative to first profit. sell2 = max(0, -3+5) = 2. Completing both trades gives 2 so far.Day 3, price = 0: buy1 = max(-3, -0) = 0. Buying today at price 0 is the best possible first buy. sell1 = max(2, 0+0) = 2. Selling today at 0 gives nothing — keep the 2 from before. buy2 = max(-3, 2-0) = 2. Using the profit of 2 and buying today at 0 gives buy2 = 2. sell2 = max(2, 2+0) = 2. Selling second stock today at 0 gives nothing extra.Day 4, price = 0: Nothing changes — same price as day 3.Day 5, price = 3: buy1 = max(0, -3) = 0. Still best to have bought at price 0. sell1 = max(2, 0+3) = 3. Selling today at 3 after buying at 0 gives profit 3. buy2 = max(2, 3-3) = 2. Buying second stock today at 3 using sell1=3 gives 0. Keep 2. sell2 = max(2, 2+3) = 5. Selling second stock today at 3 after buy2=2 gives total 5.Day 6, price = 1: buy1 = max(0, -1) = 0. Still best to have bought at 0. sell1 = max(3, 0+1) = 3. Selling today at 1 gives less than 3 — no change. buy2 = max(2, 3-1) = 2. Buying second stock at 1 using sell1=3 gives 2 — same as before. sell2 = max(5, 2+1) = 5. No improvement yet.Day 7, price = 4: buy1 = max(0, -4) = 0. No change. sell1 = max(3, 0+4) = 4. Selling today at 4 after buying at 0 gives profit 4 — new best. buy2 = max(2, 4-4) = 2. No improvement. sell2 = max(5, 2+4) = 6. Selling second stock today at 4 with buy2=2 gives total 6 — new best.Output: 6 ✅class Solution { public int maxProfit(int[] prices) { int buy1 = Integer.MIN_VALUE; int sell1 = 0; int buy2 = Integer.MIN_VALUE; int sell2 = 0; for (int price : prices) { buy1 = Math.max(buy1, -price); sell1 = Math.max(sell1, buy1 + price); buy2 = Math.max(buy2, sell1 - price); sell2 = Math.max(sell2, buy2 + price); } return sell2; }}Time Complexity: O(N) — single pass through the array. Space Complexity: O(1) — only four integer variables, no extra arrays.Approach 3 — Generalizing to At Most K TransactionsOnce you understand Approach 2, there is a natural question — what if instead of two transactions, you were allowed K transactions? That is exactly LeetCode 188.Instead of four hardcoded variables, you use two arrays of size K. buy[j] tracks the best outcome after the j-th buy and sell[j] tracks the best outcome after the j-th sell. The logic is identical to Approach 2, just in a loop.For this problem set K = 2 and it gives the same answer:class Solution { public int maxProfit(int[] prices) { int k = 2; int[] buy = new int[k]; int[] sell = new int[k]; Arrays.fill(buy, Integer.MIN_VALUE); for (int price : prices) { for (int j = 0; j < k; j++) { buy[j] = Math.max(buy[j], (j == 0 ? 0 : sell[j - 1]) - price); sell[j] = Math.max(sell[j], buy[j] + price); } } return sell[k - 1]; }}Time Complexity: O(N × K) — for K=2 this is effectively O(N). Space Complexity: O(K) — two small arrays of size K.If you understand this, LeetCode 188 becomes a five minute problem.Comparing All Three ApproachesApproach 1 — Left-Right Prefix DP (Your Approach)You build two arrays — one scanning left to right, one scanning right to left — and combine them. This is the most visual and intuitive approach. It is easy to explain because you are essentially solving LeetCode 121 twice from opposite ends and adding the results. The downside is it uses O(N) extra space for the two arrays.Approach 2 — Four Variable State MachineYou solve the entire problem in a single pass using just four variables. No arrays, no extra memory. This is the most efficient and elegant solution. Once you understand what each variable represents, the code almost writes itself. This is what most interviewers are hoping to see.Approach 3 — General K-Transaction DPThis is Approach 2 extended to handle any number of transactions using arrays instead of hardcoded variables. Solving LeetCode 123 with this approach means you have already solved LeetCode 188 as a bonus.Mistakes That Catch Most PeopleTrying to use the greedy approach from LeetCode 122: Adding every upward price movement does not work when you are limited to two transactions. You need to pick the two best non-overlapping windows, not collect everything.Buying twice without selling in between: The state machine prevents this naturally — buy2 depends on sell1, so you can never enter the second buy before completing the first sell.Initializing buy variables to 0: Both buy1 and buy2 must start at Integer.MIN_VALUE. Setting them to 0 implies you bought a stock for free, which is wrong and will give inflated profits.Returning the wrong variable: Always return sell2, not buy2 or sell1. sell2 is the only variable that represents a completed two-transaction profit.Where This Fits in the Stock SeriesLeetCode 121 — One transaction only. Find the single best buy-sell pair. [ Blog is also avaliable on this - Read Now ]LeetCode 122 — Unlimited transactions. Collect every upward price movement greedily. [ Blog is also avaliable on this - Read Now ]LeetCode 188 — At most K transactions. Direct extension of Approach 3 above.LeetCode 309 — Unlimited transactions but with a cooldown day after every sale.LeetCode 714 — Unlimited transactions but with a fee charged on every transaction.Each problem adds one new constraint on top of the previous one. If you understand LeetCode 123 deeply — especially Approach 2 — every other problem in this series becomes a small modification of the same framework.Key Takeaways✅ When you are limited to two transactions, greedy fails. You need to find two non-overlapping windows that together give maximum profit.✅ The left-right prefix DP approach is the most intuitive — precompute the best single transaction from both ends, then combine at every split point.✅ The four variable state machine solves it in one pass with O(1) space. Each variable tracks the best outcome for one state — buy1 feeds sell1, sell1 feeds buy2, buy2 feeds sell2.✅ Always initialize buy variables to Integer.MIN_VALUE to represent "not yet bought anything."✅ Understanding Approach 3 here means LeetCode 188 is already solved — just change the hardcoded 2 to K.Happy Coding! This problem is the turning point in the stock series where DP becomes unavoidable — once you crack it, the rest of the series feels manageable. 🚀

LeetCodeDynamic ProgrammingHardJavaDSAPrefix DPArraysStock Series

LeetCode 122 — Best Time to Buy and Sell Stock II | Every Approach Explained

🚀 Try This Problem First!Before reading the solution, attempt it yourself on LeetCode — you'll retain the concept far better.🔗 Problem Link: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/Understanding the ProblemYou are given an array prices where prices[i] is the stock price on day i. Unlike the classic version, here you can make as many transactions as you want — but you can only hold one share at a time. You may buy and sell on the same day.Goal: Return the maximum total profit achievable.Key Rules:You can buy and sell multiple times.You cannot hold more than one share at a time — you must sell before buying again.If no profit is possible, return 0.Constraints:1 ≤ prices.length ≤ 3 × 10⁴0 ≤ prices[i] ≤ 10⁴How This Differs From LeetCode 121 #In LeetCode 121, you were limited to exactly one buy-sell transaction. Here, the restriction is lifted — you can participate in as many transactions as you want. This fundamentally changes the strategy. Instead of hunting for the single best pair, you want to capture every profitable price movement in the array.The Core InsightLook at the price chart mentally. Every time the price goes up from one day to the next, that's money on the table. The question is — how do you collect all of it?The answer is surprisingly simple: add every single upward price difference to your profit. If prices go up three days in a row from 1 → 3 → 5 → 8, you collect (3-1) + (5-3) + (8-5) = 7, which is exactly the same as buying at 1 and selling at 8. You never miss a gain.This is the foundation of all approaches below.Approach 1 — Simple Greedy (Collect Every Upward Move)Intuition: Every time prices[i] > prices[i-1], add the difference to profit. You are essentially buying at every valley and selling at every peak, collecting each individual daily gain without explicitly tracking buy/sell days.Why it works: The total gain from buying at day 0 and selling at day N is mathematically equal to the sum of all positive daily differences in between. You never lose anything by collecting gains day by day.Example: prices = [1, 2, 3, 4, 5] Daily gains: (2-1) + (3-2) + (4-3) + (5-4) = 1+1+1+1 = 4 Same as buying at 1 and selling at 5 directly.class Solution {public int maxProfit(int[] prices) {int maxProfit = 0;for (int i = 1; i < prices.length; i++) {if (prices[i] > prices[i - 1]) {maxProfit += prices[i] - prices[i - 1];}}return maxProfit;}}Time Complexity: O(N) — single pass through the array. Space Complexity: O(1) — no extra space used.This is the cleanest and most recommended solution for this problem.Approach 2 — Peak Valley ApproachIntuition: Instead of collecting every daily gain, explicitly find every valley (local minimum) to buy at and every peak (local maximum) to sell at. You buy when price stops falling and sell when price stops rising.How it works: Scan through the array. When you find a valley (prices[i] ≤ prices[i+1]), that is your buy point. Then keep going until you find a peak (prices[i] ≥ prices[i+1]) — that is your sell point. Add the peak minus valley to profit. Repeat.Example: prices = [7, 1, 5, 3, 6, 4]Valley at index 1 (price = 1), Peak at index 2 (price = 5) → profit += 4 Valley at index 3 (price = 3), Peak at index 4 (price = 6) → profit += 3 Total = 7 ✅class Solution {public int maxProfit(int[] prices) {int i = 0;int maxProfit = 0;int valley, peak;while (i < prices.length - 1) {while (i < prices.length - 1 && prices[i] >= prices[i + 1]) {i++;}valley = prices[i];while (i < prices.length - 1 && prices[i] <= prices[i + 1]) {i++;}peak = prices[i];maxProfit += peak - valley;}return maxProfit;}}Time Complexity: O(N) — each element is visited at most twice. Space Complexity: O(1) — no extra space used.This approach is more explicit and easier to visualize on a graph, though the code is slightly more involved than Approach 1.Approach 3 — Two PointerIntuition: Use two pointers i (buy day) and j (sell day). Move j forward one step at a time. Whenever prices[j] > prices[i], you have a profitable window — add the profit and immediately move i to j (simulate selling and rebuying at the same price on the same day). Whenever prices[j] < prices[i], just move i to j since a cheaper buy day has been found.Why moving i to j after every profitable sale works: Selling at j and immediately rebuying at j costs nothing (profit of 0 for that rebuy). But it positions i at the latest price so you can catch the next upward movement. This correctly simulates collecting every upward segment.Example: prices = [7, 1, 5, 3, 6, 4]i=0, j=1 → 7 > 1, move i to 1. j=2. i=1, j=2 → 1 < 5, profit += 4, move i to 2. j=3. i=2, j=3 → 5 > 3, move i to 3. j=4. i=3, j=4 → 3 < 6, profit += 3, move i to 4. j=5. i=4, j=5 → 6 > 4, move i to 5. j=6. Loop ends. Total profit = 7 ✅class Solution {public int maxProfit(int[] prices) {int i = 0;int j = 1;int maxProfit = 0;while (i < j && j < prices.length) {if (prices[i] > prices[j]) {i = j;} else {maxProfit += prices[j] - prices[i];i = j;}j++;}return maxProfit;}}Time Complexity: O(N) — j traverses the array exactly once. Space Complexity: O(1) — only three integer variables.This approach is functionally identical to Approach 1 — both collect every upward daily movement. The two pointer framing makes the buy/sell simulation more explicit.Approach 4 — Dynamic ProgrammingIntuition: At any point in time, you are in one of two states — either you hold a stock or you do not hold a stock. Define two DP values updated each day:hold = maximum profit if you are currently holding a stock at the end of this day.cash = maximum profit if you are not holding any stock at the end of this day.Transitions:To hold on day i: either you already held yesterday, or you buy today. hold = max(hold, cash - prices[i])To have cash on day i: either you already had cash yesterday, or you sell today. cash = max(cash, hold + prices[i])Initialization:hold = -prices[0] (you bought on day 0)cash = 0 (you did nothing on day 0)class Solution {public int maxProfit(int[] prices) {int hold = -prices[0];int cash = 0;for (int i = 1; i < prices.length; i++) {hold = Math.max(hold, cash - prices[i]);cash = Math.max(cash, hold + prices[i]);}return cash;}}Time Complexity: O(N) — single pass. Space Complexity: O(1) — only two variables maintained at each step.This approach is the most powerful because it extends naturally to harder variants of this problem — like LeetCode 309 (with cooldown) and LeetCode 714 (with transaction fee) — where greedy no longer works and you need explicit state tracking.Dry Run — All Approaches on Example 1Input: prices = [7, 1, 5, 3, 6, 4], Expected Output: 7Approach 1 (Simple Greedy): Day 1→2: 1 - 7 = -6, skip. Day 2→3: 5 - 1 = 4, add. profit = 4. Day 3→4: 3 - 5 = -2, skip. Day 4→5: 6 - 3 = 3, add. profit = 7. Day 5→6: 4 - 6 = -2, skip. Result = 7 ✅Approach 4 (DP): Start: hold = -7, cash = 0. Day 1 (price=1): hold = max(-7, 0-1) = -1. cash = max(0, -1+1) = 0. Day 2 (price=5): hold = max(-1, 0-5) = -1. cash = max(0, -1+5) = 4. Day 3 (price=3): hold = max(-1, 4-3) = 1. cash = max(4, 1+3) = 4. Day 4 (price=6): hold = max(1, 4-6) = 1. cash = max(4, 1+6) = 7. Day 5 (price=4): hold = max(1, 7-4) = 3. cash = max(7, 3+4) = 7. Result = 7 ✅Comparison of All ApproachesApproach 1 — Simple Greedy Code simplicity: Simplest possible. Best for interviews — clean and readable. Does not extend to constrained variants.Approach 2 — Peak Valley Code simplicity: Moderate. Best for visual/conceptual understanding. Slightly verbose but maps directly to a chart.Approach 3 — Two Pointer Code simplicity: Simple. Explicit simulation of buy/sell actions. Functionally identical to Approach 1.Approach 4 — Dynamic Programming Code simplicity: Moderate. Most powerful — extends to cooldown, fee, and k-transaction variants. Worth mastering for the full stock problem series.Common Mistakes to AvoidThinking you need to find exact buy/sell days: The problem only asks for maximum profit — you do not need to output which days you traded. This frees you to use the simple greedy sum approach.Trying to find the global minimum and maximum: Unlike LeetCode 121, the single best buy-sell pair is not always optimal here. You need to capture multiple smaller movements, not one big one.Holding more than one share: You cannot buy twice in a row without selling in between. In Approach 3, moving i = j after every transaction ensures you always sell before the next buy.Not handling a flat or decreasing array: If prices never go up, all approaches correctly return 0 — the greedy sum adds nothing, peak-valley finds no valid pairs, and DP's cash stays at 0.Complexity SummaryAll four approaches run in O(N) time and O(1) space. The difference between them is conceptual clarity and extensibility, not raw performance.The Full Stock Problem Series on LeetCodeThis problem is part of a six-problem series. Understanding them in order builds intuition progressively:LeetCode 121 — One transaction only. Two pointer / min tracking greedy. [ Blog is also avaliable on this - Read Now]LeetCode 123 — At most 2 transactions. DP with explicit state for two transactions. [ Blog is also avaliable on this - Read Now]LeetCode 188 — At most k transactions. Generalized DP.LeetCode 309 — Unlimited transactions with cooldown after selling. DP with three states.LeetCode 714 — Unlimited transactions with a fee per transaction. DP with adjusted transitions.Each problem adds one constraint on top of the previous. If you understand the DP state machine from Approach 4 deeply, every problem in this series becomes a small modification of the same framework.Key Takeaways✅ When transactions are unlimited, collect every upward daily price movement — that is the global optimum.✅ The sum of all positive daily differences equals the sum of all peak-valley differences. Both are provably optimal.✅ The two pointer approach explicitly simulates buy and sell events — moving i = j after a sale means selling and immediately rebuying at the same price to stay positioned for the next gain.✅ The DP approach with hold and cash states is the most versatile — it is the foundation for every harder variant in the stock series.✅ Always initialize maxProfit = 0 so that the no-profit case (prices only falling) is handled correctly without extra conditions.Happy Coding! Once you have this problem locked down, the rest of the stock series will feel like natural extensions rather than new problems entirely. 🚀

LeetCodeGreedyTwo PointersDynamic ProgrammingMediumJavaArrays

LeetCode 203: Remove Linked List Elements – Step-by-Step Guide for Beginners

Try the ProblemYou can practice the problem here:https://leetcode.com/problems/remove-linked-list-elements/Problem Description (In Very Simple Words)You are given:The head of a linked listAn integer value valYour task is:👉 Remove all nodes from the linked list whose value is equal to val.👉 Return the updated head of the linked list.What is a Linked List? (Quick Recap)A linked list is a chain of nodes where each node contains:value + pointer to next nodeExample:1 → 2 → 6 → 3 → 4 → 5 → 6 → nullExample WalkthroughExample 1Input:head = [1,2,6,3,4,5,6]val = 6Output:[1,2,3,4,5]ExplanationWe remove all nodes with value 6.1 → 2 → ❌6 → 3 → 4 → 5 → ❌6Final list:1 → 2 → 3 → 4 → 5Example 2Input:head = []val = 1Output:[]Example 3Input:head = [7,7,7,7]val = 7Output:[]All nodes are removed.Constraints0 <= number of nodes <= 10^41 <= Node.val <= 500 <= val <= 50Understanding the Problem DeeplyThe tricky part is:👉 Nodes can appear anywhere:At the beginningIn the middleAt the endOr all nodes👉 Linked list does NOT allow backward traversalSo we must carefully handle pointers.Thinking About the SolutionWhen solving this problem, multiple approaches may come to mind:Possible ApproachesTraverse the list and remove nodes manually.Handle head separately, then process the rest.Use a dummy node to simplify logic.Use recursion (less preferred for beginners).Approach 1: Without Dummy Node (Manual Handling)IdeaFirst, remove nodes from the start (head) if they match val.Then traverse the list using two pointers:prev → previous nodecurr → current nodeKey ChallengeHandling head separately makes code more complex.Codeclass Solution { public ListNode removeElements(ListNode head, int val) { // Step 1: Remove matching nodes from the beginning while(head != null && head.val == val){ head = head.next; } // If list becomes empty if(head == null) return null; ListNode prev = head; ListNode curr = head.next; while(curr != null){ if(curr.val == val){ // Skip the node prev.next = curr.next; } else { // Move prev only when node is not removed prev = curr; } curr = curr.next; } return head; }}Why This WorksWe ensure prev always points to the last valid nodeWhen we find a node to delete:prev.next = curr.nextThis skips the unwanted nodeProblem With This Approach👉 Too many edge cases:Removing head nodesEmpty listAll nodes equalApproach 2: Dummy Node (Best & Clean Approach)IdeaWe create a fake node (dummy) before the head.dummy → head → rest of listThis helps us:👉 Treat head like a normal node👉 Avoid special casesVisualizationOriginal:1 → 2 → 6 → 3After dummy:-1 → 1 → 2 → 6 → 3Java Implementation (Best Approach)class Solution { public ListNode removeElements(ListNode head, int val) { // Step 1: Create dummy node ListNode dumm = new ListNode(-1, head); // Step 2: Start from dummy ListNode curr = dumm; while(curr.next != null){ // If next node needs to be removed if(curr.next.val == val){ // Skip that node curr.next = curr.next.next; } else { // Move forward only when no deletion curr = curr.next; } } // Step 3: Return new head return dumm.next; }}Step-by-Step Dry RunInput:1 → 2 → 6 → 3 → 4 → 5 → 6val = 6After dummy:-1 → 1 → 2 → 6 → 3 → 4 → 5 → 6Traversal:curr = -1 → 1 (keep)curr = 1 → 2 (keep)curr = 2 → 6 (remove)curr = 2 → 3 (keep)curr = 3 → 4 (keep)curr = 4 → 5 (keep)curr = 5 → 6 (remove)Final:1 → 2 → 3 → 4 → 5Time ComplexityO(n)We traverse the list once.Space ComplexityO(1)No extra space used.Why Dummy Node is PreferredWithout DummyWith DummyComplex edge casesClean logicSpecial handling for headNo special handlingError-proneSafe and readableApproach 3: Recursive Solution (Conceptual)IdeaWe process one node at a time and recursively solve for the rest.Codeclass Solution { public ListNode removeElements(ListNode head, int val) { if(head == null) return null; head.next = removeElements(head.next, val); if(head.val == val){ return head.next; } else { return head; } }}Time ComplexityO(n)Space ComplexityO(n)(due to recursion stack)Key TakeawaysLinked list problems are all about pointer manipulationAlways think about edge cases (especially head)Dummy node simplifies almost every linked list problemConclusionThe Remove Linked List Elements problem is perfect for understanding how linked lists work in real scenarios.While the manual approach works, the dummy node technique provides a much cleaner and safer solution.If you master this pattern, you will be able to solve many linked list problems easily in interviews.👉 Tip: Whenever you feel stuck in linked list problems, try adding a dummy node — it often simplifies everything!

Linked ListIterationDummy NodePointer ManipulationLeetCodeEasy

All Subsequences of a String (Power Set) | Recursion & Backtracking Java Solution

IntroductionThe Power Set problem for strings is a classic question in recursion and backtracking, frequently asked in coding interviews and platforms like GeeksforGeeks.In this problem, instead of numbers, we deal with strings and generate all possible subsequences (not substrings). This makes it slightly more interesting and practical for real-world applications like pattern matching, text processing, and combinatorics.In this article, we will cover:Intuition behind subsequencesRecursive (backtracking) approachSorting for lexicographical orderAlternative approachesComplexity analysisProblem StatementGiven a string s of length n, generate all non-empty subsequences of the string.RequirementsReturn only non-empty subsequencesOutput must be in lexicographically sorted orderExamplesExample 1Input:s = "abc"Output:a ab abc ac b bc cExample 2Input:s = "aa"Output:a a aaSubsequence vs Substring (Important)Substring: Continuous charactersSubsequence: Characters can be skippedExample for "abc":Subsequences → a, b, c, ab, ac, bc, abcKey InsightFor every character, we have two choices:Include it OR Exclude itSo total subsequences:2^nWe generate all and then remove the empty string.Approach 1: Recursion (Backtracking)IntuitionAt each index:Skip the characterInclude the characterBuild all combinations recursivelyJava Code (With Explanation)import java.util.*;class Solution { // List to store all subsequences List<String> a = new ArrayList<>(); void sub(String s, int ind, String curr) { // Base case: reached end of string if (ind == s.length()) { a.add(curr); // add current subsequence return; } // Choice 1: Exclude current character sub(s, ind + 1, curr); // Choice 2: Include current character sub(s, ind + 1, curr + s.charAt(ind)); } public List<String> AllPossibleStrings(String s) { // Start recursion sub(s, 0, ""); // Remove empty string (not allowed) a.remove(""); // Sort lexicographically Collections.sort(a); return a; }}Step-by-Step Dry Run (s = "abc")Start: ""→ Exclude 'a' → "" → Exclude 'b' → "" → Exclude 'c' → "" → Include 'c' → "c" → Include 'b' → "b" → Exclude 'c' → "b" → Include 'c' → "bc"→ Include 'a' → "a" → Exclude 'b' → "a" → Exclude 'c' → "a" → Include 'c' → "ac" → Include 'b' → "ab" → Exclude 'c' → "ab" → Include 'c' → "abc"Final Output (After Sorting)a ab abc ac b bc cApproach 2: Bit ManipulationIntuitionEach subsequence can be represented using binary numbers:0 → exclude1 → includeCodeimport java.util.*;class Solution { public List<String> AllPossibleStrings(String s) { List<String> result = new ArrayList<>(); int n = s.length(); int total = 1 << n; // 2^n for (int i = 1; i < total; i++) { // start from 1 to avoid empty StringBuilder sb = new StringBuilder(); for (int j = 0; j < n; j++) { if ((i & (1 << j)) != 0) { sb.append(s.charAt(j)); } } result.add(sb.toString()); } Collections.sort(result); return result; }}Approach 3: Iterative (Expanding List)IdeaStart with empty listFor each character:Add it to all existing subsequencesCodeimport java.util.*;class Solution { public List<String> AllPossibleStrings(String s) { List<String> result = new ArrayList<>(); result.add(""); for (char ch : s.toCharArray()) { int size = result.size(); for (int i = 0; i < size; i++) { result.add(result.get(i) + ch); } } result.remove(""); Collections.sort(result); return result; }}Complexity AnalysisTime Complexity: O(n × 2ⁿ)Space Complexity: O(n × 2ⁿ)Why?Total subsequences = 2ⁿEach subsequence takes O(n) to buildWhy Sorting is RequiredThe recursion generates subsequences in random order, so we sort them:Collections.sort(result);This ensures lexicographical order as required.Key TakeawaysThis is a power set problem for stringsEach character → 2 choicesRecursion = most intuitive approachBit manipulation = most optimized thinkingAlways remove empty string if requiredCommon Interview VariationsSubsets of arrayPermutations of stringCombination sumSubsequence with conditionsConclusionThe Power Set problem is a fundamental building block in recursion and combinatorics. Once you understand the include/exclude pattern, you can solve a wide range of problems efficiently.Mastering this will significantly improve your ability to tackle backtracking and decision tree problems.Frequently Asked Questions (FAQs)1. Why is the empty string removed?Because the problem requires only non-empty subsequences.2. Why is time complexity O(n × 2ⁿ)?Because there are 2ⁿ subsequences and each takes O(n) time to construct.3. Which approach is best?Recursion → best for understandingBit manipulation → best for optimization

GeeksforGeeksRecursionJavaBacktrackingMedium

I Published My First npm Package: Karos

IntroductionPublishing your first npm package is not about building something revolutionary.If you think it is, you’ll either overbuild it or never ship it.Karos exists because I kept running into the same boring, frustrating problem across backend projects — inconsistent API responses and messy error handling.The Problem I Kept SeeingIn most Express or Node.js backends:Every route formats responses differentlySome errors are strings, some are objects, some leak stack tracesStatus codes are inconsistent or guessedFrontend logic becomes defensive and conditional-heavyTeams rewrite the same response boilerplate in every projectThere is no enforced backend–frontend contract.Just “best practices” that slowly decay over time.Why I Didn’t Use Existing SolutionsThere are libraries that help with errors.There are frameworks that encourage conventions.But most of them:Add heavy abstractionsRequire configuration filesLock you into a framework styleMix business logic with infrastructureI didn’t want help.I wanted enforcement — and nothing more.What Karos Does (And Only This)Karos enforces one predictable JSON response contract across your API.That’s it.Success Response{"success": true,"data": {}}Error Response{"success": false,"error": {"code": "NOT_FOUND","message": "User not found"}}No special cases.No custom shapes per route.If a response doesn’t match this structure, it’s wrong.Stop Returning Errors. Start Throwing Them.Instead of this pattern everywhere:if (!user) {return res.status(404).json({ error: 'User not found' });}Karos forces a different mindset:if (!user) {notFoundError('User not found');}The error is thrown, not returned.A single global handler catches it, formats it, and sends the response.No repeated try/catchNo duplicated error formattingNo forgotten status codesKarosError: One Error Model to Rule Them AllAt the core of Karos is a single class: KarosError.Every error has:A strict error code (TypeScript-safe)An explicit HTTP statusOptional structured detailsA guaranteed JSON shapeThis makes backend behavior predictable and frontend handling trivial.Database Errors Are Normalized AutomaticallyRaw database errors should never reach the client.Karos automatically detects and normalizes common DB errors:Prisma unique constraint → CONFLICT (409)Prisma record not found → NOT_FOUND (404)MongoDB duplicate key → CONFLICT (409)Mongoose validation errors → VALIDATION_FAILED (400)The frontend never needs to know which database you’re using.It only cares about the contract.Express and Next.js Share the Same ContractKaros supports:Express via middlewareNext.js (App Router) via Web-standard helpersBoth produce the exact same response format.That means you can switch frameworks or mix them — and your frontend logic stays unchanged.Karos API – All Methods in One PlaceCore API ReferenceCategoryFunction / ClassDescriptionSuccessok(res, data, message?, meta?)Sends a standardized success response (Express)Error BaseKarosErrorBase error class with code, status, detailsError HelpersnotFoundError()Throws 404 NOT_FOUNDvalidationError()Throws 400 VALIDATION_FAILEDunauthorizedError()Throws 401 UNAUTHORIZEDforbiddenError()Throws 403 FORBIDDENconflictError()Throws 409 CONFLICTinternalError()Throws 500 INTERNAL_ERRORhttpError()Custom error with any statusMiddlewareerrorHandlerGlobal Express error handlerDB HandlingresolveDbError()Normalizes Prisma/Mongo errorsNext.jsnextOk()Success response for App RouternextFail()Error response for App RouterhandleNextError()Global Next.js error handlerTypesErrorCodeEnum-style error codesTypesApiSuccessResponseSuccess response typeTypesApiErrorResponseError response typeWhat Karos Is NotThis matters more than features.Karos is not:A validation libraryA logging frameworkA request lifecycle managerA replacement for good architectureA silver bulletIt solves one problem and refuses to grow beyond that.How You Can Publish Your First npm Package TooIf you’re thinking “this looks doable” — it is.Here are the actual steps, no fluff.1. Create an npm AccountGo to https://www.npmjs.comSign up and verify your email2. Prepare Your Packagenpm initMake sure:name is uniquemain points to your build outputtypes points to .d.ts if using TypeScript3. Build Your Packagenpm run build(Usually outputs to dist/)4. Login to npmnpm loginEnter:UsernamePasswordEmailOTP (if 2FA enabled)5. Publishnpm publishThat’s it.No approval process. No gatekeepers.You are officially an npm package author.LinksGitHub Repository: https://github.com/Krishna-Shrivastava-1/Karosnpm Package: https://www.npmjs.com/package/karosWhy Shipping This Mattered to MeKaros won’t make headlines.It won’t go viral.But it forced me to:Design a real API contractThink about DX instead of just codeHandle edge cases like DB errors properlyShip something other people can actually useFor a first npm package, that’s a win.Final ThoughtMost backend bugs don’t come from complex logic.They come from inconsistency.Karos doesn’t make your API smarter.It makes it disciplined.And sometimes, that’s exactly what you need.

npmexpressnextjserror-handlingtypescriptopen-sourcefirst-npm-package

LeetCode 39: Combination Sum – Java Backtracking Solution with Dry Run & Complexity

IntroductionIf you are preparing for coding interviews or improving your Data Structures and Algorithms skills, LeetCode 39 Combination Sum is one of the most important backtracking problems to learn. This problem helps you understand how recursion explores multiple possibilities and how combinations are generated efficiently. It is a foundational problem that builds strong problem-solving skills and prepares you for many advanced recursion and backtracking questions.Why Should You Solve This Problem?Combination Sum is not just another coding question — it teaches you how to think recursively and break a complex problem into smaller decisions. By solving it, you learn how to manage recursive paths, avoid duplicate combinations, and build interview-level backtracking intuition. Once you understand this pattern, problems like subsets, permutations, N-Queens, and Sudoku Solver become much easier to approach.LeetCode Problem LinkProblem Name: Combination SumProblem Link: Combination SumProblem StatementGiven an array of distinct integers called candidates and a target integer target, you need to return all unique combinations where the chosen numbers sum to the target.Important rules:You can use the same number unlimited times.Only unique combinations should be returned.Order of combinations does not matter.ExampleExample 1Input:candidates = [2,3,6,7]target = 7Output:[[2,2,3],[7]]Explanation2 + 2 + 3 = 77 itself equals targetUnderstanding the Problem in Simple WordsWe are given some numbers.We need to:Pick numbers from the arrayAdd them togetherReach the target sumUse numbers multiple times if neededAvoid duplicate combinationsThis problem belongs to the Backtracking + Recursion category.Real-Life AnalogyImagine you have coins of different values.You want to make an exact payment.You can reuse coins multiple times.You need to find every possible valid coin combination.This is exactly what Combination Sum does.Intuition Behind the SolutionAt every index, we have two choices:Pick the current numberSkip the current numberSince numbers can be reused unlimited times, when we pick a number, we stay at the same index.This creates a recursion tree.We continue until:Target becomes 0 → valid answerTarget becomes negative → invalid pathArray ends → stop recursionWhy Backtracking Works HereBacktracking helps us:Explore all possible combinationsUndo previous decisionsTry another pathIt is useful whenever we need:All combinationsAll subsetsPath explorationRecursive searchingApproach 1: Backtracking Using Pick and SkipCore IdeaAt every element:Either take itOr move to next elementJava Code (Pick and Skip Method)class Solution {List<List<Integer>> result = new ArrayList<>();public void solve(int[] candidates, int index, int target, List<Integer> current) {if (target == 0) {result.add(new ArrayList<>(current));return;}if (index == candidates.length) {return;}if (candidates[index] <= target) {current.add(candidates[index]);solve(candidates, index, target - candidates[index], current);current.remove(current.size() - 1);}solve(candidates, index + 1, target, current);}public List<List<Integer>> combinationSum(int[] candidates, int target) {solve(candidates, 0, target, new ArrayList<>());return result;}}Approach 2: Backtracking Using Loop (Optimized)This is the cleaner and more optimized version.Your code belongs to this category.Java Code (Loop-Based Backtracking)class Solution {List<List<Integer>> result = new ArrayList<>();public void solve(int[] arr, int index, int target, List<Integer> current) {if (target == 0) {result.add(new ArrayList<>(current));return;}if (index == arr.length) {return;}for (int i = index; i < arr.length; i++) {if (arr[i] > target) {continue;}current.add(arr[i]);solve(arr, i, target - arr[i], current);current.remove(current.size() - 1);}}public List<List<Integer>> combinationSum(int[] candidates, int target) {solve(candidates, 0, target, new ArrayList<>());return result;}}Dry Run of the AlgorithmInputcandidates = [2,3,6,7]target = 7Step-by-Step ExecutionStart:solve([2,3,6,7], index=0, target=7, [])Pick 2[2]target = 5Pick 2 again:[2,2]target = 3Pick 2 again:[2,2,2]target = 1No valid choice possible.Backtrack.Try 3[2,2,3]target = 0Valid answer found.Add:[2,2,3]Try 7[7]target = 0Valid answer found.Add:[7]Final Output[[2,2,3],[7]]Recursion Tree Visualization[]/ | | \2 3 6 7/2/2/3Every branch explores a different combination.Time Complexity AnalysisTime ComplexityO(2^Target)More accurately:O(N^(Target/minValue))Where:N = Number of candidatesTarget = Required sumReason:Every number can be picked multiple times.This creates many recursive branches.Space ComplexityO(Target)Reason:Recursion stack stores elements.Maximum recursion depth depends on target.Why We Pass Same Index AgainNotice this line:solve(arr, i, target - arr[i], current);We pass i, not i+1.Why?Because we can reuse the same number unlimited times.If we used i+1, we would move forward and lose repetition.Why Duplicate Combinations Are Not CreatedWe start loop from current index.This guarantees:[2,3]and[3,2]are not both generated.Order remains controlled.Common Mistakes Beginners Make1. Using i+1 Instead of iWrong:solve(arr, i+1, target-arr[i], current)This prevents reuse.2. Forgetting Backtracking StepWrong:current.remove(current.size()-1)Without removing, recursion keeps incorrect values.3. Missing Target == 0 Base CaseThis is where valid answer is stored.Important Interview InsightCombination Sum is a foundational problem.It helps build understanding for:Combination Sum IISubsetsPermutationsN-QueensWord SearchSudoku SolverThis question is frequently asked in coding interviews.Pattern RecognitionUse Backtracking when problem says:Find all combinationsGenerate all subsetsFind all pathsUse recursionExplore possibilitiesOptimized Thinking StrategyWhenever you see:Target sumRepeated selectionMultiple combinationsThink:Backtracking + DFSEdge CasesCase 1candidates = [2]target = 1Output:[]No possible answer.Case 2candidates = [1]target = 3Output:[[1,1,1]]Interview Answer in One Line“We use backtracking to recursively try all candidate numbers while reducing the target and backtrack whenever a path becomes invalid.”Final Java Codeclass Solution {List<List<Integer>> result = new ArrayList<>();public void solve(int[] arr, int index, int target, List<Integer> current) {if (target == 0) {result.add(new ArrayList<>(current));return;}for (int i = index; i < arr.length; i++) {if (arr[i] > target) {continue;}current.add(arr[i]);solve(arr, i, target - arr[i], current);current.remove(current.size() - 1);}}public List<List<Integer>> combinationSum(int[] candidates, int target) {solve(candidates, 0, target, new ArrayList<>());return result;}}Key TakeawaysCombination Sum uses Backtracking.Reuse same element by passing same index.Target becomes smaller in recursion.Backtracking removes last element.Very important for interview preparation.Frequently Asked QuestionsIs Combination Sum DP or Backtracking?It is primarily solved using Backtracking.Dynamic Programming can also solve it but recursion is more common.Why is this Medium difficulty?Because:Requires recursion understandingRequires backtracking logicRequires duplicate preventionCan we sort the array?Yes.Sorting can help with pruning.ConclusionLeetCode 39 Combination Sum is one of the best problems to learn recursion and backtracking.Once you understand this pattern, many interview problems become easier.The loop-based recursive solution is clean, optimized, and interview-friendly.If you master this question, you gain strong understanding of recursive decision trees and combination generation.

LeetcodeMediumRecursionBacktrackingJava

Master LeetCode 92: Reverse Linked List II | Detailed Java Solution & Explanation

If you are preparing for software engineering interviews, you already know that Linked Lists are a favourite topic among interviewers. While reversing an entire linked list is a standard beginner problem, reversing only a specific section of it requires a bit more pointer magic.In this blog post, we will tackle LeetCode 92. Reverse Linked List II. We will break down the problem in plain English, walk through a highly intuitive modular approach, and then look at an optimized one-pass technique.Let’s dive in!Understanding the ProblemQuestion Statement:Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list.Example:Input: head = [1,2,3,4,5], left = 2, right = 4Output: [1,4,3,2,5]In Simple Words:Imagine a chain of connected boxes. You don't want to flip the whole chain backwards. You only want to flip a specific middle section (from the 2nd box to the 4th box), while keeping the first and last boxes exactly where they are.Approach 1: The Intuitive Modular Approach (Find, Reverse, Connect)When solving complex linked list problems, breaking the problem into smaller helper functions is an excellent software engineering practice.In this approach, we will:Use a Dummy Node. This is a lifesaver when left = 1 (meaning we have to reverse from the very first node).Traverse the list to find the exact boundaries: the node just before the reversal (slow), the start of the reversal (leftNode), and the end of the reversal (rightNode).Pass the sub-list to a helper function that reverses it.Reconnect the newly reversed sub-list back to the main list.Here is the Java code for this approach:/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */class Solution { // Helper function to reverse a portion of the list public ListNode reverse(ListNode LeftHead, ListNode rightHead){ ListNode curr = LeftHead; ListNode prev = rightHead; // Standard linked list reversal logic while(curr != rightHead){ ListNode newnode = curr.next; curr.next = prev; prev = curr; curr = newnode; } return prev; } public ListNode reverseBetween(ListNode head, int left, int right) { if(left == 1 && right == 1) return head; // Dummy node helps handle edge cases easily ListNode dummy = new ListNode(-1); dummy.next = head; ListNode leftNode = null; ListNode rightNode = null; ListNode curr = head; int leftC = 1; int rightC = 1; ListNode slow = dummy; // Traverse to find the exact bounds of our sublist while(curr != null){ if(leftC == left - 1){ slow = curr; // 'slow' is the node just before the reversed section } if(leftC == left){ leftNode = curr; } if(rightC == right){ rightNode = curr; } if(leftC == left && rightC == right){ break; // We found both bounds, no need to traverse further } leftC++; rightC++; curr = curr.next; } // Reverse the sublist and connect it back ListNode rev = reverse(leftNode, rightNode.next); slow.next = rev; return dummy.next; }}🔍 Dry Run of Approach 1Let’s trace head = [1, 2, 3, 4, 5], left = 2, right = 4.Step 1: Initializationdummy = -1 -> 1 -> 2 -> 3 -> 4 -> 5slow = -1 (dummy node)Step 2: Finding Bounds (While Loop)We move curr through the list.When curr is at 1 (Position 1): left - 1 is 1, so slow becomes node 1.When curr is at 2 (Position 2): leftNode becomes node 2.When curr is at 4 (Position 4): rightNode becomes node 4. We break the loop.Step 3: The Helper ReversalWe call reverse(leftNode, rightNode.next), which means reverse(Node 2, Node 5).Inside the helper, we reverse the links for 2, 3, and 4.Because we initialized prev as rightHead (Node 5), Node 2's next becomes Node 5.The helper returns Node 4 as the new head of this reversed chunk. The chunk now looks like: 4 -> 3 -> 2 -> 5.Step 4: ReconnectionBack in the main function, slow (Node 1) is connected to the returned reversed list: slow.next = rev.Final List: dummy -> 1 -> 4 -> 3 -> 2 -> 5.Return dummy.next!Time & Space Complexity:Time Complexity: O(N). We traverse the list to find the pointers, and then the helper traverses the sub-list to reverse it. Since we visit nodes a maximum of two times, it is linear time.Space Complexity: O(1). We are only creating a few pointers (dummy, slow, curr, etc.), requiring no extra dynamic memory.Approach 2: The Optimized One-Pass SolutionLeetCode includes a follow-up challenge: "Could you do it in one pass?"While the first approach is incredibly readable, we can optimize it to reverse the nodes as we traverse them, eliminating the need for a separate helper function or a second sub-list traversal.In this approach, we:Move a prev pointer to the node just before left.Keep a curr pointer at left.Use a for loop to extract the node immediately after curr and move it to the front of the reversed sub-list. We do this exactly right - left times.class Solution { public ListNode reverseBetween(ListNode head, int left, int right) { if (head == null || left == right) return head; ListNode dummy = new ListNode(0); dummy.next = head; ListNode prev = dummy; // Step 1: Reach the node just before 'left' for (int i = 0; i < left - 1; i++) { prev = prev.next; } // Step 2: Start the reversal process ListNode curr = prev.next; for (int i = 0; i < right - left; i++) { ListNode nextNode = curr.next; // Node to be moved to the front curr.next = nextNode.next; // Detach nextNode nextNode.next = prev.next; // Point nextNode to the current front of sublist prev.next = nextNode; // Make nextNode the new front of the sublist } return dummy.next; }}🔍 Why this works (The Pointer Magic)If we are reversing [1, 2, 3, 4, 5] from 2 to 4:prev is at 1. curr is at 2.Iteration 1: Grab 3, put it after 1. List: [1, 3, 2, 4, 5].Iteration 2: Grab 4, put it after 1. List: [1, 4, 3, 2, 5].Done! We achieved the reversal in a strict single pass.Time & Space Complexity:Time Complexity: O(N). We touch each node exactly once.Space Complexity: O(1). Done entirely in-place.ConclusionReversing a portion of a linked list is a fantastic way to test your understanding of pointer manipulation.Approach 1 is amazing for interviews because it shows you can modularize code and break big problems into smaller, testable functions.Approach 2 is the perfect "flex" to show the interviewer that you understand optimization and single-pass algorithms.I highly recommend writing down the dry run on a piece of paper and drawing arrows to see how the pointers shift. That is the secret to mastering Linked Lists!Happy Coding! 💻🚀

LeetCodeLinkedListJavaReverse LinkedList II

Queue Data Structure Complete Guide - Java Explained With All Operations

IntroductionIf you have been learning Data Structures and Algorithms, you have probably already spent time with arrays, linked lists, and stacks. Now it is time to meet one of the most important and widely used data structures in computer science — the Queue.Queue is not just a theoretical concept. It powers some of the most critical systems you use every day — from how your printer handles jobs, to how your CPU schedules tasks, to how Google Maps finds the shortest path between two locations. Understanding Queue deeply means understanding how real systems work.In this complete guide we will cover absolutely everything — what a Queue is, how it differs from a Stack, every type of Queue, all operations with code, Java implementations, time and space complexity, common interview questions, and the most important LeetCode problems that use Queue.What Is a Queue?A Queue is a linear data structure that follows the FIFO principle — First In First Out. This means the element that was added first is the one that gets removed first.Think of it exactly like a real-world queue (a line of people). The person who joined the line first gets served first. No cutting in line, no serving from the back — strict order from front to back.This is the fundamental difference between a Queue and a Stack:Stack → LIFO (Last In First Out) — like a stack of plates, you take from the topQueue → FIFO (First In First Out) — like a line of people, you serve from the frontReal Life Examples of QueueBefore writing a single line of code, let us understand where queues appear in real life. This will make every technical concept feel natural.Printer Queue — when you send multiple documents to print, they print in the order they were sent. The first document sent prints first.CPU Task Scheduling — your operating system manages running processes in a queue. Tasks get CPU time in the order they arrive (in basic scheduling).Customer Service Call Center — when you call a helpline and are put on hold, you are placed in a queue. The first caller on hold gets connected first.WhatsApp Messages — messages are delivered in the order they are sent. The first message sent is the first one received.BFS (Breadth First Search) — every time you use Google Maps or any navigation app to find the shortest path, it uses BFS internally which is entirely powered by a Queue.Ticket Booking Systems — online booking portals process requests in the order they arrive. First come first served.Queue Terminology — Key Terms You Must KnowBefore diving into code, let us get the vocabulary right:Front — the end from which elements are removed (dequeued). This is where the "first person in line" stands.Rear (or Back) — the end at which elements are added (enqueued). New arrivals join here.Enqueue — the operation of adding an element to the rear of the queue. Like joining the back of a line.Dequeue — the operation of removing an element from the front of the queue. Like the first person in line being served and leaving.Peek (or Front) — looking at the front element without removing it. Like seeing who is first in line without serving them yet.isEmpty — checking whether the queue has no elements.isFull — relevant for fixed-size queues, checking whether no more elements can be added.Types of QueuesThis is where most beginners get confused. There is not just one type of Queue — there are several variations each designed to solve specific problems.1. Simple Queue (Linear Queue)The most basic form. Elements enter from the rear and leave from the front. Strict FIFO, nothing fancy.Enqueue → [ 1 | 2 | 3 | 4 | 5 ] → Dequeue rear frontProblem with Simple Queue: In array-based implementation, once elements are dequeued from the front, those slots cannot be reused even if there is space. This wastes memory. This is why Circular Queue was invented.2. Circular QueueIn a Circular Queue, the rear wraps around to the front when it reaches the end of the array. The last position connects back to the first, forming a circle. This solves the wasted space problem of simple queues. [1] [2] [3] / \ [6] [4] \ / [5] ← rearUsed in: CPU scheduling, memory management, traffic light systems, streaming buffers.3. Double Ended Queue (Deque)A Deque (pronounced "deck") allows insertion and deletion from both ends — front and rear. It is the most flexible queue type.Enqueue Front → [ 1 | 2 | 3 | 4 | 5 ] → Dequeue FrontEnqueue Rear → [ 1 | 2 | 3 | 4 | 5 ] → Dequeue RearTwo subtypes:Input Restricted Deque — insertion only at rear, deletion from both endsOutput Restricted Deque — deletion only at front, insertion at both endsUsed in: browser history (back and forward), undo-redo operations, sliding window problems.4. Priority QueueElements are not served in FIFO order — instead each element has a priority and the element with the highest priority is served first regardless of when it was added.Think of an emergency room. A patient with a critical injury jumps ahead of someone with a minor cut even if they arrived later.Two types:Max Priority Queue — highest value = highest priorityMin Priority Queue — lowest value = highest priorityUsed in: Dijkstra's shortest path, Huffman encoding, A* search algorithm, task scheduling with priorities.5. Blocking QueueA thread-safe queue used in multi-threading. If the queue is empty, a thread trying to dequeue will wait (block) until an element is available. If the queue is full, a thread trying to enqueue will wait until space is available.Used in: Producer-Consumer problems, thread pool implementations, Java's java.util.concurrent package.Queue Operations and Time ComplexityEvery queue operation has a specific time complexity that you must know cold for interviews.OperationDescriptionTime ComplexityEnqueueAdd element to rearO(1)DequeueRemove element from frontO(1)Peek/FrontView front elementO(1)isEmptyCheck if queue is emptyO(1)SizeNumber of elementsO(1)SearchFind a specific elementO(n)Space Complexity: O(n) — where n is the number of elements stored.All core queue operations are O(1). This is what makes Queue so powerful — no matter how many elements are in the queue, adding and removing always takes constant time.Implementing Queue in Java — All WaysJava gives you multiple ways to use a Queue. Let us go through each one.Way 1: Using LinkedList (Most Common)LinkedList implements the Queue interface in Java. This is the most commonly used Queue implementation.import java.util.LinkedList;import java.util.Queue;Queue<Integer> queue = new LinkedList<>();// Enqueue — add to rearqueue.offer(10);queue.offer(20);queue.offer(30);// Peek — view front without removingSystem.out.println(queue.peek()); // 10// Dequeue — remove from frontSystem.out.println(queue.poll()); // 10System.out.println(queue.poll()); // 20// Check emptySystem.out.println(queue.isEmpty()); // false// SizeSystem.out.println(queue.size()); // 1offer() vs add() — both add to the queue. add() throws an exception if the queue is full (for bounded queues). offer() returns false instead. Always prefer offer().poll() vs remove() — both remove from front. remove() throws an exception if queue is empty. poll() returns null. Always prefer poll().peek() vs element() — both view the front. element() throws exception if empty. peek() returns null. Always prefer peek().Way 2: Using ArrayDeque (Fastest)ArrayDeque is faster than LinkedList for Queue operations because it uses a resizable array internally with no node allocation overhead.import java.util.ArrayDeque;import java.util.Queue;Queue<Integer> queue = new ArrayDeque<>();queue.offer(1);queue.offer(2);queue.offer(3);System.out.println(queue.peek()); // 1System.out.println(queue.poll()); // 1System.out.println(queue.size()); // 2When to use ArrayDeque over LinkedList? Use ArrayDeque whenever possible for Queue or Stack operations. It is faster because it avoids the overhead of node objects that LinkedList creates for every element. In competitive programming and interviews, ArrayDeque is the preferred choice.Way 3: Using Deque (Double Ended Queue)import java.util.ArrayDeque;import java.util.Deque;Deque<Integer> deque = new ArrayDeque<>();// Add to frontdeque.offerFirst(10);// Add to reardeque.offerLast(20);deque.offerLast(30);// Remove from frontSystem.out.println(deque.pollFirst()); // 10// Remove from rearSystem.out.println(deque.pollLast()); // 30// Peek front and rearSystem.out.println(deque.peekFirst()); // 20System.out.println(deque.peekLast()); // 20Way 4: Using PriorityQueueimport java.util.PriorityQueue;// Min Heap — smallest element has highest priorityPriorityQueue<Integer> minPQ = new PriorityQueue<>();minPQ.offer(30);minPQ.offer(10);minPQ.offer(20);System.out.println(minPQ.poll()); // 10 — smallest comes out first// Max Heap — largest element has highest priorityPriorityQueue<Integer> maxPQ = new PriorityQueue<>((a, b) -> b - a);maxPQ.offer(30);maxPQ.offer(10);maxPQ.offer(20);System.out.println(maxPQ.poll()); // 30 — largest comes out firstWay 5: Implementing Queue From Scratch Using ArrayUnderstanding the underlying implementation helps you in interviews when asked to build one from scratch.class MyQueue { private int[] arr; private int front; private int rear; private int size; private int capacity; public MyQueue(int capacity) { this.capacity = capacity; arr = new int[capacity]; front = 0; rear = -1; size = 0; } public void enqueue(int val) { if (size == capacity) { System.out.println("Queue is full!"); return; } rear = (rear + 1) % capacity; // circular wrapping arr[rear] = val; size++; } public int dequeue() { if (isEmpty()) { System.out.println("Queue is empty!"); return -1; } int val = arr[front]; front = (front + 1) % capacity; // circular wrapping size--; return val; } public int peek() { if (isEmpty()) return -1; return arr[front]; } public boolean isEmpty() { return size == 0; } public int size() { return size; }}Notice the % capacity in enqueue and dequeue — that is what makes it a Circular Queue. Without this, once the rear reaches the end of the array, you cannot add more even if front has moved forward and freed up space.Way 6: Implementing Queue Using Two StacksThis is a very popular interview question — implement a Queue using two stacks. The idea is to use one stack for enqueue and another for dequeue.class QueueUsingTwoStacks { Stack<Integer> s1 = new Stack<>(); // for enqueue Stack<Integer> s2 = new Stack<>(); // for dequeue public void enqueue(int val) { s1.push(val); // always push to s1 } public int dequeue() { if (s2.isEmpty()) { // transfer all elements from s1 to s2 // this reverses the order, giving FIFO behavior while (!s1.isEmpty()) { s2.push(s1.pop()); } } return s2.pop(); } public int peek() { if (s2.isEmpty()) { while (!s1.isEmpty()) { s2.push(s1.pop()); } } return s2.peek(); } public boolean isEmpty() { return s1.isEmpty() && s2.isEmpty(); }}Why does this work?When you transfer elements from s1 to s2, the order reverses. The element that was added first to s1 ends up on top of s2 — which means it gets dequeued first. FIFO achieved using two LIFOs!Amortized time complexity: Each element is pushed and popped at most twice (once in s1, once in s2). So dequeue is O(1) amortized even though individual calls might take O(n).This is LeetCode 232 — Implement Queue using Stacks.Queue vs Stack — Side by SideFeatureQueueStackPrincipleFIFO — First In First OutLIFO — Last In First OutInsert atRearTopRemove fromFrontTopReal lifeLine of peopleStack of platesJava classLinkedList, ArrayDequeStack, ArrayDequeMain useBFS, schedulingDFS, backtracking, parsingPeekFront elementTop elementBFS — The Most Important Application of QueueBreadth First Search (BFS) is the single most important algorithm that uses a Queue. Understanding BFS is why Queue matters so much in DSA.BFS explores a graph or tree level by level — all nodes at distance 1 first, then all at distance 2, and so on. A Queue naturally enforces this level-by-level behavior.public void bfs(int start, List<List<Integer>> graph) { Queue<Integer> queue = new LinkedList<>(); boolean[] visited = new boolean[graph.size()]; queue.offer(start); visited[start] = true; while (!queue.isEmpty()) { int node = queue.poll(); // process front node System.out.print(node + " "); for (int neighbor : graph.get(node)) { if (!visited[neighbor]) { visited[neighbor] = true; queue.offer(neighbor); // add unvisited neighbors to rear } } }}Why Queue and not Stack for BFS? Queue ensures you process all neighbors of a node before going deeper. Stack would take you deep into one path first — that is DFS, not BFS. The FIFO property is what guarantees level-by-level exploration.BFS with Queue is used in:Shortest path in unweighted graphsLevel order traversal of treesFinding connected componentsWord ladder problemsRotten oranges, flood fill, and matrix BFS problemsLevel Order Traversal — BFS on TreesOne of the most common Queue problems in interviews is Level Order Traversal of a binary tree.public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> result = new ArrayList<>(); if (root == null) return result; Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { int levelSize = queue.size(); // number of nodes at current level List<Integer> level = new ArrayList<>(); for (int i = 0; i < levelSize; i++) { TreeNode node = queue.poll(); level.add(node.val); if (node.left != null) queue.offer(node.left); if (node.right != null) queue.offer(node.right); } result.add(level); } return result;}The key trick here is using queue.size() at the start of each while loop iteration to know exactly how many nodes belong to the current level. Process exactly that many nodes, then move to the next level.This is LeetCode 102 — Binary Tree Level Order Traversal.Sliding Window Maximum — Monotonic DequeOne of the most impressive Queue applications is the Sliding Window Maximum problem using a Monotonic Deque. This is the queue equivalent of the Monotonic Stack pattern you saw in stack problems.The idea — maintain a deque that stores indices of elements in decreasing order. The front always holds the index of the maximum element in the current window.public int[] maxSlidingWindow(int[] nums, int k) { Deque<Integer> deque = new ArrayDeque<>(); // stores indices int[] result = new int[nums.length - k + 1]; int idx = 0; for (int i = 0; i < nums.length; i++) { // remove indices that are out of the current window while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) { deque.pollFirst(); } // remove indices whose values are smaller than current // they can never be the maximum for any future window while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) { deque.pollLast(); } deque.offerLast(i); // window is fully formed, record maximum (front of deque) if (i >= k - 1) { result[idx++] = nums[deque.peekFirst()]; } } return result;}This gives O(n) time for what would otherwise be an O(n×k) problem. This is LeetCode 239 — Sliding Window Maximum.Java Queue Interface — Complete Method ReferenceHere is every method you will ever need from Java's Queue and Deque interfaces:Queue Methods:offer(e) — add to rear, returns false if full (preferred over add) poll() — remove from front, returns null if empty (preferred over remove) peek() — view front without removing, returns null if empty (preferred over element) isEmpty() — returns true if no elements size() — returns number of elements contains(o) — returns true if element existsDeque Additional Methods:offerFirst(e) — add to front offerLast(e) — add to rear pollFirst() — remove from front pollLast() — remove from rear peekFirst() — view front peekLast() — view rearPriorityQueue Specific:offer(e) — add with natural ordering or custom comparator poll() — remove element with highest priority peek() — view highest priority element without removingCommon Interview Questions About QueueThese are the questions interviewers ask to test your understanding of queues conceptually — not just coding.Q1. What is the difference between Queue and Stack? Queue is FIFO — elements are removed in the order they were added. Stack is LIFO — the most recently added element is removed first. Queue removes from the front, Stack removes from the top.Q2. Why is ArrayDeque preferred over LinkedList for Queue in Java? ArrayDeque uses a resizable array internally and has better cache locality and no node allocation overhead. LinkedList creates a new node object for every element added, which means more garbage collection pressure. ArrayDeque is faster in practice for most Queue use cases.Q3. When would you use a PriorityQueue instead of a regular Queue? When the order of processing depends on priority rather than arrival order. For example in a hospital, critical patients are treated before minor cases regardless of when they arrived. Or in Dijkstra's algorithm, always processing the shortest known distance first.Q4. How is Queue used in BFS? BFS uses a Queue to explore nodes level by level. The starting node is enqueued first. Each time a node is dequeued, all its unvisited neighbors are enqueued. Since Queue is FIFO, all neighbors of a node are processed before going deeper — guaranteeing level-by-level exploration.Q5. What is the difference between poll() and remove() in Java Queue? Both remove the front element. remove() throws NoSuchElementException if the queue is empty. poll() returns null instead of throwing. Always use poll() for safer code.Q6. Can a Queue have duplicates? Yes. Queue does not have any restriction on duplicate values unlike Sets. The same value can appear multiple times in a Queue.Q7. What is a Blocking Queue and when is it used? A Blocking Queue is a thread-safe Queue used in multi-threaded applications. When a thread tries to dequeue from an empty queue, it blocks (waits) until an element is available. When a thread tries to enqueue into a full queue, it blocks until space is available. Used in Producer-Consumer patterns.Top LeetCode Problems on QueueHere are the most important LeetCode problems that use Queue — organized from beginner to advanced:Beginner Level:232. Implement Queue using Stacks — implement Queue with two stacks, classic interview question225. Implement Stack using Queues — reverse of 232, implement Stack using Queue933. Number of Recent Calls — sliding window with QueueIntermediate Level:102. Binary Tree Level Order Traversal — BFS on tree, must know107. Binary Tree Level Order Traversal II — same but bottom up994. Rotting Oranges — multi-source BFS on grid1091. Shortest Path in Binary Matrix — BFS shortest path542. 01 Matrix — multi-source BFS, distance to nearest 0127. Word Ladder — BFS on word graph, classicAdvanced Level:239. Sliding Window Maximum — monotonic deque, must know862. Shortest Subarray with Sum at Least K — monotonic deque with prefix sums407. Trapping Rain Water II — 3D BFS with priority queue787. Cheapest Flights Within K Stops — BFS with constraintsQueue Cheat Sheet — Everything at a GlanceCreate a Queue:Queue<Integer> q = new LinkedList<>(); // standardQueue<Integer> q = new ArrayDeque<>(); // faster, preferredDeque<Integer> dq = new ArrayDeque<>(); // double endedPriorityQueue<Integer> pq = new PriorityQueue<>(); // min heapPriorityQueue<Integer> pq = new PriorityQueue<>((a,b) -> b-a); // max heapCore Operations:q.offer(x); // enqueueq.poll(); // dequeueq.peek(); // front elementq.isEmpty(); // check emptyq.size(); // number of elementsDeque Operations:dq.offerFirst(x); // add to frontdq.offerLast(x); // add to reardq.pollFirst(); // remove from frontdq.pollLast(); // remove from reardq.peekFirst(); // view frontdq.peekLast(); // view rearBFS Template:Queue<Integer> queue = new LinkedList<>();queue.offer(start);visited[start] = true;while (!queue.isEmpty()) { int node = queue.poll(); for (int neighbor : graph.get(node)) { if (!visited[neighbor]) { visited[neighbor] = true; queue.offer(neighbor); } }}ConclusionQueue is one of those data structures that appears simple on the surface but has incredible depth once you start exploring its variations and applications. From the basic FIFO concept to Circular Queues, Deques, Priority Queues, Monotonic Deques, and BFS — each layer adds a new tool to your problem-solving arsenal.Here is the learning path to follow based on everything covered in this guide:Start with understanding FIFO vs LIFO and when each applies. Then get comfortable with Java's Queue interface — offer, poll, peek. Practice the BFS template until it feels automatic. Then move to Level Order Traversal problems. Once BFS clicks, tackle multi-source BFS problems like Rotting Oranges. Finally learn the Monotonic Deque pattern for sliding window problems.Master these and you will handle every Queue problem in any coding interview with confidence.

QueueData StructureJavaBFSDequePriority QueueCircular Queue

LeetCode 2078: Two Furthest Houses With Different Colors | Java Solution Explained (Step-by-Step Guide)

Why This Problem Is InterestingAt first glance, this looks like a basic array problem. But here’s the twist:👉 If you try solving it “normally,” you’ll overthink it. 👉 If you observe patterns, it becomes one of the easiest O(n) problems.This is exactly the kind of question interviewers use to test:Do you brute force blindly?Or do you see patterns in constraints?🚀 Problem Linkhttps://leetcode.com/problems/two-furthest-houses-with-different-colors/🧩 Problem Breakdown (Understand Like a Beginner)You are given:colors = [1,1,1,6,1,1,1]Each index = house Each value = colorYou need to:👉 Pick two houses with different colors 👉 Maximize the distance between themDistance formula:|i - j|🧠 First Thought (What Most People Do)“Let me check all pairs…”(0,1), (0,2), (0,3), ...(1,2), (1,3), ...Yes, it works. But…👉 That’s O(n²) 👉 Completely unnecessary for n ≤ 100? Maybe fine 👉 But logically inefficient🟡 Approach 1: Brute Force (Baseline Thinking)💻 Codeclass Solution { public int maxDistance(int[] colors) { int n = colors.length; int max = 0; for (int i = 0; i < n; i++) { for (int j = n - 1; j > i; j--) { if (colors[i] != colors[j]) { max = Math.max(max, j - i); } } } return max; }}⏱ Time Complexity (Why O(n²)?)Outer loop → runs n timesInner loop → runs n times👉 Total = n * n = O(n²)❌ Why This Is WastefulYou are:Checking close houses (useless)When the answer depends on far houses💡 Key Turning Point (Where Real Thinking Starts)Ask yourself:👉 “To maximize |i - j|, what do I need?”Answer:👉 Make i and j as far apart as possibleThat means:i should be near 0j should be near n-1🔥 Critical Observation👉 The answer will always involve either:First house (index 0), ORLast house (index n-1)Why?Because they give maximum possible distance🟢 Approach 2: Two Direction ScanNow your idea makes perfect sense:Step 1Fix first element → find farthest different colorStep 2Fix last element → find farthest different color💻 Your Codeclass Solution { public int maxDistance(int[] colors) { int i = 0; int i2 = colors.length - 1; int j1 = 1; int j2 = colors.length - 2; int max1 = Integer.MIN_VALUE; int max2 = Integer.MIN_VALUE; while (j1 < colors.length) { if (colors[i] != colors[j1]) { max1 = Math.max(max1, Math.abs(j1 - i)); } j1++; } while (j2 >= 0) { if (colors[i2] != colors[j2]) { max2 = Math.max(max2, Math.abs(j2 - i2)); } j2--; } return Math.max(max1, max2); }}🔍 Dry Run (Deep Understanding)Input:colors = [1,1,1,6,1,1,1]🔹 First Loop (Fix index 0)Compare:0 vs 1 → same0 vs 2 → same0 vs 3 → different ✅ → distance = 30 vs 4 → same0 vs 5 → same0 vs 6 → same👉 max1 = 3🔹 Second Loop (Fix last index)Compare:6 vs 5 → same6 vs 4 → same6 vs 3 → different ✅ → distance = 36 vs 2 → same...👉 max2 = 3✅ Final Answer:max(3, 3) = 3⏱ Time Complexity (Why O(n)?)First loop → O(n)Second loop → O(n)👉 Total = O(n) + O(n) = O(n)🟢 Approach 3: Cleaner Optimization (Best Version)We can compress both loops into one:💻 Codeclass Solution { public int maxDistance(int[] colors) { int n = colors.length; int max = 0; for (int i = 0; i < n; i++) { if (colors[i] != colors[0]) { max = Math.max(max, i); } if (colors[i] != colors[n - 1]) { max = Math.max(max, n - 1 - i); } } return max; }}🔍 Why This Works (Core Insight)We only check:Distance from startDistance from endBecause:👉 Any maximum distance pair must include one endpointThis avoids:Redundant comparisonsNested loops🧠 Mental Model (Remember This)Instead of thinking:❌ “Check all pairs”Think:✅ “Where can maximum distance even exist?”🎯 Final TakeawaysAlways question brute forceDistance problems → think endpoints firstConstraints often hide optimizationsObservations > Code

LeetCodeJavaArraysTwoPointersEasy

LeetCode 88 Merge Sorted Array Explained: Brute Force to Optimal Java Solution (3 Pointer Approach)

IntroductionLeetCode 88 — Merge Sorted Array is one of the most important beginner-friendly array problems asked in coding interviews.At first glance, the problem looks very easy because both arrays are already sorted. But the real challenge is:How do we merge them efficiently without using extra space?This question is commonly asked by companies because it tests:Array manipulationTwo pointer techniqueIn-place modificationEdge case handlingSpace optimizationThe most important learning from this problem is understanding:Why merging from the back is the optimal strategy.In this article, we will cover:Problem understandingBrute force approachBetter approachOptimal 3-pointer solutionStep-by-step dry runTime & space complexityCommon mistakesInterview tipsFAQsBy the end, you will completely understand the logic behind this problem.Try This Problem👉 https://leetcode.com/problems/merge-sorted-array/Problem StatementYou are given two sorted arrays:nums1nums2Along with two integers:m → valid elements in nums1n → elements in nums2The array nums1 has size:m + nThe last n positions are empty spaces represented by 0.Your task is to merge nums2 into nums1 such that the final array remains sorted.ExampleExample 1Inputnums1 = [1,2,3,0,0,0]m = 3nums2 = [2,5,6]n = 3Output[1,2,2,3,5,6]Understanding the ProblemLet us simplify what the question is asking.We have:nums1 → already sortednums2 → already sortedWe need:one final sorted arrayBut there is one important condition:We must store the answer inside nums1 itself.That means:No returning new arrayModify nums1 directlyWhy This Problem is TrickyMany beginners immediately think:Copy nums2 into nums1Then sort nums1This works.But interviews usually expect a more optimized solution.The challenge is:Can we merge without sorting again?Yes — using the Two Pointer technique.Approach 1 — Brute Force SolutionIdeaCopy all elements of nums2 into empty positions of nums1Sort the final arrayJava Codeclass Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { // Copy nums2 into nums1 for(int i = 0; i < n; i++) { nums1[m + i] = nums2[i]; } // Sort final array Arrays.sort(nums1); }}Dry Run of Brute ForceInitial:nums1 = [1,2,3,0,0,0]nums2 = [2,5,6]After copying:[1,2,3,2,5,6]After sorting:[1,2,2,3,5,6]Time ComplexityCopyingO(n)SortingO((m+n) log(m+n))Space ComplexityO(1)Drawback of Brute ForceSorting again is unnecessary because:Arrays are already sortedWe can merge smarterApproach 2 — Extra Array MergeIdeaUse a third temporary array.This works exactly like merge step in Merge Sort.StepsCompare elements from both arraysInsert smaller one into temp arrayCopy final temp array into nums1Java Codeclass Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { int[] temp = new int[m + n]; int i = 0; int j = 0; int k = 0; while(i < m && j < n) { if(nums1[i] <= nums2[j]) { temp[k++] = nums1[i++]; } else { temp[k++] = nums2[j++]; } } while(i < m) { temp[k++] = nums1[i++]; } while(j < n) { temp[k++] = nums2[j++]; } for(i = 0; i < m + n; i++) { nums1[i] = temp[i]; } }}Time ComplexityO(m + n)Space ComplexityO(m + n)Can We Do Better?Yes.The interview-expected solution uses:Optimal Approach — Three Pointers from BackMost Important ObservationThe end of nums1 already contains empty spaces.So instead of merging from front:We merge from the back.This avoids overwriting important elements.Main IdeaWe use 3 pointers:left → last valid element in nums1right → last element in nums2insertPos → last position of nums1We compare:nums1[left]nums2[right]The larger element is placed at:nums1[insertPos]Then move pointers backward.Why Backward Merging WorksSuppose:nums1 = [1,2,3,0,0,0]nums2 = [2,5,6]If we start from front:we overwrite existing valuesBut from back:empty spaces already existSo no data loss occurs.Optimal Java Solutionclass Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { int left = m - 1; int right = n - 1; int insertPos = m + n - 1; for(int i = insertPos; i >= 0; i--) { if(right < 0 || (left >= 0 && nums1[left] >= nums2[right])) { nums1[i] = nums1[left]; left--; } else { nums1[i] = nums2[right]; right--; } } }}Step-by-Step Dry RunInputnums1 = [1,2,3,0,0,0]nums2 = [2,5,6]Initial Pointersleft = 2 → value 3right = 2 → value 6insertPos = 5Step 1Compare:3 vs 66 is larger.Place 6 at end.[1,2,3,0,0,6]Move:right--insertPos--Step 2Compare:3 vs 5Place 5.[1,2,3,0,5,6]Step 3Compare:3 vs 2Place 3.[1,2,3,3,5,6]Step 4Compare:2 vs 2Place 2.[1,2,2,3,5,6]Done.Time ComplexityWe traverse both arrays once.O(m + n)Space ComplexityNo extra space used.O(1)Why This is the Best SolutionThis solution is optimal because:✅ No sorting required ✅ No extra array required ✅ Single traversal ✅ In-place merging ✅ Interview preferred solutionCommon Mistakes1. Merging from FrontThis overwrites elements in nums1.2. Forgetting Edge CasesExample:m = 0orn = 03. Wrong Pointer InitializationCorrect:left = m - 1right = n - 14. Array Index Out of BoundsAlways check:left >= 0right >= 0Interview TipsIf interviewer asks:“Why merge from back?”Your answer:Because nums1 already has empty spaces at the end. Backward traversal prevents overwriting existing sorted elements.Frequently Asked QuestionsQ1. Why not use sorting?Because arrays are already sorted.Sorting again wastes time.Q2. Why start from end?To safely place larger elements without overwriting.Q3. Is this similar to Merge Sort?Yes.This is essentially the merge step of Merge Sort.Q4. What if nums2 is empty?Then nums1 remains unchanged.Q5. What if nums1 has no valid elements?Then copy all elements from nums2.Final TakeawayThe biggest learning from this problem is:Whenever extra space exists at the end of an array, think about backward traversal.This pattern appears frequently in interview questions.ConclusionLeetCode 88 is one of the best beginner problems to master:Two pointersIn-place array modificationEfficient mergingSpace optimizationAlthough the brute force solution works, the optimal 3-pointer approach is the real interview solution.Once you understand why backward merging works, this problem becomes extremely easy to solve in interviews and coding rounds.

ArraysTwo PointersSortingJavaEasyLeetcode

LeetCode 462: Minimum Moves to Equal Array Elements II | Java Solution Explained (Median Approach)

IntroductionLeetCode 462 is a classic mathematical and greedy problem.We are given an integer array where each operation allows us to:Increment an element by 1Decrement an element by 1Our task is to make all numbers equal while using the minimum number of moves.At first glance, this may look like a simple array problem.But the hidden concept behind this question is:Median propertyGreedy optimizationAbsolute difference minimizationThis problem is extremely popular in coding interviews because it tests logical thinking more than coding complexity.# Problem LinkProblem StatementYou are given an integer array nums.In one move:You can increase an element by 1Or decrease an element by 1You must make all array elements equal.Return the minimum number of operations required.Example 1Input:nums = [1,2,3]Output:2Explanation:[1,2,3]→ [2,2,3]→ [2,2,2]Total operations = 2Example 2Input:nums = [1,10,2,9]Output:16Key ObservationWe need to choose one target value such that all numbers move toward it.Question:Which target gives minimum total moves?Answer:MedianMedian minimizes the sum of absolute differences.Why Median Works?Suppose:nums = [1,2,3,10]If target = 2|1-2| + |2-2| + |3-2| + |10-2|= 1 + 0 + 1 + 8= 10If target = 5|1-5| + |2-5| + |3-5| + |10-5|= 4 + 3 + 2 + 5= 14Median gives minimum moves.Approach 1: Brute ForceIn this approach, we try every possible value as target.For each target:Calculate total operations neededStore minimum answerAlgorithmFind minimum and maximum elementTry every value between themCompute total movesReturn minimumJava Code (Brute Force)class Solution {public int minMoves2(int[] nums) {int min = Integer.MAX_VALUE;int max = Integer.MIN_VALUE;for (int num : nums) {min = Math.min(min, num);max = Math.max(max, num);}int result = Integer.MAX_VALUE;for (int target = min; target <= max; target++) {int moves = 0;for (int num : nums) {moves += Math.abs(num - target);}result = Math.min(result, moves);}return result;}}Time ComplexityO(N × Range)Very slow for large values.Approach 2: Sorting + Median (Optimal)This is the best and most commonly used approach.IdeaSort arrayPick median elementCalculate total absolute differenceStepsStep 1: Sort ArraySorting helps us easily find median.Step 2: Pick MedianMedian index = n / 2Step 3: Calculate MovesFor every element:moves += abs(median - value)Optimal Java Solutionclass Solution {public int minMoves2(int[] nums) {Arrays.sort(nums);int mid = nums.length / 2;int ans = 0;for (int i = 0; i < nums.length; i++) {int diff = Math.abs(nums[mid] - nums[i]);ans += diff;}return ans;}}Code ExplanationStep 1: Sort ArrayArrays.sort(nums);Sorting allows median calculation.Step 2: Get Medianint mid = nums.length / 2;Middle element becomes target.Step 3: Compute DifferenceMath.abs(nums[mid] - nums[i])Find distance from median.Step 4: Add All Movesans += diff;Store total moves.Approach 3: Two Pointer OptimizationAfter sorting, we can use two pointers.Instead of calculating absolute difference manually, we can pair smallest and largest values.IdeaAfter sorting:moves += nums[right] - nums[left]Because both numbers will meet toward median.Java Code (Two Pointer)class Solution {public int minMoves2(int[] nums) {Arrays.sort(nums);int left = 0;int right = nums.length - 1;int moves = 0;while (left < right) {moves += nums[right] - nums[left];left++;right--;}return moves;}}Why Two Pointer Works?Because:Median minimizes total distancePairing smallest and largest values gives direct movement cost.Dry RunInput:nums = [1,10,2,9]Sort:[1,2,9,10]Median:9Operations:|1-9| = 8|2-9| = 7|9-9| = 0|10-9| = 1Total:16Time ComplexitySortingO(N log N)TraversingO(N)TotalO(N log N)Space ComplexityO(1)Ignoring sorting stack.Common Mistakes1. Using Average Instead of MedianMany people think average gives minimum.Wrong.Average minimizes squared difference.Median minimizes absolute difference.2. Forgetting SortingMedian requires sorted order.3. Overflow IssueValues can be large.Sometimes use:long ansfor safer calculation.4. Using Wrong Median IndexCorrect:n / 2Edge CasesCase 1Single element array.Answer = 0Case 2All elements already equal.Answer = 0Case 3Negative numbers.Algorithm still works.FAQsQ1. Why median gives minimum moves?Median minimizes total absolute difference.Q2. Can average work?No.Average does not minimize absolute distance.Q3. Is sorting necessary?Yes.Sorting helps us easily find median.Q4. Which approach is best?Sorting + median approach.Interview InsightInterviewers ask this problem to test:Median property understandingGreedy optimizationMathematical thinkingArray manipulationConclusionLeetCode 462 is one of the most important median-based interview questions.The major learning is:Median minimizes total absolute differenceSorting makes finding median easySum of distances gives answerOnce you understand why median works, this question becomes very simple.

MathMedianMediumLeetCodeJavaArrayTwo PointerSorting

LeetCode 94: Binary Tree Inorder Traversal – Java Recursive & Iterative Solution Explained

IntroductionLeetCode 94 – Binary Tree Inorder Traversal is one of the most important beginner-friendly tree problems in Data Structures and Algorithms.This problem helps you understand:Binary tree traversalDepth First Search (DFS)RecursionStack-based traversalTree interview fundamentalsIt is commonly asked in coding interviews because tree traversal forms the foundation of many advanced tree problems.Problem Link🔗 ProblemLeetCode 94: Binary Tree Inorder TraversalOfficial Problem:LeetCode Problem LinkProblem StatementGiven the root of a binary tree, return the inorder traversal of its nodes' values.What is Inorder Traversal?In inorder traversal, we visit nodes in this order:Left → Root → RightExampleInputroot = [1,null,2,3]Tree Structure:1\2/3Inorder TraversalStep-by-step:1 → 3 → 2Output:[1,3,2]Recursive Approach (Most Common)IntuitionIn inorder traversal:Traverse left subtreeVisit current nodeTraverse right subtreeThis naturally fits recursion because trees themselves are recursive structures.Recursive DFS VisualizationTraversal order:Left → Node → RightRecursive function:inorder(node.left)visit(node)inorder(node.right)Java Recursive Solution/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* }*/class Solution {public void solve(List<Integer> list, TreeNode root) {if(root == null) return;solve(list, root.left);list.add(root.val);solve(list, root.right);}public List<Integer> inorderTraversal(TreeNode root) {List<Integer> list = new ArrayList<>();solve(list, root);return list;}}Dry Run – Recursive ApproachTree:1\2/3Step 1Start at:1Move left:nullReturn back.Add:1Step 2Move right to:2Move left to:3Add:3Return back.Add:2Final Answer[1,3,2]Time Complexity – RecursiveTime ComplexityO(N)Every node is visited once.Space ComplexityO(H)Where:H = height of treeRecursive call stack uses extra spaceWorst case:O(N)for skewed trees.Iterative Approach (Interview Follow-Up)The follow-up asks:Can you solve it iteratively?Yes.We use a stack to simulate recursion.Iterative Inorder IntuitionThe recursive order is:Left → Node → RightSo iteratively:Keep pushing left nodes into stackProcess current nodeMove to right subtreeStack-Based Traversal LogicAlgorithmWhile current node exists OR stack is not empty:Push all left nodesPop top nodeAdd node valueMove to right subtreeJava Iterative Solutionclass Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> ans = new ArrayList<>();Stack<TreeNode> stack = new Stack<>();TreeNode curr = root;while(curr != null || !stack.isEmpty()) {while(curr != null) {stack.push(curr);curr = curr.left;}curr = stack.pop();ans.add(curr.val);curr = curr.right;}return ans;}}Dry Run – Iterative ApproachTree:1\2/3Step 1Push:1Stack:[1]Step 2Pop:1Add:1Move right to:2Step 3Push:23Stack:[2,3]Step 4Pop:3Add:3Step 5Pop:2Add:2Final Answer[1,3,2]Comparison of ApproachesApproachAdvantagesDisadvantagesRecursiveEasy to write and understandUses recursion stackIterativeBetter interview practiceSlightly harder logicInterview ExplanationIn interviews, explain:In inorder traversal, we process nodes in Left → Root → Right order. Recursion naturally fits this traversal. For iterative traversal, we use a stack to simulate recursive calls.This demonstrates strong tree traversal understanding.Common Mistakes1. Wrong Traversal OrderIncorrect:Root → Left → RightThat is preorder traversal.Correct inorder:Left → Root → Right2. Forgetting Null Base CaseAlways check:if(root == null) return;3. Stack Handling ErrorsIn iterative traversal:Push all left nodes firstThen process nodeThen move rightFAQsQ1. Why is inorder traversal important?It is heavily used in:Binary Search TreesExpression treesTree reconstruction problemsQ2. What is the inorder traversal of a BST?It produces values in sorted order.Q3. Which approach is better for interviews?Recursive is easier.Iterative is preferred for deeper interview rounds.Q4. Can inorder traversal be done without stack or recursion?Yes.Using Morris Traversal with:O(1)space.Bonus: Morris Traversal (Advanced)Morris Traversal performs inorder traversal without recursion or stack.ComplexityTime ComplexityO(N)Space ComplexityO(1)This is an advanced interview optimization.ConclusionLeetCode 94 is one of the most fundamental tree traversal problems.It teaches:DFS traversalRecursionStack simulationBinary tree fundamentalsThe key inorder pattern is:Left → Root → RightMastering this problem builds a strong foundation for advanced tree interview questions like:BST validationTree iteratorsTree reconstructionMorris traversalKth smallest in BST

LeetCodeBinary Tree Inorder TraversalBinary TreeTree TraversalJavaDFSStackRecursionEasy

LeetCode 1306: Jump Game III – Java DFS & Graph Traversal Solution Explained

IntroductionLeetCode 1306 – Jump Game III is an interesting graph traversal problem that combines:Depth First Search (DFS)Breadth First Search (BFS)RecursionVisited trackingCycle detectionAt first glance, this problem looks like an array problem.But internally, it behaves exactly like a graph traversal problem where:Each index acts like a nodeEach jump acts like an edgeThis problem is commonly asked in coding interviews because it tests:Recursive thinkingGraph traversal intuitionAvoiding infinite loopsState trackingProblem Link🔗 https://leetcode.com/problems/jump-game-iii/Problem StatementYou are given:An array arrA starting index startFrom index i, you can jump:i + arr[i]ori - arr[i]Your goal is to determine whether you can reach any index having value:0ExampleInputarr = [4,2,3,0,3,1,2]start = 5OutputtrueExplanationPossible path:5 → 4 → 1 → 3At index:3Value becomes:0So answer is:trueUnderstanding the ProblemThink of every index as a graph node.From each node:index iwe have two possible edges:i + arr[i]andi - arr[i]The goal is simply:Can we reach any node containing value 0?Brute Force IntuitionA naive recursive solution would:Try both forward and backward jumpsContinue recursivelyStop when we find zeroWhy Brute Force FailsWithout tracking visited indices, recursion may enter infinite loops.Example:1 → 3 → 1 → 3 → 1...This creates cycles.So we must track visited nodes.DFS IntuitionWe perform DFS traversal from the starting index.At every index:Check boundariesCheck if already visitedCheck if value is zeroExplore both possible jumpsKey DFS ObservationEach index should only be visited once.Why?Because revisiting creates cycles and unnecessary computation.So we use:HashSet<Integer> visitedorboolean[] visitedRecursive DFS ApproachSteps1. Boundary CheckIf index goes outside array:return false2. Visited CheckIf already visited:return false3. Found ZeroIf current index contains:0Return:true4. Explore Both DirectionsTry:start + arr[start]andstart - arr[start]Java DFS Solutionclass Solution { public boolean solve(HashSet<Integer> zeroIndexes, HashSet<Integer> visited, int start, int[] arr) { if(start >= arr.length || start < 0) return false; if(visited.contains(start)) return false; visited.add(start); if(zeroIndexes.contains(start)) return true; return solve(zeroIndexes, visited, start + arr[start], arr) || solve(zeroIndexes, visited, start - arr[start], arr); } public boolean canReach(int[] arr, int start) { HashSet<Integer> visited = new HashSet<>(); HashSet<Integer> zeroIndexes = new HashSet<>(); for(int i = 0; i < arr.length; i++) { if(arr[i] == 0) { zeroIndexes.add(i); } } return solve(zeroIndexes, visited, start, arr); }}Simpler Optimized DFS SolutionWe actually do not need a separate set for zero indexes.We can directly check:arr[start] == 0Cleaner Java DFS Solutionclass Solution { public boolean dfs(int[] arr, boolean[] visited, int start) { if(start < 0 || start >= arr.length) return false; if(visited[start]) return false; if(arr[start] == 0) return true; visited[start] = true; return dfs(arr, visited, start + arr[start]) || dfs(arr, visited, start - arr[start]); } public boolean canReach(int[] arr, int start) { return dfs(arr, new boolean[arr.length], start); }}Dry RunInputarr = [4,2,3,0,3,1,2]start = 5Step 1Current index:5Value:1Possible jumps:5 + 1 = 65 - 1 = 4Step 2Visit index:4Value:3Possible jumps:4 + 3 = 7 (invalid)4 - 3 = 1Step 3Visit index:1Value:2Possible jumps:1 + 2 = 31 - 2 = -1 (invalid)Step 4Visit index:3Value:0Return:trueBFS ApproachThis problem can also be solved using BFS.Instead of recursion:Use queueExplore neighbors level by levelJava BFS Solutionclass Solution { public boolean canReach(int[] arr, int start) { Queue<Integer> queue = new LinkedList<>(); boolean[] visited = new boolean[arr.length]; queue.offer(start); while(!queue.isEmpty()) { int index = queue.poll(); if(index < 0 || index >= arr.length) continue; if(visited[index]) continue; if(arr[index] == 0) return true; visited[index] = true; queue.offer(index + arr[index]); queue.offer(index - arr[index]); } return false; }}Time Complexity AnalysisDFS ComplexityTime ComplexityO(N)Each index is visited at most once.Space ComplexityO(N)Due to recursion stack and visited array.BFS ComplexityTime ComplexityO(N)Space ComplexityO(N)DFS vs BFSApproachAdvantagesDisadvantagesDFSSimple recursive logicRecursion stackBFSIterative solutionQueue managementInterview ExplanationIn interviews, explain:This problem behaves like graph traversal where each index acts as a node and jumps act as edges. We use DFS or BFS with visited tracking to avoid infinite cycles.This demonstrates strong graph intuition.Common Mistakes1. Forgetting Visited TrackingThis causes infinite recursion.2. Missing Boundary ChecksAlways check:start < 0 || start >= arr.length3. Revisiting NodesAvoid processing already visited indices.FAQsQ1. Is this an array problem or graph problem?Internally it is a graph traversal problem.Q2. Which is better: DFS or BFS?Both are valid.DFS is usually simpler for this problem.Q3. Why do we need visited tracking?To avoid infinite loops caused by cycles.Q4. Can this be solved greedily?No.Because multiple paths must be explored.ConclusionLeetCode 1306 is an excellent beginner-friendly graph traversal problem.It teaches:DFS traversalBFS traversalCycle detectionRecursive thinkingVisited state managementThe most important insight is:Treat every index as a graph node.Once you understand this idea, many graph and traversal interview problems become much easier.

LeetCodeMediumDFSBFSGraph TraversalJavaRecursion

LeetCode 145: Binary Tree Postorder Traversal – Java Recursive & Iterative Solution Explained

IntroductionLeetCode 145 – Binary Tree Postorder Traversal is one of the most important tree traversal problems for beginners learning Data Structures and Algorithms.This problem teaches:Binary Tree TraversalDepth First Search (DFS)RecursionStack-based traversalTree traversal patternsPostorder traversal is extremely useful in advanced tree problems such as:Tree deletionExpression tree evaluationBottom-up computationsDynamic programming on treesProblem Link🔗 https://leetcode.com/problems/binary-tree-postorder-traversal/Problem StatementGiven the root of a binary tree, return the postorder traversal of its nodes' values.What is Postorder Traversal?In postorder traversal, nodes are visited in this order:Left → Right → RootUnlike preorder or inorder traversal, the root node is processed at the end.ExampleInputroot = [1,null,2,3]Tree Structure:1\2/3Postorder TraversalTraversal order:3 → 2 → 1Output:[3,2,1]Recursive Approach (Most Common)IntuitionIn postorder traversal:Traverse left subtreeTraverse right subtreeVisit current nodeThis naturally fits recursion because trees themselves are recursive structures.Recursive DFS VisualizationTraversal pattern:Left → Right → RootRecursive function:postorder(node.left)postorder(node.right)visit(node)Java Recursive Solution/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* }*/class Solution {public void solve(List<Integer> list, TreeNode root) {if(root == null) return;solve(list, root.left);solve(list, root.right);list.add(root.val);}public List<Integer> postorderTraversal(TreeNode root) {List<Integer> list = new ArrayList<>();solve(list, root);return list;}}Dry Run – Recursive ApproachTree:1\2/3Step 1Start at:1Move left:nullReturn back.Step 2Move right to:2Move left to:3Left and right of 3 are null.Add:3Step 3Return to:2Add:2Step 4Return to:1Add:1Final Answer[3,2,1]Time Complexity – RecursiveTime ComplexityO(N)Every node is visited once.Space ComplexityO(H)Where:H = height of the treeRecursive call stack uses extra spaceWorst case:O(N)for skewed trees.Iterative Approach (Interview Follow-Up)The follow-up asks:Can you solve it iteratively?Yes.We use stacks to simulate recursion.Iterative Postorder IntuitionPostorder traversal order is:Left → Right → RootOne common trick is:Traverse in modified preorder:Root → Right → LeftReverse the result.After reversing, we get:Left → Right → Rootwhich is postorder traversal.Stack-Based Iterative LogicAlgorithmPush root into stack.Pop node.Add node value to answer.Push left child.Push right child.Reverse final answer.Java Iterative Solutionclass Solution {public List<Integer> postorderTraversal(TreeNode root) {LinkedList<Integer> ans = new LinkedList<>();if(root == null) return ans;Stack<TreeNode> stack = new Stack<>();stack.push(root);while(!stack.isEmpty()) {TreeNode node = stack.pop();ans.addFirst(node.val);if(node.left != null) {stack.push(node.left);}if(node.right != null) {stack.push(node.right);}}return ans;}}Dry Run – Iterative ApproachTree:1\2/3Step 1Push:1Step 2Pop:1Add at front:[1]Push right child:2Step 3Pop:2Add at front:[2,1]Push left child:3Step 4Pop:3Add at front:[3,2,1]Final Answer[3,2,1]Comparison of ApproachesApproachAdvantagesDisadvantagesRecursiveEasy to understandUses recursion stackIterativeBetter interview practiceSlightly harder logicInterview ExplanationIn interviews, explain:Postorder traversal processes nodes in Left → Right → Root order. Recursion naturally handles this traversal. Iteratively, we simulate recursion using a stack and reverse traversal order.This demonstrates strong tree traversal understanding.Common Mistakes1. Wrong Traversal OrderIncorrect:Root → Left → RightThat is preorder traversal.Correct postorder:Left → Right → Root2. Forgetting Null Base CaseAlways check:if(root == null) return;3. Incorrect Stack Push OrderFor iterative solution:Push left firstPush right secondbecause we reverse the result later.FAQsQ1. Why is postorder traversal useful?It is used in:Tree deletionExpression tree evaluationBottom-up dynamic programmingCalculating subtree informationQ2. Which approach is preferred in interviews?Recursive is simpler.Iterative is often asked as a follow-up.Q3. Can postorder traversal be done without stack or recursion?Yes.Using Morris Traversal.Q4. What is the difference between preorder, inorder, and postorder?TraversalOrderPreorderRoot → Left → RightInorderLeft → Root → RightPostorderLeft → Right → RootBonus: Morris Postorder TraversalMorris traversal performs tree traversal using:O(1)extra space.This is considered an advanced interview topic.ConclusionLeetCode 145 is an excellent beginner-friendly tree traversal problem.It teaches:DFS traversalRecursionStack simulationBinary tree fundamentalsThe key postorder pattern is:Left → Right → RootMastering this traversal helps in solving many advanced tree problems such as:Tree DPTree deletionExpression evaluationSubtree calculationsAdvanced DFS problems

LeetCodeBinary Tree Postorder TraversalBinary TreeTree TraversalJavaDFSStackRecursionEasy

LeetCode 154: Find Minimum in Rotated Sorted Array II – Java Binary Search Solution Explained

IntroductionLeetCode 154 – Find Minimum in Rotated Sorted Array II is a classic binary search interview problem.This problem is an advanced version of:Find Minimum in Rotated Sorted ArrayThe major difference is:The array may contain duplicates.That small change makes the problem much harder because duplicates can break normal binary search logic.This problem teaches:Modified binary searchRotated array conceptsHandling duplicatesEdge case optimizationInterview problem-solving techniquesProblem Link🔗 ProblemLeetCode 154: Find Minimum in Rotated Sorted Array IIOfficial Problem: LeetCode Problem LinkProblem StatementAn ascending sorted array is rotated between 1 and n times.Example:[0,1,4,4,5,6,7]may become:[4,5,6,7,0,1,4]or[0,1,4,4,5,6,7]Given the rotated sorted array nums that may contain duplicates, return the minimum element.ExampleExample 1Input:nums = [1,3,5]Output:1Example 2Input:nums = [2,2,2,0,1]Output:0Understanding Rotated Sorted ArraysNormally a sorted array looks like:[1,2,3,4,5]After rotation:[4,5,1,2,3]The minimum element becomes the pivot point.Our goal is to efficiently find this pivot.Brute Force ApproachIntuitionTraverse the entire array and keep track of the smallest element.AlgorithmInitialize minimum as first element.Traverse the array.Update minimum whenever a smaller element appears.Return minimum.Java Code – Brute Forceclass Solution { public int findMin(int[] nums) { int min = nums[0]; for(int num : nums) { min = Math.min(min, num); } return min; }}Dry Run – Brute ForceInput:[2,2,2,0,1]Traversal:ElementMinimum2222220010Final answer:0Complexity Analysis – Brute ForceTime ComplexityO(N)Space ComplexityO(1)Can We Do Better?Yes.Since the array is sorted and rotated, we can use Binary Search.However, duplicates make the problem tricky.Binary Search IntuitionIn a rotated sorted array:One half is always sorted.The minimum lies in the unsorted half.Without duplicates, binary search becomes straightforward.But duplicates create ambiguity.Example:[2,2,2,0,2]If:nums[mid] == nums[right]we cannot determine which side contains the minimum.So we shrink the search space carefully.Key Binary Search ObservationsCase 1If:nums[mid]<nums[right]nums[mid] < nums[right]nums[mid]<nums[right]then the right half is sorted, and minimum may lie at mid or left side.Move:right = midCase 2If:nums[mid]>nums[right]nums[mid] > nums[right]nums[mid]>nums[right]then minimum lies in the right half.Move:left = mid + 1Case 3If:nums[mid]=nums[right]nums[mid] = nums[right]nums[mid]=nums[right]we cannot identify the correct side.Safely reduce search space:right--Optimized Binary Search ApproachStepsInitialize two pointers:leftrightFind middle element.Compare nums[mid] with nums[right].Narrow the search space accordingly.Continue until pointers meet.Java Binary Search Solutionclass Solution { public int findMin(int[] nums) { if(nums.length == 1) return nums[0]; int left = 0; int right = nums.length - 1; int min = Integer.MAX_VALUE; while(left <= right) { int mid = left + (right - left) / 2; if(nums[mid] < nums[right]) { right = mid; min = Math.min(min, nums[right]); } else if(nums[mid] > nums[right]) { min = Math.min(min, nums[right]); left = mid + 1; } else { right--; } min = Math.min(min, nums[mid]); } return min; }}Dry Run – Binary SearchInputnums = [2,2,2,0,1]Initial StateLeftRight04Iteration 1Midmid = 2Value:nums[mid] = 2nums[right] = 1Since:2>12 > 12>1Move:left = mid + 1Now:LeftRight34Iteration 2Midmid = 3Value:nums[mid] = 0nums[right] = 1Since:0<10 < 10<1Move:right = midNow:LeftRight33Final Answer0Time Complexity AnalysisAverage CaseO(log N)Worst CaseDue to duplicates:O(N)Why Worst Case Becomes O(N)Consider:[1,1,1,1,1]Every comparison becomes:nums[mid] == nums[right]We can only shrink by one element:right--This degrades binary search to linear complexity.Interview ExplanationIn interviews, explain:Duplicates destroy the ability to always determine the sorted half uniquely. When nums[mid] == nums[right], we cannot confidently eliminate one side, so we reduce the search space by one element.This is the key insight interviewers look for.Common Mistakes1. Using Standard Binary Search LogicStandard rotated-array logic fails with duplicates.2. Ignoring Duplicate CaseThis condition is essential:else { right--;}3. Infinite Loop ErrorsAlways update pointers carefully.Alternative Simpler Binary SearchA cleaner version:class Solution { public int findMin(int[] nums) { int left = 0; int right = nums.length - 1; while(left < right) { int mid = left + (right - left) / 2; if(nums[mid] < nums[right]) { right = mid; } else if(nums[mid] > nums[right]) { left = mid + 1; } else { right--; } } return nums[left]; }}This is the most common interview solution.FAQsQ1. Why does binary search become O(N)?Duplicates prevent us from discarding half the search space confidently.Q2. Why compare with nums[right]?It helps identify whether the minimum lies on the left or right side.Q3. Is this problem important for interviews?Yes.It is a very popular advanced binary search interview problem.ConclusionLeetCode 154 is an excellent problem for mastering:Modified binary searchRotated sorted arraysDuplicate handlingSearch optimizationThe key challenge is handling:nums[mid]=nums[right]nums[mid] = nums[right]nums[mid]=nums[right]correctly.Once you understand this pattern, many advanced binary search interview problems become much easier.

HardBinary SearchRotated Sorted ArrayJavaLeetCode

LeetCode 110: Balanced Binary Tree – Java Optimized DFS Solution Explained

IntroductionLeetCode 110 – Balanced Binary Tree is one of the most important binary tree interview problems.This problem teaches:Tree recursionHeight calculationDepth First Search (DFS)Bottom-up recursionOptimization techniquesIt is frequently asked in coding interviews because it checks whether you can:Traverse trees efficientlyAvoid repeated calculationsCombine recursion with conditionsOptimize brute force tree solutionsThis problem is also a foundation for advanced tree problems like:AVL TreesHeight-balanced treesDiameter of Binary TreeTree DP problemsProblem Link🔗 https://leetcode.com/problems/balanced-binary-tree/Problem StatementGiven the root of a binary tree:Return:trueif the tree is:height-balancedOtherwise return:falseWhat is a Balanced Binary Tree?A binary tree is balanced if:For every node,|height(left subtree) - height(right subtree)| <= 1Meaning:Left and right subtree heights should not differ by more than:1Example 1Inputroot = [3,9,20,null,null,15,7]Tree:3/ \9 20/ \15 7OutputtrueExplanation:Every node satisfies:height difference <= 1Example 2Inputroot = [1,2,2,3,3,null,null,4,4]Tree:1/ \2 2/ \3 3/ \4 4OutputfalseExplanation:Left subtree becomes much deeper than right subtree.Difference becomes greater than:1Key ObservationTo determine if tree is balanced:At every node we need:Height of left subtreeHeight of right subtreeCompare differenceThis naturally becomes a recursive DFS problem.Brute Force ApproachIntuitionFor every node:Calculate left heightCalculate right heightCompare differenceRecursively check childrenBrute Force Java Solutionclass Solution {public int height(TreeNode root) {if(root == null)return 0;return 1 + Math.max(height(root.left), height(root.right));}public boolean isBalanced(TreeNode root) {if(root == null)return true;int left = height(root.left);int right = height(root.right);if(Math.abs(left - right) > 1)return false;return isBalanced(root.left) && isBalanced(root.right);}}Problem with Brute ForceThe height function gets called repeatedly.For every node:Heights are recalculated again and again.This increases complexity significantly.Brute Force ComplexityTime ComplexityO(N²)because height calculation repeats.Space ComplexityO(H)for recursion stack.Optimized DFS ApproachInstead of:Calculating heights separatelyWe can:Calculate height and balance together.Core Optimization IdeaWhile calculating height:If subtree becomes unbalanced:Return negative value immediatelyThis avoids unnecessary computation.Optimized Java Solutionclass Solution {public int solve(TreeNode roo) {if(roo == null)return 0;int left = solve(roo.left);if(left < 0) {return -1;}int right = solve(roo.right);if(right < 0) {return -1;}if(Math.abs(left - right) > 1) {return -1000;}return 1 + Math.max(left, right);}public boolean isBalanced(TreeNode root) {int ans = solve(root);return ans < 0 ? false : true;}}Cleaner Optimized VersionWe can simplify negative returns using:-1consistently.Cleaner Java Solutionclass Solution {public int height(TreeNode root) {if(root == null)return 0;int left = height(root.left);if(left == -1)return -1;int right = height(root.right);if(right == -1)return -1;if(Math.abs(left - right) > 1)return -1;return 1 + Math.max(left, right);}public boolean isBalanced(TreeNode root) {return height(root) != -1;}}Why This WorksAt every node:Recursively calculate left heightRecursively calculate right heightIf difference > 1:Tree is unbalancedPropagate failure upward immediately.Dry RunInput1/ \2 2/ \3 3/ \4 4Step 1Start from leaf nodes:4 → height = 1Step 2Node:3gets:left = 1right = 1Difference:0Balanced.Height:2Step 3At node:2Left height:2Right height:0Difference:2Unbalanced.Return:-1Final ResultTree is:Not balancedReturn:falseTime Complexity AnalysisOptimized DFS SolutionTime ComplexityO(N)because every node is visited once.Space ComplexityO(H)where:H = height of treeWorst case:O(N)for skewed tree.Brute Force vs OptimizedApproachTime ComplexitySpace ComplexityBrute ForceO(N²)O(H)Optimized DFSO(N)O(H)Interview ExplanationIn interviews, explain:Instead of recalculating heights repeatedly, we combine height calculation and balance checking into a single DFS traversal.This demonstrates:Optimization skillsRecursive DFS understandingBottom-up tree processingCommon Mistakes1. Recalculating Heights RepeatedlyThis causes:O(N²)complexity.2. Forgetting Absolute DifferenceAlways use:Math.abs(left - right)3. Not Handling Null NodesBase case:if(root == null)return 0;is necessary.FAQsQ1. What is a balanced binary tree?A tree where left and right subtree heights differ by at most:1for every node.Q2. Why use DFS?Because height calculation naturally follows recursive depth traversal.Q3. Why return -1?It acts as a signal:Subtree already unbalancedQ4. Is this problem important for interviews?Very important.It is one of the most common tree optimization questions.ConclusionLeetCode 110 is an excellent binary tree optimization problem.It teaches:DFS traversalHeight calculationBottom-up recursionOptimization techniquesThe key insight is:Combine balance checking and height calculation in one DFS traversal.Once you understand this optimization pattern, many advanced tree problems become much easier.

LeetCodeBalanced Binary TreeJavaBinary TreeDFSTree HeightRecursionTree

LeetCode 102: Binary Tree Level Order Traversal – Java BFS Solution Explained

IntroductionLeetCode 102 – Binary Tree Level Order Traversal is one of the most important Binary Tree traversal problems for coding interviews.This problem introduces:Breadth First Search (BFS)Queue data structureLevel-by-level traversalTree traversal patternsInterview-level BFS thinkingUnlike DFS traversals like preorder, inorder, and postorder, this problem explores the tree level by level.This traversal is widely used in:Graph traversalShortest path problemsTree serializationZigzag traversalBFS-based interview questionsProblem Link🔗 https://leetcode.com/problems/binary-tree-level-order-traversal/Problem StatementGiven the root of a binary tree, return the level order traversal of its nodes' values.Traversal should happen:Level by levelLeft to rightExampleInputroot = [3,9,20,null,null,15,7]Tree Structure: 3 / \ 9 20 / \ 15 7Level Order TraversalLevel 1:[3]Level 2:[9,20]Level 3:[15,7]Final Output:[[3],[9,20],[15,7]]Understanding the ProblemThe main challenge is:Process nodes level by level.This is exactly what:Breadth First Search (BFS)is designed for.Why Queue is Used?A queue follows:First In First Out (FIFO)This ensures:Nodes are processed in insertion orderParent nodes are processed before child nodesLevels are traversed correctlyBrute Force IntuitionOne brute force idea is:Calculate height of treeTraverse each level separatelyStore nodes level by levelBrute Force ComplexityThis approach becomes inefficient because:Each level traversal may revisit nodesComplexity may become:O(N²)for skewed trees.Optimal BFS IntuitionInstead of traversing each level separately:Use a queueProcess nodes level by level naturallyAt every level:Store queue sizeProcess exactly those many nodesAdd children into queueMove to next levelKey BFS ObservationBefore processing a level:int size = queue.size();This tells us:How many nodes belong to the current level.BFS AlgorithmSteps1. Initialize QueueInsert root node.2. Process Until Queue Becomes EmptyWhile queue is not empty:Find current level sizeTraverse current levelStore valuesPush child nodes3. Store Current LevelAfter processing one level:ans.add(levelList);Java BFS Solution/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * } */class Solution { public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> ans = new ArrayList<>(); Queue<TreeNode> queue = new LinkedList<>(); if(root == null) return ans; queue.offer(root); while(!queue.isEmpty()) { int size = queue.size(); List<Integer> level = new ArrayList<>(); for(int i = 0; i < size; i++) { root = queue.poll(); level.add(root.val); if(root.left != null) queue.offer(root.left); if(root.right != null) queue.offer(root.right); } ans.add(level); } return ans; }}Dry RunInputroot = [3,9,20,null,null,15,7]Tree: 3 / \ 9 20 / \ 15 7Initial Queue[3]Level 1Queue size:1Process:3Add children:9, 20Level result:[3]Queue now:[9,20]Level 2Queue size:2Process:9, 20Add children:15, 7Level result:[9,20]Queue now:[15,7]Level 3Queue size:2Process:15, 7Level result:[15,7]Queue becomes empty.Final Answer[[3],[9,20],[15,7]]Time Complexity AnalysisTime ComplexityO(N)Every node is visited exactly once.Space ComplexityO(N)Queue may store an entire level of nodes.DFS Alternative ApproachThis problem can also be solved using DFS recursion.Idea:Pass current level during recursionCreate new list when level appears first timeAdd node into correct level listJava DFS Solutionclass Solution { public void dfs(TreeNode root, int level, List<List<Integer>> ans) { if(root == null) return; if(level == ans.size()) { ans.add(new ArrayList<>()); } ans.get(level).add(root.val); dfs(root.left, level + 1, ans); dfs(root.right, level + 1, ans); } public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> ans = new ArrayList<>(); dfs(root, 0, ans); return ans; }}BFS vs DFS for Level Order TraversalApproachAdvantagesDisadvantagesBFSNatural level traversalUses queueDFSRecursive solutionSlightly harder intuitionInterview ExplanationIn interviews, explain:Level order traversal is a BFS problem because we process nodes level by level. A queue naturally supports this traversal order.This demonstrates strong BFS understanding.Common Mistakes1. Forgetting Queue SizeWithout storing:int size = queue.size();levels cannot be separated correctly.2. Using DFS IncorrectlySimple DFS alone does not guarantee level ordering.3. Forgetting Null CheckAlways handle:if(root == null)FAQsQ1. Why is BFS preferred here?Because BFS naturally processes nodes level by level.Q2. Can this problem be solved recursively?Yes.Using DFS with level tracking.Q3. What data structure is mainly used?Queue.Q4. Is Level Order Traversal important?Yes.It is one of the most frequently asked BFS tree problems.Related ProblemsAfter mastering this problem, practice:Binary Tree Zigzag Level Order TraversalAverage of Levels in Binary TreeRight Side View of Binary TreeBinary Tree Vertical Order TraversalMaximum Depth of Binary TreeConclusionLeetCode 102 is one of the most important BFS tree traversal problems.It teaches:BFS traversalQueue usageLevel-by-level processingTree traversal fundamentalsThe key idea is:Use queue size to separate levels.Once this intuition becomes clear, many BFS-based tree interview problems become much easier.

LeetCodeBinary Tree Level Order TraversalBFSQueueBinary TreeJavaTree TraversalMedium

LeetCode 144: Binary Tree Preorder Traversal – Java Recursive & Iterative Solution Explained

IntroductionLeetCode 144 – Binary Tree Preorder Traversal is one of the most important beginner-friendly tree traversal problems in Data Structures and Algorithms.This problem helps you understand:Binary Tree TraversalDepth First Search (DFS)RecursionStack-based traversalTree traversal patternsPreorder traversal is widely used in:Tree copyingSerializationExpression treesDFS-based problemsHierarchical data processingIt is also one of the most commonly asked tree problems in coding interviews.Problem Link🔗 ProblemLeetCode 144: Binary Tree Preorder TraversalOfficial Problem:LeetCode Problem LinkProblem StatementGiven the root of a binary tree, return the preorder traversal of its nodes' values.What is Preorder Traversal?In preorder traversal, nodes are visited in this order:Root → Left → RightThe root node is processed first before traversing subtrees.ExampleInputroot = [1,null,2,3]Tree Structure:1\2/3Preorder TraversalTraversal order:1 → 2 → 3Output:[1,2,3]Recursive Approach (Most Common)IntuitionIn preorder traversal:Visit current nodeTraverse left subtreeTraverse right subtreeThis naturally fits recursion because trees themselves are recursive structures.Recursive DFS VisualizationTraversal pattern:Root → Left → RightRecursive function:visit(node)preorder(node.left)preorder(node.right)Java Recursive Solution/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* }*/class Solution {public void solve(List<Integer> list, TreeNode root) {if(root == null) return;list.add(root.val);solve(list, root.left);solve(list, root.right);}public List<Integer> preorderTraversal(TreeNode root) {List<Integer> list = new ArrayList<>();solve(list, root);return list;}}Dry Run – Recursive ApproachTree:1\2/3Step 1Start at:1Add:1Move right to:2Step 2Add:2Move left to:3Step 3Add:3Final Answer[1,2,3]Time Complexity – RecursiveTime ComplexityO(N)Every node is visited once.Space ComplexityO(H)Where:H = height of treeRecursive call stack uses extra spaceWorst case:O(N)for skewed trees.Iterative Approach (Interview Follow-Up)The follow-up asks:Can you solve it iteratively?Yes.We use a stack to simulate recursion.Iterative Preorder IntuitionPreorder traversal order is:Root → Left → RightUsing a stack:Process current node immediatelyPush right child firstPush left child secondWhy?Because stacks follow:Last In First Out (LIFO)So left subtree gets processed first.Stack-Based Iterative LogicAlgorithmPush root into stack.Pop node.Add node value.Push right child.Push left child.Repeat until stack becomes empty.Java Iterative Solutionclass Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> ans = new ArrayList<>();if(root == null) return ans;Stack<TreeNode> stack = new Stack<>();stack.push(root);while(!stack.isEmpty()) {TreeNode node = stack.pop();ans.add(node.val);if(node.right != null) {stack.push(node.right);}if(node.left != null) {stack.push(node.left);}}return ans;}}Dry Run – Iterative ApproachTree:1\2/3Step 1Push:1Step 2Pop:1Add:[1]Push right child:2Step 3Pop:2Add:[1,2]Push left child:3Step 4Pop:3Add:[1,2,3]Final Answer[1,2,3]Comparison of ApproachesApproachAdvantagesDisadvantagesRecursiveEasy to understandUses recursion stackIterativeBetter interview practiceSlightly harder logicInterview ExplanationIn interviews, explain:Preorder traversal processes nodes in Root → Left → Right order. Recursion naturally handles this traversal. Iteratively, we use a stack and push the right child before the left child so the left subtree gets processed first.This demonstrates strong DFS and stack understanding.Common Mistakes1. Wrong Traversal OrderIncorrect:Left → Root → RightThat is inorder traversal.Correct preorder:Root → Left → Right2. Forgetting Null Base CaseAlways check:if(root == null) return;3. Wrong Stack Push OrderFor iterative traversal:Push right firstPush left secondOtherwise traversal order becomes incorrect.FAQsQ1. Why is preorder traversal useful?It is heavily used in:Tree cloningSerializationDFS traversalExpression treesQ2. Which approach is preferred in interviews?Recursive is simpler.Iterative is often asked as a follow-up.Q3. Can preorder traversal be done without stack or recursion?Yes.Using Morris Traversal.Q4. What is the difference between preorder, inorder, and postorder?TraversalOrderPreorderRoot → Left → RightInorderLeft → Root → RightPostorderLeft → Right → RootBonus: Morris Preorder TraversalMorris traversal performs preorder traversal using:O(1)extra space.This is considered an advanced interview topic.ConclusionLeetCode 144 is one of the most fundamental binary tree traversal problems.It teaches:DFS traversalRecursionStack simulationBinary tree fundamentalsThe key preorder pattern is:Root → Left → RightMastering this traversal builds a strong foundation for advanced tree problems such as:Tree serializationDFS-based problemsTree reconstructionExpression treesMorris traversal

LeetCodeBinary Tree Preorder TraversalBinary TreeTree TraversalJavaDFSStackRecursionEasy

Subsets Problem (LeetCode 78) Explained | Recursion, Iterative & Bit Manipulation

IntroductionThe Subsets problem (LeetCode 78) is one of the most fundamental and frequently asked questions in coding interviews. It introduces the concept of generating a power set, which is a core idea in recursion, backtracking, and combinatorics.Mastering this problem helps in solving a wide range of advanced problems like combinations, permutations, and decision-based recursion.In this article, we will explore:Intuition behind subsetsRecursive (backtracking) approachIterative (loop-based) approachBit manipulation approachTime and space complexity analysisProblem StatementGiven an integer array nums of unique elements, return all possible subsets (the power set).Key PointsEach element can either be included or excludedNo duplicate subsetsReturn subsets in any orderExamplesExample 1Input:nums = [1, 2, 3]Output:[[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]Example 2Input:nums = [0]Output:[[], [0]]Key InsightFor each element, there are two choices:Include it OR Exclude itSo total subsets:2^nThis makes it a binary decision tree problem, very similar to:Permutation with SpacesBinary choices recursionBacktracking problemsApproach 1: Recursion + Backtracking (Most Important)IntuitionAt each index:Skip the elementInclude the elementBuild subsets step by step and backtrack.Java Code (With Explanation)import java.util.*;class Solution { List<List<Integer>> liss = new ArrayList<>(); void solve(int[] an, int ind, List<Integer> lis) { // Base case: reached end → one subset formed if (ind == an.length) { liss.add(new ArrayList<>(lis)); // store copy return; } // Choice 1: Do NOT include current element solve(an, ind + 1, lis); // Choice 2: Include current element lis.add(an[ind]); solve(an, ind + 1, lis); // Backtrack: remove last added element lis.remove(lis.size() - 1); } public List<List<Integer>> subsets(int[] nums) { List<Integer> lis = new ArrayList<>(); solve(nums, 0, lis); return liss; }}Dry Run (nums = [1,2])Start: [] → skip 1 → [] → skip 2 → [] → take 2 → [2] → take 1 → [1] → skip 2 → [1] → take 2 → [1,2]Final Output:[], [2], [1], [1,2]Approach 2: Iterative (Loop-Based)IntuitionStart with an empty subset:[ [] ]For each element:Add it to all existing subsetsCodeimport java.util.*;class Solution { public List<List<Integer>> subsets(int[] nums) { List<List<Integer>> result = new ArrayList<>(); result.add(new ArrayList<>()); for (int num : nums) { int size = result.size(); for (int i = 0; i < size; i++) { List<Integer> temp = new ArrayList<>(result.get(i)); temp.add(num); result.add(temp); } } return result; }}How It WorksFor [1,2,3]:Start: [[]]Add 1 → [[], [1]]Add 2 → [[], [1], [2], [1,2]]Add 3 → [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]Approach 3: Bit ManipulationIntuitionEach subset can be represented using a binary number:For n = 3:000 → []001 → [1]010 → [2]011 → [1,2]...Codeimport java.util.*;class Solution { public List<List<Integer>> subsets(int[] nums) { List<List<Integer>> result = new ArrayList<>(); int n = nums.length; int total = 1 << n; // 2^n for (int i = 0; i < total; i++) { List<Integer> subset = new ArrayList<>(); for (int j = 0; j < n; j++) { if ((i & (1 << j)) != 0) { subset.add(nums[j]); } } result.add(subset); } return result; }}Complexity AnalysisApproachTime ComplexitySpace ComplexityRecursionO(2^n)O(n) stackIterativeO(2^n)O(2^n)Bit ManipulationO(2^n)O(2^n)Why All Approaches Are O(2ⁿ)Because:Total subsets = 2ⁿEach subset takes up to O(n) to constructWhen to Use Which ApproachRecursion / Backtracking → Best for interviews (easy to explain)Iterative → Clean and beginner-friendlyBit Manipulation → Best for optimization & advanced understandingKey TakeawaysSubsets = power set problemEvery element → 2 choicesThink in terms of decision treesBacktracking = build + undo (add/remove)Common Interview VariationsSubsets with duplicatesCombination sumPermutationsK-sized subsetsConclusionThe Subsets problem is a foundational DSA concept that appears across many interview questions. Understanding all approaches—especially recursion and iterative expansion—gives a strong base for solving complex backtracking problems.If you master this pattern, you unlock a whole category of problems in recursion and combinatorics.Frequently Asked Questions (FAQs)1. Why are there 2ⁿ subsets?Because each element has 2 choices: include or exclude.2. Which approach is best for interviews?Recursion + backtracking is the most preferred.3. Is bit manipulation important?Yes, it helps in optimizing and understanding binary patterns.

LeetCodeMediumJavaRecursionBacktracking

LeetCode 290: Word Pattern – Multiple Ways to Verify Bijection Between Pattern Characters and Words

Try the ProblemYou can practice the problem here:https://leetcode.com/problems/word-pattern/Problem DescriptionYou are given:A string patternA string sThe string s consists of words separated by spaces.Your task is to determine whether s follows the same pattern defined by the string pattern.To follow the pattern, there must be a bijection between pattern characters and words.Understanding the Meaning of BijectionA bijection means a one-to-one relationship between two sets.For this problem it means:Every character in the pattern maps to exactly one word.Every word maps to exactly one pattern character.Two characters cannot map to the same word.Two words cannot map to the same character.This ensures the mapping is unique in both directions.Example WalkthroughExample 1Inputpattern = "abba"s = "dog cat cat dog"OutputtrueExplanationMapping:a → dogb → catPattern:a b b aWords:dog cat cat dogThe mapping is perfectly consistent.Example 2Inputpattern = "abba"s = "dog cat cat fish"OutputfalseExplanationThe last word "fish" breaks the pattern because "a" was already mapped to "dog".Example 3Inputpattern = "aaaa"s = "dog cat cat dog"OutputfalseExplanationPattern requires:a → same word every timeBut the words differ.Constraints1 <= pattern.length <= 300pattern contains lowercase English letters1 <= s.length <= 3000s contains lowercase letters and spaceswords are separated by a single spaceno leading or trailing spacesCore ObservationBefore applying any algorithm, we should verify one simple condition.If the number of pattern characters does not match the number of words, then the pattern cannot match.Example:pattern = "abba"s = "dog cat dog"Pattern length = 4Words = 3This automatically returns false.Thinking About Possible ApproachesWhile solving this problem, several strategies may come to mind:Use one HashMap to store pattern → word mapping and check duplicates manually.Use two HashMaps to enforce bijection from both directions.Track first occurrence indices of pattern characters and words.Compare mapping patterns using arrays or maps.Let’s explore these approaches one by one.Approach 1: Single HashMap (Your Solution)IdeaWe store mapping:pattern character → wordWhile iterating:If the character already exists in the map→ check if it maps to the same word.If it does not exist→ ensure that no other character already maps to that word.This ensures bijection.Java Implementationclass Solution { public boolean wordPattern(String pattern, String s) { String words[] = s.split(" "); // Length mismatch means impossible mapping if(pattern.length() != words.length) return false; HashMap<Character,String> mp = new HashMap<>(); for(int i = 0; i < words.length; i++){ char ch = pattern.charAt(i); if(mp.containsKey(ch)){ if(!mp.get(ch).equals(words[i])){ return false; } }else{ // Prevent two characters mapping to same word if(mp.containsValue(words[i])){ return false; } } mp.put(ch, words[i]); } return true; }}Time ComplexityO(n²)Because containsValue() can take O(n) time in worst case.Space ComplexityO(n)Approach 2: Two HashMaps (Cleaner Bijection Enforcement)IdeaInstead of checking containsValue, we maintain two maps.pattern → wordword → patternThis ensures bijection naturally.Java Implementationclass Solution { public boolean wordPattern(String pattern, String s) { String[] words = s.split(" "); if(pattern.length() != words.length) return false; HashMap<Character, String> map1 = new HashMap<>(); HashMap<String, Character> map2 = new HashMap<>(); for(int i = 0; i < pattern.length(); i++){ char ch = pattern.charAt(i); String word = words[i]; if(map1.containsKey(ch) && !map1.get(ch).equals(word)) return false; if(map2.containsKey(word) && map2.get(word) != ch) return false; map1.put(ch, word); map2.put(word, ch); } return true; }}Time ComplexityO(n)Because both maps allow constant-time lookups.Space ComplexityO(n)Approach 3: Index Mapping Technique (Elegant Trick)IdeaAnother clever technique is to compare first occurrence indices.Example:pattern = abbawords = dog cat cat dogPattern index sequence:a → 0b → 1b → 1a → 0Words index sequence:dog → 0cat → 1cat → 1dog → 0If the index sequences match, then the pattern holds.Java Implementationclass Solution { public boolean wordPattern(String pattern, String s) { String[] words = s.split(" "); if(pattern.length() != words.length) return false; HashMap<Character,Integer> map1 = new HashMap<>(); HashMap<String,Integer> map2 = new HashMap<>(); for(int i = 0; i < pattern.length(); i++){ char ch = pattern.charAt(i); String word = words[i]; if(!map1.getOrDefault(ch, -1) .equals(map2.getOrDefault(word, -1))){ return false; } map1.put(ch, i); map2.put(word, i); } return true; }}Time ComplexityO(n)Space ComplexityO(n)Comparison of ApproachesApproachTime ComplexitySpace ComplexityNotesSingle HashMapO(n²)O(n)Simple but slowerTwo HashMapsO(n)O(n)Cleaner bijection enforcementIndex MappingO(n)O(n)Elegant and interview-friendlyKey Interview InsightProblems like this test your understanding of:Bijection MappingSimilar problems include:Isomorphic StringsWord Pattern IISubstitution Cipher ProblemsUnderstanding how to enforce one-to-one mappings is a powerful technique.ConclusionThe Word Pattern problem is an excellent example of how HashMaps can enforce relationships between two datasets.While a simple HashMap solution works, more optimized methods like two-way mapping or index comparison provide cleaner and more efficient implementations.Mastering these techniques will help you solve many pattern-matching and mapping problems commonly asked in coding interviews.

HashMapString ManipulationBijection MappingTwo HashMapsIndex MappingLeetCode Easy

LeetCode 543: Diameter of Binary Tree – Java DFS Solution Explained

IntroductionLeetCode 543 – Diameter of Binary Tree is one of the most popular binary tree interview problems.This problem teaches:Depth First Search (DFS)Tree height calculationRecursive traversalBottom-up recursionTree optimization techniquesIt is extremely important because it introduces a very common pattern in tree problems:Use recursion to calculate subtree heights while simultaneously updating a global answer.This same idea is used in:Balanced Binary TreeMaximum Path SumLongest ZigZag PathTree DP problemsProblem Link🔗 https://leetcode.com/problems/diameter-of-binary-tree/Problem StatementGiven the root of a binary tree:Return:Length of the diameter of the treeThe diameter is:The length of the longest path between any two nodes in the tree.This path:May pass through the rootMay not pass through the rootImportant NoteThe diameter is measured in:EDGESnot nodes.Example 1Inputroot = [1,2,3,4,5]Tree: 1 / \ 2 3 / \ 4 5Output3Explanation:Longest path:4 → 2 → 1 → 3Edges count:3Example 2Inputroot = [1,2]Tree: 1 / 2Output:1Understanding DiameterAt every node:Possible longest path through that node is:left subtree height + right subtree heightWhy?Because:One side contributes left edgesOther side contributes right edgesTogether they form a path.Key ObservationFor every node:Diameter through node=leftHeight + rightHeightWe compute this for all nodes.Maximum among them becomes answer.Brute Force ApproachIntuitionFor every node:Calculate left subtree heightCalculate right subtree heightCompute diameterRecursively repeat for childrenBrute Force ComplexityHeight gets recalculated repeatedly.Time ComplexityO(N²)Space ComplexityO(H)where:H = tree heightOptimized DFS ApproachInstead of separately calculating:HeightDiameterWe calculate both in one DFS traversal.Core IdeaWhile calculating subtree height:We also update:max diameterThis avoids repeated traversal.Java Solutionclass Solution { int max = Integer.MIN_VALUE; public int solve(TreeNode roo) { if(roo == null) return 0; int left = solve(roo.left); int right = solve(roo.right); max = Math.max(max, left + right); return 1 + Math.max(left, right); } public int diameterOfBinaryTree(TreeNode root) { solve(root); return max; }}Cleaner Optimized Versionclass Solution { int diameter = 0; public int height(TreeNode root) { if(root == null) return 0; int left = height(root.left); int right = height(root.right); diameter = Math.max(diameter, left + right); return 1 + Math.max(left, right); } public int diameterOfBinaryTree(TreeNode root) { height(root); return diameter; }}Why This WorksAt every node:Find left subtree heightFind right subtree heightCompute:left + rightUpdate global maximum diameterReturn current subtree height upwardDry RunInput 1 / \ 2 3 / \ 4 5Step 1Leaf nodes:4 → height = 15 → height = 13 → height = 1Step 2At node:2Left height:1Right height:1Diameter through node:1 + 1 = 2Update:max = 2Height of node 2:2Step 3At root:1Left height:2Right height:1Diameter:2 + 1 = 3Update:max = 3Final Answer3Recursive Visualizationheight(1) ├── height(2) │ ├── height(4) │ └── height(5) │ └── height(3)Diameter gets updated during return phase.Time Complexity AnalysisOptimized DFS SolutionTime ComplexityO(N)because every node is visited once.Space ComplexityO(H)where:H = tree heightWorst case:O(N)for skewed tree.Brute Force vs OptimizedApproachTime ComplexitySpace ComplexityBrute ForceO(N²)O(H)Optimized DFSO(N)O(H)Interview ExplanationIn interviews, explain:While recursively calculating subtree heights, we simultaneously compute the maximum possible path passing through every node.This demonstrates:DFS understandingBottom-up recursionOptimization skillsTree DP thinkingCommon Mistakes1. Counting Nodes Instead of EdgesDiameter measures:edgesnot nodes.2. Forgetting Global VariableDiameter must be updated across all nodes.3. Returning Diameter Instead of HeightRecursive function should return:heightnot diameter.FAQsQ1. Does diameter always pass through root?No.It can exist completely inside a subtree.Q2. Why use DFS?Because height calculation naturally follows recursive depth traversal.Q3. Why update diameter globally?Because longest path may occur at any node.Q4. Is this problem important for interviews?Very important.It is one of the most common recursive tree questions.ConclusionLeetCode 543 is one of the best problems for learning recursive tree optimization.It teaches:DFS traversalHeight calculationBottom-up recursionGlobal answer trackingThe key insight is:Diameter through a node equals left subtree height + right subtree height.Once you understand this pattern, many advanced binary tree problems become much easier.

LeetCodeDiameter of Binary TreeJavaBinary TreeDFSTreeRecursionEasy

LeetCode 61 Rotate List Java Solution | Brute Force + Optimal Approach Explained (Linked List Rotation)

🚀 IntroductionThe Rotate List problem is a classic linked list question frequently asked in coding interviews.It tests your understanding of:linked list traversalpointer manipulationhandling large constraints efficiently👉 Try the problem yourself: https://leetcode.com/problems/rotate-list/🧠 IntuitionRotating a list means shifting elements to the right.Example:1 → 2 → 3 → 4 → 5, k = 2 → 4 → 5 → 1 → 2 → 3Instead of rotating one by one, we can:either simulate using extra spaceor optimize using pointer manipulation📘 Problem ExplanationYou are given:Head of a linked listInteger kReturn the list after rotating it k times to the right🧩 Approach 1: Brute Force (Array-Based)💡 IdeaStore values in arrayRotate indicesrebuild linked list💻 Java Codeclass Solution { public ListNode rotateRight(ListNode head, int k) { if(head == null) return head; int count = 0; ListNode curr= head; while(curr != null){ count++; curr = curr.next; } curr = head; int[] arr = new int[count]; for(int i =0; i <count;i++){ arr[i] = curr.val; curr = curr.next; } ListNode ans = new ListNode(-1); ListNode finAns = ans; k = k % count; for(int i = 0;i < arr.length;i++){ int ind =(i+(count-k))%arr.length; ans.next = new ListNode(arr[ind]); ans = ans.next; } return finAns.next; }}🔍 Dry Run (Brute Force)Input:[1,2,3,4,5], k = 2Array:[1,2,3,4,5]After rotation logic:[4,5,1,2,3]Rebuild list → ✅ Final Answer⏱️ ComplexityTypeValueTimeO(n)SpaceO(n)⚠️ DrawbackUses extra spaceNot optimal for large inputs⚡ Approach 2: Optimal (Circular Linked List)💡 IdeaInstead of rebuilding:convert list into circularbreak at correct position💻 Java Codeclass Solution { public ListNode rotateRight(ListNode head, int k) { if (head == null || head.next == null || k == 0) return head; int length = 1; ListNode curr = head; while (curr.next != null) { curr = curr.next; length++; } curr.next = head; k = k % length; int steps = length - k; ListNode newTail = curr; while (steps-- > 0) { newTail = newTail.next; } ListNode newHead = newTail.next; newTail.next = null; return newHead; }}🔍 Dry Run (Optimal)Input: [1,2,3,4,5], k = 2Length = 5k = 2Steps = 5 - 2 = 3Move 3 steps → new tail = 3new head = 4Final:4 → 5 → 1 → 2 → 3⏱️ ComplexityTypeValueTimeO(n)SpaceO(1)📊 ComparisonApproachTimeSpaceBest ForArray (Brute)O(n)O(n)BeginnersCircular (Optimal)O(n)O(1)Interviews📚 Related ProblemsSimilar PatternLinksReverse Linked ListProblem LinkLinked List CycleProblem LinkRemove Nth Node From EndProblem Link⚠️ Common MistakesForgetting k % lengthIncorrect pointer breakingNot handling single nodeOff-by-one in traversal🎯 Key Points to RememberAlways optimize kUse circular approach for best performanceUnderstand pointer movement carefully❓ FAQQ1: Why do we use k % length?Because rotating more than length gives same result.Q2: Which approach is better?Optimal circular linked list approach.Q3: Can we use array approach in interviews?Yes, but optimal is preferred.Q4: What is the key trick here?Convert linked list into circular structure.

Linked ListTwo PointerLeetCodeJavaMedium

LeetCode 2553: Separate the Digits in an Array – Java Solution Explained (2 Easy Approaches)

IntroductionIn coding interviews and competitive programming, many problems test how well you can manipulate numbers and arrays together. One such beginner-friendly problem is LeetCode 2553 – Separate the Digits in an Array.In this problem, we are given an integer array, and we need to separate every digit of every number while maintaining the original order.This problem is excellent for practicing:Array traversalDigit extractionReverse processingArrayList usage in JavaThinking about order preservationProblem Link🔗 ProblemLeetCode 2553: Separate the Digits in an ArrayProblem StatementGiven an array of positive integers nums, return an array containing all digits of each integer in the same order they appear.ExampleInput:nums = [13,25,83,77]Output:[1,3,2,5,8,3,7,7]IntuitionThe main challenge is:Extract digits from each numberPreserve the original left-to-right orderNormally, extracting digits using % 10 gives digits in reverse order.Example:83 → 3 → 8So we need a way to restore the correct order.Approach 1 – Using String ConversionIdeaConvert every number into a string and then traverse each character.This is the simplest and most beginner-friendly approach.AlgorithmTraverse every number in the array.Convert the number into a string.Traverse each character of the string.Convert character back to integer.Store digits into ArrayList.Convert ArrayList to array.Java Code – String Approachclass Solution { public int[] separateDigits(int[] nums) { ArrayList<Integer> list = new ArrayList<>(); for (int num : nums) { String str = String.valueOf(num); for (char ch : str.toCharArray()) { list.add(ch - '0'); } } int[] ans = new int[list.size()]; for (int i = 0; i < list.size(); i++) { ans[i] = list.get(i); } return ans; }}Dry Run (String Approach)Input:nums = [13,25]Step 113 → "13"Digits added:1, 3Step 225 → "25"Digits added:2, 5Final Array:[1,3,2,5]Time Complexity & Space ComplexityTime ComplexityO(N × D)Where:N = number of elementsD = number of digitsSpace ComplexityO(N × D)For storing digits.Approach 2 – Mathematical Digit Extraction (Optimal Without String)This is the approach you implemented in your code.Instead of converting numbers into strings, we extract digits mathematically using:digit = num % 10num = num / 10But digits come in reverse order.To fix this:Traverse the original array from back to frontStore extracted digitsReverse the final resultThis avoids string conversion completely.Intuition Behind Reverse TraversalSuppose:nums = [13,25]If we traverse from the end:25 → 5,213 → 3,1Stored list:[5,2,3,1]Now reverse the list:[1,3,2,5]Correct answer achieved.Java Code – Mathematical Approachclass Solution { public int[] separateDigits(int[] nums) { ArrayList<Integer> list = new ArrayList<>(); for (int i = nums.length - 1; i >= 0; i--) { if (nums[i] < 10) { list.add(nums[i]); } else { int val = nums[i]; while (val != 0) { int digit = val % 10; val = val / 10; list.add(digit); } } } int[] ans = new int[list.size()]; int k = 0; for (int i = list.size() - 1; i >= 0; i--) { ans[k++] = list.get(i); } return ans; }}Dry Run (Mathematical Approach)Input:nums = [13,25,83]Traverse from Back83Digits extracted:3, 8List:[3,8]25Digits extracted:5,2List:[3,8,5,2]13Digits extracted:3,1List:[3,8,5,2,3,1]Reverse Final List[1,3,2,5,8,3]Correct answer.Time Complexity Analysis & Space ComplexityTime ComplexityO(N × D)Because every digit is processed once.Space ComplexityO(N × D)For storing final digits.Which Approach is Better?ApproachAdvantagesDisadvantagesString ConversionEasy to understandUses extra string conversionMathematical ExtractionBetter DSA practiceSlightly harder logicInterview PerspectiveIn interviews:Beginners should first explain the string approach.Then discuss optimization using mathematical extraction.Interviewers like when candidates:Understand digit manipulationThink about order preservationCompare multiple approachesCommon Mistakes1. Forgetting Reverse OrderUsing % 10 extracts digits backward.Example:123 → 3,2,1You must reverse later.2. Not Handling Single Digit NumbersSingle digit numbers should directly be added.3. Character Conversion MistakeWrong:list.add(ch);Correct:list.add(ch - '0');Frequently Asked Questions (FAQs)Q1. Why do digits come in reverse order?Because % 10 always extracts the last digit first.Example:123 % 10 = 3Q2. Can we solve this without ArrayList?Yes, but ArrayList makes dynamic storage easier.Q3. Which approach is more optimal?Both have similar complexity.Mathematical extraction avoids string conversion and is preferred in interviews.Q4. Is this problem important for interviews?Yes. It teaches:Number manipulationOrder handlingArray traversalBasic optimization thinkingConclusionLeetCode 2553 is a simple yet valuable beginner problem for understanding:Digit extractionArray handlingReverse traversalOrder preservationYou learned two approaches:String Conversion ApproachMathematical Digit Extraction ApproachThe mathematical solution is especially useful because it strengthens core DSA concepts and improves problem-solving skills for interviews.If you're preparing for coding interviews in Java, this is a great problem to master before moving to harder digit manipulation questions.

ArrayEasyLeetcodeDigit ExtractionJava

LeetCode 1365: How Many Numbers Are Smaller Than the Current Number | Java Solution, Intuition, Dry Run & Complexity Analysis

IntroductionIn this problem, we are given an integer array nums.For every element in the array, we must calculate how many numbers are smaller than the current number.The result should be stored in another array where:Each index contains the count of smaller numbersComparison must be done against every other elementWe cannot count the element itselfThis is a beginner-friendly array problem that teaches comparison logic and nested loop thinking.Problem StatementGiven the array nums, return an array answer such that:answer[i] = count of numbers smaller than nums[i]Question LinkProblem Link -: Leetcode 1365ExampleInputnums = [8,1,2,2,3]Output[4,0,1,1,3]Explanation8 → four smaller numbers → 1,2,2,31 → no smaller number2 → one smaller number → 12 → one smaller number → 13 → three smaller numbers → 1,2,2Understanding the ProblemWe need to check:For every element:How many values in the array are smaller than it?This means:Compare one number with all other numbersCount valid smaller valuesStore count in answer arrayIntuitionThe simplest idea is:Pick one numberCompare it with every elementCount smaller numbersSave resultRepeat for all indicesSince constraints are small:nums.length <= 500Brute force works perfectly.ApproachWe use two loops:Outer loop → selects current numberInner loop → compares with all numbersIf:nums[j] < nums[i]Then increase count.Java Solutionclass Solution { public int[] smallerNumbersThanCurrent(int[] nums) { int i = 0; int j = 1; int ans[] = new int[nums.length]; int cou = 0; while(i < nums.length){ if(i != j && nums[i] > nums[j]){ cou++; } j++; if(j == nums.length){ ans[i] = cou; i++; cou = 0; j = 0; } } return ans; }}Code ExplanationVariablesiCurrent element index.jUsed for comparison.couStores count of smaller numbers.ans[]Final result array.Step-by-Step LogicStep 1Pick current number using:iStep 2Compare with every number using:jStep 3If another value is smaller:nums[i] > nums[j]Increase count.Step 4Store count.Step 5Move to next element.Dry RunInputnums = [8,1,2,2,3]First Element = 8Compare with:NumberSmaller?1Yes2Yes2Yes3YesCount = 4ans[0] = 4Second Element = 1No smaller number.ans[1] = 0Third Element = 2Smaller number:1Count = 1ans[2] = 1Final Answer[4,0,1,1,3]Time ComplexityWe compare every element with every other element.ComplexityO(N²)Because:Outer loop = NInner loop = NTotal:N × NSpace ComplexityWe only store output array.ComplexityO(N)Better Clean Version (Recommended)Your logic works, but interviewers usually prefer readable code.class Solution { public int[] smallerNumbersThanCurrent(int[] nums) { int n = nums.length; int[] ans = new int[n]; for(int i = 0; i < n; i++) { int count = 0; for(int j = 0; j < n; j++) { if(i != j && nums[j] < nums[i]) { count++; } } ans[i] = count; } return ans; }}Optimized ApproachSince:0 <= nums[i] <= 100We can use frequency counting.This gives:O(N + K)Where:N = array sizeK = range of valuesCommon Mistakes1. Comparing Same IndexWrong:nums[i] > nums[i]Correct:i != j2. Forgetting Reset CountWrong:count keeps increasingCorrect:count = 0after each iteration.3. Index Out Of BoundsAlways ensure:j < nums.lengthInterview TipsThis problem teaches:Nested loopsArray traversalCounting logicComparison problemsBrute force thinkingInterviewers may ask:Can you optimize it?Answer:Use counting sort or prefix frequency.FAQsIs this problem easy?Yes. It is beginner-friendly.Is brute force accepted?Yes.Constraints are small.Can we optimize?Yes.Using counting frequency array.Is this asked in interviews?Yes.Especially for beginners.Final ThoughtsLeetCode 1365 is a simple array problem that helps build strong fundamentals.You learn:How comparisons workHow nested loops solve counting problemsHow to convert logic into output arrays

LeetCodeEasyTwo PointerArrayJava

Reverse Vowels of a String – From Extra Space Approach to Two Pointer Optimization (LeetCode 345)

🔗 Problem LinkLeetCode 345 – Reverse Vowels of a String 👉 https://leetcode.com/problems/reverse-vowels-of-a-string/IntroductionThis problem is very similar to Reverse Only Letters, but with a small twist:Instead of reversing all letters, we only reverse the vowels.At first, we might think of extracting vowels, reversing them, and putting them back. That works — but it is not the most optimal approach.In this article, we’ll:Understand the brute-force style approach (your solution)Analyze its time complexityOptimize it using the Two Pointer patternCompare both approaches📌 Problem UnderstandingYou are given a string s.You must:Reverse only the vowelsKeep all other characters in the same positionVowels include:a, e, i, o, uA, E, I, O, UExample 1Input: "IceCreAm"Output: "AceCreIm"Vowels: ['I','e','e','A'] Reversed: ['A','e','e','I']Example 2Input: "leetcode"Output: "leotcede"🧠 Your First Approach – Extract, Reverse, ReplaceYour idea:Extract all vowels into a string.Store their indices.Reverse the vowel string.Replace vowels at stored indices.Let’s look at your code.💻 Your Code (Extract & Replace Method)class Solution { public String reverseVowels(String s) { String vow = ""; List<Integer> lis = new ArrayList<>(); HashMap<Integer,Character> mp = new HashMap<>(); for(int i =0;i<s.length();i++){ if(((s.charAt(i) == 'a') || (s.charAt(i) == 'e') || (s.charAt(i) == 'i') || (s.charAt(i) == 'o') || (s.charAt(i) == 'u') || (s.charAt(i) == 'A') || (s.charAt(i) == 'E') || (s.charAt(i) == 'I') || (s.charAt(i) == 'O') || (s.charAt(i) == 'U')) ){ vow += s.charAt(i); lis.add(i); } } String so = ""; for(int i = vow.length()-1; i >= 0; i--){ so += vow.charAt(i); } for(int i =0; i< lis.size();i++){ mp.put(lis.get(i), so.charAt(i)); } String ans = ""; for(int i =0 ; i< s.length();i++){ if(mp.containsKey(i)){ ans += mp.get(i); }else{ ans += s.charAt(i); } } return ans; }}🔍 How This WorksStep 1 – Extract VowelsStore:Vowel characters in vowTheir indices in lisStep 2 – Reverse the Vowel StringCreate new reversed string so.Step 3 – Map Indices to Reversed VowelsUse a HashMap to store:index → reversed vowelStep 4 – Build Final StringTraverse original string:If index in map → use reversed vowelElse → use original character⚠️ Problem with This ApproachAlthough correct, it has inefficiencies:String concatenation (+=) → O(n²) in worst caseExtra space used:Vowel stringList of indicesHashMapFinal answer stringTime Complexity: O(n²) (due to string concatenation) Space Complexity: O(n)We can do better.🚀 Optimized Approach – Two Pointers (Best Solution)Instead of extracting vowels separately, we can:Convert string into char arrayUse two pointersSwap vowels directlyThis avoids extra structures.💻 Optimized Two Pointer Solutionclass Solution { public String reverseVowels(String s) { int i = 0, j = s.length() - 1; char[] arr = s.toCharArray(); while(i < j){ if(!isVowel(arr[i])){ i++; } else if(!isVowel(arr[j])){ j--; } else{ char temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; i++; j--; } } return new String(arr); } private boolean isVowel(char c){ return c=='a'||c=='e'||c=='i'||c=='o'||c=='u'|| c=='A'||c=='E'||c=='I'||c=='O'||c=='U'; }}🎯 Why This WorksWe:Move left pointer until vowel foundMove right pointer until vowel foundSwapContinueNo extra storage needed.⏱ Complexity ComparisonYour ApproachTime: O(n²) (string concatenation)Space: O(n)Two Pointer ApproachTime: O(n)Space: O(n) (char array)Much cleaner and faster.🔥 Key LearningThis problem reinforces:Two pointer patternIn-place modificationAvoiding unnecessary extra spaceRecognizing optimization opportunitiesWhenever you see:"Reverse something but keep other elements fixed"Think:👉 Two Pointers🏁 Final ThoughtsYour approach shows strong logical thinking:Extract → Reverse → ReplaceThat’s a valid way to solve it.But the optimized two-pointer approach is more interview-friendly.If you master this pattern, you can easily solve:Reverse Only LettersReverse StringValid PalindromeRemove Duplicates from Sorted Array

Two PointersString ManipulationHashMapLeetCodeEasy

Remove Nth Node From End – The Smart Way to Solve in One Pass (LeetCode 19)

🚀 Try the ProblemPractice here:https://leetcode.com/problems/remove-nth-node-from-end-of-list/🤔 Let’s Think Differently…Imagine this list:1 → 2 → 3 → 4 → 5You are asked:👉 Remove the 2nd node from the endSo counting from end:5 (1st), 4 (2nd) ❌ remove thisFinal list:1 → 2 → 3 → 5🧠 Problem in Simple WordsYou are given:Head of a linked listA number n👉 Remove the nth node from the end👉 Return the updated list📦 Constraints1 <= number of nodes <= 300 <= Node.val <= 1001 <= n <= size of list🧩 First Thought (Counting Method)💡 IdeaCount total nodesFind position from start:position = total - nTraverse again and remove that node✅ Code (Counting Approach)class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { if(head == null) return head; // Step 1: Count nodes int co = 0; ListNode tempHead = head; while(tempHead != null){ co++; tempHead = tempHead.next; } // Step 2: If removing head if(co == n) return head.next; // Step 3: Find node before target int k = co - n; int con = 1; ListNode temp = head; while(con < k){ temp = temp.next; con++; } // Step 4: Remove node temp.next = temp.next.next; return head; }}⏱️ ComplexityTime ComplexityO(n) + O(n) = O(n)(two traversals)Space ComplexityO(1)⚠️ Limitation of This Approach👉 It requires two passesBut the problem asks:Can you solve it in one pass?🚀 Optimal Approach: Two Pointer Technique (One Pass)Now comes the interesting part 🔥🧠 Core IdeaWe use two pointers:fast pointerslow pointer🎯 Trick👉 Move fast pointer n steps aheadThen move both pointers together until:fast reaches endAt that moment:👉 slow will be at the node before the one to remove📌 Why This WorksBecause the gap between fast and slow is always n nodesSo when fast reaches end:👉 slow is exactly where we need it🔥 Step-by-Step VisualizationList:1 → 2 → 3 → 4 → 5n = 2Step 1: Move fast 2 stepsfast → 3slow → 1Step 2: Move both togetherfast → 4, slow → 2fast → 5, slow → 3fast → null, slow → 4👉 Now slow is at node before target🧼 Clean and Safe Approach (Using Dummy Node)Using dummy node avoids edge cases like removing head.💻 Code (Optimal One Pass Solution)class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { // Dummy node to handle edge cases ListNode dummy = new ListNode(0, head); ListNode fast = dummy; ListNode slow = dummy; // Move fast pointer n steps ahead for(int i = 0; i < n; i++){ fast = fast.next; } // Move both pointers while(fast.next != null){ fast = fast.next; slow = slow.next; } // Remove nth node slow.next = slow.next.next; return dummy.next; }}⏱️ ComplexityTime ComplexityO(n)(single pass)Space ComplexityO(1)⚖️ Comparing ApproachesApproachPassesTimeSpaceDifficultyCounting2O(n)O(1)EasyTwo Pointer1O(n)O(1)Optimal❌ Common MistakesForgetting to handle removing head nodeNot using dummy nodeOff-by-one errors in pointer movementMoving fast incorrectly🔥 Interview InsightThis problem is a classic example of:Fast & Slow Pointer TechniqueUsed in many problems like:Cycle DetectionMiddle of Linked ListPalindrome Linked List🧠 Final ThoughtAt first, counting feels natural…But once you learn this trick:"Create a gap and move together"👉 You unlock a powerful pattern.🚀 ConclusionThe Remove Nth Node From End problem is not just about deletion…It teaches:Efficient traversalPointer coordinationOne-pass optimization👉 Tip: Whenever you see “from end”, think:"Can I use two pointers with a gap?"That’s your shortcut to solving these problems like a pro 🚀

Linked ListTwo PointersFast & Slow PointerOne Pass AlgorithmLeetCodeMedium

Longest Palindrome – Building the Maximum Length from Given Letters (LeetCode 409)

🔗 Problem LinkLeetCode 409 – Longest Palindrome 👉 https://leetcode.com/problems/longest-palindrome/IntroductionThis is one of those problems where you don’t actually need to build the palindrome.You just need to calculate the maximum possible length of a palindrome that can be formed using the given characters.The key idea here is understanding:How palindromes are structured.Once you understand that, the solution becomes straightforward and elegant.📌 Problem UnderstandingYou are given a string s containing:Lowercase lettersUppercase lettersCase-sensitive (meaning 'A' and 'a' are different)You must return:The length of the longest palindrome that can be built using those characters.You can rearrange characters in any order.Example 1Input: s = "abccccdd"Output: 7One possible palindrome:dccaccdLength = 7Example 2Input: s = "a"Output: 1🧠 Key Observation About PalindromesA palindrome:Reads the same forward and backward.Has mirror symmetry.This means:Characters must appear in pairs.At most one character can appear an odd number of times (middle character).🧠 Intuition Behind the ApproachLet’s think step by step:Count frequency of each character.For every character:If frequency is even → use all of them.If frequency is odd → use (frequency - 1).If at least one odd frequency exists → we can place one odd character in the center.That’s it.This is a greedy approach.💻 Your Codeclass Solution { public int longestPalindrome(String s) { if(s.length() == 1) return 1; HashMap<Character,Integer> mp = new HashMap<>(); for(int i =0; i < s.length();i++){ mp.put(s.charAt(i),mp.getOrDefault(s.charAt(i),0)+1); } int len =0; boolean odd = false; for(int a : mp.values()){ if(a%2 == 0){ len+=a; }else{ len+=a-1; odd= true; } } if(odd){ return len+1; } return len; }}🔍 Step-by-Step Explanation1️⃣ Edge Caseif(s.length() == 1) return 1;If there is only one character, the answer is 1.2️⃣ Frequency CountingHashMap<Character,Integer> mp = new HashMap<>();for(int i =0; i < s.length();i++){ mp.put(s.charAt(i),mp.getOrDefault(s.charAt(i),0)+1);}We count how many times each character appears.3️⃣ Build the Palindrome Lengthint len = 0;boolean odd = false;len → stores palindrome lengthodd → tracks whether any odd frequency exists4️⃣ Process Each Frequencyfor(int a : mp.values()){ if(a % 2 == 0){ len += a; }else{ len += a - 1; odd = true; }}If frequency is even → use all characters.If odd:Use a - 1 (which is even)Keep track that we saw an odd number5️⃣ Add Middle Character If Neededif(odd){ return len + 1;}If at least one odd frequency exists → we can place one character in the center.Otherwise → return len.🎯 Why This WorksIn a palindrome:All characters must appear in pairs (mirrored sides).Only one character can be unpaired (center).So we:Use all even counts.Use even portion of odd counts.Add one center character if possible.⏱ Complexity AnalysisTime Complexity: O(n)One pass to count frequenciesOne pass over map (max 52 characters: A–Z, a–z)Space Complexity: O(52) ≈ O(1)At most 52 distinct characters.🔥 Cleaner Optimization IdeaWe don’t even need a boolean variable.We can simply:Add a / 2 * 2 for every frequencyIf total length < original string length → add 1Example optimized version:class Solution { public int longestPalindrome(String s) { HashMap<Character,Integer> mp = new HashMap<>(); for(char ch : s.toCharArray()){ mp.put(ch, mp.getOrDefault(ch, 0) + 1); } int len = 0; for(int count : mp.values()){ len += (count / 2) * 2; } if(len < s.length()){ len += 1; } return len; }}🏁 Final ThoughtsThis problem teaches:Understanding palindrome structureFrequency countingGreedy logicHandling odd and even countsIt’s a simple but powerful pattern question.If you truly understand this, you can easily solve problems like:Palindrome PermutationLongest Palindrome by Concatenating Two Letter WordsCount Palindromic Subsequences

HashMapStringGreedyFrequency CountLeetCodeEasy

Find First and Last Position in Sorted Array – From Brute Force to Binary Search (LeetCode 34)

Problem LinkLeetCode 34 – Find First and Last Position of Element in Sorted Array 👉 https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/📌 Problem OverviewYou are given a sorted array (non-decreasing order) and a target value.Your task:Return the starting and ending index of the target.If target does not exist → return [-1, -1]Required Time Complexity: O(log n)Example 1Input: nums = [5,7,7,8,8,10], target = 8 Output: [3,4]Example 2Input: nums = [5,7,7,8,8,10], target = 6 Output: [-1,-1]🧠 My First Intuition – Brute Force (O(n))When I first saw this problem, my thinking was simple:"Since the array is sorted, I just need to find the first occurrence and the last occurrence."So I used two loops:One loop from left → to find first occurrenceOne loop from right → to find last occurrenceHere is my submitted solution:class Solution { public int[] searchRange(int[] nums, int t) { int arr[] = new int[2]; arr[0] = -1; arr[1] = -1; for(int i = nums.length-1;i >=0 ;i--){ if(nums[i] == t){ arr[1] = i; break; } } for(int i = 0;i <nums.length ;i++){ if(nums[i] == t){ arr[0] = i; break; } } return arr; }}✅ Why This WorksSince the array is sorted, occurrences of the same number are grouped together.First loop (reverse) finds last occurrence.Second loop (forward) finds first occurrence.❌ Problem with This ApproachTime Complexity = O(n)Worst case:Target is not presentWe scan entire array twiceBut the problem clearly states:You must write an algorithm with O(log n) runtime complexity.That means: We must use Binary Search.🚀 Optimized Approach – Binary Search (O(log n))💡 Key IntuitionIf the array is sorted:We can use Binary Search to find the first occurrenceWe can use Binary Search again to find the last occurrenceInstead of stopping when we find the target:For first occurrence → continue searching leftFor last occurrence → continue searching right🧠 Idea Breakdown1️⃣ Find First OccurrenceWhen we find target at mid:Store indexMove left → high = mid - 1Because there might be another occurrence before it2️⃣ Find Last OccurrenceWhen we find target at mid:Store indexMove right → low = mid + 1Because there might be another occurrence after it💻 Optimized Code (Binary Search Approach)class Solution { public int[] searchRange(int[] nums, int target) { int[] result = new int[2]; result[0] = findFirst(nums, target); result[1] = findLast(nums, target); return result; } private int findFirst(int[] nums, int target) { int low = 0, high = nums.length - 1; int index = -1; while (low <= high) { int mid = low + (high - low) / 2; if (nums[mid] == target) { index = mid; high = mid - 1; // move left } else if (nums[mid] < target) { low = mid + 1; } else { high = mid - 1; } } return index; } private int findLast(int[] nums, int target) { int low = 0, high = nums.length - 1; int index = -1; while (low <= high) { int mid = low + (high - low) / 2; if (nums[mid] == target) { index = mid; low = mid + 1; // move right } else if (nums[mid] < target) { low = mid + 1; } else { high = mid - 1; } } return index; }}🔍 Why This WorksBinary Search normally stops when target is found.Here, we modify it slightly:Keep searching even after finding target.Narrow the search space toward the boundary we want.This guarantees:First occurrence → leftmost indexLast occurrence → rightmost index⏱ Complexity AnalysisBrute Force ApproachTime: O(n)Space: O(1)Binary Search ApproachTime: O(log n)Space: O(1)This satisfies the problem constraint.🎯 Key Learning from This ProblemThis problem teaches an important pattern:When array is sorted and you need boundaries → Think Binary Search.It is not just about finding the element.It is about finding:First occurrence (Lower Bound)Last occurrence (Upper Bound)This pattern appears in many interview problems.📚 Similar Problems to Practicehttps://leetcode.com/problems/binary-search/https://leetcode.com/problems/search-insert-position/https://leetcode.com/problems/search-in-rotated-sorted-array/https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/https://leetcode.com/problems/sqrtx/🏁 Final ThoughtsMy journey solving this problem:First thought → Use two loops (works but O(n))Then realized constraint → Must be O(log n)Optimized using two Binary SearchesThis is how problem solving improves:Start with correct solution.Then optimize.Then recognize patterns.LeetCode 34 is one of the most important Binary Search boundary problems.If you master this, you unlock an entire category of advanced Binary Search questions.

Binary SearchLeetCodeMedium

Minimum Changes to Make Alternating Binary String – LeetCode 1758 Explained

Try This QuestionBefore reading the solution, try solving the problem yourself on LeetCode:👉 https://leetcode.com/problems/minimum-changes-to-make-alternating-binary-string/Problem StatementYou are given a binary string s consisting only of characters '0' and '1'.In one operation, you can change any '0' to '1' or '1' to '0'.A string is called alternating if no two adjacent characters are the same.Example of Alternating Strings01010101011010Example of Non-Alternating Strings0001001111101Your task is to return the minimum number of operations required to make the string alternating.Example WalkthroughExample 1Inputs = "0100"Possible fix:0101Only the last character needs to change, so the answer is:Output1Example 2Inputs = "10"The string is already alternating.Output0Example 3Inputs = "1111"Possible alternating strings:01011010Minimum operations needed = 2Output2Key ObservationAn alternating binary string can only have two possible patterns:Pattern 10101010101...Pattern 21010101010...So instead of trying many combinations, we only need to check:1️⃣ How many changes are required to convert s → "010101..."2️⃣ How many changes are required to convert s → "101010..."Then we return the minimum of the two.ApproachStep 1Generate two possible alternating strings:s1 = "010101..."s2 = "101010..."Both will be of the same length as the input string.Step 2Compare the original string with both patterns.Count mismatches.For example:s = 0100s1 = 0101Mismatch count = 1Step 3Repeat for the second pattern.Finally return:min(mismatch1, mismatch2)Intuition Behind the SolutionInstead of flipping characters randomly, we compare the string with the two valid alternating possibilities.Why only two?Because:Alternating strings must start with either 0 or 1After that, the pattern is fixed.So we simply compute which pattern requires fewer changes.This makes the solution efficient and simple.Java Implementationclass Solution { public int minOperations(String s) { int co1 = 0; int co2 = 0; String s1 = ""; String s2 = ""; for(int i = 0; i < s.length(); i++){ if(i % 2 == 0){ s1 += "0"; } else { s1 += "1"; } } for(int i = 0; i < s.length(); i++){ if(i % 2 == 0){ s2 += "1"; } else { s2 += "0"; } } for(int i = 0; i < s.length(); i++){ if(s.charAt(i) != s1.charAt(i)){ co1++; } } for(int i = 0; i < s.length(); i++){ if(s.charAt(i) != s2.charAt(i)){ co2++; } } return Math.min(co1, co2); }}Complexity AnalysisTime ComplexityO(n)We iterate through the string a few times.Space ComplexityO(n)Because we create two extra strings of size n.Optimized Approach (Better Interview Answer)We can avoid creating extra strings and calculate mismatches directly.Optimized Java Codeclass Solution { public int minOperations(String s) { int pattern1 = 0; int pattern2 = 0; for(int i = 0; i < s.length(); i++){ char expected1 = (i % 2 == 0) ? '0' : '1'; char expected2 = (i % 2 == 0) ? '1' : '0'; if(s.charAt(i) != expected1) pattern1++; if(s.charAt(i) != expected2) pattern2++; } return Math.min(pattern1, pattern2); }}Space Complexity NowO(1)No extra strings required.Why This Problem Is ImportantThis problem teaches important interview concepts:✔ Pattern observation✔ Greedy thinking✔ String manipulation✔ Optimization techniquesMany companies ask similar pattern-based string problems.Final ThoughtsThe trick in this problem is realizing that only two alternating patterns exist. Once you identify that, the problem becomes straightforward.Instead of trying multiple modifications, you simply compare and count mismatches.This leads to a clean and efficient O(n) solution.If you are preparing for coding interviews, practicing problems like this will improve your pattern recognition skills, which is a key skill for solving medium and hard problems later.Happy Coding 🚀

LeetCodeBinary StringGreedy AlgorithmJavaEasy

Reverse LinkedList (LeetCode 206) – The One Trick That Changes Everything

🚀 Try the ProblemPractice here:https://leetcode.com/problems/reverse-linked-list/🤔 Let’s Start With a Simple Question…What happens if you take this:1 → 2 → 3 → 4 → 5…and try to reverse it?You want:5 → 4 → 3 → 2 → 1Sounds easy, right?But here’s the catch:👉 You can only move forward in a linked list👉 There is no backward pointerSo how do we reverse something that only goes one way?🧠 The Core Problem (In Simple Words)You are given the head of a linked list.👉 Reverse the list👉 Return the new head📦 Constraints0 <= number of nodes <= 5000-5000 <= Node.val <= 5000🔍 Before Jumping to Code — Think Like ThisWhen solving this, your brain might go:Can I store values somewhere and reverse? ❌ (extra space)Can I rebuild the list? ❌ (unnecessary)Can I just change links? ✅ (YES, THIS IS THE KEY)⚡ The Breakthrough Idea👉 Instead of moving nodes👉 We reverse the direction of pointers🎯 Visual Intuition (Very Important)Let’s take:1 → 2 → 3 → 4 → nullWe want:null ← 1 ← 2 ← 3 ← 4But how?🧩 The 3-Pointer Magic TrickWe use 3 pointers:prev → stores previous nodecurr → current nodenext → stores next node🔄 Step-by-Step TransformationInitial State:prev = nullcurr = 1 → 2 → 3 → 4Step 1:Save next nodeReverse linkf = 21 → nullMove pointers:prev = 1curr = 2Step 2:f = 32 → 1Move:prev = 2curr = 3Continue…Eventually:4 → 3 → 2 → 1 → null💡 Final Insight👉 Each step reverses one link👉 At the end, prev becomes the new head✅ Clean Java Code (Iterative Approach)class Solution {public ListNode reverseList(ListNode head) {// Previous pointer starts as nullListNode prev = null;// Current pointer starts from headListNode curr = head;while (curr != null) {// Store next nodeListNode f = curr.next;// Reverse the linkcurr.next = prev;// Move prev forwardprev = curr;// Move curr forwardcurr = f;}// New head is prevreturn prev;}}⏱️ ComplexityTime ComplexityO(n)We traverse the list once.Space ComplexityO(1)No extra space used.🔁 Another Way: Recursive ApproachNow let’s think differently…👉 What if we reverse the rest of the list first, then fix the current node?🧠 Recursive IdeaFor:1 → 2 → 3 → 4We:Reverse from 2 → 3 → 4Then fix 1💻 Recursive Codeclass Solution {public ListNode reverseList(ListNode head) {// Base caseif(head == null || head.next == null)return head;// Reverse restListNode newHead = reverseList(head.next);// Fix current nodehead.next.next = head;head.next = null;return newHead;}}⚖️ Iterative vs RecursiveApproachProsConsIterativeFast, O(1) spaceSlightly tricky to understandRecursiveElegant, clean logicUses stack (O(n) space)❌ Common MistakesForgetting to store next nodeLosing reference to rest of listNot updating pointers correctlyReturning wrong node🔥 Real Interview InsightThis problem is not just about reversing a list.It teaches:👉 Pointer manipulation👉 In-place updates👉 Thinking in steps👉 Breaking problems into small operations🧠 Final ThoughtAt first, this problem feels tricky…But once you understand this line:curr.next = prev👉 Everything clicks.🚀 ConclusionThe Reverse Linked List problem is one of the most important foundational problems in DSA.Mastering it will:Boost your confidenceStrengthen pointer logicHelp in many advanced problems👉 Tip: Practice this until you can visualize pointer movement in your head — that’s when you truly master linked lists.

Linked ListPointer ManipulationIterative ApproachRecursionLeetCodeEasy

LeetCode 2784: Check if Array is Good – Java HashMap Solution Explained

IntroductionLeetCode 2784 – Check if Array is Good is a beginner-friendly array and hashing problem that tests your understanding of:Frequency countingHashMap usageArray validationPermutation logicEdge case handlingAlthough the problem looks simple initially, many candidates fail because they misunderstand the exact structure of the required array.This problem is commonly asked to test:Attention to detailLogical validationCounting techniquesHashing fundamentalsProblem Link🔗 https://leetcode.com/problems/check-if-array-is-good/Problem StatementAn array is considered good if it is a permutation of:base[n] = [1, 2, 3, ..., n-1, n, n]Meaning:Numbers from:1 to n-1appear exactly once.Number:nappears exactly twice.You need to return:trueif the given array is good, otherwise:falseUnderstanding the PatternA valid good array must follow:[1, 2, 3, ..., n-1, n, n]Examples:[1,1][1,2,3,3][1,2,3,4,4]Invalid examples:[1,2,2][1,2,4,4][1,1,2,2]Key ObservationsObservation 1The maximum element determines:nObservation 2Array size must be:n + 1because:1 to n-1 => n-1 elementsn appears twice => 2 elementsTotal = n + 1Observation 3Frequency conditions:NumberFrequency1 to n-1Exactly 1nExactly 2Brute Force ApproachIdeaSort arrayCompare with expected arrayReturn resultBrute Force AlgorithmStep 1Find maximum element:nStep 2Create expected array:[1,2,3,...,n,n]Step 3Sort both arrays and compare.Brute Force ComplexityTime ComplexityO(N log N)due to sorting.Space ComplexityO(N)Optimized HashMap ApproachInstead of sorting:Count frequencies directlyValidate conditionsThis makes the solution faster and cleaner.Intuition Behind HashMap SolutionWe store frequency of every number.Then verify:Maximum element appears twiceEvery other number appears onceArray length equals:max + 1Java HashMap Solutionclass Solution { public boolean isGood(int[] nums) { if(nums.length == 1) return false; int maxElement = Integer.MIN_VALUE; HashMap<Integer, Integer> map = new HashMap<>(); for(int i = 0; i < nums.length; i++) { map.put(nums[i], map.getOrDefault(nums[i], 0) + 1); maxElement = Math.max(maxElement, nums[i]); } int n = maxElement; if(nums.length != n + 1) { return false; } for(int i = 1; i <= n; i++) { if(!map.containsKey(i)) { return false; } if(i == n) { if(map.get(i) != 2) return false; } else { if(map.get(i) != 1) return false; } } return true; }}Dry RunInputnums = [1,3,3,2]Step 1 – Find MaximumMaximum element:3So:n = 3Step 2 – Length CheckExpected length:n + 1 = 4Actual length:4Valid.Step 3 – Frequency CountFrequency map:NumberCount112132Step 4 – Validate ConditionsNumbers 1 and 2 appear once ✅Number 3 appears twice ✅Return:trueEdge CasesCase 1[1]Invalid because:base[1] = [1,1]Case 2[1,1]Valid.Case 3[1,2,2]Invalid because:n = 2Expected:[1,2,2]Actually valid.Case 4[3,4,4,1,2,1]Invalid because:length != max + 1Optimized Alternative Using SortingAnother clean solution:Sort arrayVerify:nums[i] == i + 1for all except last.Last two elements should be equal.Java Sorting Solutionclass Solution { public boolean isGood(int[] nums) { Arrays.sort(nums); int n = nums.length - 1; for(int i = 0; i < n; i++) { if(nums[i] != i + 1) return false; } return nums[n] == n; }}Time Complexity AnalysisHashMap SolutionTime ComplexityO(N)Space ComplexityO(N)Sorting SolutionTime ComplexityO(N log N)Space ComplexityO(1)excluding sorting overhead.HashMap vs SortingApproachTime ComplexitySpace ComplexityHashMapO(N)O(N)SortingO(N log N)O(1)Interview ExplanationIn interviews, explain:A good array must follow the exact pattern [1,2,3,...,n,n]. The maximum element determines n, and frequency counting helps verify whether all required numbers appear correctly.This demonstrates strong understanding of:Frequency countingValidation logicEdge case handlingCommon Mistakes1. Forgetting Length CheckAlways verify:length == max + 12. Ignoring Missing NumbersArray must contain:1 to ncompletely.3. Wrong Frequency ValidationOnly maximum element should appear twice.All others must appear once.FAQsQ1. Why does maximum element determine n?Because:base[n]always ends with:n,nQ2. Why should array size be n + 1?Because:1 to n-1 => n-1 elementsn repeated twice => 2 elementsTotal = n+1Q3. Which approach is better?HashMap solution is faster.Sorting solution is simpler.Q4. Is this problem important for interviews?Yes.It tests:HashingValidation logicEdge case thinkingRelated ProblemsAfter mastering this problem, practice:Contains DuplicateFind All Duplicates in an ArrayValid AnagramConclusionLeetCode 2784 is a great beginner-friendly hashing problem.It teaches:Frequency countingValidation logicHashMap usageEdge case handlingThe key insight is:A good array must exactly match the structure [1,2,3,...,n,n].Once you understand this pattern, the problem becomes straightforward and easy to implement.

LeetCodeJavaHashMapArrayFrequency CountEasy

Merge Sort Algorithm Explained | Java Implementation, Intuition & Complexity

IntroductionSorting is one of the most fundamental operations in computer science, and Merge Sort is among the most efficient and widely used sorting algorithms.It follows the Divide and Conquer approach, making it highly scalable and predictable even for large datasets.In this article, we will cover:Intuition behind Merge SortStep-by-step breakdownMultiple approachesJava implementation with commentsTime & space complexity analysis🔗 Problem LinkGeeksforGeeks: Merge SortProblem StatementGiven an array arr[] with starting index l and ending index r, sort the array using the Merge Sort algorithm.ExamplesExample 1Input:arr = [4, 1, 3, 9, 7]Output:[1, 3, 4, 7, 9]Example 2Input:arr = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]Output:[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]Key InsightMerge Sort works by:Divide → Conquer → CombineDivide the array into two halvesRecursively sort each halfMerge both sorted halvesIntuition (Visual Understanding)For:[4, 1, 3, 9, 7]Step 1: Divide[4, 1, 3] [9, 7][4, 1] [3] [9] [7][4] [1]Step 2: Merge[4] [1] → [1, 4][1, 4] [3] → [1, 3, 4][9] [7] → [7, 9]Step 3: Final Merge[1, 3, 4] + [7, 9] → [1, 3, 4, 7, 9]Approach 1: Recursive Merge Sort (Top-Down)IdeaKeep dividing until single elements remainMerge sorted subarraysJava Codeclass Solution { // Function to merge two sorted halves void merge(int[] arr, int l, int mid, int h) { // Temporary array to store merged result int[] temp = new int[h - l + 1]; int i = l; // pointer for left half int j = mid + 1; // pointer for right half int k = 0; // pointer for temp array // Compare elements from both halves while (i <= mid && j <= h) { if (arr[i] <= arr[j]) { temp[k] = arr[i]; i++; } else { temp[k] = arr[j]; j++; } k++; } // Copy remaining elements from left half while (i <= mid) { temp[k] = arr[i]; i++; k++; } // Copy remaining elements from right half while (j <= h) { temp[k] = arr[j]; j++; k++; } // Copy sorted elements back to original array for (int m = 0; m < temp.length; m++) { arr[l + m] = temp[m]; } } // Recursive merge sort function void mergeSort(int arr[], int l, int h) { // Base case: single element if (l >= h) return; int mid = l + (h - l) / 2; // Sort left half mergeSort(arr, l, mid); // Sort right half mergeSort(arr, mid + 1, h); // Merge both halves merge(arr, l, mid, h); }}Approach 2: Iterative Merge Sort (Bottom-Up)IdeaStart with subarrays of size 1Merge pairsIncrease size graduallyCodeclass Solution { void merge(int[] arr, int l, int mid, int h) { int[] temp = new int[h - l + 1]; int i = l, j = mid + 1, k = 0; while (i <= mid && j <= h) { if (arr[i] <= arr[j]) temp[k++] = arr[i++]; else temp[k++] = arr[j++]; } while (i <= mid) temp[k++] = arr[i++]; while (j <= h) temp[k++] = arr[j++]; for (int m = 0; m < temp.length; m++) { arr[l + m] = temp[m]; } } void mergeSort(int[] arr, int n) { for (int size = 1; size < n; size *= 2) { for (int l = 0; l < n - size; l += 2 * size) { int mid = l + size - 1; int h = Math.min(l + 2 * size - 1, n - 1); merge(arr, l, mid, h); } } }}Approach 3: Using Built-in Sorting (For Comparison)Arrays.sort(arr);👉 Internally uses optimized algorithms (TimSort in Java)Complexity AnalysisTime ComplexityCaseComplexityBestO(n log n)AverageO(n log n)WorstO(n log n)Space ComplexityO(n) (extra array for merging)Why Merge Sort is PowerfulStable sorting algorithmWorks efficiently on large datasetsPredictable performanceUsed in external sorting (large files)❌ Why Not Use Bubble/Selection Sort?AlgorithmTime ComplexityBubble SortO(n²)Selection SortO(n²)Merge SortO(n log n) ✅Key TakeawaysMerge Sort uses divide and conquerRecursion splits problem into smaller partsMerging is the key stepAlways O(n log n), regardless of inputWhen to Use Merge SortLarge datasetsLinked lists (very efficient)Stable sorting requiredExternal sortingConclusionMerge Sort is one of the most reliable and efficient sorting algorithms. Understanding its recursive structure and merging process is essential for mastering advanced algorithms.Once you grasp the divide-and-conquer pattern, it becomes easier to solve many complex problems.Frequently Asked Questions (FAQs)1. Is Merge Sort stable?Yes, it maintains the relative order of equal elements.2. Why is extra space required?Because we use a temporary array during merging.3. Can it be done in-place?Not efficiently; standard merge sort requires extra space.

GeekfOfGeeksMediumSortingMerge SortJava

LeetCode 1980: Find Unique Binary String – Multiple Ways to Generate a Missing Binary Combination

Try the ProblemYou can solve the problem here:https://leetcode.com/problems/find-unique-binary-string/Problem DescriptionYou are given an array nums containing n unique binary strings, where each string has length n.Your task is to return any binary string of length n that does not appear in the array.Important ConditionsEach string consists only of '0' and '1'.Every string in the array is unique.The output must be a binary string of length n.If multiple valid answers exist, any one of them is acceptable.ExamplesExample 1Inputnums = ["01","10"]Output"11"ExplanationPossible binary strings of length 2:00011011Since "01" and "10" are already present, valid answers could be:00 or 11Example 2Inputnums = ["00","01"]Output"11"Another valid output could be:10Example 3Inputnums = ["111","011","001"]Output101Other valid answers include:000010100110Constraintsn == nums.length1 <= n <= 16nums[i].length == nnums[i] consists only of '0' and '1'All strings in nums are uniqueImportant ObservationThe total number of binary strings of length n is:2^nBut the array contains only:n stringsSince 2^n grows very quickly and n ≤ 16, there are many possible binary strings missing from the array. Our goal is simply to construct one of those missing strings.Thinking About the ProblemBefore jumping into coding, it's useful to think about different strategies that could help us generate a binary string that does not appear in the array.Possible Ways to Think About the ProblemWhen approaching this problem, several ideas may come to mind:Generate all possible binary strings of length n and check which one is missing.Store all strings in a HashSet or HashMap and construct a candidate string to verify whether it exists.Manipulate existing strings by flipping bits to create new combinations.Use a mathematical trick that guarantees the new string is different from every string in the list.Each of these approaches leads to a different solution strategy.In this article, we will walk through these approaches and understand how they work.Approach 1: Brute Force – Generate All Binary StringsIdeaThe simplest idea is to generate every possible binary string of length n and check whether it exists in the given array.Since there are:2^n possible binary stringsWe can generate them one by one and return the first string that does not appear in nums.StepsConvert numbers from 0 to (2^n - 1) into binary strings.Pad the binary string with leading zeros so its length becomes n.Check if that string exists in the array.If not, return it.Time ComplexityO(2^n * n)This works because n is at most 16, but it is still not the most elegant approach.Approach 2: HashMap + Bit Flipping (My Approach)IdeaWhile solving this problem, another idea is to store all given binary strings inside a HashMap for quick lookup.Then we can try to construct a new binary string by flipping bits from the existing strings.The intuition is simple:If the current character is '0', change it to '1'.If the current character is '1', change it to '0'.By flipping bits at different positions, we attempt to build a new binary combination.Once the string is constructed, we check whether it already exists in the map.If the generated string does not exist, we return it as our answer.Java Implementation (My Solution)class Solution { public String findDifferentBinaryString(String[] nums) { int len = nums[0].length(); // HashMap to store all given binary strings HashMap<String, Integer> mp = new HashMap<>(); for(int i = 0; i < nums.length; i++){ mp.put(nums[i], i); } int cou = 0; String ans = ""; for(int i = 0; i < nums.length; i++){ if(cou < len){ // Flip the current bit if(nums[i].charAt(cou) == '0'){ ans += '1'; cou++; } else{ ans += '0'; cou++; } }else{ // If generated string does not exist in map if(!mp.containsKey(ans)){ return ans; } // Reset and try building again ans = ""; cou = 0; } } return ans; }}Time ComplexityO(n²)Because we iterate through the array and perform string operations.Space ComplexityO(n)For storing the strings in the HashMap.Approach 3: Cantor’s Diagonalization (Optimal Solution)IdeaA clever mathematical observation allows us to construct a string that must differ from every string in the array.We build a new string such that:The first character differs from the first string.The second character differs from the second string.The third character differs from the third string.And so on.By ensuring that the generated string differs from each string at least at one position, it is guaranteed not to exist in the array.This technique is known as Cantor’s Diagonalization.Java Implementationclass Solution { public String findDifferentBinaryString(String[] nums) { int n = nums.length; StringBuilder result = new StringBuilder(); for(int i = 0; i < n; i++){ // Flip the diagonal bit if(nums[i].charAt(i) == '0'){ result.append('1'); } else{ result.append('0'); } } return result.toString(); }}Time ComplexityO(n)We only traverse the array once.Space ComplexityO(n)For storing the resulting string.Comparison of ApproachesApproachTime ComplexitySpace ComplexityNotesBrute ForceO(2^n * n)O(n)Simple but inefficientHashMap + Bit FlippingO(n²)O(n)Constructive approachCantor DiagonalizationO(n)O(n)Optimal and elegantKey TakeawaysThis problem highlights an interesting concept in algorithm design:Sometimes the best solution is not searching for the answer but constructing one directly.By understanding the structure of the input, we can generate a result that is guaranteed to be unique.ConclusionThe Find Unique Binary String problem can be solved using multiple strategies, ranging from brute force enumeration to clever mathematical construction.While brute force works due to the small constraint (n ≤ 16), more elegant solutions exist. Using hashing or constructive approaches improves efficiency and demonstrates deeper algorithmic thinking.Among all approaches, the Cantor Diagonalization technique provides the most efficient and mathematically guaranteed solution.Understanding problems like this helps strengthen skills in string manipulation, hashing, and constructive algorithms, which are commonly tested in coding interviews.

Binary StringsHashingCantor DiagonalizationLeetCodeMedium

LeetCode 104: Maximum Depth of Binary Tree – Java Recursive Solution Explained

IntroductionLeetCode 104 – Maximum Depth of Binary Tree is one of the most important beginner tree problems in Data Structures and Algorithms.This problem teaches:Binary Tree TraversalDepth First Search (DFS)RecursionTree Height CalculationDivide and ConquerIt is one of the most frequently asked tree questions in coding interviews because it builds the foundation for:Tree recursionHeight problemsBalanced tree problemsDiameter problemsDFS traversalIf you are starting binary trees, this is one of the best problems to master first.Problem Link🔗 https://leetcode.com/problems/maximum-depth-of-binary-tree/Problem StatementGiven the root of a binary tree:Return:Maximum depth of the treeMaximum depth means:Number of nodes along the longest path from root to the farthest leaf node.Example 1Inputroot = [3,9,20,null,null,15,7]Tree: 3 / \ 9 20 / \ 15 7Output3Explanation:Longest path:3 → 20 → 15contains:3 nodesExample 2Inputroot = [1,null,2]Tree:1 \ 2Output:2Understanding Maximum DepthDepth means:How many levels exist in the treeFor example: 1 / \ 2 3 / 4Levels:Level 1 → 1Level 2 → 2,3Level 3 → 4Maximum depth:3Key ObservationThe depth of a tree depends on:Maximum depth of left subtreeandMaximum depth of right subtreeSo:Depth(root)=1 + max(leftDepth, rightDepth)This is the core recursive formula.Recursive IntuitionAt every node:Find depth of left subtreeFind depth of right subtreeTake maximumAdd current nodeThis naturally becomes a recursive DFS problem.Java Recursive Solutionclass Solution { public int maxDepth(TreeNode root) { if(root == null) return 0; int left = maxDepth(root.left); int right = maxDepth(root.right); return 1 + Math.max(left, right); }}Why This WorksAt every node:Recursively calculate left depthRecursively calculate right depthChoose bigger depthAdd:1for current node.This continues until leaf nodes.Dry RunInput 3 / \ 9 20 / \ 15 7Step 1Start from root:3Step 2Left subtree:9Depth:1Step 3Right subtree:20Its children:15 and 7Depth becomes:2Step 4At root:1 + max(1,2)Result:3Recursive Call FlowmaxDepth(3) ├── maxDepth(9) │ ├── 0 │ └── 0 │ └── maxDepth(20) ├── maxDepth(15) └── maxDepth(7)Then values return upward.Alternative BFS ApproachWe can also solve this using:Level Order Traversalusing a queue.Every level increases depth by:1BFS Java Solutionclass Solution { public int maxDepth(TreeNode root) { if(root == null) return 0; Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); int depth = 0; while(!queue.isEmpty()) { int size = queue.size(); for(int i = 0; i < size; i++) { TreeNode node = queue.poll(); if(node.left != null) queue.offer(node.left); if(node.right != null) queue.offer(node.right); } depth++; } return depth; }}DFS vs BFSApproachTechniqueSpaceDFSRecursionO(H)BFSQueueO(N)Time Complexity AnalysisRecursive DFS SolutionTime ComplexityO(N)because every node is visited once.Space ComplexityO(H)where:H = tree heightWorst case:O(N)for skewed tree.BFS SolutionTime ComplexityO(N)Space ComplexityO(N)queue may contain full level.Interview ExplanationIn interviews, explain:The depth of a node depends on the maximum depth between its left and right subtree. This naturally forms a recursive divide-and-conquer problem.This demonstrates:Tree recursion understandingDFS traversal knowledgeDivide and conquer thinkingCommon Mistakes1. Forgetting Base CaseAlways handle:if(root == null) return 0;2. Using Min Instead of MaxWe need:Longest pathnot shortest.3. Incorrect Depth CountingRemember to add:1for current node.FAQsQ1. What is maximum depth?It is the number of nodes in the longest root-to-leaf path.Q2. Why is recursion preferred?Tree problems naturally fit recursive structures.Q3. Can this be solved iteratively?Yes.Using BFS with queue.Q4. Is this problem important for interviews?Very important.It is one of the most fundamental tree recursion problems.Related ProblemsAfter mastering this problem, practice:Minimum Depth of Binary TreeBalanced Binary TreeDiameter of Binary TreeBinary Tree Level Order TraversalPath SumConclusionLeetCode 104 is one of the most important beginner binary tree problems.It teaches:Recursive DFSTree height calculationDivide and conquerBinary tree traversalThe key insight is:Maximum depth equals 1 + maximum depth of left and right subtree.Once this recursive pattern becomes clear, many advanced tree problems become easier to solve.

LeetCodeDepth of Binary TreeJavaBinary TreeDFSBFSRecursionTreeEasy

LeetCode 187 – Repeated DNA Sequences (Java Solution with Sliding Window and HashSet)

IntroductionIn this article, we will solve LeetCode 187: Repeated DNA Sequences using Java. This is a popular string problem that tests your understanding of the sliding window technique and efficient use of hash-based data structures.DNA sequences are composed of four characters:A (Adenine)C (Cytosine)G (Guanine)T (Thymine)The goal is to identify all 10-letter-long substrings that appear more than once in a given DNA string.You can try solving the problem directly on LeetCode here: https://leetcode.com/problems/repeated-dna-sequences/Problem StatementGiven a string s that represents a DNA sequence, return all the 10-letter-long substrings that occur more than once.Example 1Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"Output: ["AAAAACCCCC", "CCCCCAAAAA"]Example 2Input: s = "AAAAAAAAAAAAA"Output: ["AAAAAAAAAA"]Key ObservationsWe only need substrings of fixed length 10.The maximum length of the string can be up to 10^5.A brute-force solution checking all substrings multiple times would be inefficient.This problem can be solved efficiently using a sliding window and hash-based data structures.Approach 1: Sliding Window with HashSet (Given Solution)IdeaUse two pointers (i and j) to maintain a sliding window.Build a substring of size 10 dynamically.Store previously seen substrings in a HashSet.If a substring is already present in the set:Check if it is already in the result list.If not, add it to the result list.Slide the window forward and continue.Java Code (Your Implementation)class Solution { public List<String> findRepeatedDnaSequences(String s) { HashSet<String> ms = new HashSet<>(); List<String> lis = new ArrayList<>(); int i = 0; int j = 0; String tes = ""; while (j < s.length()) { tes += s.charAt(j); if (j - i + 1 < 10) { j++; } else { if (j - i + 1 == 10) { if (ms.contains(tes)) { boolean fl = false; for (String a : lis) { if (a.equals(tes)) { fl = true; } } if (!fl) { lis.add(tes); } } else { ms.add(tes); } tes = tes.substring(1); i++; j++; } } } return lis; }}ExplanationThe variable tes maintains the current substring.ms stores all previously seen substrings of length 10.If a substring already exists in ms, we manually check whether it has already been added to the result list.This avoids duplicate entries in the final output.Time ComplexitySliding through the string: O(n)Checking duplicates in the result list: O(n) in the worst caseOverall worst-case complexity: O(n²)Space ComplexityHashSet storage: O(n)Limitation of Approach 1The manual duplicate check using a loop inside the result list introduces unnecessary overhead. This makes the solution less efficient.We can improve this by using another HashSet to automatically handle duplicates.Approach 2: Optimized Solution Using Two HashSetsIdeaUse one HashSet called seen to track all substrings of length 10.Use another HashSet called repeated to store substrings that appear more than once.Iterate from index 0 to s.length() - 10.Extract substring of length 10.If adding to seen fails, it means it has appeared before.Add it directly to repeated.This removes the need for a nested loop.Optimized Java Codeclass Solution { public List<String> findRepeatedDnaSequences(String s) { Set<String> seen = new HashSet<>(); Set<String> repeated = new HashSet<>(); for (int i = 0; i <= s.length() - 10; i++) { String substring = s.substring(i, i + 10); if (!seen.add(substring)) { repeated.add(substring); } } return new ArrayList<>(repeated); }}Why This Approach is BetterNo manual duplicate checking.Cleaner and more readable code.Uses HashSet properties efficiently.Each substring is processed only once.Time Complexity (Optimized)Single traversal of the string: O(n)Substring extraction of fixed length 10: O(1)Overall time complexity: O(n)Space ComplexityTwo HashSets storing substrings: O(n)ConclusionLeetCode 187 is a classic example of combining the sliding window technique with hash-based data structures.The first approach works but has unnecessary overhead due to manual duplicate checks.The second approach is more optimal, cleaner, and recommended for interviews.Always leverage the properties of HashSet to avoid redundant checks.This problem highlights the importance of choosing the right data structure to optimize performance.

JavaSliding WindowMedium

LeetCode 2657: Find the Prefix Common Array of Two Arrays – Java Hashing Solution Explained

IntroductionLeetCode 2657 – Find the Prefix Common Array of Two Arrays is an interesting prefix and hashing problem that tests your understanding of:Prefix processingHashingFrequency countingSet operationsArray traversalAt first glance, the problem may look confusing because of the term:Prefix Common ArrayBut once you understand the meaning of prefixes and common elements, the problem becomes straightforward.This problem is useful for improving:Prefix-based thinkingHashing intuitionOptimization skillsInterview problem-solving abilityProblem Link🔗 Find the prefix Common Array of Two ArraysProblem StatementYou are given two permutations:A and BBoth arrays contain numbers:1 to nexactly once.You need to create an array:Cwhere:C[i]represents:Count of numbers present in both arrays from index 0 to i.Understanding Prefix Common ArraySuppose:A = [1,3,2,4]B = [3,1,2,4]Prefix at Index 0A Prefix = [1]B Prefix = [3]Common numbers:NoneSo:C[0] = 0Prefix at Index 1A Prefix = [1,3]B Prefix = [3,1]Common numbers:1, 3So:C[1] = 2Final Output[0,2,3,4]Key ObservationBoth arrays are permutations.This means:Every number appears exactly once.Once a number appears in both prefixes, it remains common forever.This simplifies the logic significantly.Brute Force ApproachIntuitionFor every index:Build prefixesCompare elementsCount common numbersBrute Force AlgorithmFor each index:Traverse all previous elementsCheck whether numbers exist in both prefixesCount matchesBrute Force ComplexityTime ComplexityO(N²)because for every index we may scan previous elements.Space ComplexityO(N)Understanding ApproachThis approach uses:HashMapPrefix trackingCounting common valuesThe idea is:Store prefix elements from BTraverse A prefixCount matching numbersThis works because prefixes gradually expand.Java Solutionclass Solution { public int[] findThePrefixCommonArray(int[] A, int[] B) { int j = 0; int[] ans = new int[A.length]; HashMap<Integer, Integer> map = new HashMap<>(); for(int i = 0; i < A.length; i++) { map.put(B[i], i); int counter = 0; int c = 0; for(int a : map.keySet()) { if(map.containsKey(A[c])) { counter++; } c++; } ans[j] = counter; j++; } return ans; }}Better Optimized ApproachWe can solve this more cleanly using:HashSetor frequency counting.Optimized IntuitionAt every index:Add A[i]Add B[i]Track which numbers appearedIf a number appears in both arrays, increase common countBest Optimized Approach Using Frequency ArrayBecause values are from:1 to nwe can use a frequency array.Optimized Java Solutionclass Solution { public int[] findThePrefixCommonArray(int[] A, int[] B) { int n = A.length; int[] ans = new int[n]; int[] freq = new int[n + 1]; int common = 0; for(int i = 0; i < n; i++) { freq[A[i]]++; if(freq[A[i]] == 2) common++; freq[B[i]]++; if(freq[B[i]] == 2) common++; ans[i] = common; } return ans; }}Why Does This Work?Every number appears once in A and once in B.So:First appearance → frequency becomes 1Second appearance → frequency becomes 2When frequency becomes:2it means the number has appeared in both prefixes.So we increase:commonDry RunInputA = [1,3,2,4]B = [3,1,2,4]Step 1Index:0Add:1 and 3Frequencies:1 → 13 → 1No common elements.ans[0] = 0Step 2Add:3 and 1Frequencies:1 → 23 → 2Two common elements found.ans[1] = 2Step 3Add:2 and 2Frequency:2 → 2Common becomes:3ans[2] = 3Step 4Add:4 and 4Frequency:4 → 2Common becomes:4ans[3] = 4Final Output[0,2,3,4]Time Complexity AnalysisTime ComplexityO(N²)Nested traversal inside loop.Space ComplexityO(N)Optimized Frequency ApproachTime ComplexityO(N)Single traversal.Space ComplexityO(N)Frequency array.HashMap vs Frequency ArrayApproachTime ComplexitySpace ComplexityHashMapO(N²)O(N)Frequency ArrayO(N)O(N)Interview ExplanationIn interviews, explain:Since both arrays are permutations, every number appears exactly twice overall — once in A and once in B. Using frequency counting, whenever a number’s frequency becomes 2, it means it has appeared in both prefixes.This demonstrates:Prefix understandingOptimization thinkingHashing skillsCommon Mistakes1. Recalculating Common Elements Every TimeThis causes:O(N²)complexity.2. Forgetting Arrays Are PermutationsThis special condition allows frequency optimization.3. Incorrect Prefix LogicRemember:Prefix means elements from 0 to i.FAQsQ1. Why is this called Prefix Common Array?Because:C[i]stores common elements between prefixes ending at index:iQ2. Why does frequency 2 mean common?Because every number appears once in each array.Q3. Which approach is best?Frequency array approach is the most optimized.Q4. Is this problem important for interviews?Yes.It tests:Prefix logicHashingOptimizationArray traversalRelated ProblemsAfter mastering this problem, practice:Intersection of Two ArraysIntersection of Two Arrays IIContains DuplicateSubarray Sum Equals KPrefix SumFind the Difference of Two ArraysConclusionLeetCode 2657 is an excellent prefix and hashing problem.It teaches:Prefix processingFrequency countingOptimization techniquesHashing fundamentalsThe key insight is:A number becomes common exactly when its frequency becomes 2.Once you understand this observation, the optimized solution becomes very simple and efficient.

LeetCodePrefix Common ArrayJavaHashMapHashSetArrayPrefixArrayMedium

Check if All Characters Have Equal Number of Occurrences – Frequency Map Approach (LeetCode 1941)

🔗 Problem LinkLeetCode 1941 – Check if All Characters Have Equal Number of Occurrences 👉 https://leetcode.com/problems/check-if-all-characters-have-equal-number-of-occurrences/IntroductionThis is one of those problems that looks very simple at first glance — and it actually is — but it helps strengthen your understanding of frequency counting using HashMap.The problem asks us to determine whether all characters in a string occur the same number of times.No sliding window. No binary search. Just clean frequency logic.But even simple problems help build strong foundations.📌 Problem UnderstandingA string is considered "good" if:Every character that appears in the stringAppears the same number of timesIf even one character has a different frequency → return false.Example 1Input: s = "abacbc"Output: trueCharacter counts:a → 2b → 2c → 2All equal → ✔ trueExample 2Input: s = "aaabb"Output: falseCharacter counts:a → 3b → 2Not equal → ✘ false🧠 Approach & IntuitionWhen I saw this problem, my thinking was:Count the frequency of every character.Compare all frequencies.If all are equal → return true.The important part is choosing a reference frequency and comparing everything against it.💻 Your Codeclass Solution { public boolean areOccurrencesEqual(String s) { HashMap<Character,Integer> mp = new HashMap<>(); int ref =0; char c = s.charAt(0); for(int i =0 ; i< s.length();i++){ if(c == s.charAt(i)){ ref++; } mp.put(s.charAt(i),mp.getOrDefault(s.charAt(i),0)+1); } for(int a:mp.values()){ if(ref != a){ return false; } } return true; }}🔍 Step-by-Step Explanation1️⃣ Initialize HashMapHashMap<Character,Integer> mp = new HashMap<>();This stores frequency of each character.2️⃣ Choose Reference Characterchar c = s.charAt(0);int ref = 0;You use the first character as a reference.Then count how many times it appears while also building the frequency map.3️⃣ Build Frequency Mapmp.put(s.charAt(i), mp.getOrDefault(s.charAt(i), 0) + 1);This line increases count for each character.4️⃣ Compare Frequenciesfor(int a : mp.values()){ if(ref != a){ return false; }}If any frequency differs from the reference count → return false.Otherwise → true.⏱ Time and Space ComplexityTime Complexity: O(n)One loop to count frequenciesOne loop over at most 26 charactersSpace Complexity: O(26) ≈ O(1)Only lowercase English letters are allowed.🔥 Small Optimization IdeaYour solution works perfectly.However, we can simplify it slightly:Instead of separately counting the reference frequency, we can:First build the entire frequency map.Take the frequency of the first character from the map.Compare all values with it.Cleaner Versionclass Solution { public boolean areOccurrencesEqual(String s) { HashMap<Character,Integer> mp = new HashMap<>(); for(char ch : s.toCharArray()){ mp.put(ch, mp.getOrDefault(ch, 0) + 1); } int ref = mp.get(s.charAt(0)); for(int freq : mp.values()){ if(freq != ref){ return false; } } return true; }}Same logic — slightly cleaner structure.🎯 Key Learning from This ProblemThis problem reinforces:Frequency counting using HashMapUsing a reference value for comparisonClean loop logicEarly return for optimizationEven though it is an easy problem, it builds the base for harder problems like:Valid AnagramGroup AnagramsFirst Unique CharacterRansom Note🏁 Final ThoughtsProblems like this are not about complexity.They are about:Writing clean logicHandling frequency maps properlyThinking clearly about conditionsMastering easy problems makes medium and hard problems much easier later.

HashMapStringFrequency CountLeetCodeEasy

🚀 My First Spring Boot Backend

Why Spring Boot? 🔥✅ MongoRepository = FREE CRUD (no Mongoose models!)✅ Docker 1-file deploy (Render/Vercel style)✅ TypeScript-level safety (Java types)✅ Enterprise-grade (Netflix/Amazon use)✅ 120MB Docker image (super fast deploy)My Stack: Spring Boot + MongoDB Atlas + Render DockerProject Setup ⚙️pom.xml:<dependencies><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-web</artifactId><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-data-mongodb</artifactId><groupId>org.springframework.boot</groupId><artifactId>spring-boot-devtools</artifactId></dependencies>Core Files 💻Todo.java:@Document(collection = "todo")@Datapublic class Todo {@Id @JsonProperty("_id") private String id;private String title;private Boolean status;}TodoRepository.java (EMPTY!):public interface TodoRepository extends MongoRepository<Todo, String> {// FREE: findAll(), save(), findById(), deleteById()}TodoController.java:@RestController @RequestMapping("/api") @CrossOrigin("*")public class TodoController {@Autowired private TodoRepository todoRepository;@GetMapping("/todos")public ResponseEntity<Map<String, Object>> getAll() {List<Todo> todos = todoRepository.findAll();return ResponseEntity.ok(Map.of("success", true,"message", "Todos fetched!","data", todos,"count", todos.size()));}}Docker Magic 🐳# STAGE 1: BUILD (Temporary - Heavy)FROM maven:3.9.6-eclipse-temurin-17-alpine AS buildWORKDIR /appCOPY . . # Copy ALL filesRUN mvn clean package -DskipTests # Build JAR# STAGE 2: RUNTIME (Lightweight - Production)FROM eclipse-temurin:17-jdk-alpineWORKDIR /appCOPY --from=build /app/target/*.jar app.jar # JAR ONLY!EXPOSE $PORTENTRYPOINT ["java", "-jar", "app.jar"]Render Deployment (EXACT Steps) 🌐Step 1: Create DockerfileProject root (same level as pom.xml):└── Dockerfile ← EXACT name, NO extension!Step 2: GitHub Pushgit add Dockerfilegit commit -m "Add multi-stage Docker"git push origin mainStep 3: Render.com (5 Clicks)1. render.com → Sign up (GitHub)2. "New +" → "Web Service"3. Connect GitHub repo → Select branch "main"4. ⚙️ Settings:├── Name: firstcrud-spring├── Runtime: **Docker** ✅├── Build Command: (EMPTY)├── Start Command: (EMPTY)5. Environment → Add Variable:├── Key: SPRING_DATA_MONGODB_URI├── Value: mongodb+srv://user:pass@cluster0...6. "Create Web Service" → Deploy!Step 4: Watch Magic (3-5 mins)Render Logs:✅ Cloning GitHub repo✅ Building Docker image✅ Maven: BUILD SUCCESS✅ JAR created: 25MB✅ Deploying → LIVE!Step 5: Test Live APIGET: https://firstcrud-spring.onrender.com/api/todosPOST: https://firstcrud-spring.onrender.com/api/todosAuto-deploy: git push → Render LIVE in 2 mins! 🚀Configuration (Secure!) 🔒application.yml (GitHub - Safe):spring:data:mongodb:uri: ${SPRING_DATA_MONGODB_URI:mongodb://localhost:27017/todos}server:port: ${PORT:8080}Local: mvn spring-boot:run -Dspring.profiles.active=localSecurity Checklist ✅1. Atlas: New user (delete leaked db_user)2. Network Access: 0.0.0.0/03. GitHub: NO secrets (use ${ENV_VAR})4. Render: Environment Variables5. CORS: @CrossOrigin("*")Live Demo 🌟API: https://firstcrud-spring.onrender.com/api/todosPOST Body: {"title": "Buy Milk", "status": false}Response:{"success": true,"message": "Created!","data": {"_id": "abc123", "title": "Buy Milk"}}Frontend (Vite):VITE_API_URL=https://firstcrud-spring.onrender.com/apifetch(`${import.meta.env.VITE_API_URL}/todos`)Stack Cost: $0 💰✅ MongoDB Atlas: 512MB free✅ Render: 750 hours free✅ GitHub: Free✅ Docker Hub: FreeYou can see the live demo project here -: https://springboottodo.vercel.app/Github Link -: Link(Note : Render free tier is slow due to cold start of server so if the application is not active then it takes more time to respond in that case wait for 2 to 3 minutes.)

SpringBoot

LeetCode 36: Valid Sudoku Explained – Java Solutions, Intuition & Formula Dry Run

IntroductionSudoku is a universally beloved puzzle, but validating a Sudoku boardalgorithmically is a classic technical interview question. In this post, we aregoing to dive deep into LeetCode 36: Valid Sudoku.We won't just look at the code; we will explore the intuition behind the problemso you don't have to memorize anything. We’ll cover an ingenious in-placevalidation approach, break down the complex math formula used to check3 \times 3 sub-boxes, and look at an alternative optimal solution usingHashSets.Let's dive in!Understanding the ProblemThe problem asks us to determine if a partially filled 9 \times 9 Sudoku boardis valid. To be valid, the filled cells must follow three straightforward rules:1. Each row must contain the digits 1-9 without repetition.2. Each column must contain the digits 1-9 without repetition.3. Each of the nine 3 \times 3 sub-boxes must contain the digits 1-9 withoutrepetition.Important Note: A valid board doesn't mean the board is fully solvable! We onlycare about checking the numbers that are currently on the board.Intuition: How to Think About the ProblemBefore writing code, how do we, as humans, check if a Sudoku board is valid? Ifyou place a 5 in a cell, you quickly scan horizontally (its row), vertically(its column), and within its small 3 \times 3 square. If you see another 5, theboard is invalid.To translate this to code, we have two choices:1. The Simulation Approach: Go cell by cell. Pick up the number, hide it, andcheck its row, column, and 3 \times 3 box to see if that number existsanywhere else. (This is the approach we will look at first).2. The Memory Approach: Go cell by cell, but keep a "notebook" (like a HashTable) of everything we have seen so far. If we see a number we've alreadywritten down for a specific row, column, or box, it's invalid.Approach 1: The In-Place Validation (Space-Optimized)Here is a brilliant solution that validates the board without using any extradata structures.The Logic: Iterate through every cell on the board. When we find a number, wetemporarily replace it with a . (empty space). Then, we iterate 9 times to checkits entire row, column, and sub-box. If the number is found, we return false.Otherwise, we put the number back and move to the next cell.The Java Codeclass Solution {public boolean isvalid(char[][] board, int i, int j, char k) {for(int m = 0; m < 9; m++) {// Check rowif(board[i][m] == k) return false;// Check columnif(board[m][j] == k) return false;// Check 3x3 sub-boxif(board[3 * (i / 3) + m / 3][3 * (j / 3) + m % 3] == k) return false;}return true;}public boolean isValidSudoku(char[][] board) {for(int i = 0; i < board.length; i++) {for(int j = 0; j < board[0].length; j++) {if(board[i][j] != '.') {char temp = board[i][j];board[i][j] = '.'; // Temporarily remove the numberif(!isvalid(board, i, j, temp)) {return false;}board[i][j] = temp; // Put the number back}}}return true;}}The Math Breakdown: Demystifying the 3 \times 3 Grid FormulaThe hardest part of this code to understand is this exact line: board[3*(i/3) +m/3][3*(j/3) + m%3]How does a single loop variable m (from 0 to 8) traverse a 3 \times 3 grid?Let’s do a dry run.Step 1: Finding the Starting Point of the BoxThe grid is 9 \times 9, broken into nine 3 \times 3 boxes. If we are at a randomcell, say row i = 4, col j = 5, which box are we in? Because integer division inJava drops the decimal:i / 3 = 4 / 3 = 1j / 3 = 5 / 3 = 1Now multiply by 3 to get the actual starting coordinates (top-left corner) ofthat specific sub-box:3 * 1 = 3 (Row offset)3 * 1 = 3 (Col offset) So, the 3 \times 3 box starts at row 3, col 3.Step 2: Traversing the Box (Dry Run)Now, as m goes from 0 to 8, we use m / 3 for rows and m % 3 for columns:m = 0: row offset 0/3 = 0, col offset 0%3 = 0 \rightarrow Checks (3+0, 3+0) = (3, 3)m = 1: row offset 1/3 = 0, col offset 1%3 = 1 \rightarrow Checks (3+0, 3+1) = (3, 4)m = 2: row offset 2/3 = 0, col offset 2%3 = 2 \rightarrow Checks (3+0, 3+2) = (3, 5)m = 3: row offset 3/3 = 1, col offset 3%3 = 0 \rightarrow Checks (3+1, 3+0) = (4, 3)m = 4: row offset 4/3 = 1, col offset 4%3 = 1 \rightarrow Checks (3+1, 3+1) = (4, 4)...and so on up to m = 8.This brilliant math formula maps a 1D loop (0 to 8) directly onto a 2D3 \times 3 grid perfectly! No nested loops needed inside the isvalid function.Approach 2: The HashSet Solution (Single Pass)While the first approach is highly space-efficient, it does a bit of redundantchecking. An alternative approach that interviewers love is using a HashSet.Instead of checking rows and columns every time we see a number, we generate aunique "string signature" for every number and attempt to add it to a HashSet.If we see a 5 at row 0 and col 1, we create three strings:1. "5 in row 0"2. "5 in col 1"3. "5 in block 0-0"The HashSet.add() method returns false if the item already exists in the set. Ifit returns false, we instantly know the board is invalid!HashSet Java Code:class Solution {public boolean isValidSudoku(char[][] board) {HashSet<String> seen = new HashSet<>();for (int i = 0; i < 9; i++) {for (int j = 0; j < 9; j++) {char number = board[i][j];if (number != '.') {// HashSet.add() returns false if the element already existsif (!seen.add(number + " in row " + i) ||!seen.add(number + " in col " + j) ||!seen.add(number + " in block " + i/3 + "-" + j/3)) {return false;}}}}return true;}}Notice how we use i/3 + "-" + j/3 to identify the blocks. Top-left is block 0-0,bottom-right is block 2-2.Time and Space Complexity BreakdownInterviewers will always ask for your complexity analysis. Because a Sudokuboard is strictly fixed at 9 \times 9, the strict Big-O is actually constant.However, let's look at it conceptually as if the board were N \times N.Approach 1: In-Place Validation (Your Solution)Time Complexity: O(1) (Strictly speaking). We traverse 81 cells, and foreach cell, we do at most 9 iterations. 81 \times 9 = 729 operations. Since729 is a constant, it's O(1). (If the board was N \times N, time complexitywould be O(N^3) because for N^2 cells, we iterate N times).Space Complexity: O(1). We only use primitive variables (i, j, k, m, temp).No extra memory is allocated.Approach 2: HashSet ApproachTime Complexity: O(1). We traverse the 81 cells exactly once. Generatingstrings and adding to a HashSet takes O(1) time. (If the board wasN \times N, time complexity would be O(N^2)).Space Complexity: O(1). The HashSet will store a maximum of81 \times 3 = 243 strings. Since this upper limit is fixed, space isconstant.ConclusionThe Valid Sudoku problem is a fantastic exercise in matrix traversal andcoordinate math.When solving this in an interview:1. Use the first approach if you want to impress the interviewer with O(1)space complexity and your deep understanding of math formulas (the /3 and %3trick).2. Use the second approach (HashSet) if you want to show off your knowledge ofdata structures and write highly readable, clean, and clever code.I hope this breakdown gives you the intuition needed so you never have tomemorize the code for LeetCode 36!Happy Coding! Keep Learning🤟

LeetCodeJavaMatrixHash TableRecursionBacktrackingMedium

LeetCode 1752: Check if Array Is Sorted and Rotated – Java Solution Explained

IntroductionLeetCode 1752 – Check if Array Is Sorted and Rotated is a classic array observation problem that tests your understanding of:Sorted arraysRotation logicCircular traversalEdge case handlingPattern recognitionAt first, many developers overcomplicate this problem by trying to actually rotate arrays and compare them. However, the problem can be solved using a very elegant observation.This problem is commonly asked in coding interviews because it evaluates:Logical thinkingArray traversal skillsOptimization abilityUnderstanding of rotated arraysProblem Link🔗 https://leetcode.com/problems/check-if-array-is-sorted-and-rotated/Problem StatementGiven an array:numsReturn:trueif the array was originally sorted in non-decreasing order and then rotated some number of times.Otherwise return:falseDuplicates are allowed.Understanding RotationSuppose the original sorted array is:[1,2,3,4,5]After rotation:[3,4,5,1,2]The array is still almost sorted except for one “breaking point”.Key ObservationA sorted rotated array can have:At most one decreasing pairExample:[3,4,5,1,2]Breaking point:5 > 1Only once.Invalid Example[2,1,3,4]Breaking points:2 > 1and circularly:4 > 2Two breaking points.So answer is:falseBrute Force ApproachIntuitionTry all possible rotations.For every rotation:Rotate arrayCheck if sortedIf any rotation works → return trueBrute Force AlgorithmFor every rotation count:Create rotated arrayVerify sorted orderIf sorted:return trueElse:return falseBrute Force ComplexityTime ComplexityO(N²)because each rotation requires traversal.Space ComplexityO(N)This solution:Finds rotation pointSorts arrayRotates sorted arrayCompares with originalThis is a valid simulation-based approach.Java Solutionclass Solution { public boolean check(int[] nums) { int[] arr = new int[nums.length]; int o = 0; int mini = Integer.MIN_VALUE; int temp = 0; int maxnumind = 0; for(int a : nums) { arr[o] = a; temp = mini; mini = Math.max(mini, a); if(mini != temp) { maxnumind = o; } o++; } for(int i = 0; i < nums.length - 1; i++) { if(nums[i] > nums[i + 1]) { maxnumind = i; } } int ro = nums.length - maxnumind - 1; Arrays.sort(nums); int[] rotarr = new int[nums.length]; for(int i = 0; i < nums.length; i++) { rotarr[i] = nums[(i + ro) % nums.length]; } for(int i = 0; i < arr.length; i++) { if(rotarr[i] != arr[i]) { return false; } } return true; }}Optimized Approach (Best Solution)We do not need:SortingExtra arraysRotation simulationWe only count:decreasing pairsOptimized IntuitionFor a valid rotated sorted array:nums[i] > nums[i+1]can happen only once.Also check circular condition:last element > first elementOptimized Java Solutionclass Solution { public boolean check(int[] nums) { int count = 0; for(int i = 0; i < nums.length; i++) { if(nums[i] > nums[(i + 1) % nums.length]) { count++; } } return count <= 1; }}Why This WorksIf array is sorted and rotated:Sequence increases normallyOnly one position breaks orderIf more than one break exists:Not a rotated sorted arrayDry RunInputnums = [3,4,5,1,2]Step 1Compare adjacent elements:3 < 44 < 55 > 1 ← breaking point1 < 22 < 3 (circular)Breaking points:1Valid.Return:trueAnother Dry RunInputnums = [2,1,3,4]Comparisons:2 > 1 ← break1 < 33 < 44 > 2 ← circular breakBreaking points:2Invalid.Return:falseTime Complexity AnalysisTime ComplexityO(N log N)because of sorting.Space ComplexityO(N)extra arrays used.Optimized ApproachTime ComplexityO(N)single traversal.Space ComplexityO(1)Comparison of ApproachesApproachTime ComplexitySpace ComplexityRotation SimulationO(N log N)O(N)Decreasing Pair CountO(N)O(1)Interview ExplanationIn interviews, explain:A sorted rotated array can contain only one position where the order decreases. By counting such breaking points including circular comparison, we can determine validity in linear time.This demonstrates:Pattern recognitionCircular traversal understandingOptimization thinkingCommon Mistakes1. Forgetting Circular CheckAlways compare:nums[n-1] > nums[0]using modulo.2. Actually Rotating ArraysUnnecessary and inefficient.3. Using Strictly Increasing LogicDuplicates are allowed.So:1,1,2,2is valid.FAQsQ1. Why use modulo?To compare:last element with first elementcircularly.Q2. Why is only one break allowed?Because rotation shifts sorted order only once.Q3. Is sorting required?No.Observation-based traversal is enough.Q4. Is this problem important for interviews?Yes.It tests:Array logicRotationsOptimizationObservation skillsRelated ProblemsAfter mastering this problem, practice:Search in Rotated Sorted ArrayFind Minimum in Rotated Sorted ArrayFind Minimum in Rotated Sorted Array IIConclusionLeetCode 1752 is an excellent observation-based array problem.It teaches:Rotated array logicCircular traversalOptimization techniquesPattern recognitionThe key insight is:A sorted rotated array can have at most one decreasing point.Once you understand this observation, the optimized solution becomes extremely clean and efficient.

LeetCodeJavaArrayRotation ProblemsSortingEasy

Valid Anagram – Frequency Counting Pattern Explained (LeetCode 242)

🔗 Problem LinkLeetCode 242 – Valid Anagram 👉 https://leetcode.com/problems/valid-anagram/IntroductionThis is one of the most important string frequency problems in coding interviews.The idea of checking whether two strings are anagrams appears in many variations:Group AnagramsRansom NoteFind the DifferencePermutation in StringIf you master this pattern, you unlock a whole category of problems.Let’s break it down step by step.📌 Problem UnderstandingTwo strings are anagrams if:They contain the same charactersWith the same frequenciesOrder does not matterExample 1Input: s = "anagram" t = "nagaram"Output: trueBoth contain:a → 3n → 1g → 1r → 1m → 1Example 2Input: s = "rat" t = "car"Output: falseDifferent character frequencies.🧠 IntuitionThe core idea:If two strings are anagrams, their character frequencies must match exactly.So we:Check if lengths are equal.Count frequency of characters in first string.Subtract frequencies using second string.If at any point frequency becomes negative → not anagram.💻 Your Codeclass Solution { public boolean isAnagram(String s, String t) { if(s.length() != t.length()) return false; HashMap<Character,Integer> mp = new HashMap<>(); for(int i =0;i<s.length();i++){ mp.put(s.charAt(i),mp.getOrDefault(s.charAt(i),0)+1); } for(int i =0; i < t.length();i++){ if(mp.containsKey(t.charAt(i)) && mp.get(t.charAt(i)) > 0){ mp.put(t.charAt(i),mp.get(t.charAt(i))-1); }else{ return false; } } return true; }}🔍 Step-by-Step Explanation1️⃣ Length Checkif(s.length() != t.length()) return false;If lengths differ → cannot be anagrams.2️⃣ Build Frequency Mapmp.put(s.charAt(i), mp.getOrDefault(s.charAt(i), 0) + 1);Count occurrences of each character in s.3️⃣ Subtract Using Second Stringif(mp.containsKey(t.charAt(i)) && mp.get(t.charAt(i)) > 0)If character exists and frequency is available → reduce it.Otherwise → return false immediately.🎯 Why This WorksWe treat:First string as frequency builderSecond string as frequency consumerIf all frequencies match perfectly, we return true.⏱ Complexity AnalysisTime Complexity: O(n)One pass to build mapOne pass to compareSpace Complexity: O(26) ≈ O(1)Only lowercase English letters allowed.🔥 Optimized Approach – Using Array Instead of HashMapSince the problem guarantees:s and t consist of lowercase English lettersWe can replace HashMap with an integer array of size 26.This is faster and cleaner.Optimized Versionclass Solution { public boolean isAnagram(String s, String t) { if(s.length() != t.length()) return false; int[] freq = new int[26]; for(char c : s.toCharArray()){ freq[c - 'a']++; } for(char c : t.toCharArray()){ freq[c - 'a']--; if(freq[c - 'a'] < 0){ return false; } } return true; }}🚀 Why This Is BetterNo HashMap overheadDirect index accessCleaner codeFaster in interviews🏁 Final ThoughtsThis problem teaches:Frequency counting patternEarly exit optimizationUsing arrays instead of HashMap when character set is limitedThinking in terms of resource balanceValid Anagram is a foundation problem.Once you master it, you can easily solve:Ransom NoteFind the DifferenceGroup AnagramsCheck Equal Character Occurrences

HashMapStringFrequency CountArraysLeetCodeEasy

Reverse Only Letters – Two Pointer Strategy Explained (LeetCode 917)

🔗 Problem LinkLeetCode 917 – Reverse Only Letters 👉 https://leetcode.com/problems/reverse-only-letters/IntroductionThis is a very clean two-pointer problem.The challenge is not just reversing a string — it’s reversing only the letters while keeping all non-letter characters in their original positions.This problem strengthens:Two pointer techniqueCharacter validation logicIn-place string manipulationLet’s break it down.📌 Problem UnderstandingYou are given a string s.Rules:All non-English letters must remain at the same index.Only English letters (uppercase or lowercase) should be reversed.Return the modified string.Example 1Input: "ab-cd"Output: "dc-ba"Only letters are reversed. Hyphen stays at same position.Example 2Input: "a-bC-dEf-ghIj"Output: "j-Ih-gfE-dCba"Example 3Input: "Test1ng-Leet=code-Q!"Output: "Qedo1ct-eeLg=ntse-T!"Notice:Numbers, -, =, ! stay fixed.Only letters move.🧠 IntuitionThe first thought might be:Extract all lettersReverse themPut them backBut that would require extra space.Instead, we can solve this efficiently using Two Pointers.🚀 Two Pointer ApproachWe use:i → starting from leftj → starting from rightSteps:Convert string into char array.Move i forward until it points to a letter.Move j backward until it points to a letter.Swap letters.Continue until i < j.💻 Your Codeclass Solution { public String reverseOnlyLetters(String s) { int i = 0; int j = s.length() - 1; char arr[] = s.toCharArray(); while(i < j){ boolean l = ('A' <= s.charAt(i) && s.charAt(i) <= 'Z') || ('a' <= s.charAt(i) && s.charAt(i) <= 'z'); boolean r = ('A' <= s.charAt(j) && s.charAt(j) <= 'Z') || ('a' <= s.charAt(j) && s.charAt(j) <= 'z'); if(l && r){ char temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; i++; j--; }else if(l){ j--; }else if(r){ i++; }else{ i++; j--; } } return new String(arr); }}🔍 Step-by-Step Explanation1️⃣ Convert to Character Arraychar arr[] = s.toCharArray();Strings are immutable in Java. So we convert to char array to modify it.2️⃣ Initialize Two Pointersint i = 0;int j = s.length() - 1;We start from both ends.3️⃣ Check If Characters Are Lettersboolean l = ('A' <= s.charAt(i) && s.charAt(i) <= 'Z') || ('a' <= s.charAt(i) && s.charAt(i) <= 'z');You manually check ASCII ranges for uppercase and lowercase letters.Same logic for r.4️⃣ Swap When Both Are Lettersif(l && r){ char temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; i++; j--;}Only swap letters.5️⃣ Move Pointers When One Is Not LetterIf left is letter but right is not → move jIf right is letter but left is not → move iIf both are not letters → move bothThis ensures:Non-letter characters remain in their positions.🎯 Why This WorksWe never move non-letter characters.We only swap valid letters.Since we use two pointers:Time complexity stays linear.No extra array needed for letters.⏱ Complexity AnalysisTime Complexity: O(n)Each character is visited at most once.Space Complexity: O(n)Because we convert string to char array.(If considering output string creation, still O(n))🔥 Cleaner OptimizationInstead of manually checking ASCII ranges, Java provides:Character.isLetter(c)Cleaner version:class Solution { public String reverseOnlyLetters(String s) { int i = 0, j = s.length() - 1; char[] arr = s.toCharArray(); while(i < j){ if(!Character.isLetter(arr[i])){ i++; }else if(!Character.isLetter(arr[j])){ j--; }else{ char temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; i++; j--; } } return new String(arr); }}Much cleaner and readable.🏁 Final ThoughtsThis problem teaches:Two pointer patternIn-place string reversalCharacter validation logicClean pointer movement strategyIt’s a simple but powerful pattern that appears often in interviews.If you master this, you can easily solve:Reverse Vowels of a StringValid PalindromeReverse String IIPalindrome with One Removal

Two PointersString ManipulationLeetCodeEasy

Range Sum Query - Immutable

LeetCode Problem 303Link of the Problem to try -: LinkGiven an integer array nums, handle multiple queries of the following type:Calculate the sum of the elements of nums between indices left and right inclusive where left <= right.Implement the NumArray class:NumArray(int[] nums) Initializes the object with the integer array nums.int sumRange(int left, int right) Returns the sum of the elements of nums between indices left and right inclusive (i.e. nums[left] + nums[left + 1] + ... + nums[right]).Example 1:Input["NumArray", "sumRange", "sumRange", "sumRange"][[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]Output[null, 1, -1, -3]ExplanationNumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);numArray.sumRange(0, 2); // return (-2) + 0 + 3 = 1numArray.sumRange(2, 5); // return 3 + (-5) + 2 + (-1) = -1numArray.sumRange(0, 5); // return (-2) + 0 + 3 + (-5) + 2 + (-1) = -3Constraints:1 <= nums.length <= 104-105 <= nums[i] <= 1050 <= left <= right < nums.lengthAt most 104 calls will be made to sumRange.Solution:Efficient Range Sum Queries using Prefix SumsWhile this problem may initially seem challenging, the solution is remarkably elegant. The key is to shift the heavy lifting from the query phase to the initialization phase using a Prefix Sum array.The StrategyInstead of calculating the sum from scratch every time a range is requested, we use two steps:The Constructor: During initialization, we create a Prefix Sum array. Each index i in this new array stores the cumulative sum of all elements from the beginning of the original array up to i.The sumRange Method: To find the sum between a left and right pointer, we simply use the precalculated values. The sum of the range is calculated as:Sum(left, right) = PrefixSum[right] - PrefixSum[left - 1]Why This is BetterBy pre-calculating the sums in the constructor, we transform the sumRange operation from a slow O(n) search into a lightning-fast O(1) constant-time lookup. This approach is highly efficient for applications where the data remains the same but the number of queries is high.Code:class NumArray {int[] ans ;public NumArray(int[] nums) {ans = new int[nums.length];int pre =0;for(int i=0;i<nums.length;i++){pre += nums[i];ans[i] = pre;}}public int sumRange(int left, int right) {if(left == 0) return ans[right];return ans[right]-ans[left-1];}}/*** Your NumArray object will be instantiated and called as such:* NumArray obj = new NumArray(nums);* int param_1 = obj.sumRange(left,right);*/

LeetCodeEasyPrefix Sum

Find the Difference – Smart ASCII Sum Trick (LeetCode 389)

🔗 Problem LinkLeetCode 389 – Find the Difference 👉 https://leetcode.com/problems/find-the-difference/IntroductionThis is a very clever problem.At first glance, you might think:Use a HashMapCount frequenciesCompare both stringsBut there’s a much smarter and cleaner way to solve it using character arithmetic (ASCII values).This problem teaches an important lesson:Sometimes math can replace extra space.Let’s break it down.📌 Problem UnderstandingYou are given two strings:stString t is created by:Shuffling string sAdding one extra character at a random positionYour task:Return the extra character added to t.Example 1Input: s = "abcd" t = "abcde"Output: "e"Example 2Input: s = "" t = "y"Output: "y"🧠 First Intuition (Brute Force Thinking)When solving this for the first time, a common approach would be:Count frequency of characters in sCount frequency of characters in tCompare bothThe one with extra count is the answerThat works in O(n) time and O(26) space.But we can do better.🚀 Smarter Approach – ASCII Sum Trick💡 Key InsightCharacters are stored as integer ASCII values.If:We add all ASCII values of characters in tSubtract all ASCII values of characters in sWhat remains?👉 The ASCII value of the extra character.Because:All matching characters cancel out.Only the added character remains.💻 Your Codeclass Solution { public char findTheDifference(String s, String t) { int tot = 0; for(int i = 0; i < t.length(); i++){ tot += (int)t.charAt(i); } for(int i = 0; i < s.length(); i++){ tot -= (int)s.charAt(i); } return (char)tot; }}🔍 Step-by-Step Explanation1️⃣ Initialize Totalint tot = 0;This will store the running ASCII difference.2️⃣ Add All Characters of ttot += (int)t.charAt(i);We add ASCII values of every character in t.3️⃣ Subtract All Characters of stot -= (int)s.charAt(i);We subtract ASCII values of every character in s.4️⃣ Return Remaining Characterreturn (char)tot;After subtraction, only the extra character’s ASCII value remains.We convert it back to char.🎯 Why This WorksLet’s take example:s = "abcd"t = "abcde"ASCII Sum:t = a + b + c + d + es = a + b + c + dSubtract:(t sum) - (s sum) = eEverything cancels except the extra letter.Simple and powerful.⏱ Complexity AnalysisTime Complexity: O(n)One loop over tOne loop over sSpace Complexity: O(1)No extra data structure used.🔥 Even Smarter Approach – XOR TrickAnother elegant method is using XOR:Why XOR Works?Properties:a ^ a = 0a ^ 0 = aXOR is commutativeIf we XOR all characters in both strings:Matching characters cancel out.Only the extra character remains.XOR Versionclass Solution { public char findTheDifference(String s, String t) { char result = 0; for(char c : s.toCharArray()){ result ^= c; } for(char c : t.toCharArray()){ result ^= c; } return result; }}This is considered the most elegant solution.🏁 Final ThoughtsThis problem teaches:Thinking beyond brute forceUsing mathematical propertiesUnderstanding ASCII representationUsing XOR smartlySometimes the best solution is not about data structures — it’s about recognizing hidden math patterns.

StringMath TrickASCIIBit ManipulationLeetCodeEasy

Ransom Note – Frequency Counting Made Simple (LeetCode 383)

🔗 Problem LinkLeetCode 383 – Ransom Note 👉 https://leetcode.com/problems/ransom-note/IntroductionThis is a classic frequency-count problem that tests your understanding of:Character countingHashMap usageGreedy validation logicAt first glance, the problem looks very simple — but it’s a very common interview question because it checks whether you can think in terms of resource usage.Here:magazine → available resourcesransomNote → required resourcesWe must check if the available letters are sufficient to construct the ransom note.📌 Problem UnderstandingYou are given:ransomNotemagazineRules:Each letter in magazine can be used only once.Return true if ransomNote can be formed.Otherwise return false.Example 1Input: ransomNote = "a", magazine = "b"Output: falseExample 2Input: ransomNote = "aa", magazine = "ab"Output: falseExample 3Input: ransomNote = "aa", magazine = "aab"Output: true🧠 IntuitionThe logic is straightforward:Count frequency of each character in magazine.For each character in ransomNote:Check if it exists in the map.Check if its frequency is greater than 0.Reduce frequency after using it.If at any point we cannot use a character → return false.This is a greedy approach.💻 Your Codeclass Solution { public boolean canConstruct(String r, String m) { HashMap<Character,Integer> mp = new HashMap<>(); for(int i =0 ; i < m.length();i++){ mp.put(m.charAt(i),mp.getOrDefault(m.charAt(i),0)+1); } for(int i = 0 ; i <r.length();i++){ if(mp.containsKey(r.charAt(i)) && mp.get(r.charAt(i)) > 0){ mp.put(r.charAt(i),mp.get(r.charAt(i)) -1); }else{ return false; } } return true; }}🔍 Step-by-Step Explanation1️⃣ Build Frequency Map from MagazineHashMap<Character,Integer> mp = new HashMap<>();for(int i =0 ; i < m.length();i++){ mp.put(m.charAt(i), mp.getOrDefault(m.charAt(i),0) + 1);}We count how many times each character appears in the magazine.2️⃣ Check Each Character in Ransom Notefor(int i = 0 ; i < r.length();i++){For every character in ransomNote:3️⃣ Validate Availabilityif(mp.containsKey(r.charAt(i)) && mp.get(r.charAt(i)) > 0)If:Character exists in mapFrequency is still availableThen reduce its count:mp.put(r.charAt(i), mp.get(r.charAt(i)) - 1);Otherwise:return false;Immediately stop if we cannot construct.🎯 Why This WorksWe treat:magazine as supplyransomNote as demandWe reduce supply every time we use a character.If supply runs out → construction fails.⏱ Complexity AnalysisTime Complexity: O(n + m)One pass to build map from magazineOne pass to check ransomNoteSpace Complexity: O(26) ≈ O(1)Only lowercase English letters.🔥 Even Better Optimization – Using Array Instead of HashMapSince we know:Only lowercase letters are allowedWe can use an integer array of size 26.This is faster and more memory-efficient.Optimized Versionclass Solution { public boolean canConstruct(String r, String m) { int[] freq = new int[26]; for(char c : m.toCharArray()){ freq[c - 'a']++; } for(char c : r.toCharArray()){ if(freq[c - 'a'] == 0){ return false; } freq[c - 'a']--; } return true; }}This avoids HashMap overhead.🏁 Final ThoughtsThis problem reinforces:Frequency counting patternGreedy character usageEarly exit for optimizationUsing arrays instead of HashMap when character set is limitedIt’s a foundational problem that appears often in interviews.If you master this pattern, you can easily solve:Valid AnagramFind the DifferenceCheck if All Characters Have Equal OccurrencesPermutation in String

HashMapStringFrequency CountGreedyLeetCodeEasy