Complete DSA Notes & Beginner Guide (2026)

Chapter 01

Arrays

The most fundamental data structure — contiguous memory, indexed access, and the building block of everything.

📦

📖 What is an Array?

An array is a collection of elements stored at contiguous memory locations. Each element can be accessed directly using its index (position number starting from 0).

Think of it like a row of numbered lockers — you can instantly open locker #5 without checking lockers #1 through #4.

🗄️ Array in Memory — arr = [10, 20, 30, 40, 50]

10idx 0

20idx 1

30idx 2

40idx 3

50idx 4

Memory: [0x100] [0x104] [0x108] [0x10C] [0x110] — each 4 bytes apart (int)

💡

Key Insight

Because elements are contiguous, accessing any index takes O(1) time — the computer calculates the exact memory address using: base_address + (index × element_size).

⏱️ Time Complexity Table

Operation	Time	Why?
Access by Index	O(1)	Direct memory calculation
Search (unsorted)	O(n)	Must check each element
Search (sorted)	O(log n)	Binary Search
Insert at end	O(1)	Append directly
Insert at beginning	O(n)	Shift all elements right
Delete	O(n)	Shift elements to fill gap

🔀 Technique: Two Pointers

Use two pointers (usually one at the start, one at the end) to solve problems in O(n) instead of O(n²). Works great on sorted arrays.

🎯 Two Sum on Sorted Array — Target = 9

1L 👈

2

3

5

7

8R 👉

L + R = 1 + 8 = 9 ✅ Found! | If sum < target → move L right | If sum > target → move R left

two_sum_sorted.py
def two_sum_sorted(arr, target):
    left, right = 0, len(arr) - 1

    while left < right:
        current_sum = arr[left] + arr[right]

        if current_sum == target:
            return [left, right]  # ✅ Found
        elif current_sum < target:
            left += 1            # Need bigger sum
        else:
            right -= 1           # Need smaller sum

    return []  # No solution found

# Example
print(two_sum_sorted([1,2,3,5,7,8], 9))  # [0, 5]

🪟 Technique: Sliding Window

Maintain a "window" of elements and slide it across the array. Avoids recalculating from scratch each time — turns O(n×k) into O(n).

📏 Maximum Sum Subarray of Size 3

arr = [2, 1, 5, 1, 3, 2] → Window size k = 3

2win

1win

5win

1

3

2

Window 1: 2+1+5=8 → Slide → 1+5+1=7 → 5+1+3=9 ✅ Max → 1+3+2=6

sliding_window.py
def max_sum_subarray(arr, k):
    window_sum = sum(arr[:k])  # First window
    max_sum = window_sum

    for i in range(k, len(arr)):
        window_sum += arr[i] - arr[i - k]  # Slide: add new, remove old
        max_sum = max(max_sum, window_sum)

    return max_sum

print(max_sum_subarray([2,1,5,1,3,2], 3))  # 9

✅ Solved Problem: Reverse an Array In-Place

reverse_array.py
def reverse_array(arr):
    left, right = 0, len(arr) - 1
    while left < right:
        arr[left], arr[right] = arr[right], arr[left]  # Swap
        left += 1
        right -= 1
    return arr

# Before: [1, 2, 3, 4, 5]
# After:  [5, 4, 3, 2, 1]
# Time: O(n)  |  Space: O(1)

🔄 Step-by-Step Swap Visualization

Step 1: [1, 2, 3, 4, 5] → swap(1,5) → [5, 2, 3, 4, 1]
Step 2: [5, 2, 3, 4, 1] → swap(2,4) → [5, 4, 3, 2, 1]
Step 3: L meets R at middle → DONE ✅
Result: [5, 4, 3, 2, 1]

🏆 LeetCode Practice — Arrays

#1 Two Sum Easy

#26 Remove Duplicates from Sorted Array Easy

#53 Maximum Subarray (Kadane's Algorithm) Medium

#121 Best Time to Buy and Sell Stock Easy

