{"id":490,"date":"2026-06-21T20:25:50","date_gmt":"2026-06-21T20:25:50","guid":{"rendered":"https:\/\/paknoteshub.online\/?page_id=490"},"modified":"2026-06-21T20:30:36","modified_gmt":"2026-06-21T20:30:36","slug":"dsa","status":"publish","type":"page","link":"https:\/\/paknoteshub.online\/?page_id=490","title":{"rendered":"DSA"},"content":{"rendered":"\t\t
\n\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\r\n\r\n\r\n \r\n \r\n Data Structures & Algorithms \u2013 University Level \u2013 Pak Notes Hub<\/title>\r\n <link href=\"https:\/\/fonts.googleapis.com\/css2?family=Inter:wght@400;500;600;700&family=Fira+Code:wght@400;500&display=swap\" rel=\"stylesheet\"\/>\r\n <style>\r\n *, *::before, *::after { box-sizing: border-box; margin: 0; padding: 0; }\r\n :root {\r\n --green: #1a7a4a;\r\n --green-dark: #145f38;\r\n --green-light: #e8f5ee;\r\n --teal: #17a589;\r\n --accent: #f0b127;\r\n --dark: #1c2833;\r\n --mid: #566573;\r\n --light: #f4f6f7;\r\n --code-bg: #f0f4f8;\r\n --code-border: #2e86c1;\r\n --note-bg: #fef9e7;\r\n --note-border: #f0b127;\r\n --white: #ffffff;\r\n --radius: 10px;\r\n --shadow: 0 4px 24px rgba(26,122,74,.10);\r\n }\r\n html { scroll-behavior: smooth; }\r\n body { font-family: 'Inter', sans-serif; background: #f2f6f3; color: var(--dark); line-height: 1.7; font-size: 15px; }\r\n\r\n \/* NAV *\/\r\n nav { position: sticky; top: 0; z-index: 100; background: var(--green-dark); padding: 0 2rem; display: flex; align-items: center; justify-content: space-between; height: 56px; box-shadow: 0 2px 12px rgba(0,0,0,.25); }\r\n .nav-brand { color: #fff; font-weight: 700; font-size: 1.05rem; }\r\n .nav-brand span { color: #a9dfbf; }\r\n .nav-links { display: flex; gap: 1.2rem; }\r\n .nav-links a { color: #d5f5e3; font-size: .85rem; font-weight: 500; text-decoration: none; transition: color .2s; }\r\n .nav-links a:hover { color: #fff; }\r\n\r\n \/* HERO *\/\r\n .hero { background: linear-gradient(135deg, var(--green) 0%, #145f38 60%, #0d4527 100%); padding: 5rem 2rem 4rem; text-align: center; position: relative; overflow: hidden; }\r\n .hero::before { content: '\u2211'; position: absolute; right: 6%; top: 50%; transform: translateY(-50%); font-size: 9rem; font-family: 'Times New Roman', serif; color: rgba(255,255,255,.06); font-weight: 700; pointer-events: none; }\r\n .hero-tag { display: inline-block; background: rgba(255,255,255,.12); color: #a9dfbf; font-size: .78rem; font-weight: 600; letter-spacing: 1.5px; text-transform: uppercase; padding: .35rem 1rem; border-radius: 100px; margin-bottom: 1.2rem; border: 1px solid rgba(169,223,163,.3); }\r\n .hero h1 { color: #fff; font-size: clamp(1.8rem, 5vw, 3rem); font-weight: 700; line-height: 1.15; margin-bottom: .8rem; }\r\n .hero h1 span { color: #a9dfbf; }\r\n .hero p { color: #d5f5e3; font-size: 1.05rem; max-width: 600px; margin: 0 auto 2rem; }\r\n .hero-pills { display: flex; flex-wrap: wrap; justify-content: center; gap: .7rem; }\r\n .pill { background: rgba(255,255,255,.13); color: #e8f5ee; padding: .45rem 1.1rem; border-radius: 100px; font-size: .82rem; font-weight: 500; border: 1px solid rgba(255,255,255,.18); }\r\n\r\n \/* PROGRESS BAR *\/\r\n .progress-bar { position: fixed; top: 0; left: 0; height: 3px; background: var(--accent); z-index: 200; transition: width .1s linear; width: 0%; }\r\n\r\n \/* LAYOUT *\/\r\n .page-wrap { max-width: 1000px; margin: 0 auto; padding: 2.5rem 1.5rem 4rem; display: grid; grid-template-columns: 250px 1fr; gap: 2.5rem; align-items: start; }\r\n\r\n \/* SIDEBAR *\/\r\n .sidebar { position: sticky; top: 72px; background: var(--white); border-radius: var(--radius); box-shadow: var(--shadow); overflow: hidden; }\r\n .sidebar-title { background: var(--green); color: #fff; font-size: .75rem; font-weight: 700; letter-spacing: 1.2px; text-transform: uppercase; padding: .85rem 1.1rem; }\r\n .toc-list { list-style: none; padding: .5rem 0; max-height: calc(100vh - 130px); overflow-y: auto; }\r\n .toc-list li a { display: flex; align-items: center; gap: .55rem; padding: .4rem 1.1rem; color: var(--mid); font-size: .81rem; font-weight: 500; text-decoration: none; transition: all .18s; border-left: 3px solid transparent; }\r\n .toc-list li a:hover, .toc-list li a.active { color: var(--green); background: var(--green-light); border-left-color: var(--green); }\r\n .toc-num { display: inline-flex; align-items: center; justify-content: center; min-width: 20px; height: 20px; border-radius: 4px; background: var(--green-light); color: var(--green); font-size: .7rem; font-weight: 700; flex-shrink: 0; }\r\n .toc-list li a.active .toc-num { background: var(--green); color: #fff; }\r\n\r\n \/* UNIT CARD *\/\r\n .unit { background: var(--white); border-radius: var(--radius); box-shadow: var(--shadow); margin-bottom: 2.5rem; overflow: hidden; scroll-margin-top: 72px; }\r\n .unit-header { background: linear-gradient(100deg, var(--green) 0%, #1d9560 100%); padding: 1.4rem 1.8rem; }\r\n .unit-num-badge { background: rgba(255,255,255,.18); color: #a9dfbf; font-size: .72rem; font-weight: 700; letter-spacing: 1px; text-transform: uppercase; padding: .3rem .75rem; border-radius: 100px; }\r\n .unit-header h2 { color: #fff; font-size: 1.25rem; font-weight: 700; line-height: 1.25; margin-top: .35rem; }\r\n .unit-header p { color: #c8f0d8; font-size: .85rem; margin-top: .2rem; }\r\n .unit-body { padding: 1.8rem; }\r\n\r\n \/* HEADINGS & TEXT *\/\r\n .unit-body h3 { font-size: 1rem; font-weight: 700; color: var(--green); margin: 1.6rem 0 .7rem; padding-left: .85rem; border-left: 3px solid var(--green); line-height: 1.3; }\r\n .unit-body h3:first-child { margin-top: 0; }\r\n .unit-body p { color: var(--dark); margin-bottom: .7rem; }\r\n .unit-body ul { list-style: none; padding: 0; margin: .5rem 0 1rem; }\r\n .unit-body ul li { padding: .3rem 0 .3rem 1.5rem; position: relative; color: var(--dark); font-size: .93rem; }\r\n .unit-body ul li::before { content: '\u27a4'; position: absolute; left: 0; color: var(--teal); font-size: .75rem; top: .45rem; }\r\n\r\n \/* CODE BLOCK *\/\r\n .code-block { background: var(--code-bg); border-left: 4px solid var(--code-border); border-radius: 6px; padding: 1.1rem 1.3rem; margin: .9rem 0 1rem; overflow-x: auto; }\r\n .code-block pre { font-family: 'Fira Code', monospace; font-size: .83rem; color: #1a3a54; line-height: 1.75; white-space: pre; }\r\n .cm { color: #7f8c8d; } .kw { color: #1a5276; font-weight: 600; } .st { color: #1e8449; }\r\n\r\n \/* TABLES *\/\r\n .data-table { width: 100%; border-collapse: collapse; margin: .9rem 0 1.2rem; font-size: .87rem; border-radius: 8px; overflow: hidden; box-shadow: 0 1px 6px rgba(0,0,0,.06); }\r\n .data-table thead th { background: var(--green); color: #fff; padding: .7rem 1rem; text-align: left; font-weight: 600; font-size: .82rem; }\r\n .data-table tbody tr:nth-child(even) { background: var(--green-light); }\r\n .data-table tbody tr:hover { background: #d4efdf; }\r\n .data-table td { padding: .6rem 1rem; border-bottom: 1px solid #dce8e0; vertical-align: top; }\r\n .data-table td:first-child { font-weight: 600; color: var(--green-dark); }\r\n\r\n \/* BOXES *\/\r\n .info-box { background: var(--note-bg); border: 1px solid var(--note-border); border-radius: 7px; padding: .85rem 1.1rem; margin: .9rem 0; font-size: .88rem; line-height: 1.6; color: #7d6608; display: flex; align-items: flex-start; gap: .7rem; }\r\n .practice { background: var(--green-light); border: 1.5px dashed var(--green); border-radius: 8px; padding: .85rem 1.1rem; margin-top: 1.4rem; color: var(--green-dark); font-size: .88rem; font-weight: 500; }\r\n\r\n \/* BACK TO TOP *\/\r\n #back-top { position: fixed; bottom: 2rem; right: 2rem; background: var(--green); color: #fff; width: 42px; height: 42px; border-radius: 50%; border: none; cursor: pointer; font-size: 1.1rem; box-shadow: 0 4px 14px rgba(26,122,74,.35); display: flex; align-items: center; justify-content: center; opacity: 0; transition: opacity .25s, transform .25s; pointer-events: none; }\r\n #back-top.visible { opacity: 1; pointer-events: auto; }\r\n #back-top:hover { transform: translateY(-2px); }\r\n\r\n \/* CONGRATS *\/\r\n .congrats { background: linear-gradient(135deg, var(--green) 0%, #145f38 100%); border-radius: var(--radius); padding: 2.5rem 2rem; text-align: center; color: #fff; margin-bottom: 2.5rem; box-shadow: var(--shadow); }\r\n .congrats h2 { font-size: 1.8rem; margin-bottom: .5rem; }\r\n .congrats p { color: #d5f5e3; font-size: 1rem; }\r\n\r\n \/* RESPONSIVE *\/\r\n @media (max-width: 720px) {\r\n .page-wrap { grid-template-columns: 1fr; }\r\n .sidebar { position: static; display: none; }\r\n .hero::before { display: none; }\r\n nav .nav-links { display: none; }\r\n }\r\n <\/style>\r\n<\/head>\r\n<body>\r\n\r\n<div class=\"progress-bar\" id=\"progress\"><\/div>\r\n\r\n<nav>\r\n <div class=\"nav-brand\">Pak <span>Notes Hub<\/span><\/div>\r\n <div class=\"nav-links\">\r\n <a href=\"#unit-1\">Basics<\/a>\r\n <a href=\"#unit-5\">Trees<\/a>\r\n <a href=\"#unit-9\">Algorithms<\/a>\r\n <\/div>\r\n<\/nav>\r\n\r\n<section class=\"hero\">\r\n <div class=\"hero-tag\">\ud83d\udcca University Level \u2014 BS CS \/ BS IT<\/div>\r\n <h1>Data Structures &<br\/><span>Algorithms Complete Notes<\/span><\/h1>\r\n <p>Arrays \u00b7 Linked Lists \u00b7 Trees \u00b7 Graphs \u00b7 Sorting \u00b7 Searching \u00b7 Dynamic Programming \u2014 Master DSA in Easy English<\/p>\r\n <div class=\"hero-pills\">\r\n <div class=\"pill\">Time Complexity<\/div>\r\n <div class=\"pill\">Space Complexity<\/div>\r\n <div class=\"pill\">Algorithm Design<\/div>\r\n <\/div>\r\n<\/section>\r\n\r\n<div class=\"page-wrap\">\r\n\r\n <!-- SIDEBAR -->\r\n <aside class=\"sidebar\">\r\n <div class=\"sidebar-title\">\ud83d\udcda Table of Contents<\/div>\r\n <ul class=\"toc-list\">\r\n <li><a href=\"#unit-1\"><span class=\"toc-num\">1<\/span> Basics & Complexity<\/a><\/li>\r\n <li><a href=\"#unit-2\"><span class=\"toc-num\">2<\/span> Arrays & Strings<\/a><\/li>\r\n <li><a href=\"#unit-3\"><span class=\"toc-num\">3<\/span> Linked Lists<\/a><\/li>\r\n <li><a href=\"#unit-4\"><span class=\"toc-num\">4<\/span> Stack & Queue<\/a><\/li>\r\n <li><a href=\"#unit-5\"><span class=\"toc-num\">5<\/span> Trees<\/a><\/li>\r\n <li><a href=\"#unit-6\"><span class=\"toc-num\">6<\/span> Binary Search Trees<\/a><\/li>\r\n <li><a href=\"#unit-7\"><span class=\"toc-num\">7<\/span> Heaps<\/a><\/li>\r\n <li><a href=\"#unit-8\"><span class=\"toc-num\">8<\/span> Graphs<\/a><\/li>\r\n <li><a href=\"#unit-9\"><span class=\"toc-num\">9<\/span> Sorting Algorithms<\/a><\/li>\r\n <li><a href=\"#unit-10\"><span class=\"toc-num\">10<\/span> Searching<\/a><\/li>\r\n <li><a href=\"#unit-11\"><span class=\"toc-num\">11<\/span> Dynamic Programming<\/a><\/li>\r\n <li><a href=\"#unit-12\"><span class=\"toc-num\">12<\/span> Greedy Algorithms<\/a><\/li>\r\n <\/ul>\r\n <\/aside>\r\n\r\n <main>\r\n\r\n <!-- \u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550 UNIT 1 -->\r\n <div class=\"unit\" id=\"unit-1\">\r\n <div class=\"unit-header\">\r\n <div class=\"unit-num-badge\">Unit 1<\/div>\r\n <h2>Basics & Time Complexity<\/h2>\r\n <p>Foundation of Data Structures and Algorithm Analysis<\/p>\r\n <\/div>\r\n <div class=\"unit-body\">\r\n\r\n <h3>What is a Data Structure?<\/h3>\r\n <p>A <strong>data structure<\/strong> is a way to organize, store, and manage data efficiently. Different data structures are optimized for different operations.<\/p>\r\n <div class=\"info-box\">\ud83d\udca1 Think of it like choosing between a library card catalog (fast lookup), a shelf (sequential access), or a filing cabinet (organized groups).<\/div>\r\n\r\n <h3>Why Study DSA?<\/h3>\r\n <ul>\r\n <li>Write faster and more efficient code<\/li>\r\n <li>Pass technical interviews (DSA is 70% of coding interviews)<\/li>\r\n <li>Understand how databases, OS, and compilers work<\/li>\r\n <li>Optimize applications for scale<\/li>\r\n <\/ul>\r\n\r\n <h3>Big O Notation \u2013 Time Complexity<\/h3>\r\n <p>Big O describes the <strong>worst-case<\/strong> runtime as input size grows. It ignores constants and lower-order terms.<\/p>\r\n <table class=\"data-table\">\r\n <thead>\r\n <tr><th>Notation<\/th><th>Name<\/th><th>Example Operations<\/th><th>Speed<\/th><\/tr>\r\n <\/thead>\r\n <tbody>\r\n <tr><td>O(1)<\/td><td>Constant<\/td><td>Array access by index, hash lookup<\/td><td>\u26a1 Excellent<\/td><\/tr>\r\n <tr><td>O(log n)<\/td><td>Logarithmic<\/td><td>Binary search<\/td><td>\u2713 Great<\/td><\/tr>\r\n <tr><td>O(n)<\/td><td>Linear<\/td><td>Simple loop, linear search<\/td><td>\u2248 Good<\/td><\/tr>\r\n <tr><td>O(n log n)<\/td><td>Linearithmic<\/td><td>Merge sort, quick sort<\/td><td>\u26a0 Fair<\/td><\/tr>\r\n <tr><td>O(n\u00b2)<\/td><td>Quadratic<\/td><td>Bubble sort, nested loops<\/td><td>\u2717 Bad<\/td><\/tr>\r\n <tr><td>O(n\u00b3)<\/td><td>Cubic<\/td><td>Triple nested loops<\/td><td>\u2717 Worse<\/td><\/tr>\r\n <tr><td>O(2\u207f)<\/td><td>Exponential<\/td><td>Recursion without memoization<\/td><td>\u2717\u2717 Terrible<\/td><\/tr>\r\n <tr><td>O(n!)<\/td><td>Factorial<\/td><td>Permutations<\/td><td>\u2717\u2717\u2717 Impossible<\/td><\/tr>\r\n <\/tbody>\r\n <\/table>\r\n\r\n <h3>Calculating Time Complexity<\/h3>\r\n <div class=\"code-block\"><pre><span class=\"cm\">\/\/ Example 1: O(1) - Constant<\/span>\r\n<span class=\"kw\">int<\/span> getFirst(<span class=\"kw\">int<\/span>[] arr) {\r\n <span class=\"kw\">return<\/span> arr[0]; <span class=\"cm\">\/\/ Always 1 operation, regardless of array size<\/span>\r\n}\r\n\r\n<span class=\"cm\">\/\/ Example 2: O(n) - Linear<\/span>\r\n<span class=\"kw\">void<\/span> printAll(<span class=\"kw\">int<\/span>[] arr) {\r\n <span class=\"kw\">for<\/span>(<span class=\"kw\">int<\/span> i = 0; i < arr.length; i++) { <span class=\"cm\">\/\/ Loop runs n times<\/span>\r\n System.out.println(arr[i]);\r\n }\r\n}\r\n\r\n<span class=\"cm\">\/\/ Example 3: O(n\u00b2) - Quadratic<\/span>\r\n<span class=\"kw\">void<\/span> bubbleSort(<span class=\"kw\">int<\/span>[] arr) {\r\n <span class=\"kw\">for<\/span>(<span class=\"kw\">int<\/span> i = 0; i < arr.length; i++) { <span class=\"cm\">\/\/ Outer loop: n times<\/span>\r\n <span class=\"kw\">for<\/span>(<span class=\"kw\">int<\/span> j = 0; j < arr.length-1; j++) { <span class=\"cm\">\/\/ Inner loop: n times<\/span>\r\n <span class=\"cm\">\/\/ n \u00d7 n = O(n\u00b2)<\/span>\r\n }\r\n }\r\n}<\/pre><\/div>\r\n\r\n <h3>Space Complexity<\/h3>\r\n <p>Space complexity measures the <strong>extra memory<\/strong> used by an algorithm (not counting input).<\/p>\r\n <div class=\"code-block\"><pre><span class=\"cm\">\/\/ O(1) space - only uses fixed variables<\/span>\r\n<span class=\"kw\">int<\/span> sum(<span class=\"kw\">int<\/span>[] arr) {\r\n <span class=\"kw\">int<\/span> total = 0; <span class=\"cm\">\/\/ Just 1 variable<\/span>\r\n <span class=\"kw\">for<\/span>(<span class=\"kw\">int<\/span> x : arr) total += x;\r\n <span class=\"kw\">return<\/span> total;\r\n}\r\n\r\n<span class=\"cm\">\/\/ O(n) space - creates new array<\/span>\r\n<span class=\"kw\">int<\/span>[] duplicate(<span class=\"kw\">int<\/span>[] arr) {\r\n <span class=\"kw\">int<\/span>[] copy = <span class=\"kw\">new int<\/span>[arr.length]; <span class=\"cm\">\/\/ New array of size n<\/span>\r\n System.arraycopy(arr, 0, copy, 0, arr.length);\r\n <span class=\"kw\">return<\/span> copy;\r\n}<\/pre><\/div>\r\n\r\n <div class=\"practice\"><strong>\u270f\ufe0f Practice:<\/strong> What is the time complexity of: (a) Finding max in unsorted array (b) Binary search (c) Accessing element at index 5<\/div>\r\n <\/div>\r\n <\/div>\r\n\r\n <!-- \u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550 UNIT 2 -->\r\n <div class=\"unit\" id=\"unit-2\">\r\n <div class=\"unit-header\">\r\n <div class=\"unit-num-badge\">Unit 2<\/div>\r\n <h2>Arrays & Strings<\/h2>\r\n <p>Fundamental Data Structures with Contiguous Memory<\/p>\r\n <\/div>\r\n <div class=\"unit-body\">\r\n\r\n <h3>Array Basics<\/h3>\r\n <p>An <strong>array<\/strong> is a fixed-size collection of elements stored in <strong>contiguous memory<\/strong>. Fast access but slow insertion\/deletion.<\/p>\r\n <table class=\"data-table\">\r\n <thead>\r\n <tr><th>Operation<\/th><th>Time Complexity<\/th><th>Notes<\/th><\/tr>\r\n <\/thead>\r\n <tbody>\r\n <tr><td>Access element<\/td><td>O(1)<\/td><td>Direct memory access via index<\/td><\/tr>\r\n <tr><td>Search (unsorted)<\/td><td>O(n)<\/td><td>Must check each element<\/td><\/tr>\r\n <tr><td>Search (sorted)<\/td><td>O(log n)<\/td><td>Binary search<\/td><\/tr>\r\n <tr><td>Insert at end<\/td><td>O(1)<\/td><td>If space available<\/td><\/tr>\r\n <tr><td>Insert at middle<\/td><td>O(n)<\/td><td>Shift remaining elements<\/td><\/tr>\r\n <tr><td>Delete<\/td><td>O(n)<\/td><td>Shift remaining elements<\/td><\/tr>\r\n <\/tbody>\r\n <\/table>\r\n\r\n <h3>2D Arrays (Matrices)<\/h3>\r\n <p>A 2D array is an array of arrays. Think of it as a grid with rows and columns.<\/p>\r\n <div class=\"code-block\"><pre><span class=\"cm\">\/\/ 2D array declaration and access<\/span>\r\n<span class=\"kw\">int<\/span>[][] matrix = {\r\n {1, 2, 3},\r\n {4, 5, 6},\r\n {7, 8, 9}\r\n};\r\n\r\n<span class=\"cm\">\/\/ Access element at row 1, column 2<\/span>\r\n<span class=\"kw\">int<\/span> value = matrix[1][2]; <span class=\"cm\">\/\/ Returns 6<\/span>\r\n\r\n<span class=\"cm\">\/\/ Traverse 2D array<\/span>\r\n<span class=\"kw\">for<\/span>(<span class=\"kw\">int<\/span> i = 0; i < matrix.length; i++) {\r\n <span class=\"kw\">for<\/span>(<span class=\"kw\">int<\/span> j = 0; j < matrix[i].length; j++) {\r\n System.out.print(matrix[i][j] + \" \");\r\n }\r\n System.out.println();\r\n}<\/pre><\/div>\r\n\r\n <h3>Common Array Problems<\/h3>\r\n \r\n <div style=\"background: #f0f9ff; border-left: 4px solid #0284c7; padding: 1rem; margin: 1rem 0; border-radius: 4px;\">\r\n <strong>Two Pointer Technique:<\/strong> Use two pointers moving in opposite or same direction to solve problems efficiently.\r\n <\/div>\r\n\r\n <div class=\"code-block\"><pre><span class=\"cm\">\/\/ Find if array is sorted<\/span>\r\n<span class=\"kw\">boolean<\/span> isSorted(<span class=\"kw\">int<\/span>[] arr) {\r\n <span class=\"kw\">for<\/span>(<span class=\"kw\">int<\/span> i = 0; i < arr.length - 1; i++) {\r\n <span class=\"kw\">if<\/span>(arr[i] > arr[i+1]) <span class=\"kw\">return false<\/span>;\r\n }\r\n <span class=\"kw\">return true<\/span>;\r\n}\r\n\r\n<span class=\"cm\">\/\/ Reverse array using two pointers<\/span>\r\n<span class=\"kw\">void<\/span> reverse(<span class=\"kw\">int<\/span>[] arr) {\r\n <span class=\"kw\">int<\/span> left = 0, right = arr.length - 1;\r\n <span class=\"kw\">while<\/span>(left < right) {\r\n <span class=\"cm\">\/\/ Swap<\/span>\r\n <span class=\"kw\">int<\/span> temp = arr[left];\r\n arr[left] = arr[right];\r\n arr[right] = temp;\r\n left++;\r\n right--;\r\n }\r\n}<\/pre><\/div>\r\n\r\n <h3>String Manipulation<\/h3>\r\n <p>Strings are arrays of characters. Many array techniques apply to strings.<\/p>\r\n <div class=\"code-block\"><pre><span class=\"cm\">\/\/ Check if palindrome<\/span>\r\n<span class=\"kw\">boolean<\/span> isPalindrome(String s) {\r\n <span class=\"kw\">int<\/span> left = 0, right = s.length() - 1;\r\n <span class=\"kw\">while<\/span>(left < right) {\r\n <span class=\"kw\">if<\/span>(s.charAt(left) != s.charAt(right)) {\r\n <span class=\"kw\">return false<\/span>;\r\n }\r\n left++;\r\n right--;\r\n }\r\n <span class=\"kw\">return true<\/span>;\r\n}\r\n\r\n<span class=\"cm\">\/\/ Reverse string<\/span>\r\nString reverse(String s) {\r\n char[] chars = s.toCharArray();\r\n <span class=\"kw\">int<\/span> left = 0, right = chars.length - 1;\r\n <span class=\"kw\">while<\/span>(left < right) {\r\n <span class=\"kw\">char<\/span> temp = chars[left];\r\n chars[left] = chars[right];\r\n chars[right] = temp;\r\n left++;\r\n right--;\r\n }\r\n <span class=\"kw\">return new<\/span> String(chars);\r\n}<\/pre><\/div>\r\n\r\n <div class=\"practice\"><strong>\u270f\ufe0f Practice:<\/strong> (a) Find max element in array (b) Count occurrences of element (c) Rotate array by k positions<\/div>\r\n <\/div>\r\n <\/div>\r\n\r\n <!-- \u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550 UNIT 3 -->\r\n <div class=\"unit\" id=\"unit-3\">\r\n <div class=\"unit-header\">\r\n <div class=\"unit-num-badge\">Unit 3<\/div>\r\n <h2>Linked Lists<\/h2>\r\n <p>Dynamic Data Structure with Non-Contiguous Memory<\/p>\r\n <\/div>\r\n <div class=\"unit-body\">\r\n\r\n <h3>Linked List Basics<\/h3>\r\n <p>A <strong>linked list<\/strong> is a dynamic collection where elements (nodes) are linked via pointers. Unlike arrays, it uses <strong>non-contiguous memory<\/strong>.<\/p>\r\n <div class=\"code-block\"><pre><span class=\"cm\">\/\/ Node structure<\/span>\r\n<span class=\"kw\">class<\/span> Node {\r\n <span class=\"kw\">int<\/span> data;\r\n Node next;\r\n \r\n Node(<span class=\"kw\">int<\/span> data) {\r\n <span class=\"kw\">this<\/span>.data = data;\r\n <span class=\"kw\">this<\/span>.next = <span class=\"kw\">null<\/span>;\r\n }\r\n}\r\n\r\n<span class=\"cm\">\/\/ Simple linked list<\/span>\r\n<span class=\"kw\">class<\/span> LinkedList {\r\n Node head;\r\n \r\n <span class=\"cm\">\/\/ Insert at beginning - O(1)<\/span>\r\n <span class=\"kw\">void<\/span> insertFirst(<span class=\"kw\">int<\/span> data) {\r\n Node newNode = <span class=\"kw\">new<\/span> Node(data);\r\n newNode.next = head;\r\n head = newNode;\r\n }\r\n}<\/pre><\/div>\r\n\r\n <h3>Linked List Operations<\/h3>\r\n <table class=\"data-table\">\r\n <thead>\r\n <tr><th>Operation<\/th><th>Time<\/th><th>Space<\/th><th>Notes<\/th><\/tr>\r\n <\/thead>\r\n <tbody>\r\n <tr><td>Access<\/td><td>O(n)<\/td><td>O(1)<\/td><td>Must traverse from head<\/td><\/tr>\r\n <tr><td>Search<\/td><td>O(n)<\/td><td>O(1)<\/td><td>Linear search<\/td><\/tr>\r\n <tr><td>Insert at head<\/td><td>O(1)<\/td><td>O(1)<\/td><td>Very fast<\/td><\/tr>\r\n <tr><td>Insert at tail<\/td><td>O(n)<\/td><td>O(1)<\/td><td>Need to find tail<\/td><\/tr>\r\n <tr><td>Delete at head<\/td><td>O(1)<\/td><td>O(1)<\/td><td>Very fast<\/td><\/tr>\r\n <tr><td>Delete at tail<\/td><td>O(n)<\/td><td>O(1)<\/td><td>Need previous node<\/td><\/tr>\r\n <\/tbody>\r\n <\/table>\r\n\r\n <h3>Traversal & Display<\/h3>\r\n <div class=\"code-block\"><pre><span class=\"cm\">\/\/ Display all elements<\/span>\r\n<span class=\"kw\">void<\/span> display() {\r\n Node current = head;\r\n <span class=\"kw\">while<\/span>(current != <span class=\"kw\">null<\/span>) {\r\n System.out.print(current.data + \" \u2192 \");\r\n current = current.next;\r\n }\r\n System.out.println(<span class=\"st\">\"null\"<\/span>);\r\n}<\/pre><\/div>\r\n\r\n <h3>Doubly Linked List<\/h3>\r\n <p>Each node has pointers to both next AND previous nodes. Allows backward traversal.<\/p>\r\n <div class=\"code-block\"><pre><span class=\"cm\">\/\/ Doubly linked list node<\/span>\r\n<span class=\"kw\">class<\/span> DNode {\r\n <span class=\"kw\">int<\/span> data;\r\n DNode next, prev;\r\n \r\n DNode(<span class=\"kw\">int<\/span> data) {\r\n <span class=\"kw\">this<\/span>.data = data;\r\n <span class=\"kw\">this<\/span>.next = <span class=\"kw\">this<\/span>.prev = <span class=\"kw\">null<\/span>;\r\n }\r\n}<\/pre><\/div>\r\n\r\n <h3>Circular Linked List<\/h3>\r\n <p>The last node points back to the first node, forming a circle. No null at the end.<\/p>\r\n <div class=\"info-box\">\ud83d\udca1 Use cases: Round-robin scheduling, music playlists, carousel components<\/div>\r\n\r\n <div class=\"practice\"><strong>\u270f\ufe0f Practice:<\/strong> (a) Find length of linked list (b) Reverse a linked list (c) Find middle element<\/div>\r\n <\/div>\r\n <\/div>\r\n\r\n <!-- \u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550 UNIT 4 -->\r\n <div class=\"unit\" id=\"unit-4\">\r\n <div class=\"unit-header\">\r\n <div class=\"unit-num-badge\">Unit 4<\/div>\r\n <h2>Stack & Queue<\/h2>\r\n <p>Specialized Data Structures with Restricted Access Patterns<\/p>\r\n <\/div>\r\n <div class=\"unit-body\">\r\n\r\n <h3>Stack (LIFO \u2013 Last In First Out)<\/h3>\r\n <p>Think of a stack of plates. You add and remove from the <strong>same end (top)<\/strong>. Last plate added is first one removed.<\/p>\r\n <table class=\"data-table\">\r\n <thead>\r\n <tr><th>Operation<\/th><th>Time<\/th><th>Description<\/th><\/tr>\r\n <\/thead>\r\n <tbody>\r\n <tr><td>Push (add)<\/td><td>O(1)<\/td><td>Add element to top<\/td><\/tr>\r\n <tr><td>Pop (remove)<\/td><td>O(1)<\/td><td>Remove from top<\/td><\/tr>\r\n <tr><td>Peek (view)<\/td><td>O(1)<\/td><td>View top without removing<\/td><\/tr>\r\n <tr><td>isEmpty<\/td><td>O(1)<\/td><td>Check if empty<\/td><\/tr>\r\n <\/tbody>\r\n <\/table>\r\n\r\n <div class=\"code-block\"><pre><span class=\"cm\">\/\/ Stack implementation<\/span>\r\n<span class=\"kw\">class<\/span> Stack {\r\n <span class=\"kw\">private int<\/span>[] items;\r\n <span class=\"kw\">private int<\/span> top = -1;\r\n \r\n Stack(<span class=\"kw\">int<\/span> capacity) {\r\n items = <span class=\"kw\">new int<\/span>[capacity];\r\n }\r\n \r\n <span class=\"kw\">void<\/span> push(<span class=\"kw\">int<\/span> value) {\r\n items[++top] = value;\r\n }\r\n \r\n <span class=\"kw\">int<\/span> pop() {\r\n <span class=\"kw\">return<\/span> items[top--];\r\n }\r\n \r\n <span class=\"kw\">int<\/span> peek() {\r\n <span class=\"kw\">return<\/span> items[top];\r\n }\r\n \r\n <span class=\"kw\">boolean<\/span> isEmpty() {\r\n <span class=\"kw\">return<\/span> top == -1;\r\n }\r\n}<\/pre><\/div>\r\n\r\n <h3>Stack Applications<\/h3>\r\n <ul>\r\n <li><strong>Browser history:<\/strong> Back button uses stack<\/li>\r\n <li><strong>Undo\/Redo:<\/strong> All editors use stacks<\/li>\r\n <li><strong>Function calls:<\/strong> Call stack in programming<\/li>\r\n <li><strong>Expression evaluation:<\/strong> Check balanced parentheses<\/li>\r\n <li><strong>Parsing:<\/strong> Compilers use stacks<\/li>\r\n <\/ul>\r\n\r\n <div class=\"code-block\"><pre><span class=\"cm\">\/\/ Check balanced parentheses using stack<\/span>\r\n<span class=\"kw\">boolean<\/span> isBalanced(String s) {\r\n Stack<Character> st = <span class=\"kw\">new<\/span> Stack<>();\r\n \r\n <span class=\"kw\">for<\/span>(char c : s.toCharArray()) {\r\n <span class=\"kw\">if<\/span>(c == <span class=\"st\">'('<\/span> || c == <span class=\"st\">'['<\/span> || c == <span class=\"st\">'{'<\/span>) {\r\n st.push(c);\r\n } <span class=\"kw\">else if<\/span>(c == <span class=\"st\">')'<\/span> || c == <span class=\"st\">']'<\/span> || c == <span class=\"st\">'}'<\/span>) {\r\n <span class=\"kw\">if<\/span>(st.isEmpty()) <span class=\"kw\">return false<\/span>;\r\n st.pop();\r\n }\r\n }\r\n \r\n <span class=\"kw\">return<\/span> st.isEmpty();\r\n}<\/pre><\/div>\r\n\r\n <h3>Queue (FIFO \u2013 First In First Out)<\/h3>\r\n <p>Think of a queue at a movie theater. You <strong>add at the back (rear) and remove from front<\/strong>. First person in is first served.<\/p>\r\n <table class=\"data-table\">\r\n <thead>\r\n <tr><th>Operation<\/th><th>Time<\/th><th>Description<\/th><\/tr>\r\n <\/thead>\r\n <tbody>\r\n <tr><td>Enqueue<\/td><td>O(1)<\/td><td>Add to rear<\/td><\/tr>\r\n <tr><td>Dequeue<\/td><td>O(1)<\/td><td>Remove from front<\/td><\/tr>\r\n <tr><td>Peek<\/td><td>O(1)<\/td><td>View front element<\/td><\/tr>\r\n <\/tbody>\r\n <\/table>\r\n\r\n <h3>Queue Applications<\/h3>\r\n <ul>\r\n <li><strong>CPU scheduling:<\/strong> Process queue<\/li>\r\n <li><strong>Printer queue:<\/strong> Print jobs in order<\/li>\r\n <li><strong>BFS graph traversal:<\/strong> Level-order traversal<\/li>\r\n <li><strong>Message queues:<\/strong> Kafka, RabbitMQ<\/li>\r\n <\/ul>\r\n\r\n <h3>Priority Queue<\/h3>\r\n <p>Elements are removed based on <strong>priority<\/strong>, not just insertion order. Uses a heap internally.<\/p>\r\n <div class=\"info-box\">\ud83d\udca1 Example: Hospital emergency room. Critical patients served before minor injuries, regardless of arrival order.<\/div>\r\n\r\n <div class=\"practice\"><strong>\u270f\ufe0f Practice:<\/strong> (a) Implement stack using queue (b) Implement queue using stack (c) Reverse a queue<\/div>\r\n <\/div>\r\n <\/div>\r\n\r\n <!-- \u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550 UNIT 5 -->\r\n <div class=\"unit\" id=\"unit-5\">\r\n <div class=\"unit-header\">\r\n <div class=\"unit-num-badge\">Unit 5<\/div>\r\n <h2>Trees<\/h2>\r\n <p>Hierarchical Data Structure for Organizing Information<\/p>\r\n <\/div>\r\n <div class=\"unit-body\">\r\n\r\n <h3>Tree Basics<\/h3>\r\n <p>A <strong>tree<\/strong> is a hierarchical data structure with a root node and child nodes. It's a connected graph with no cycles.<\/p>\r\n <div class=\"code-block\"><pre> A (root)\r\n \/|\\\r\n B C D\r\n \/| |\r\n E F G\r\n\r\nTerminology:\r\n- Root: Top node (A)\r\n- Parent: Node with children (A is parent of B, C, D)\r\n- Children: Nodes under a parent (B, C are children of A)\r\n- Leaf: Node with no children (E, F, G)\r\n- Subtree: Tree below any node\r\n- Height: Distance from node to deepest leaf\r\n- Depth: Distance from root to node<\/pre><\/div>\r\n\r\n <h3>Binary Tree<\/h3>\r\n <p>Each node has at most <strong>2 children<\/strong> (left and right).<\/p>\r\n <div class=\"code-block\"><pre><span class=\"cm\">\/\/ Binary tree node<\/span>\r\n<span class=\"kw\">class<\/span> TreeNode {\r\n <span class=\"kw\">int<\/span> data;\r\n TreeNode left, right;\r\n \r\n TreeNode(<span class=\"kw\">int<\/span> data) {\r\n <span class=\"kw\">this<\/span>.data = data;\r\n }\r\n}<\/pre><\/div>\r\n\r\n <h3>Tree Traversals<\/h3>\r\n <p>Four main ways to visit all nodes:<\/p>\r\n <table class=\"data-table\">\r\n <thead>\r\n <tr><th>Traversal<\/th><th>Order<\/th><th>Example (see diagram)<\/th><th>Use Case<\/th><\/tr>\r\n <\/thead>\r\n <tbody>\r\n <tr><td>Inorder<\/td><td>Left \u2192 Root \u2192 Right<\/td><td>E, B, F, A, C, G, D<\/td><td>BST (sorted output)<\/td><\/tr>\r\n <tr><td>Preorder<\/td><td>Root \u2192 Left \u2192 Right<\/td><td>A, B, E, F, C, D, G<\/td><td>Copy tree, prefix notation<\/td><\/tr>\r\n <tr><td>Postorder<\/td><td>Left \u2192 Right \u2192 Root<\/td><td>E, F, B, C, G, D, A<\/td><td>Delete tree<\/td><\/tr>\r\n <tr><td>Level Order<\/td><td>Level by level<\/td><td>A, B, C, D, E, F, G<\/td><td>BFS<\/td><\/tr>\r\n <\/tbody>\r\n <\/table>\r\n\r\n <div class=\"code-block\"><pre><span class=\"cm\">\/\/ Inorder traversal (recursive)<\/span>\r\n<span class=\"kw\">void<\/span> inorder(TreeNode root) {\r\n <span class=\"kw\">if<\/span>(root == <span class=\"kw\">null<\/span>) <span class=\"kw\">return<\/span>;\r\n inorder(root.left);\r\n System.out.print(root.data + <span class=\"st\">\" \"<\/span>);\r\n inorder(root.right);\r\n}\r\n\r\n<span class=\"cm\">\/\/ Level order traversal (using queue for BFS)<\/span>\r\n<span class=\"kw\">void<\/span> levelOrder(TreeNode root) {\r\n Queue<TreeNode> q = <span class=\"kw\">new<\/span> LinkedList<>();\r\n q.add(root);\r\n \r\n <span class=\"kw\">while<\/span>(!q.isEmpty()) {\r\n TreeNode node = q.poll();\r\n System.out.print(node.data + <span class=\"st\">\" \"<\/span>);\r\n \r\n <span class=\"kw\">if<\/span>(node.left != <span class=\"kw\">null<\/span>) q.add(node.left);\r\n <span class=\"kw\">if<\/span>(node.right != <span class=\"kw\">null<\/span>) q.add(node.right);\r\n }\r\n}<\/pre><\/div>\r\n\r\n <h3>Tree Properties<\/h3>\r\n <ul>\r\n <li><strong>Perfect Binary Tree:<\/strong> All levels completely filled<\/li>\r\n <li><strong>Complete Binary Tree:<\/strong> All levels filled except possibly the last<\/li>\r\n <li><strong>Balanced Binary Tree:<\/strong> Height difference \u2264 1 for all subtrees<\/li>\r\n <li><strong>Full Binary Tree:<\/strong> Every node has 0 or 2 children<\/li>\r\n <\/ul>\r\n\r\n <div class=\"practice\"><strong>\u270f\ufe0f Practice:<\/strong> (a) Find height of tree (b) Count total nodes (c) Find sum of all nodes<\/div>\r\n <\/div>\r\n <\/div>\r\n\r\n <!-- \u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550 UNIT 6 -->\r\n <div class=\"unit\" id=\"unit-6\">\r\n <div class=\"unit-header\">\r\n <div class=\"unit-num-badge\">Unit 6<\/div>\r\n <h2>Binary Search Trees<\/h2>\r\n <p>Ordered Trees for Efficient Searching<\/p>\r\n <\/div>\r\n <div class=\"unit-body\">\r\n\r\n <h3>BST Property<\/h3>\r\n <p>A <strong>Binary Search Tree<\/strong> is a binary tree where:<\/p>\r\n <ul>\r\n <li>Left subtree has values <strong>smaller<\/strong> than root<\/li>\r\n <li>Right subtree has values <strong>greater<\/strong> than root<\/li>\r\n <li>Both left and right subtrees are also BSTs<\/li>\r\n <\/ul>\r\n\r\n <h3>BST Operations<\/h3>\r\n <table class=\"data-table\">\r\n <thead>\r\n <tr><th>Operation<\/th><th>Best Case<\/th><th>Worst Case<\/th><th>Notes<\/th><\/tr>\r\n <\/thead>\r\n <tbody>\r\n <tr><td>Search<\/td><td>O(log n)<\/td><td>O(n)<\/td><td>Worst if tree is skewed<\/td><\/tr>\r\n <tr><td>Insert<\/td><td>O(log n)<\/td><td>O(n)<\/td><td>Always at leaf<\/td><\/tr>\r\n <tr><td>Delete<\/td><td>O(log n)<\/td><td>O(n)<\/td><td>Complex if node has 2 children<\/td><\/tr>\r\n <tr><td>Inorder Traversal<\/td><td>O(n)<\/td><td>O(n)<\/td><td>Gives sorted output<\/td><\/tr>\r\n <\/tbody>\r\n <\/table>\r\n\r\n <div class=\"code-block\"><pre><span class=\"cm\">\/\/ BST Search<\/span>\r\n<span class=\"kw\">TreeNode<\/span> search(TreeNode root, <span class=\"kw\">int<\/span> key) {\r\n <span class=\"kw\">if<\/span>(root == <span class=\"kw\">null<\/span>) <span class=\"kw\">return null<\/span>;\r\n \r\n <span class=\"kw\">if<\/span>(key == root.data) <span class=\"kw\">return<\/span> root;\r\n <span class=\"kw\">else if<\/span>(key < root.data) <span class=\"kw\">return<\/span> search(root.left, key);\r\n <span class=\"kw\">else<\/span> <span class=\"kw\">return<\/span> search(root.right, key);\r\n}\r\n\r\n<span class=\"cm\">\/\/ BST Insert<\/span>\r\n<span class=\"kw\">TreeNode<\/span> insert(TreeNode root, <span class=\"kw\">int<\/span> value) {\r\n <span class=\"kw\">if<\/span>(root == <span class=\"kw\">null<\/span>) <span class=\"kw\">return new<\/span> TreeNode(value);\r\n \r\n <span class=\"kw\">if<\/span>(value < root.data) {\r\n root.left = insert(root.left, value);\r\n } <span class=\"kw\">else if<\/span>(value > root.data) {\r\n root.right = insert(root.right, value);\r\n }\r\n \r\n <span class=\"kw\">return<\/span> root;\r\n}<\/pre><\/div>\r\n\r\n <h3>BST Delete \u2013 3 Cases<\/h3>\r\n <ul>\r\n <li><strong>Node is leaf:<\/strong> Simply remove it<\/li>\r\n <li><strong>Node has 1 child:<\/strong> Replace with its child<\/li>\r\n <li><strong>Node has 2 children:<\/strong> Replace with inorder successor (smallest in right subtree), then delete successor<\/li>\r\n <\/ul>\r\n\r\n <h3>Balanced BSTs \u2013 AVL & Red-Black Trees<\/h3>\r\n <p>Regular BSTs can become skewed. Balanced trees ensure O(log n) for all operations.<\/p>\r\n <div class=\"info-box\">\ud83d\udca1 <strong>AVL Tree:<\/strong> Height difference \u2264 1. Rotations keep it balanced. <strong>Red-Black Tree:<\/strong> Used in Java HashMap, C++ map.<\/div>\r\n\r\n <div class=\"practice\"><strong>\u270f\ufe0f Practice:<\/strong> (a) Check if tree is BST (b) Find kth smallest element (c) Find LCA (Lowest Common Ancestor)<\/div>\r\n <\/div>\r\n <\/div>\r\n\r\n <!-- \u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550 UNIT 7 -->\r\n <div class=\"unit\" id=\"unit-7\">\r\n <div class=\"unit-header\">\r\n <div class=\"unit-num-badge\">Unit 7<\/div>\r\n <h2>Heaps & Priority Queues<\/h2>\r\n <p>Complete Binary Trees with Heap Property<\/p>\r\n <\/div>\r\n <div class=\"unit-body\">\r\n\r\n <h3>Heap Property<\/h3>\r\n <p>A <strong>heap<\/strong> is a complete binary tree where each parent is greater (max heap) or smaller (min heap) than its children.<\/p>\r\n <ul>\r\n <li><strong>Max Heap:<\/strong> Parent \u2265 Children. Root is maximum.<\/li>\r\n <li><strong>Min Heap:<\/strong> Parent \u2264 Children. Root is minimum.<\/li>\r\n <li><strong>Complete Binary Tree:<\/strong> All levels filled except possibly last, which is left-aligned.<\/li>\r\n <\/ul>\r\n\r\n <h3>Heap Operations<\/h3>\r\n <table class=\"data-table\">\r\n <thead>\r\n <tr><th>Operation<\/th><th>Time<\/th><th>Description<\/th><\/tr>\r\n <\/thead>\r\n <tbody>\r\n <tr><td>Insert<\/td><td>O(log n)<\/td><td>Add at end, bubble up<\/td><\/tr>\r\n <tr><td>Delete Min\/Max<\/td><td>O(log n)<\/td><td>Remove root, move last to root, bubble down<\/td><\/tr>\r\n <tr><td>Peek Min\/Max<\/td><td>O(1)<\/td><td>View root<\/td><\/tr>\r\n <tr><td>Heapify<\/td><td>O(n)<\/td><td>Build heap from array<\/td><\/tr>\r\n <\/tbody>\r\n <\/table>\r\n\r\n <div class=\"code-block\"><pre><span class=\"cm\">\/\/ Min Heap using array<\/span>\r\n<span class=\"kw\">class<\/span> MinHeap {\r\n <span class=\"kw\">private int<\/span>[] heap;\r\n <span class=\"kw\">private int<\/span> size = 0;\r\n \r\n <span class=\"cm\">\/\/ Parent: (i-1)\/2, Left: 2i+1, Right: 2i+2<\/span>\r\n \r\n <span class=\"kw\">void<\/span> insert(<span class=\"kw\">int<\/span> value) {\r\n heap[size] = value;\r\n <span class=\"fn\">bubbleUp<\/span>(size);\r\n size++;\r\n }\r\n \r\n <span class=\"kw\">void<\/span> bubbleUp(<span class=\"kw\">int<\/span> index) {\r\n <span class=\"kw\">while<\/span>(index > 0) {\r\n <span class=\"kw\">int<\/span> parent = (index - 1) \/ 2;\r\n <span class=\"kw\">if<\/span>(heap[index] < heap[parent]) {\r\n <span class=\"cm\">\/\/ Swap<\/span>\r\n <span class=\"kw\">int<\/span> temp = heap[index];\r\n heap[index] = heap[parent];\r\n heap[parent] = temp;\r\n index = parent;\r\n } <span class=\"kw\">else<\/span> <span class=\"kw\">break<\/span>;\r\n }\r\n }\r\n}<\/pre><\/div>\r\n\r\n <h3>Heap Applications<\/h3>\r\n <ul>\r\n <li><strong>Priority Queue:<\/strong> Process elements by priority<\/li>\r\n <li><strong>Dijkstra's algorithm:<\/strong> Shortest path<\/li>\r\n <li><strong>Heap Sort:<\/strong> Efficient sorting O(n log n)<\/li>\r\n <li><strong>Top K elements:<\/strong> Find k largest\/smallest efficiently<\/li>\r\n <\/ul>\r\n\r\n <div class=\"practice\"><strong>\u270f\ufe0f Practice:<\/strong> (a) Implement max heap (b) Implement heap sort (c) Find Kth largest element<\/div>\r\n <\/div>\r\n <\/div>\r\n\r\n <!-- \u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550 UNIT 8 -->\r\n <div class=\"unit\" id=\"unit-8\">\r\n <div class=\"unit-header\">\r\n <div class=\"unit-num-badge\">Unit 8<\/div>\r\n <h2>Graphs<\/h2>\r\n <p>Non-Linear Data Structure for Connected Data<\/p>\r\n <\/div>\r\n <div class=\"unit-body\">\r\n\r\n <h3>Graph Basics<\/h3>\r\n <p>A <strong>graph<\/strong> consists of <strong>vertices (nodes)<\/strong> and <strong>edges (connections)<\/strong>. Can be directed or undirected, weighted or unweighted.<\/p>\r\n <div class=\"code-block\"><pre><span class=\"cm\">\/\/ Types of Graphs:<\/span>\r\n1. Directed (Digraph): A\u2192B (one direction)\r\n2. Undirected: A\u2014B (both directions)\r\n3. Weighted: Edge has a value\/cost\r\n4. Unweighted: All edges equal\r\n\r\n<span class=\"cm\">\/\/ Density:<\/span>\r\n- Sparse: Few edges (n ~ m, where m is edges)\r\n- Dense: Many edges (m ~ n\u00b2)<\/pre><\/div>\r\n\r\n <h3>Graph Representations<\/h3>\r\n <table class=\"data-table\">\r\n <thead>\r\n <tr><th>Representation<\/th><th>Space<\/th><th>Add Edge<\/th><th>Check Edge<\/th><\/tr>\r\n <\/thead>\r\n <tbody>\r\n <tr><td>Adjacency Matrix<\/td><td>O(V\u00b2)<\/td><td>O(1)<\/td><td>O(1)<\/td><\/tr>\r\n <tr><td>Adjacency List<\/td><td>O(V+E)<\/td><td>O(1)<\/td><td>O(E)<\/td><\/tr>\r\n <tr><td>Edge List<\/td><td>O(E)<\/td><td>O(1)<\/td><td>O(E)<\/td><\/tr>\r\n <\/tbody>\r\n <\/table>\r\n\r\n <div class=\"code-block\"><pre><span class=\"cm\">\/\/ Adjacency List representation<\/span>\r\nMap<Integer, List<Integer>> graph = <span class=\"kw\">new<\/span> HashMap<>();\r\n\r\n<span class=\"cm\">\/\/ Add edge from u to v<\/span>\r\n<span class=\"kw\">void<\/span> addEdge(<span class=\"kw\">int<\/span> u, <span class=\"kw\">int<\/span> v) {\r\n graph.putIfAbsent(u, <span class=\"kw\">new<\/span> ArrayList<>());\r\n graph.get(u).add(v);\r\n}<\/pre><\/div>\r\n\r\n <h3>Graph Traversals<\/h3>\r\n \r\n <div style=\"background: #f0fdf4; border-left: 4px solid #16a34a; padding: 1rem; margin: 1rem 0; border-radius: 4px;\">\r\n <strong>BFS (Breadth-First Search):<\/strong> Level by level. Uses queue. O(V + E) time. Finds shortest path in unweighted graph.\r\n <\/div>\r\n\r\n <div style=\"background: #fef3c7; border-left: 4px solid #ea580c; padding: 1rem; margin: 1rem 0; border-radius: 4px;\">\r\n <strong>DFS (Depth-First Search):<\/strong> Go deep first. Uses stack\/recursion. O(V + E) time. Finds connected components, detect cycles.\r\n <\/div>\r\n\r\n <div class=\"code-block\"><pre><span class=\"cm\">\/\/ BFS Traversal<\/span>\r\n<span class=\"kw\">void<\/span> bfs(<span class=\"kw\">int<\/span> start) {\r\n Queue<Integer> q = <span class=\"kw\">new<\/span> LinkedList<>();\r\n Set<Integer> visited = <span class=\"kw\">new<\/span> HashSet<>();\r\n \r\n q.add(start);\r\n visited.add(start);\r\n \r\n <span class=\"kw\">while<\/span>(!q.isEmpty()) {\r\n <span class=\"kw\">int<\/span> node = q.poll();\r\n System.out.print(node + <span class=\"st\">\" \"<\/span>);\r\n \r\n <span class=\"kw\">for<\/span>(<span class=\"kw\">int<\/span> neighbor : graph.getOrDefault(node, <span class=\"kw\">new<\/span> ArrayList<>())) {\r\n <span class=\"kw\">if<\/span>(!visited.contains(neighbor)) {\r\n visited.add(neighbor);\r\n q.add(neighbor);\r\n }\r\n }\r\n }\r\n}\r\n\r\n<span class=\"cm\">\/\/ DFS Traversal (Recursive)<\/span>\r\n<span class=\"kw\">void<\/span> dfs(<span class=\"kw\">int<\/span> node, Set<Integer> visited) {\r\n visited.add(node);\r\n System.out.print(node + <span class=\"st\">\" \"<\/span>);\r\n \r\n <span class=\"kw\">for<\/span>(<span class=\"kw\">int<\/span> neighbor : graph.getOrDefault(node, <span class=\"kw\">new<\/span> ArrayList<>())) {\r\n <span class=\"kw\">if<\/span>(!visited.contains(neighbor)) {\r\n dfs(neighbor, visited);\r\n }\r\n }\r\n}<\/pre><\/div>\r\n\r\n <h3>Important Graph Algorithms<\/h3>\r\n <ul>\r\n <li><strong>Dijkstra:<\/strong> Shortest path (weighted, non-negative)<\/li>\r\n <li><strong>Bellman-Ford:<\/strong> Shortest path (handles negative weights)<\/li>\r\n <li><strong>Floyd-Warshall:<\/strong> All pairs shortest path<\/li>\r\n <li><strong>Kruskal\/Prim:<\/strong> Minimum Spanning Tree<\/li>\r\n <li><strong>Topological Sort:<\/strong> DAG ordering<\/li>\r\n <\/ul>\r\n\r\n <div class=\"practice\"><strong>\u270f\ufe0f Practice:<\/strong> (a) Detect cycle in graph (b) Find connected components (c) Topological sort<\/div>\r\n <\/div>\r\n <\/div>\r\n\r\n <!-- \u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550 UNIT 9 -->\r\n <div class=\"unit\" id=\"unit-9\">\r\n <div class=\"unit-header\">\r\n <div class=\"unit-num-badge\">Unit 9<\/div>\r\n <h2>Sorting Algorithms<\/h2>\r\n <p>Methods to Arrange Elements in Order<\/p>\r\n <\/div>\r\n <div class=\"unit-body\">\r\n\r\n <h3>Sorting Comparison<\/h3>\r\n <table class=\"data-table\">\r\n <thead>\r\n <tr><th>Algorithm<\/th><th>Best<\/th><th>Average<\/th><th>Worst<\/th><th>Space<\/th><th>Stable<\/th><\/tr>\r\n <\/thead>\r\n <tbody>\r\n <tr><td>Bubble Sort<\/td><td>O(n)<\/td><td>O(n\u00b2)<\/td><td>O(n\u00b2)<\/td><td>O(1)<\/td><td>\u2713<\/td><\/tr>\r\n <tr><td>Selection Sort<\/td><td>O(n\u00b2)<\/td><td>O(n\u00b2)<\/td><td>O(n\u00b2)<\/td><td>O(1)<\/td><td>\u2717<\/td><\/tr>\r\n <tr><td>Insertion Sort<\/td><td>O(n)<\/td><td>O(n\u00b2)<\/td><td>O(n\u00b2)<\/td><td>O(1)<\/td><td>\u2713<\/td><\/tr>\r\n <tr><td>Merge Sort<\/td><td>O(n log n)<\/td><td>O(n log n)<\/td><td>O(n log n)<\/td><td>O(n)<\/td><td>\u2713<\/td><\/tr>\r\n <tr><td>Quick Sort<\/td><td>O(n log n)<\/td><td>O(n log n)<\/td><td>O(n\u00b2)<\/td><td>O(log n)<\/td><td>\u2717<\/td><\/tr>\r\n <tr><td>Heap Sort<\/td><td>O(n log n)<\/td><td>O(n log n)<\/td><td>O(n log n)<\/td><td>O(1)<\/td><td>\u2717<\/td><\/tr>\r\n <\/tbody>\r\n <\/table>\r\n\r\n <h3>Bubble Sort \u2013 O(n\u00b2)<\/h3>\r\n <p>Repeatedly swap adjacent elements if they're in wrong order. Simplest but slowest.<\/p>\r\n <div class=\"code-block\"><pre><span class=\"cm\">\/\/ Bubble Sort<\/span>\r\n<span class=\"kw\">void<\/span> bubbleSort(<span class=\"kw\">int<\/span>[] arr) {\r\n <span class=\"kw\">int<\/span> n = arr.length;\r\n \r\n <span class=\"kw\">for<\/span>(<span class=\"kw\">int<\/span> i = 0; i < n - 1; i++) {\r\n <span class=\"cm\">\/\/ Last i elements are already sorted<\/span>\r\n <span class=\"kw\">for<\/span>(<span class=\"kw\">int<\/span> j = 0; j < n - i - 1; j++) {\r\n <span class=\"kw\">if<\/span>(arr[j] > arr[j + 1]) {\r\n <span class=\"cm\">\/\/ Swap<\/span>\r\n <span class=\"kw\">int<\/span> temp = arr[j];\r\n arr[j] = arr[j + 1];\r\n arr[j + 1] = temp;\r\n }\r\n }\r\n }\r\n}<\/pre><\/div>\r\n\r\n <h3>Quick Sort \u2013 O(n log n) average<\/h3>\r\n <p>Divide-and-conquer. Pick pivot, partition, recursively sort. Fastest in practice.<\/p>\r\n <div class=\"code-block\"><pre><span class=\"cm\">\/\/ Quick Sort<\/span>\r\n<span class=\"kw\">void<\/span> quickSort(<span class=\"kw\">int<\/span>[] arr, <span class=\"kw\">int<\/span> low, <span class=\"kw\">int<\/span> high) {\r\n <span class=\"kw\">if<\/span>(low < high) {\r\n <span class=\"kw\">int<\/span> pi = partition(arr, low, high);\r\n quickSort(arr, low, pi - 1);\r\n quickSort(arr, pi + 1, high);\r\n }\r\n}\r\n\r\n<span class=\"kw\">int<\/span> partition(<span class=\"kw\">int<\/span>[] arr, <span class=\"kw\">int<\/span> low, <span class=\"kw\">int<\/span> high) {\r\n <span class=\"kw\">int<\/span> pivot = arr[high];\r\n <span class=\"kw\">int<\/span> i = low - 1;\r\n \r\n <span class=\"kw\">for<\/span>(<span class=\"kw\">int<\/span> j = low; j < high; j++) {\r\n <span class=\"kw\">if<\/span>(arr[j] < pivot) {\r\n i++;\r\n <span class=\"cm\">\/\/ Swap arr[i] and arr[j]<\/span>\r\n <span class=\"kw\">int<\/span> temp = arr[i];\r\n arr[i] = arr[j];\r\n arr[j] = temp;\r\n }\r\n }\r\n \r\n <span class=\"cm\">\/\/ Swap arr[i+1] and arr[high]<\/span>\r\n <span class=\"kw\">int<\/span> temp = arr[i + 1];\r\n arr[i + 1] = arr[high];\r\n arr[high] = temp;\r\n \r\n <span class=\"kw\">return<\/span> i + 1;\r\n}<\/pre><\/div>\r\n\r\n <h3>Merge Sort \u2013 O(n log n) guaranteed<\/h3>\r\n <p>Divide-and-conquer. Divide array in half, recursively sort, merge. Stable and predictable.<\/p>\r\n <div class=\"code-block\"><pre><span class=\"cm\">\/\/ Merge Sort<\/span>\r\n<span class=\"kw\">void<\/span> mergeSort(<span class=\"kw\">int<\/span>[] arr, <span class=\"kw\">int<\/span> left, <span class=\"kw\">int<\/span> right) {\r\n <span class=\"kw\">if<\/span>(left < right) {\r\n <span class=\"kw\">int<\/span> mid = left + (right - left) \/ 2;\r\n mergeSort(arr, left, mid);\r\n mergeSort(arr, mid + 1, right);\r\n merge(arr, left, mid, right);\r\n }\r\n}<\/pre><\/div>\r\n\r\n <div class=\"practice\"><strong>\u270f\ufe0f Practice:<\/strong> (a) Implement insertion sort (b) Find median of two sorted arrays (c) Sort array of 0s, 1s, 2s (Dutch Flag)<\/div>\r\n <\/div>\r\n <\/div>\r\n\r\n <!-- \u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550 UNIT 10 -->\r\n <div class=\"unit\" id=\"unit-10\">\r\n <div class=\"unit-header\">\r\n <div class=\"unit-num-badge\">Unit 10<\/div>\r\n <h2>Searching Algorithms<\/h2>\r\n <p>Methods to Find Elements Efficiently<\/p>\r\n <\/div>\r\n <div class=\"unit-body\">\r\n\r\n <h3>Linear Search \u2013 O(n)<\/h3>\r\n <p>Check each element one by one. Works on unsorted arrays.<\/p>\r\n <div class=\"code-block\"><pre><span class=\"cm\">\/\/ Linear Search<\/span>\r\n<span class=\"kw\">int<\/span> linearSearch(<span class=\"kw\">int<\/span>[] arr, <span class=\"kw\">int<\/span> target) {\r\n <span class=\"kw\">for<\/span>(<span class=\"kw\">int<\/span> i = 0; i < arr.length; i++) {\r\n <span class=\"kw\">if<\/span>(arr[i] == target) {\r\n <span class=\"kw\">return<\/span> i;\r\n }\r\n }\r\n <span class=\"kw\">return<\/span> -1; <span class=\"cm\">\/\/ Not found<\/span>\r\n}<\/pre><\/div>\r\n\r\n <h3>Binary Search \u2013 O(log n)<\/h3>\r\n <p>Eliminate half the remaining elements each time. <strong>Requires sorted array.<\/strong> Much faster for large data.<\/p>\r\n <div class=\"code-block\"><pre><span class=\"cm\">\/\/ Binary Search (Iterative)<\/span>\r\n<span class=\"kw\">int<\/span> binarySearch(<span class=\"kw\">int<\/span>[] arr, <span class=\"kw\">int<\/span> target) {\r\n <span class=\"kw\">int<\/span> left = 0, right = arr.length - 1;\r\n \r\n <span class=\"kw\">while<\/span>(left <= right) {\r\n <span class=\"kw\">int<\/span> mid = left + (right - left) \/ 2;\r\n \r\n <span class=\"kw\">if<\/span>(arr[mid] == target) {\r\n <span class=\"kw\">return<\/span> mid;\r\n } <span class=\"kw\">else if<\/span>(arr[mid] < target) {\r\n left = mid + 1; <span class=\"cm\">\/\/ Search right half<\/span>\r\n } <span class=\"kw\">else<\/span> {\r\n right = mid - 1; <span class=\"cm\">\/\/ Search left half<\/span>\r\n }\r\n }\r\n \r\n <span class=\"kw\">return<\/span> -1; <span class=\"cm\">\/\/ Not found<\/span>\r\n}\r\n\r\n<span class=\"cm\">\/\/ Binary Search (Recursive)<\/span>\r\n<span class=\"kw\">int<\/span> binarySearchRec(<span class=\"kw\">int<\/span>[] arr, <span class=\"kw\">int<\/span> target, <span class=\"kw\">int<\/span> left, <span class=\"kw\">int<\/span> right) {\r\n <span class=\"kw\">if<\/span>(left > right) <span class=\"kw\">return<\/span> -1;\r\n \r\n <span class=\"kw\">int<\/span> mid = left + (right - left) \/ 2;\r\n \r\n <span class=\"kw\">if<\/span>(arr[mid] == target) <span class=\"kw\">return<\/span> mid;\r\n <span class=\"kw\">else if<\/span>(arr[mid] < target) <span class=\"kw\">return<\/span> binarySearchRec(arr, target, mid + 1, right);\r\n <span class=\"kw\">else<\/span> <span class=\"kw\">return<\/span> binarySearchRec(arr, target, left, mid - 1);\r\n}<\/pre><\/div>\r\n\r\n <h3>Search Comparison<\/h3>\r\n <table class=\"data-table\">\r\n <thead>\r\n <tr><th>Algorithm<\/th><th>Time<\/th><th>Space<\/th><th>Requires Sorting<\/th><\/tr>\r\n <\/thead>\r\n <tbody>\r\n <tr><td>Linear Search<\/td><td>O(n)<\/td><td>O(1)<\/td><td>No<\/td><\/tr>\r\n <tr><td>Binary Search<\/td><td>O(log n)<\/td><td>O(1)<\/td><td>Yes<\/td><\/tr>\r\n <tr><td>Hash Lookup<\/td><td>O(1) avg<\/td><td>O(n)<\/td><td>No<\/td><\/tr>\r\n <\/tbody>\r\n <\/table>\r\n\r\n <h3>Binary Search Variations<\/h3>\r\n <ul>\r\n <li><strong>Find first occurrence:<\/strong> Search left half even if found<\/li>\r\n <li><strong>Find last occurrence:<\/strong> Search right half even if found<\/li>\r\n <li><strong>Find smallest \u2265 target:<\/strong> Lower bound<\/li>\r\n <li><strong>Find largest \u2264 target:<\/strong> Upper bound<\/li>\r\n <\/ul>\r\n\r\n <div class=\"practice\"><strong>\u270f\ufe0f Practice:<\/strong> (a) Find first and last position of element (b) Search in rotated sorted array (c) Find peak element<\/div>\r\n <\/div>\r\n <\/div>\r\n\r\n <!-- \u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550 UNIT 11 -->\r\n <div class=\"unit\" id=\"unit-11\">\r\n <div class=\"unit-header\">\r\n <div class=\"unit-num-badge\">Unit 11<\/div>\r\n <h2>Dynamic Programming<\/h2>\r\n <p>Optimization Technique Breaking Problems into Overlapping Subproblems<\/p>\r\n <\/div>\r\n <div class=\"unit-body\">\r\n\r\n <h3>What is Dynamic Programming?<\/h3>\r\n <p>DP solves problems by breaking them into overlapping subproblems and storing results (memoization) to avoid recomputation.<\/p>\r\n <div class=\"info-box\">\ud83d\udca1 Two conditions for DP: (1) Optimal substructure (2) Overlapping subproblems<\/div>\r\n\r\n <h3>Fibonacci Sequence \u2013 Classic Example<\/h3>\r\n <div class=\"code-block\"><pre><span class=\"cm\">\/\/ Naive Recursion \u2013 EXPONENTIAL O(2\u207f) \u2013 VERY SLOW<\/span>\r\n<span class=\"kw\">int<\/span> fib(<span class=\"kw\">int<\/span> n) {\r\n <span class=\"kw\">if<\/span>(n <= 1) <span class=\"kw\">return<\/span> n;\r\n <span class=\"kw\">return<\/span> fib(n-1) + fib(n-2); <span class=\"cm\">\/\/ Recomputes same values!<\/span>\r\n}\r\n\r\n<span class=\"cm\">\/\/ DP with Memoization \u2013 O(n) \u2013 MUCH FASTER<\/span>\r\n<span class=\"kw\">int<\/span> fib(<span class=\"kw\">int<\/span> n, int[] memo) {\r\n <span class=\"kw\">if<\/span>(n <= 1) <span class=\"kw\">return<\/span> n;\r\n <span class=\"kw\">if<\/span>(memo[n] != 0) <span class=\"kw\">return<\/span> memo[n]; <span class=\"cm\">\/\/ Return cached result<\/span>\r\n \r\n memo[n] = fib(n-1, memo) + fib(n-2, memo);\r\n <span class=\"kw\">return<\/span> memo[n];\r\n}\r\n\r\n<span class=\"cm\">\/\/ DP with Tabulation (bottom-up) \u2013 O(n) \u2013 BEST<\/span>\r\n<span class=\"kw\">int<\/span> fib(<span class=\"kw\">int<\/span> n) {\r\n <span class=\"kw\">int<\/span>[] dp = <span class=\"kw\">new int<\/span>[n+1];\r\n dp[0] = 0; dp[1] = 1;\r\n \r\n <span class=\"kw\">for<\/span>(<span class=\"kw\">int<\/span> i = 2; i <= n; i++) {\r\n dp[i] = dp[i-1] + dp[i-2];\r\n }\r\n \r\n <span class=\"kw\">return<\/span> dp[n];\r\n}<\/pre><\/div>\r\n\r\n <h3>0\/1 Knapsack Problem<\/h3>\r\n <p>Given items with weight and value, fill knapsack of capacity W to maximize value.<\/p>\r\n <div class=\"code-block\"><pre><span class=\"cm\">\/\/ 0\/1 Knapsack using DP<\/span>\r\n<span class=\"kw\">int<\/span> knapsack(<span class=\"kw\">int<\/span>[] weights, <span class=\"kw\">int<\/span>[] values, <span class=\"kw\">int<\/span> W) {\r\n <span class=\"kw\">int<\/span> n = weights.length;\r\n <span class=\"kw\">int<\/span>[][] dp = <span class=\"kw\">new int<\/span>[n+1][W+1];\r\n \r\n <span class=\"cm\">\/\/ dp[i][w] = max value with first i items and capacity w<\/span>\r\n \r\n <span class=\"kw\">for<\/span>(<span class=\"kw\">int<\/span> i = 1; i <= n; i++) {\r\n <span class=\"kw\">for<\/span>(<span class=\"kw\">int<\/span> w = 1; w <= W; w++) {\r\n <span class=\"kw\">if<\/span>(weights[i-1] <= w) {\r\n <span class=\"cm\">\/\/ Include or exclude item<\/span>\r\n dp[i][w] = Math.max(\r\n values[i-1] + dp[i-1][w-weights[i-1]], <span class=\"cm\">\/\/ Include<\/span>\r\n dp[i-1][w] <span class=\"cm\">\/\/ Exclude<\/span>\r\n );\r\n } <span class=\"kw\">else<\/span> {\r\n dp[i][w] = dp[i-1][w]; <span class=\"cm\">\/\/ Can't include<\/span>\r\n }\r\n }\r\n }\r\n \r\n <span class=\"kw\">return<\/span> dp[n][W];\r\n}<\/pre><\/div>\r\n\r\n <h3>Common DP Problems<\/h3>\r\n <ul>\r\n <li><strong>Longest Common Subsequence (LCS):<\/strong> O(m\u00d7n)<\/li>\r\n <li><strong>Edit Distance:<\/strong> O(m\u00d7n)<\/li>\r\n <li><strong>Coin Change:<\/strong> O(n\u00d7W)<\/li>\r\n <li><strong>Maximum Subarray Sum:<\/strong> O(n)<\/li>\r\n <li><strong>Rod Cutting:<\/strong> O(n\u00b2)<\/li>\r\n <\/ul>\r\n\r\n <div class=\"practice\"><strong>\u270f\ufe0f Practice:<\/strong> (a) Longest increasing subsequence (b) Longest palindromic subsequence (c) House robber problem<\/div>\r\n <\/div>\r\n <\/div>\r\n\r\n <!-- \u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550\u2550 UNIT 12 -->\r\n <div class=\"unit\" id=\"unit-12\">\r\n <div class=\"unit-header\">\r\n <div class=\"unit-num-badge\">Unit 12<\/div>\r\n <h2>Greedy Algorithms<\/h2>\r\n <p>Making Locally Optimal Choices for Global Solution<\/p>\r\n <\/div>\r\n <div class=\"unit-body\">\r\n\r\n <h3>Greedy Approach<\/h3>\r\n <p>Greedy algorithms make the best choice at each step, hoping to find a global optimum. Fast but not always optimal.<\/p>\r\n <div class=\"info-box\">\ud83d\udca1 Greedy works when problem has \"greedy choice property\" \u2013 local optimum = global optimum. Example: Dijkstra, Huffman coding.<\/div>\r\n\r\n <h3>Activity Selection Problem<\/h3>\r\n <p>Select maximum non-overlapping activities.<\/p>\r\n <div class=\"code-block\"><pre><span class=\"cm\">\/\/ Activity Selection \u2013 Greedy approach<\/span>\r\n<span class=\"kw\">void<\/span> activitySelection(List<Activity> activities) {\r\n <span class=\"cm\">\/\/ Sort by finish time<\/span>\r\n activities.sort((a, b) -> a.finish - b.finish);\r\n \r\n List<Activity> selected = <span class=\"kw\">new<\/span> ArrayList<>();\r\n selected.add(activities.get(0));\r\n <span class=\"kw\">int<\/span> lastFinish = activities.get(0).finish;\r\n \r\n <span class=\"kw\">for<\/span>(<span class=\"kw\">int<\/span> i = 1; i < activities.size(); i++) {\r\n <span class=\"kw\">if<\/span>(activities.get(i).start >= lastFinish) {\r\n selected.add(activities.get(i));\r\n lastFinish = activities.get(i).finish;\r\n }\r\n }\r\n \r\n System.out.println(<span class=\"st\">\"Selected \"<\/span> + selected.size() + <span class=\"st\">\" activities\"<\/span>);\r\n}<\/pre><\/div>\r\n\r\n <h3>Huffman Coding<\/h3>\r\n <p>Assign variable-length codes based on character frequency. More frequent \u2192 shorter code.<\/p>\r\n <div class=\"info-box\">\ud83d\udca1 Used in compression (ZIP, JPEG). Saves space by using fewer bits for common characters.<\/div>\r\n\r\n <h3>Fractional Knapsack<\/h3>\r\n <p>Unlike 0\/1 knapsack, you can take fractional items. Greedy works here!<\/p>\r\n <div class=\"code-block\"><pre><span class=\"cm\">\/\/ Greedy approach: Take items by value\/weight ratio<\/span>\r\n<span class=\"kw\">double<\/span> knapsack(<span class=\"kw\">int<\/span>[] values, <span class=\"kw\">int<\/span>[] weights, <span class=\"kw\">int<\/span> W) {\r\n <span class=\"cm\">\/\/ Sort by value\/weight ratio in descending order<\/span>\r\n <span class=\"cm\">\/\/ Take items greedily until capacity full<\/span>\r\n}\r\nTime Complexity: O(n log n) due to sorting<\/pre><\/div>\r\n\r\n <h3>Greedy Problems<\/h3>\r\n <ul>\r\n <li><strong>Coin Change (minimum coins):<\/strong> O(n log n)<\/li>\r\n <li><strong>Interval Scheduling:<\/strong> O(n log n)<\/li>\r\n <li><strong>Job Sequencing:<\/strong> O(n log n)<\/li>\r\n <li><strong>Minimum Spanning Tree (Kruskal\/Prim):<\/strong> O(E log V)<\/li>\r\n <\/ul>\r\n\r\n <div class=\"success-box\">\u2713 <strong>When Greedy Fails:<\/strong> 0\/1 Knapsack \u2013 greedy by value\/weight ratio doesn't work. Must use DP!<\/div>\r\n\r\n <div class=\"practice\"><strong>\u270f\ufe0f Practice:<\/strong> (a) Implement coin change with minimum coins (b) Gas station problem (c) Jump game<\/div>\r\n <\/div>\r\n <\/div>\r\n\r\n <!-- CONGRATS -->\r\n <div class=\"congrats\">\r\n <h2>\ud83c\udf89 Congratulations!<\/h2>\r\n <p>You've completed the comprehensive DSA course! Now practice these concepts on LeetCode, HackerRank, or CodeSignal.<\/p>\r\n <\/div>\r\n\r\n <!-- SUMMARY -->\r\n <div class=\"unit\">\r\n <div class=\"unit-header\">\r\n <div class=\"unit-num-badge\">\ud83d\udccb<\/div>\r\n <h2>Quick Reference \u2013 Time Complexities<\/h2>\r\n <p>Bookmark this for quick lookup during coding<\/p>\r\n <\/div>\r\n <div class=\"unit-body\">\r\n <table class=\"data-table\">\r\n <thead>\r\n <tr><th>Data Structure \/ Operation<\/th><th>Best<\/th><th>Average<\/th><th>Worst<\/th><\/tr>\r\n <\/thead>\r\n <tbody>\r\n <tr><td>Array Access<\/td><td>O(1)<\/td><td>O(1)<\/td><td>O(1)<\/td><\/tr>\r\n <tr><td>Linked List Search<\/td><td>O(1)<\/td><td>O(n)<\/td><td>O(n)<\/td><\/tr>\r\n <tr><td>Binary Search Tree Search<\/td><td>O(log n)<\/td><td>O(log n)<\/td><td>O(n)<\/td><\/tr>\r\n <tr><td>Hash Table Insert<\/td><td>O(1)<\/td><td>O(1)<\/td><td>O(n)<\/td><\/tr>\r\n <tr><td>Heap Insert\/Delete<\/td><td>O(log n)<\/td><td>O(log n)<\/td><td>O(log n)<\/td><\/tr>\r\n <tr><td>Graph BFS\/DFS<\/td><td>O(V+E)<\/td><td>O(V+E)<\/td><td>O(V+E)<\/td><\/tr>\r\n <tr><td>Merge Sort<\/td><td>O(n log n)<\/td><td>O(n log n)<\/td><td>O(n log n)<\/td><\/tr>\r\n <tr><td>Quick Sort<\/td><td>O(n log n)<\/td><td>O(n log n)<\/td><td>O(n\u00b2)<\/td><\/tr>\r\n <\/tbody>\r\n <\/table>\r\n <\/div>\r\n <\/div>\r\n\r\n <p style=\"text-align: center; color: var(--mid); font-size: .85rem; padding-bottom: 1rem;\">\r\n \ud83d\udcda Pak Notes Hub \u2014 DSA Complete Notes | University Level | BS CS \/ BS IT<br>\r\n For corrections and suggestions: support@paknoteshub.com\r\n <\/p>\r\n <\/main>\r\n<\/div>\r\n\r\n<button id=\"back-top\" onclick=\"window.scrollTo({top:0,behavior:'smooth'})\">\u2191<\/button>\r\n\r\n<script>\r\n const progress = document.getElementById('progress');\r\n window.addEventListener('scroll', () => {\r\n const scrollPercent = (window.scrollY \/ (document.documentElement.scrollHeight - window.innerHeight)) * 100;\r\n progress.style.width = scrollPercent + '%';\r\n document.getElementById('back-top').classList.toggle('visible', window.scrollY > 400);\r\n });\r\n \r\n document.querySelectorAll('.unit').forEach(unit => {\r\n const observer = new IntersectionObserver(entries => {\r\n entries.forEach(entry => {\r\n if(entry.isIntersecting) {\r\n const id = entry.target.id;\r\n document.querySelectorAll('.toc-list a').forEach(a => {\r\n a.classList.toggle('active', a.href.endsWith(id));\r\n });\r\n }\r\n });\r\n }, { rootMargin: '-20% 0px -70% 0px' });\r\n observer.observe(unit);\r\n });\r\n<\/script>\r\n<\/body>\r\n<\/html>\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t","protected":false},"excerpt":{"rendered":"<p>Data Structures & Algorithms \u2013 University Level \u2013 Pak Notes Hub Pak Notes Hub Basics Trees Algorithms \ud83d\udcca University Level \u2014 BS CS \/ BS IT Data Structures &Algorithms Complete Notes Arrays \u00b7 Linked Lists \u00b7 Trees \u00b7 Graphs \u00b7 Sorting \u00b7 Searching \u00b7 Dynamic Programming \u2014 Master DSA in Easy English Time Complexity Space […]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_angie_page":false,"footnotes":""},"class_list":["post-490","page","type-page","status-publish","hentry"],"_hostinger_reach_plugin_has_subscription_block":false,"_hostinger_reach_plugin_is_elementor":false,"_links":{"self":[{"href":"https:\/\/paknoteshub.online\/index.php?rest_route=\/wp\/v2\/pages\/490","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/paknoteshub.online\/index.php?rest_route=\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/paknoteshub.online\/index.php?rest_route=\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/paknoteshub.online\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/paknoteshub.online\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=490"}],"version-history":[{"count":7,"href":"https:\/\/paknoteshub.online\/index.php?rest_route=\/wp\/v2\/pages\/490\/revisions"}],"predecessor-version":[{"id":498,"href":"https:\/\/paknoteshub.online\/index.php?rest_route=\/wp\/v2\/pages\/490\/revisions\/498"}],"wp:attachment":[{"href":"https:\/\/paknoteshub.online\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=490"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}