Scribd
Upload
9 views2 pages

DSA in Python CheatSheet

This cheat sheet provides an overview of various data structures and algorithms in Python, including arrays, strings, recursion, searching, sorting, hashing, stacks, queues, linked lists, trees, heaps, graphs, and dynamic programming. Each section includes definitions, approaches, advantages, use cases, and examples. It serves as a quick reference for implementing these concepts in Python.

Uploaded by

axyyyz8
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
9 views2 pages

DSA in Python CheatSheet

This cheat sheet provides an overview of various data structures and algorithms in Python, including arrays, strings, recursion, searching, sorting, hashing, stacks, queues, linked lists, trees, heaps, graphs, and dynamic programming. Each section includes definitions, approaches, advantages, use cases, and examples. It serves as a quick reference for implementing these concepts in Python.

Uploaded by

axyyyz8
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

■ DSA in Python – Cheat Sheet

Arrays / Lists
• Definition: Sequential collection of elements.
• Approach: Index-based access, iteration, sliding window.
• Advantages: Fast access O(1) by index.
• Use Cases: Searching, subarrays, Kadane’s, Prefix sums.
• Example: nums = [1,2,3,4,5] → nums[2] = 3

Strings
• Definition: Immutable sequence of characters.
• Approach: Use slicing, hashing, two-pointers.
• Use Cases: Anagrams, Palindrome, Pattern Matching.
• Example: 'racecar' == 'racecar'[::-1] → True

Recursion
• Definition: Function calling itself until base case.
• Advantages: Simplifies backtracking problems.
• Use Cases: Factorial, Fibonacci, N-Queens.
• Example: def fact(n): return 1 if n==0 else n*fact(n-1)

Searching
• Linear Search: O(n).
• Binary Search: O(log n) (requires sorted array).
• Use Cases: Search element, Rotated array search.
• Example: binary_search([1,2,3,4], 3) → 2

Sorting
• Basic: Bubble, Insertion, Selection (O(n²)).
• Efficient: Merge, Quick, Heap sort (O(n log n)).
• Use Cases: Ranking, Median, Interval scheduling.
• Example: sorted([5,2,9,1]) → [1,2,5,9]

Hashing
• Definition: Key-value mapping using hash functions.
• Advantages: O(1) average lookups.
• Use Cases: Two Sum, Frequency count.
• Example: Counter('banana') → {'a':3, 'b':1, 'n':2}

Stacks & Queues


• Stack: LIFO (Undo operations).
• Queue: FIFO (Task scheduling).
• Use Cases: Balanced Parentheses, BFS.
• Example: stack.append(10); stack.pop()

Linked List
• Definition: Nodes with value + pointer.
• Advantages: Dynamic size, O(1) insert/delete at head.
• Use Cases: Queues, Stacks, Hash chains.
• Example: class Node: def __init__(self,val): self.val=val; self.next=None

Trees (BST, Binary Tree)


• Definition: Hierarchical data structure.
• Traversals: Inorder, Preorder, Postorder, BFS.
• Use Cases: Expression trees, Indexing, Autocomplete.
• Example: inorder(root) → traversal order

Heaps
• Definition: Complete binary tree with heap property.
• Advantages: Efficient min/max retrieval.
• Use Cases: Priority queue, Kth largest.
• Example: heapq.nlargest(2, [3,2,1,5,6,4])[-1] → 5

Graphs
• Definition: Nodes + edges.
• Traversal: BFS, DFS.
• Use Cases: Social networks, Routing, Dependencies.
• Example: graph={0:[1,2],1:[0,3],2:[0],3:[1]}

Dynamic Programming (DP)


• Definition: Solve problems by breaking into subproblems.
• Approach: Recursion + memoization / tabulation.
• Use Cases: Fibonacci, Knapsack, LCS.
• Example: fib(10) → 55

You might also like