#238 Product of Array Except Self Medium

#15 3Sum Medium

#42 Trapping Rain Water Hard

Chapter 02

Linked Lists

Dynamic data structures where elements are connected via pointers — no contiguous memory needed.

🔗

📖 What is a Linked List?

A linked list is a linear data structure where each element (called a node) contains data and a pointer/reference to the next node. Unlike arrays, nodes can be stored anywhere in memory.

🔗 Singly Linked List: 3 → 7 → 11 → 5 → NULL

3

→

7

→

11

→

5

→

NULL ❌

Each box = Node { data, next_pointer } | HEAD points to first node

✅ Advantages

Dynamic size — grows/shrinks easily
O(1) insertion at head
No wasted memory
No shifting needed for insert/delete

❌ Disadvantages

No random access (must traverse)
Extra memory for pointers
Not cache-friendly
O(n) access time

🔨 Node Structure & Basic Operations

linked_list.py
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def insert_at_head(self, data):  # O(1)
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    def insert_at_tail(self, data):  # O(n)
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        curr = self.head
        while curr.next:
            curr = curr.next
        curr.next = new_node

    def delete(self, data):  # O(n)
        if self.head and self.head.data == data:
            self.head = self.head.next
            return
        curr = self.head
        while curr.next:
            if curr.next.data == data:
                curr.next = curr.next.next
                return
            curr = curr.next

    def display(self):
        curr = self.head
        while curr:
            print(curr.data, end=" → ")
            curr = curr.next
        print("NULL")

Operation	Time	Note
Insert at Head	O(1)	Just change head pointer
Insert at Tail	O(n)	Must traverse to end
Delete a Node	O(n)	Must find the node first
Search	O(n)	Linear scan required
Access by Index	O(n)	No random access!

✅ Solved Problem: Reverse a Linked List

This is the most asked linked list question in interviews. Use three pointers: prev, curr, and next.

🔄 Reversal Step-by-Step

Before: 1 → 2 → 3 → NULL

Step 1: prev=NULL, curr=1 → reverse 1's pointer → NULL ← 1 2 → 3 → NULL
Step 2: prev=1, curr=2 → reverse 2's pointer → NULL ← 1 ← 2 3 → NULL
Step 3: prev=2, curr=3 → reverse 3's pointer → NULL ← 1 ← 2 ← 3

After: 3 → 2 → 1 → NULL ✅

reverse_linked_list.py
def reverse_list(head):
    prev = None
    curr = head

    while curr:
        next_node = curr.next  # Save next
        curr.next = prev       # Reverse pointer
        prev = curr            # Move prev forward
        curr = next_node       # Move curr forward

    return prev  # New head
# Time: O(n)  |  Space: O(1)

🏆 LeetCode Practice — Linked Lists

#206 Reverse Linked List Easy

#21 Merge Two Sorted Lists Easy

#141 Linked List Cycle Easy

#19 Remove Nth Node From End Medium

#143 Reorder List Medium

#23 Merge K Sorted Lists Hard

Chapter 03

Stacks & Queues

Restricted access data structures — LIFO and FIFO principles that power undo buttons, BFS, and much more.

📚

📚 Stack — Last In, First Out (LIFO)

A stack is like a stack of plates — you can only add or remove from the top. The last plate placed on top is the first one you pick up.

📚 Stack Operations Visualized

PUSH(40) ⬇️

40 ← TOP (new)

30

20

10

POP() ⬆️

30 ← TOP

20

10

Returns: 40

stack.py
# Python list works as a stack!
stack = []

stack.append(10)  # push
stack.append(20)  # push
stack.append(30)  # push

top = stack.pop()  # pop → 30
peek = stack[-1]  # peek → 20 (don't remove)

# All operations: O(1) ✅

🚶‍♂️ Queue — First In, First Out (FIFO)

A queue is like a line at a store — the first person in line is the first one served. Elements enter from the rear and leave from the front.

🚶‍♂️ Queue: Enqueue & Dequeue

DEQUEUE ←

