Scribd
Upload
2 views3 pages

DSA Patterns Guide

The document outlines various data structure and algorithm (DSA) patterns, detailing their use cases and providing examples for each. Key patterns include Two Pointers, Sliding Window, Fast and Slow Pointers, and Dynamic Programming, among others. Each pattern is accompanied by a template for implementation and specific scenarios where it is most effective.

Uploaded by

sohailalhaddad
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
2 views3 pages

DSA Patterns Guide

The document outlines various data structure and algorithm (DSA) patterns, detailing their use cases and providing examples for each. Key patterns include Two Pointers, Sliding Window, Fast and Slow Pointers, and Dynamic Programming, among others. Each pattern is accompanied by a template for implementation and specific scenarios where it is most effective.

Uploaded by

sohailalhaddad
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

DSA Patterns - Theory, Use Cases, and Examples

1. Two Pointers

Use When: You're working with sorted arrays or comparing two elements from different ends.

Examples: Reverse String, Two Sum II, Container With Most Water.

Template:

left, right = 0, len(arr) - 1

while left < right:

# your condition here

left += 1 or right -= 1

2. Sliding Window

Use When: You need to find subarrays or substrings in a range.

Examples: Maximum Sum Subarray of Size K, Longest Substring Without Repeating Characters.

Template:

start = 0

for end in range(len(arr)):

# expand window

while window_invalid:

# shrink window from left

start += 1

3. Fast and Slow Pointers

Use When: Detecting cycles (like in linked lists or number transformations).

Examples: Linked List Cycle, Happy Number.

4. Hashing / HashMap

Use When: You need O(1) lookup, counting, or checking for previously seen values.

Examples: Two Sum, Isomorphic Strings, Group Anagrams.

5. Prefix Sum / Difference Array


DSA Patterns - Theory, Use Cases, and Examples

Use When: Repeated sum in a range, optimization.

Examples: Subarray Sum Equals K, Range Sum Query.

6. Binary Search

Use When: Working with sorted arrays or when conditions are monotonic.

Examples: Binary Search, Search Insert Position, Peak Element.

7. Backtracking

Use When: Exploring all combinations or permutations.

Examples: Subsets, Permutations, N-Queens.

8. Greedy

Use When: You can make locally optimal choices for globally optimal results.

Examples: Jump Game, Activity Selection.

9. Stack-Based Patterns

Use When: Parsing expressions, finding next greater/smaller elements.

Examples: Valid Parentheses, Daily Temperatures.

10. Dynamic Programming (DP)

Use When: Overlapping subproblems and optimal substructure are present.

Examples: Climbing Stairs, House Robber, LCS.

11. Two Heaps

Use When: Finding median in a stream, maintaining top-k.

Examples: Median from Data Stream, Kth Largest Element.

12. Topological Sort (Graph / DAG)


DSA Patterns - Theory, Use Cases, and Examples

Use When: Solving ordering problems with dependencies.

Examples: Course Schedule, Alien Dictionary.

13. Union Find / DSU

Use When: Handling disjoint sets, cycle detection in graphs.

Examples: Number of Islands, Kruskal's Algorithm.

14. Trie (Prefix Tree)

Use When: Handling prefix-based search.

Examples: Implement Trie, Replace Words.

15. Bit Manipulation

Use When: Optimizing for space or bit-level tricks.

Examples: Single Number, Counting Bits.

You might also like