DSA Cheat Sheet: Concepts, Patterns & Free PDF Revision

A dsa cheat sheet is a compact revision map of data structures, algorithms, patterns, complexity rules, and implementation cues. It matters because interviews rarely test isolated syntax; they test whether you can choose the right structure for problems like UPI fraud checks, IRCTC allocation, or routing. After reading, you can revise, classify, and implement core DSA ideas faster.

This page is built for dsa quick revision before coding interviews, GATE-style theory questions, and timed problem-solving rounds. Use it as a one-page reference, then save the page as a dsa cheat sheet pdf from your browser print menu if you want an offline copy.

You will be able to compare all major DSA concepts, recognise standard patterns, estimate time and space complexity, and write clean starter code for arrays, lists, trees, graphs, dynamic programming, greedy algorithms, and advanced structures.

---

Core Concepts

DSA has four layers: complexity analysis, data structures, algorithms, and problem-solving patterns. Complexity tells you how a solution scales. Data structures decide how data is stored and accessed. Algorithms define the procedure. Patterns help you recognise repeated problem shapes quickly.

The table below works as a compact comparison matrix for the complete cheat sheet. Treat it as your first-pass revision before going into the detailed sections.

1.Time and Space Complexity

Complexity analysis measures how time and memory grow as input size increases. Big O describes an upper bound, Big Omega describes a lower bound, and Big Theta describes a tight bound. For interviews, Big O is most commonly asked because it helps compare whether a solution will pass constraints.

A familiar example is checking one Aadhaar number in an unsorted list of one crore records: a linear scan is O(n), while a hash-based lookup is expected O(1). An industry-specific example is a healthcare appointment platform calculating available slots; checking every doctor and every slot may become O(d × s), while indexed calendars reduce practical lookup time.

Most GATE and interview questions ask for worst-case time complexity. Binary search is O(log n), merge sort is O(n log n), BFS is O(V + E), and nested loops over the same input are usually O(n²) unless the loop variables move monotonically.

Code Example

2.Arrays and Strings

Arrays store elements in contiguous memory and allow O(1) indexed access. Strings behave like arrays of characters in many DSA problems, though immutability depends on the language. Core variants include static arrays, dynamic arrays, character arrays, strings, prefix arrays, suffix arrays, and two-dimensional arrays.

A familiar example is a UPI transaction history list where the latest 50 entries can be indexed quickly. An industry-specific example is an e-commerce inventory grid where rows represent warehouses and columns represent SKUs. Use arrays when position matters, scanning is frequent, and memory locality helps performance.

For subarray sum problems, prefix sums turn repeated range-sum queries from O(n) each into O(1) after O(n) preprocessing. For substring and window problems, prefer two pointers or sliding window before trying nested loops.

Code Example

3.Linked Lists

A linked list stores data in nodes where each node points to another node. The standard variants are singly linked list, doubly linked list, circular singly linked list, and circular doubly linked list. Linked lists are useful when insertion and deletion near known nodes are more important than random indexing.

A familiar example is a music playlist where moving to the next song is natural and a doubly linked list also supports previous navigation. An industry-specific example is an LRU cache in a SaaS dashboard, where a doubly linked list plus hash map supports quick eviction of the least recently used item.

A common mistake is using a linked list for frequent index-based access. Accessing the kth node takes O(k), so arrays are usually better when random access is required.

Code Example

4.Stacks and Queues

A stack follows LIFO: last in, first out. A queue follows FIFO: first in, first out. A deque supports insertion and deletion at both ends. Important variants include normal stack, monotonic stack, normal queue, circular queue, priority queue, and monotonic queue.

A familiar example is undo history in a note-taking app, where the latest action is reversed first. Another example is a bank token queue, where customers are served in arrival order. Industry-specific use cases include BFS job processing, compiler expression parsing, and rate-limited task scheduling.

Balanced parentheses, next greater element, and expression evaluation usually need stacks. Level-order traversal and shortest path in an unweighted graph usually need queues.

Code Example

5.Hashing

Hashing maps keys to values using a hash function. Standard structures are hash set, hash map, frequency map, ordered hash map, and hash table with collision handling through chaining or open addressing. Average lookup, insertion, and deletion are O(1), but worst-case can degrade if collisions are severe.