10

20

30

40

→ ENQUEUE

FRONT = 10 | REAR = 40

queue.py
from collections import deque

queue = deque()

queue.append(10)    # enqueue
queue.append(20)    # enqueue
queue.append(30)    # enqueue

front = queue.popleft()  # dequeue → 10
peek = queue[0]          # peek → 20

# All operations: O(1) ✅
# ⚠️ Don't use list.pop(0) — it's O(n)!

✅ Solved Problem: Valid Parentheses

🎯

Problem

Given a string containing '(', ')', '{', '}', '[', ']', determine if the input string is valid. Every open bracket must have a matching close bracket in the correct order.

valid_parentheses.py
def is_valid(s):
    stack = []
    mapping = {')': '(', '}': '{', ']': '['}

    for char in s:
        if char in mapping:
            top = stack.pop() if stack else '#'
            if mapping[char] != top:
                return False
        else:
            stack.append(char)

    return len(stack) == 0

print(is_valid("({[]})"))  # True ✅
print(is_valid("({[})"))   # False ❌

🏆 LeetCode Practice — Stacks & Queues

#20 Valid Parentheses Easy

#155 Min Stack Medium

#232 Implement Queue using Stacks Easy

#150 Evaluate Reverse Polish Notation Medium

#739 Daily Temperatures Medium

#84 Largest Rectangle in Histogram Hard

Chapter 04

Trees

Hierarchical data structures — from file systems to databases, trees are everywhere.

🌳

🌳 Binary Tree Structure

A tree where each node has at most two children: left and right. The topmost node is the root. Nodes with no children are called leaves.

🌳 Binary Search Tree (BST) — Left < Root < Right

8

╱ ╲

3

10

╱ ╲ ╲

1

6

14

Root: 8 | Leaves: 1, 6, 14 | Height: 3

🔄 Tree Traversals (DFS)

Three ways to visit every node in a binary tree using depth-first search. Remember the mnemonic: the name tells you when you visit the root.

📍 Traversal Orders for the BST above

In-Order (Left → Root → Right): 1, 3, 6, 8, 10, 14

→ Gives sorted order for BST! ⭐

Pre-Order (Root → Left → Right): 8, 3, 1, 6, 10, 14

→ Used to copy/serialize a tree

Post-Order (Left → Right → Root): 1, 6, 3, 14, 10, 8

→ Used to delete a tree

tree_traversals.py
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def inorder(node):      # Left → Root → Right
    if not node: return
    inorder(node.left)
    print(node.val, end=" ")
    inorder(node.right)

def preorder(node):     # Root → Left → Right
    if not node: return
    print(node.val, end=" ")
    preorder(node.left)
    preorder(node.right)

def postorder(node):    # Left → Right → Root
    if not node: return
    postorder(node.left)
    postorder(node.right)
    print(node.val, end=" ")

✅ Solved: Maximum Depth of Binary Tree

max_depth.py
def max_depth(root):
    if not root:
        return 0

    left_depth = max_depth(root.left)
    right_depth = max_depth(root.right)

    return max(left_depth, right_depth) + 1

# Time: O(n)  |  Space: O(h) where h = height

🌟

Recursion Pattern for Trees

Almost every tree problem follows: Base case (null node) → Recurse left → Recurse right → Combine results. Master this pattern!

🏆 LeetCode Practice — Trees

#104 Maximum Depth of Binary Tree Easy

#226 Invert Binary Tree Easy

#100 Same Tree Easy

#102 Binary Tree Level Order Traversal Medium

#98 Validate BST Medium

#236 Lowest Common Ancestor Medium

#124 Binary Tree Maximum Path Sum Hard

Chapter 05

Sorting & Searching

The classic algorithms that form the backbone of computer science — learn to arrange and find data efficiently.

🔄

📊 Sorting Algorithms Comparison

