DSA Notes
HubAlgorithm vs Data Structure — Key Differences, Definitions, and How They Work TogetherApplications of DSA — How Data Structures and Algorithms Power Real-World SoftwareTime and Space Complexity — A Complete BeginnerWhat is DSA? — A Complete BeginnerWhy Learn DSA? — Career Benefits, Real-World Impact, and Long-Term ValueAsymptotic Analysis — Complete Framework with Recurrence Relations and Master TheoremBest, Average, and Worst Case Analysis — A Practical Guide for Every AlgorithmBig O Notation — Complete Guide with Formal Definition, Rules, and ExamplesBig Omega Notation — Lower Bounds, Best Case, and Formal DefinitionBig Theta (Θ) Notation — Tight Bounds and Exact Growth RatesSpace Complexity — Memory Analysis, Auxiliary Space, and Time-Space TradeoffsTime Complexity Examples — 25 Worked Problems from Basic to AdvancedArray Interview Problems — 15 Classic Problems with Complete SolutionsArray Operations — Every Operation Explained with Code, Complexity, and Edge CasesArray Rotation — Algorithms, Techniques, and Interview ProblemsArray Searching — Linear Search, Binary Search, and Advanced TechniquesArrays — The Complete Introduction to the Most Fundamental Data StructureDynamic Arrays — How Python Lists and ArrayLists Work InternallyMultidimensional Arrays — 2D Arrays, Matrices, and Memory LayoutSliding Window Technique — Complete Guide with 10 Classic ProblemsAnagram Problems — Detection, Grouping, and Sliding Window VariationsPalindrome Problems — Check, Longest, Count, and Expand Around CenterPattern Searching — KMP, Rabin-Karp, and Boyer-Moore AlgorithmsString Interview Problems — 10 Classic Problems with Complete SolutionsString Matching — Longest Common Subsequence, Edit Distance, and Z-AlgorithmString Operations — Complete Reference with Complexity and ImplementationStrings — Complete Introduction to String Data Structure and OperationsCircular Linked List — Structure, Operations, and ApplicationsDoubly Linked List — Complete Implementation with Bidirectional OperationsLinked List Interview Problems — 12 Classic Problems with Complete SolutionsLinked Lists — A Complete Introduction with Memory Model and TypesLinked List Operations — Every Technique with Code and ComplexityReverse Linked List — All Approaches from Basic to AdvancedSingly Linked List — Complete Implementation with All OperationsBalanced Parentheses — Stack-Based Validation with All VariantsInfix, Prefix, and Postfix Expressions — Stack-Based Conversion and EvaluationStack Implementation — Three Complete Implementations with Edge CasesStack Interview Problems — 10 Classic Problems with Complete SolutionsStack — Complete Introduction to LIFO Data StructureStack Using Arrays — Memory Layout, Capacity Management, and PerformanceStack Using Linked List — Implementation, Analysis, and When to Use ItCircular Queue — The Ring Buffer Explained with ImplementationDeque — Double-Ended Queue with Complete Implementation and ApplicationsPriority Queue — Complete Guide from Concept to ImplementationQueue Applications — BFS, Level-Order Traversal, 01-BFS, and MoreQueue Implementation — Array, Linked List, and Two-Stack ApproachesQueue Interview Problems — 10 Classic Problems with Complete SolutionsQueue — Complete Introduction to the FIFO Data StructureAVL Tree - Self-Balancing Binary Search TreeBinary Search Tree (BST)Binary Tree - Structure and OperationsFenwick Tree (Binary Indexed Tree)Red-Black Tree - Another Balanced BSTSegment Tree - Range Query Data StructureTree Interview Problems CollectionTree Data Structure FundamentalsTree Traversals - Inorder, Preorder, Postorder, Level OrderHeap — Complete Introduction to the Priority-Based Tree Data StructureHeap Operations — Complete Reference with Complexity AnalysisHeap Problems — 8 Classic Interview Problems with Complete SolutionsMax Heap — Complete Implementation and ApplicationsMin Heap — Complete Implementation with All OperationsPriority Queue Using Heap — Implementation, Applications, and PatternsBellman-Ford Algorithm — Shortest Path with Negative Weights and Cycle DetectionBFS Algorithm — Breadth-First Search with All Applications and VariantsDFS Algorithm — Depth-First Search with Cycle Detection and All ApplicationsDijkstraFloyd-Warshall Algorithm — All-Pairs Shortest Paths with Complete AnalysisGraph Interview Problems — 12 Classic Problems with Complete SolutionsGraph — Complete Introduction to the Most Powerful Data StructureGraph Representation — Adjacency List, Matrix, Edge List with Complete AnalysisKruskalMinimum Spanning Tree — Definition, Properties, and ApplicationsPrimShortest Path Algorithms — Complete Comparison and Selection GuideTopological Sorting — DFS and BFS (KahnUnion-Find (DSU) in Graphs — Connected Components and Dynamic ConnectivitySeparate Chaining — Complete Implementation and AnalysisCollision Handling — Chaining vs Open Addressing Complete ComparisonHash Functions — Design, Properties, and Common ImplementationsHashing — Complete Introduction to Hash Tables and Hash FunctionsHashing Problems — 10 Classic Interview Problems with Complete SolutionsOpen Addressing — Linear Probing, Quadratic Probing, and Double HashingBubble Sort — Complete Analysis with Optimizations and When to Use ItCounting Sort — O(n+k) Sorting That Breaks the Comparison Lower BoundHeap Sort — Guaranteed O(n log n) with O(1) SpaceInsertion Sort — The O(n) Best Case Sort That Powers PythonMerge Sort — Complete Guide to the Guaranteed O(n log n) Stable SortQuick Sort — The Fastest Practical Sorting Algorithm with Complete AnalysisRadix Sort — O(nk) Digit-by-Digit Sorting for Large Integer RangesSelection Sort — Complete Analysis with Swaps Minimization PropertySorting Algorithm Comparison — The Complete Decision GuideSorting — Complete Introduction to Sorting AlgorithmsBinary Search — Complete Guide with All Variants and Proof of CorrectnessInterpolation Search — O(log log n) Search for Uniformly Distributed DataLinear Search — Complete Guide with All Variants and ApplicationsSearch Algorithm Comparison — Choosing the Right Search for Every SituationSearching Interview Problems — 10 Classic Problems with Complete SolutionsTernary Search — Finding Maximum/Minimum of Unimodal FunctionsBacktracking Introduction — The Recursive Exploration with UndoRecursion Basics — The Complete BeginnerRecursion Problems — 12 Classic Problems from Basic to AdvancedRecursion Tree — Visualizing Recursion for Complexity AnalysisRecursion vs Iteration — When to Use Each and How to ConvertTail Recursion — Definition, Optimization, and Converting to IterationDP Interview Problems — 12 Classic Problems with Pattern Recognition GuideDynamic Programming — Complete Introduction with Properties and Problem IdentificationFibonacci DP — From Exponential to Linear with Memoization and Matrix ExponentiationKnapsack Problem — 0/1, Unbounded, and Fractional with Complete AnalysisLongest Common Subsequence — Complete Guide with DP Table and String VariantsLongest Increasing Subsequence — O(n log n) with Patience SortingMatrix Chain Multiplication — Interval DP with Complete AnalysisMemoization — Top-Down Dynamic Programming with CachingTabulation — Bottom-Up Dynamic Programming with Complete Table BuildingActivity Selection Problem — Greedy Scheduling with Proof of CorrectnessFractional Knapsack — Greedy by Value Density with ProofGreedy Interview Problems — 10 Classic Problems with Complete SolutionsGreedy Algorithms — Complete Introduction with Proof TechniquesHuffman Coding — Optimal Prefix-Free Data CompressionJob Sequencing Problem — Greedy Scheduling with DeadlinesBacktracking — The Complete Guide to Recursive Exploration with UndoBacktracking Problems — 12 Classic Interview Problems with Complete SolutionsN-Queens Problem — Complete Solution with Backtracking and OptimizationRat in a Maze — Backtracking Path Finding with All SolutionsSubset Generation — All Subsets, Combinations, and Partitions with BacktrackingSudoku Solver — Backtracking with Constraint PropagationCodeforces Guide — Complete Strategy to Reach 1800+ RatingCommon CP Techniques — Essential Algorithms Every Competitive Programmer Must KnowContest Strategies — How to Perform Your Best in Competitive Programming ContestsCompetitive Programming — Complete Introduction for BeginnersFast Input/Output — Why I/O Speed Matters and Complete Templates for C++ and PythonLeetCode Guide — Complete Strategy to Crack FAANG InterviewsBit Manipulation — Complete Guide with All Tricks and Interview ProblemsBloom Filter — Space-Efficient Probabilistic Membership TestingComputational Geometry — Points, Lines, Convex Hull, and Geometric AlgorithmsDisjoint Set Union (DSU) — Union-Find with Path Compression and Union by RankRandomized Algorithms — Las Vegas, Monte Carlo, and Probabilistic TechniquesSkip List — The Probabilistic Data Structure that Competes with Balanced BSTsSuffix Array — Construction, LCP Array, and String Search ApplicationsTrie Data Structure — Complete Guide with Implementation and ApplicationsAutocomplete System Using TrieLibrary Management System Using DSARoute Finder Using GraphsMini Search Engine ProjectSocial Network Analysis Using GraphsEssential Coding Patterns for InterviewsDSA Cheatsheet: Quick ReferenceEssential DSA Interview QuestionsFAANG DSA Sheet: Company-Specific Patterns and ProblemsProblem Solving Strategies for Coding InterviewsComplexity CheatsheetImportant Algorithms SummaryBest Practice Platforms for DSARecommended Books for DSA
Master fast I/O in competitive programming — why cin/cout is slow, how sync_with_stdio and tie affect speed, custom fast readers in C++, Python stdin tricks, complete templates for C++ and Python with all optimizations, and when I/O speed is the difference between AC and TLE.
Why I/O Speed Matters
In competitive programming, your solution must complete within a strict time limit — usually 1-3 seconds. For problems with large inputs (n = 10^5 to 10^6), the time spent just reading input can consume a significant portion of your time budget.
Concrete example:
| Slow C++ cin | ~2.0 seconds |
| Fast C++ (sync off) | ~0.2 seconds |
| Custom fast reader | ~0.1 seconds |
| Python built-in input() | ~3.0 seconds for 10^6 integers |
| Python sys.stdin | ~0.5 seconds |
If your algorithm is O(n log n) in 0.5 seconds but I/O takes 2 seconds — you TLE. This is why fast I/O is a fundamental skill.
Complete C++ Template
Example
#include <bits/stdc++.h>
using namespace std;
// Typedefs
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpii;
// Macros
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define sz(x) (int)(x).size()
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) for(int i=0;i<(n);i++)
// Constants
const int INF = 1e9 + 5;
const ll LLINF = 2e18;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
void solve() {
// Your solution here
int n;
cin >> n;
vector<int> arr(n);
for (int& x : arr) cin >> x;
// Process...
cout << 42 << '\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t = 1;
cin >> t; // Comment this line if no multiple test cases
while (t--) {
solve();
}
return 0;
}
Custom Fast Reader (Fastest Possible C++)
For extreme cases (n = 10^7 or more) where even optimized cin is too slow:
Example
#include <bits/stdc++.h>
using namespace std;
// Custom fast reader using raw system calls
namespace fastio {
const int BUFSIZE = 1 << 22; // 4 MB buffer
char buf[BUFSIZE];
int bufpos = 0, buflen = 0;
inline char gc() {
if (bufpos == buflen) {
buflen = fread(buf, 1, BUFSIZE, stdin);
bufpos = 0;
if (!buflen) return EOF;
}
return buf[bufpos++];
}
inline int read_int() {
int x = 0;
char c = gc();
bool neg = false;
while (c != '-' && (c < '0' || c > '9')) c = gc();
if (c == '-') { neg = true; c = gc(); }
while (c >= '0' && c <= '9') { x = x*10 + (c-'0'); c = gc(); }
return neg ? -x : x;
}
inline long long read_ll() {
long long x = 0;
char c = gc();
bool neg = false;
while (c != '-' && (c < '0' || c > '9')) c = gc();
if (c == '-') { neg = true; c = gc(); }
while (c >= '0' && c <= '9') { x = x*10 + (c-'0'); c = gc(); }
return neg ? -x : x;
}
}
int main() {
int n = fastio::read_int();
vector<int> arr(n);
for (int& x : arr) x = fastio::read_int();
// ...
}
This is typically 2-3x faster than optimized cin for very large inputs.
Python Fast I/O
The Problem with Python's input()
python example
# SLOW: input() is the standard function
n = int(input())
arr = list(map(int, input().split()))For n = 10^5, this might be fine. For n = 10^6, it's often too slow.
Solution: Use sys.stdin
Example
import sys
input = sys.stdin.readline # Override input() globally
n = int(input())
arr = list(map(int, input().split()))
This is 3-5x faster than the default input().
Even Faster: Read All at Once
Example
import sys
# Method 1: Read all input at once
data = sys.stdin.read().split()
idx = 0
n = int(data[idx]); idx += 1
arr = [int(data[idx+i]) for i in range(n)]; idx += n
Fastest: sys.stdin.buffer (Binary Mode)
Example
import sys
input = sys.stdin.buffer.readline
n = int(input())
arr = list(map(int, input().split()))
Binary mode avoids string decoding overhead — fastest pure Python I/O.
Complete Python Template
Example
import sys
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify, nlargest, nsmallest
from functools import lru_cache
from itertools import combinations, permutations, product
from math import gcd, lcm, log2, sqrt, inf, ceil, floor
from bisect import bisect_left, bisect_right, insort
# Fast I/O
input = sys.stdin.readline
print = sys.stdout.write # Optional: for very fast output
# Or even simpler for most problems:
# input = lambda: sys.stdin.readline().rstrip()
def solve():
n = int(input())
arr = list(map(int, input().split()))
# Your solution
ans = max(arr)
sys.stdout.write(str(ans) + '\n')
t = int(input())
for _ in range(t):
solve()
Output Optimization
C++ Output
cpp example
// SLOW: Multiple small writes
for (int x : arr) cout << x << ' ';
// FAST: Build string first, write once
string out;
out.reserve(arr.size() * 12);
for (int x : arr) {
out += to_string(x);
out += ' ';
}
cout << out;
// Or use printf for formatted output (still fast without sync)
// But don't mix with cin after sync_with_stdio(false)!Python Output
python example
# SLOW: print() inside a loop with large output
for x in arr:
print(x)
# FAST: Join and print once
sys.stdout.write('\n'.join(map(str, arr)) + '\n')
# Or:
print(*arr, sep='\n') # Still better than printing individuallyCommon I/O Patterns in Competitive Programming
Example
# Read a single integer
n = int(input())
# Read a line of space-separated integers
arr = list(map(int, input().split()))
# Read n lines, each with k integers
grid = [list(map(int, input().split())) for _ in range(n)]
# Read a string
s = input().strip()
# Read t test cases
t = int(input())
for _ in range(t):
n, m = map(int, input().split())
# solve(n, m)
# Read edges of a graph
n, m = map(int, input().split())
adj = [[] for _ in range(n)]
for _ in range(m):
u, v = map(int, input().split())
u -= 1; v -= 1 # 0-indexed
adj[u].append(v)
adj[v].append(u)
When I/O Optimization Is Critical
| n ≤ 10^4 | Any I/O method works fine |
| n ≤ 10^5 | Standard cin/input() with basic optimization |
| n ≤ 10^6 | MUST use fast I/O (sync_with_stdio, sys.stdin) |
| n ≤ 10^7 | Custom fast reader in C++; Python may TLE regardless |
| n ≤ 10^8 | C++ custom reader; Python is unlikely to pass |
Summary
Fast I/O is a low-effort, high-reward optimization that every competitive programmer must implement automatically:
C++:
cpp example
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// Use '\n' not endlPython:
Example
import sys
input = sys.stdin.readline
These two changes take 5 seconds to type and can prevent TLE on large-input problems. Add them to every solution as a reflex.
*Next Lesson: Contest Strategies*
Continue the lesson path
Study next in this module
01Competitive ProgrammingCompetitive Programming — Complete Introduction for BeginnersA complete introduction to competitive programming — what it is, why it matters for careers, the major platforms (Codeforces, LeetCode, CodeChef, AtCoder), rating systems explained, the problem-solving mindset, how contests work, and a complete roadmap from beginner to expert.02Competitive ProgrammingLeetCode Guide — Complete Strategy to Crack FAANG InterviewsThe definitive LeetCode guide — how to use LeetCode effectively, topic-wise problem lists, the 150-problem study plan, how to approach medium and hard problems, common patterns to master, time management in interviews, and which problems to prioritize by company.03Competitive ProgrammingContest Strategies — How to Perform Your Best in Competitive Programming ContestsMaster competitive programming contest strategies — pre-contest preparation, during-contest time management, the scanning strategy, when to skip problems, stress testing techniques, hacking, debugging under pressure, post-contest upsolving, and mental management during competition.04Competitive ProgrammingCommon CP Techniques — Essential Algorithms Every Competitive Programmer Must KnowMaster the essential competitive programming techniques — two pointers, sliding window, binary search on answer, prefix sums, sparse table, coordinate compression, BFS on implicit graphs, bitmask DP, and modular arithmetic — with implementation templates and when to apply each technique.