A familiar example is checking whether a PAN number has already been submitted during onboarding. An industry-specific example is fraud detection in payments, where transaction IDs can be stored in a hash set to detect duplicate processing. Hashing is also the backbone of grouping, counting, caching, and deduplication problems.

Use a hash map when the problem asks for “first occurrence”, “frequency”, “seen before”, “pair with target sum”, or “group by key”. Sorting may work, but hashing often preserves linear-time performance.

Code Example

6.Recursion and Backtracking

Recursion solves a problem by calling the same function on a smaller input. Backtracking is recursion with controlled exploration: choose, explore, and undo. Standard variants include linear recursion, tree recursion, divide-and-conquer recursion, tail recursion, subset generation, permutation generation, combination search, and constraint satisfaction.

A familiar example is generating all possible phone keypad combinations for a support helpline. An industry-specific example is assigning nurses to shifts in a hospital while respecting constraints such as availability and maximum hours. Backtracking is powerful when the search space is large but constraints can prune invalid paths early.

Missing the base case causes infinite recursion. Forgetting to undo a choice during backtracking corrupts later branches and produces wrong results.

Code Example

7.Sorting and Searching

Sorting arranges data in a defined order, while searching locates a target or boundary. Sorting variants include bubble sort, selection sort, insertion sort, merge sort, quick sort, heap sort, counting sort, radix sort, bucket sort, and stable built-in sorts. Searching variants include linear search, binary search, lower bound, upper bound, and binary search on answer.

A familiar example is sorting food delivery orders by delivery time. An industry-specific example is ranking insurance claims by risk score before manual review. Binary search applies only when the search space is monotonic: if a condition is true at some point, it remains true on one side.

Merge sort has O(n log n) worst-case time and O(n) extra space. Quick sort has O(n log n) average time but O(n²) worst-case without good pivoting. Binary search is O(log n), but only on sorted or monotonic spaces.

Code Example

8.Trees and BSTs

A tree is a hierarchical structure with nodes and edges, while a binary tree limits each node to at most two children. Important types include general tree, binary tree, full binary tree, complete binary tree, perfect binary tree, balanced tree, binary search tree, AVL tree, red-black tree, B-tree, and expression tree.

A familiar example is a family hierarchy, where parent-child relationships form a tree. An industry-specific example is a database index, where B-trees help locate records efficiently. Tree traversals include preorder, inorder, postorder, and level order; BST inorder traversal produces sorted order.

For a valid BST, every node in the left subtree must be smaller than the root and every node in the right subtree must be larger. Checking only immediate children is not enough.

Code Example

9.Heaps and Priorities

A heap is a complete binary tree that keeps either the minimum or maximum element at the root. Standard variants include min heap, max heap, binary heap, d-ary heap, binomial heap, Fibonacci heap, and priority queue abstraction. In interviews, binary heaps are the most common implementation.

A familiar example is showing the cheapest train options first after a search. An industry-specific example is a cloud monitoring system that always processes the most severe alert before lower-priority logs. Heaps are ideal for Top K, merging sorted streams, scheduling, and Dijkstra’s algorithm.

Python’s standard heapq module implements a min heap. For max heap behavior, store negative values or wrap objects with reversed comparison logic.

Code Example

10.Tries

A trie is a tree-like structure where each path represents a prefix. Common variants include standard trie, compressed trie or radix tree, suffix trie, ternary search tree, and binary trie for bitwise queries. Tries trade memory for fast prefix operations.

A familiar example is contact search on a phone, where typing “ra” suggests names starting with that prefix. An industry-specific example is a logistics platform matching pincode prefixes for serviceability rules. Tries are useful for autocomplete, spell check, dictionary search, prefix count, and longest prefix matching.

A trie can consume high memory when the alphabet is large and strings share few prefixes. Use hash maps for children instead of fixed-size arrays when the character set is sparse.

Code Example

11.Range Query Structures

Range query structures answer questions over subarrays efficiently. The main variants are prefix sum, difference array, sparse table, square-root decomposition, Fenwick tree, lazy Fenwick tree, segment tree, and lazy segment tree. Choose based on whether updates are absent, point-based, or range-based.

A familiar example is calculating monthly expense totals from daily transactions. An industry-specific example is a stock analytics service answering repeated range maximum or sum queries over price history. Prefix sums are best for static sums, Fenwick trees for point updates with prefix queries, and segment trees for broader associative operations.