Algorithm	Best	Average	Worst	Space	Stable?
Bubble Sort	O(n)	O(n²)	O(n²)	O(1)	✅
Selection Sort	O(n²)	O(n²)	O(n²)	O(1)	❌
Insertion Sort	O(n)	O(n²)	O(n²)	O(1)	✅
Merge Sort	O(n log n)	O(n log n)	O(n log n)	O(n)	✅
Quick Sort	O(n log n)	O(n log n)	O(n²)	O(log n)	❌

⚠️

Which to Use?

Small arrays (<50): Insertion Sort. General purpose: Merge Sort (stable) or Quick Sort (fast in practice). Most languages use Timsort (hybrid of merge + insertion).

🔍 Binary Search

The most important searching algorithm. Works on sorted arrays by repeatedly halving the search space. Time: O(log n) — finds any element in a billion-item array in ~30 steps!

🔍 Binary Search for Target = 23

Array: [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]

Step 1: mid = arr[4] = 16 → 16 < 23 → search RIGHT half

Step 2: mid = arr[7] = 56 → 56 > 23 → search LEFT half

Step 3: mid = arr[5] = 23 → 23 == 23 → FOUND at index 5! ✅

Only 3 comparisons instead of 10 (linear scan)!

binary_search.py
def binary_search(arr, target):
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = (left + right) // 2

        if arr[mid] == target:
            return mid       # ✅ Found
        elif arr[mid] < target:
            left = mid + 1   # Search right half
        else:
            right = mid - 1  # Search left half

    return -1  # Not found

# Time: O(log n)  |  Space: O(1)

✅ Solved: Merge Sort Implementation

🧩 Merge Sort: Divide & Conquer

[38, 27, 43, 3, 9, 82, 10]
↙ SPLIT ↘
[38, 27, 43]
[3, 9, 82, 10]
↙↘          ↙↘
[38] [27,43]
[3,9] [82,10]
⬆ MERGE (sort while combining) ⬆
[3, 9, 10, 27, 38, 43, 82] ✅

merge_sort.py
def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])

    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i]); i += 1
        else:
            result.append(right[j]); j += 1

    result.extend(left[i:])
    result.extend(right[j:])
    return result

# Time: O(n log n)  |  Space: O(n)

🏆 LeetCode Practice — Sorting & Searching

#704 Binary Search Easy

#35 Search Insert Position Easy

#33 Search in Rotated Sorted Array Medium

#215 Kth Largest Element in an Array Medium

#56 Merge Intervals Medium

#4 Median of Two Sorted Arrays Hard

Chapter 06

Hash Maps & Graphs

Key-value lookups in O(1) and exploring connected networks — essential for real-world applications.

🧩

🗺️ Hash Map (Dictionary)

A hash map stores key-value pairs and provides O(1) average lookup. It uses a hash function to convert keys into array indices.

🗺️ Hash Map: {"apple": 5, "banana": 3, "cherry": 8}

[0]

→

🍎 "apple": 5

[1]

→

empty

[2]

→

🍌 "banana": 3

[3]

→

🍒 "cherry": 8

[4]

→

empty

hash("apple") % 5 = 0 | hash("banana") % 5 = 2 | hash("cherry") % 5 = 3

hashmap_example.py
# Python dict IS a hash map
scores = {}

scores["Alice"] = 95    # Insert: O(1)
scores["Bob"] = 87      # Insert: O(1)

print(scores["Alice"])    # Lookup: O(1) → 95
print("Bob" in scores)    # Check: O(1) → True

del scores["Bob"]         # Delete: O(1)

# Common pattern: frequency counter
def count_chars(s):
    freq = {}
    for char in s:
        freq[char] = freq.get(char, 0) + 1
    return freq

print(count_chars("hello"))
# {'h': 1, 'e': 1, 'l': 2, 'o': 1}

🕸️ Graphs — Basics

A graph consists of vertices (nodes) connected by edges. Graphs model networks, social connections, maps, and dependencies.

🕸️ Undirected Graph — Adjacency List Representation

🅰️ — 🅱️ — 🅲️

| ╲ |

🅳️ 🅴️

