Scribd
Upload
7 views6 pages

DSA Python Pattern Notes v2

The document outlines various data structures and algorithms including Hashing, Sliding Window, Two Pointers, Stack, Heap, BFS, and DFS, explaining their use cases, examples, and Python code implementations. Each technique is described with its intuition, when to use it, and when not to use it. The content is aimed at helping programmers efficiently solve specific types of problems.

Uploaded by

Shreyas GN
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
7 views6 pages

DSA Python Pattern Notes v2

The document outlines various data structures and algorithms including Hashing, Sliding Window, Two Pointers, Stack, Heap, BFS, and DFS, explaining their use cases, examples, and Python code implementations. Each technique is described with its intuition, when to use it, and when not to use it. The content is aimed at helping programmers efficiently solve specific types of problems.

Uploaded by

Shreyas GN
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

1.

Hashing (Dictionary)

Hashing allows storing and retrieving data in constant time using key-value pairs. In Python,
dictionaries implement hashing.

Intuition: Instead of searching through a list (O(n)), store values so you can instantly check
existence.

Example Problem: Two Sum — Given array and target, find indices of two numbers adding to
target.

Approach: Traverse array, store visited numbers in dictionary. For each element x, check if target-x
exists.

Python Code: d = {}; for i,x in enumerate(arr): if target-x in d: return [d[target-x], i]; d[x]=i

When to use: Pair problems, frequency counting, prefix sums.

When NOT to use: When order matters strictly or constraints are very small.
2. Sliding Window

Sliding window is used for contiguous subarray/substring problems.

Intuition: Maintain a window using two pointers. Expand to include elements, shrink when condition
breaks.

Example: Longest substring without repeating characters.

Approach: Use set/map to track characters, move left pointer when duplicate appears.

Python Code: left=0; s=set(); for right in range(len(str)): while str[right] in s: [Link](str[left]);
left+=1; [Link](str[right])

When to use: Substring, subarray, max/min length problems.

When NOT to use: Non-contiguous problems.


3. Two Pointers

Two pointers technique is used when working with sorted arrays or searching pairs.

Intuition: Start from both ends and move pointers inward based on condition.

Example: Find pair with target sum in sorted array.

Python Code: left, right = 0, len(arr)-1; while left<right: if arr[left]+arr[right]==target: return True

When to use: Sorted input, pair problems.

When NOT to use: Unsorted data without preprocessing.


4. Stack

Stack follows LIFO (Last In First Out). Python list can be used.

Example: Valid Parentheses.

Approach: Push opening brackets, pop when matching closing bracket appears.

Python Code: stack=[]; for c in s: if c in '([{': [Link](c); else: if not stack: return False;
[Link]()

When to use: Matching, recursion simulation.

When NOT to use: Queue-like problems.


5. Heap (Priority Queue)

Heap is used for efficiently retrieving smallest/largest elements.

Python uses min heap via heapq.

Example: Top K frequent elements.

Approach: Use heap of size k.

Python Code: import heapq; [Link](heap,x); [Link](heap)

When to use: Top K, scheduling.

When NOT to use: Simple sorting problems.


6. BFS and DFS

BFS explores level by level using queue. DFS explores depth using recursion.

Example: Number of Islands.

Approach: Traverse grid, mark visited nodes.

Python Code BFS: from collections import deque; q=deque(); [Link]((i,j))

When to use: Graphs, trees, grids.

When NOT to use: Simple array problems.

You might also like