Fenwick tree update and prefix query are O(log n). Segment tree range query and point update are also O(log n), but segment trees handle more operations such as min, max, GCD, and lazy range updates.

Code Example

12.Graph Algorithms

A graph contains vertices and edges. Core variants include directed graph, undirected graph, weighted graph, unweighted graph, cyclic graph, acyclic graph, connected graph, disconnected graph, dense graph, sparse graph, tree, DAG, multigraph, and bipartite graph. Representations include adjacency list, adjacency matrix, and edge list.

A familiar example is metro stations connected by routes. An industry-specific example is a recommendation graph where users, restaurants, and orders form relationships. Essential algorithms include BFS, DFS, topological sort, cycle detection, Dijkstra, Bellman-Ford, Floyd-Warshall, Prim, Kruskal, and strongly connected components.

Use BFS for shortest path in an unweighted graph. Use Dijkstra for non-negative weighted graphs. Use Bellman-Ford when negative edges may exist. Topological sort works only on a DAG.

Code Example

13.Disjoint Set Union

Disjoint Set Union, also called Union-Find, tracks elements split into non-overlapping sets. The two key optimisations are path compression and union by rank or size. It supports find and union operations almost in constant amortized time, commonly written as O(α(n)), where α is the inverse Ackermann function.

A familiar example is grouping mobile numbers that belong to the same household plan. An industry-specific example is detecting whether adding a network cable would create a cycle in a data-center topology. DSU is heavily used in Kruskal’s minimum spanning tree, connected components, account merging, and offline query problems.

The standard interview question is cycle detection in an undirected graph. If an edge connects two vertices already in the same DSU set, adding that edge creates a cycle.

Code Example

14.Greedy Algorithms

Greedy algorithms make the best local choice at each step. They work only when the problem has greedy-choice property and optimal substructure. Standard greedy categories include interval scheduling, activity selection, fractional knapsack, Huffman coding, job sequencing, minimum spanning tree, coin change for canonical coin systems, and shortest paths with non-negative edges.

A familiar example is choosing the maximum number of non-overlapping movie shows in one day. An industry-specific example is a logistics platform assigning deliveries by earliest deadline to reduce missed SLA windows. Greedy solutions are short, but the proof matters: sorting by the right key is usually the heart of the solution.

Greedy does not work for every optimisation problem. The classic 0/1 knapsack problem needs dynamic programming, while fractional knapsack works greedily by value-to-weight ratio.

Code Example

15.Dynamic Programming

Dynamic programming stores answers to overlapping subproblems. The main variants are top-down memoization, bottom-up tabulation, one-dimensional DP, two-dimensional DP, interval DP, tree DP, digit DP, bitmask DP, DP on graphs or DAGs, and space-optimised DP. DP is used when brute force repeats the same states.

A familiar example is calculating the number of ways to climb stairs when you can take one or two steps. An industry-specific example is an ed-tech platform recommending an optimal learning path based on prerequisite completion and available time. Define state, transition, base case, order of computation, and final answer.

A DP solution is incomplete until you can state the state definition and transition. For example, dp[i] may mean “best answer considering the first i items”; without that meaning, the recurrence is easy to misuse.

Code Example

16.Bit Manipulation

Bit manipulation works directly with binary digits. Core operations include AND, OR, XOR, NOT, left shift, right shift, set bit, clear bit, toggle bit, check bit, count set bits, extract lowest set bit, and bitmask enumeration. It is useful when values are naturally represented as flags or compact states.

A familiar example is storing notification preferences where SMS, email, and WhatsApp alerts are individual bits. An industry-specific example is a permissions system in a SaaS product where read, write, export, and admin capabilities are combined in one integer mask. XOR is especially common for finding unique values.

The expression x & (x - 1) removes the lowest set bit. It is used to count set bits in O(number of set bits), which can be faster than checking every bit.

Code Example

17.Math and Number Theory

Math-based DSA covers arithmetic techniques that reduce brute force. Standard subtopics include divisibility, prime testing, sieve of Eratosthenes, GCD, LCM, modular arithmetic, modular inverse, fast exponentiation, permutations, combinations, factorial precomputation, matrix exponentiation, and probability basics.

A familiar example is calculating the next common billing cycle using LCM. An industry-specific example is cryptographic key handling, where modular arithmetic appears heavily in public-key systems. Competitive and interview problems often use modulo 1,000,000,007 to keep large counting answers bounded.