A: [B, D]
B: [A, C, E]
C: [B, E]
D: [A]
E: [B, C]

graph_bfs_dfs.py
from collections import deque

graph = {
    'A': ['B', 'D'],
    'B': ['A', 'C', 'E'],
    'C': ['B', 'E'],
    'D': ['A'],
    'E': ['B', 'C'],
}

def bfs(graph, start):         # Breadth-First Search
    visited = set([start])
    queue = deque([start])
    while queue:
        node = queue.popleft()
        print(node, end=" ")
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

def dfs(graph, node, visited=None):  # Depth-First Search
    if visited is None:
        visited = set()
    visited.add(node)
    print(node, end=" ")
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

bfs(graph, 'A')  # A B D C E
dfs(graph, 'A')  # A B C E D

🧩 Intro to Dynamic Programming

DP is about breaking a problem into overlapping subproblems and storing results to avoid recalculation. Two approaches: top-down (memoization) and bottom-up (tabulation).

🐇 Fibonacci: Why DP Matters

Without DP (Naive Recursion):

fib(5) calls fib(4)+fib(3), fib(4) calls fib(3)+fib(2)...

fib(3) is calculated multiple times! → O(2ⁿ) 🐢

With DP (Memoization):

Store fib(3) result after first calculation. Reuse it! → O(n) ⚡

dp_fibonacci.py
# ❌ Naive Recursion — O(2^n)
def fib_naive(n):
    if n <= 1: return n
    return fib_naive(n-1) + fib_naive(n-2)

# ✅ Top-Down DP (Memoization) — O(n)
def fib_memo(n, memo={}):
    if n <= 1: return n
    if n not in memo:
        memo[n] = fib_memo(n-1) + fib_memo(n-2)
    return memo[n]

# ✅ Bottom-Up DP (Tabulation) — O(n)
def fib_tab(n):
    if n <= 1: return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

print(fib_tab(10))  # 55

🔥

DP Recognition Pattern

Ask yourself: "Can I solve this using solutions to smaller versions of the same problem?" and "Are there overlapping subproblems?" If YES to both → use DP!

🏆 LeetCode Practice — Hash Maps, Graphs & DP

#217 Contains Duplicate Easy

#242 Valid Anagram Easy

#49 Group Anagrams Medium

#200 Number of Islands Medium

#133 Clone Graph Medium

#70 Climbing Stairs Easy

#322 Coin Change Medium

#300 Longest Increasing Subsequence Medium

Quick Reference

Big-O Cheat Sheet

Master time and space complexity at a glance.

📋

⏱️ Complexity Rankings (Best → Worst)

📈 Growth Rate Comparison

          O(1)
          ██ Constant — Hash lookup
        
          O(log n)
          ████ Logarithmic — Binary Search
        
          O(n)
          ████████ Linear — Single loop
        
          O(n log n)
          ████████████ Linearithmic — Merge Sort
        
          O(n²)
          ████████████████████ Quadratic — Nested loop
        
          O(2ⁿ)
          █████████████████████████████████ Exponential — Recursive fib

📌

Rule of Thumb

If n = 10⁶ (1 million), your algorithm needs to be O(n log n) or better to run in ~1 second. O(n²) would take ~10¹² operations — far too slow!

Data Structure	Access	Search	Insert	Delete
Array	O(1)	O(n)	O(n)	O(n)
Linked List	O(n)	O(n)	O(1)	O(1)
Hash Map	O(1)	O(1)	O(1)	O(1)
BST (balanced)	O(log n)	O(log n)	O(log n)	O(log n)
Stack / Queue	O(n)	O(n)	O(1)	O(1)

🎉 Congratulations!

You've completed the DSA Beginner's Notes! Keep practicing on LeetCode, and remember — consistency beats intensity.

🚀📈💪

"The only way to learn DSA is to solve problems. Every day."

Total LeetCode Problems Listed: 40+ | Topics Covered: 6 Chapters | Difficulty: Beginner → Intermediate