Euclid’s algorithm computes GCD in O(log min(a, b)) time. The relation lcm(a, b) = abs(a × b) // gcd(a, b) is frequently tested.

Code Example

Choose the structure from the required operation: fast lookup suggests hashing, ordered range queries suggest trees, repeated optimal subproblems suggest DP, shortest unweighted path suggests BFS, and top K suggests heap.

---

Problem-Solving Patterns

Patterns connect problem statements to implementation choices. During dsa quick revision, practise recognising these triggers before writing code: contiguous range, sorted input, repeated state, graph relation, top K, prefix, cycle, or monotonic condition.

Sliding Window

Sliding window handles contiguous subarray or substring problems. Fixed-size windows solve problems such as maximum sum of k consecutive values. Variable-size windows solve problems such as longest substring with at most k distinct characters.

A familiar example is finding the highest spending streak across seven days of wallet transactions. An industry-specific example is monitoring the maximum API errors in any five-minute window for a cloud service. Use this pattern when the answer depends on a continuous segment.

Code Example

Two Pointers

Two pointers use two indices that move through data in a controlled way. Variants include opposite-direction pointers, same-direction fast-slow pointers, partition pointers, and merge pointers. This pattern often reduces O(n²) pair checks to O(n) after sorting or when monotonic movement is possible.

A familiar example is finding two wallet transactions that add up to a target budget after sorting amounts. An industry-specific example is merging two sorted logs from different servers into one chronological stream. Fast-slow pointers are also used to detect cycles in linked lists.

Code Example

---

Learning Path

Use this roadmap to convert the cheat sheet into a practical study plan. Each phase builds one layer: correctness, efficiency, pattern recognition, and interview readiness.

---

Frequently Asked Questions

What is DSA Cheat Sheet: All Concepts in One Page (Free PDF)?

It is a compact reference that summarises data structures, algorithms, patterns, complexity rules, and common implementation templates in one place. You can use this page for revision and save it as a dsa cheat sheet pdf using your browser’s print-to-PDF option.

What should a dsa cheat sheet include?

It should include complexity analysis, arrays, strings, linked lists, stacks, queues, hashing, recursion, sorting, searching, trees, heaps, tries, range query structures, graphs, DSU, greedy, DP, bit manipulation, and number theory. It should also include when to use each concept, not only definitions.

How do I use this cheat sheet for interview revision?

Start with the comparison table, then revise one concept group at a time. For every topic, ask three questions: what operation is needed, what structure supports it efficiently, and what is the time-space complexity?

When should I use hashing instead of sorting?

Use hashing when you need fast lookup, frequency counting, duplicate detection, or pair checks in expected O(1) time per operation. Use sorting when order matters, memory should be lower, or the problem depends on ranking, intervals, or monotonic scanning.

When should I use dynamic programming instead of greedy?

Use greedy only when a local choice can be proven safe for the global optimum. Use DP when choices interact across states, subproblems overlap, and trying one locally best choice may block a better future answer.

What is the most common DSA mistake in interviews?

The most common mistake is jumping into code before identifying the pattern and constraints. A solution that works for small input may fail if O(n²) is used where n is large and an O(n log n) or O(n) solution is expected.

How many DSA patterns are enough for placements?

There is no fixed number, but most placement problems repeatedly use arrays, strings, hashing, two pointers, sliding window, binary search, recursion, trees, graphs, heaps, greedy, and DP. Depth matters more than memorising labels.

Is Python acceptable for DSA interviews?

Python is accepted in many interviews and coding platforms, but you must know its performance characteristics. Lists, dictionaries, sets, deque from collections, and heapq are especially useful; the official collections documentation is a reliable reference.

---

Key Takeaways

The most useful DSA revision points are concrete: arrays give fast indexing, hashing gives expected O(1) lookup, heaps solve Top K and priority problems, BFS solves unweighted shortest paths, DSU tracks components, and DP removes repeated subproblem work.

For GATE and interviews, the most tested areas are time complexity, recursion recurrence, sorting bounds, tree traversals, BFS versus DFS, Dijkstra versus Bellman-Ford, greedy proof, DP state transition, and amortized DSU complexity.

The natural next step is to turn this dsa cheat sheet into active practice: pick one concept daily, solve three mixed problems without looking at the topic tag, write the complexity first, and then code the cleanest accepted solution.