DSA PATTERNS Problems - rs-hash/GETTHATJOB GitHub Wiki

DSA-BASICS

1. Two-Pointers-Patterns

This technique involves using two pointers to traverse through the data structure (usually an array or string). The pointers can move towards each other or in the same direction at different speeds.

Use cases:

  • Searching for pairs or triplets that meet specific conditions.

  • Comparing elements from opposite ends.

  • Merging two sorted arrays.

2. Fast-and-Slow-Pointers-(Tortoise-and-Hare)

A variation of the two pointers technique where one pointer moves faster (two steps) than the other (one step), often used to detect cycles or find the middle of a structure.

Use cases:

  • Detecting cycles in linked lists.

  • Finding the middle of a linked list.

3.Sliding-Window-Pattern

The sliding window technique is used to handle subarray or substring problems. It involves using two pointers (left and right) to represent the current window and sliding the window across the array.

Use cases:

  • Finding subarrays or substrings with specific properties.

  • Optimizing problems that involve contiguous elements.

4.Merge-Intervals-Pattern

The merge intervals pattern involves working with intervals (start and end points). The goal is often to merge overlapping intervals or find gaps between intervals.

Use cases:

  • Merging intervals.

  • Checking for overlapping intervals.

5. Binary-Search-Pattern

Binary search is used to find an element in a sorted array or range. The core idea is to repeatedly divide the search space in half.

Use cases:

  • Searching in sorted arrays.

  • Optimizing search-related problems.

6. Breadth first search pattern

BFS is an algorithm used for searching or traversing a graph or tree. It explores all the nodes at the present depth level before moving on to nodes at the next depth level.

Use cases:

  • Finding the shortest path in an unweighted graph.

  • Solving problems involving levels or layers (e.g., distance from a source).

7.Depth‐First Search (DFS) Pattern

DFS is used for searching or traversing a tree or graph by exploring as far down a branch as possible before backtracking.

Use cases:

  • Solving problems in graphs or trees (e.g., finding paths, counting components).

  • Detecting cycles in graphs.

8. Topological Sort (Graph-based)

What it is: Topological sort is a linear ordering of vertices in a Directed Acyclic Graph (DAG), where for every directed edge 𝑢→𝑣 vertex 𝑢 comes before 𝑣in the ordering.

Use cases:

  • Solving problems related to dependencies (e.g., course scheduling).

9. Union-Find (Disjoint Set Union)

Union-Find is a data structure used to efficiently manage and merge disjoint sets. It supports two main operations: find (to find which set an element belongs to) and union (to merge two sets).

Use cases:

  • Solving problems involving connected components.

  • Detecting cycles in graphs

10. Dynamic Programming (DP)

Dynamic programming is a technique for solving problems by breaking them down into simpler subproblems and storing the results of subproblems to avoid redundant computation.

Use cases:

  • Solving optimization problems.

  • Solving problems involving recurrence relations.

11. Backtracking Pattern

Backtracking is an algorithmic approach for solving problems incrementally by trying partial solutions and abandoning (backtracking) them as soon as it’s determined they cannot lead to a valid solution.

Use cases:

  • Solving constraint satisfaction problems.

  • Generating all possible permutations or combinations.

12. Heap / Priority Queue Pattern

A heap is a specialized tree-based data structure that satisfies the heap property. It’s typically used to implement priority queues, where the highest (or lowest) priority element can be accessed in constant time.

Use cases:

  • Finding the k-th largest/smallest elements.

  • Scheduling problems or problems involving prioritization

13. Trie (Prefix Tree)

A trie is a tree-like data structure that stores strings or sequences, where each node represents a common prefix of strings.

Use cases:

  • Efficient searching and prefix matching (e.g., autocomplete).

  • Storing a large dictionary or set of strings.

14. Segment Tree

A segment tree is a binary tree used to represent intervals or segments. It allows querying and updating of segments (range queries) efficiently.

Use cases:

  • Solving range query problems (e.g., sum or min/max queries on a range).

15. Matrix Manipulation Pattern

Matrix manipulation involves performing operations (like searching, updating, or rotating) on two-dimensional grids.

Use cases:

  • Solving problems related to 2D arrays (e.g., pathfinding, rotation, or searching).

16. Greedy Algorithm Pattern

Greedy algorithms make the optimal choice at each step with the hope of finding the global optimum. These algorithms work well when a problem has an optimal substructure and local optimums lead to the global optimum.

Use cases:

  • Problems that can be solved by making a series of choices that seem the best at the moment.

  • Optimizing problems like finding the minimum or maximum of certain attributes (e.g., sum, weight, cost).

17. Bit Manipulation Pattern

Bit manipulation involves directly working with bits (0s and 1s) using bitwise operations (AND, OR, XOR, etc.). It is useful for efficiently solving problems involving numbers at the bit level.

Use cases:

  • Solving problems that involve binary numbers or bit operations.

  • Reducing the time complexity of problems involving numbers or flags.

18. Divide and Conquer Pattern

Divide and conquer involves breaking a problem down into smaller subproblems, solving them independently, and then combining the results. This is especially useful for recursive problems.

Use cases:

  • Sorting and searching algorithms.

  • Problems that can be split into independent subproblems.

19. Top K / Kth Largest Element Pattern

The problem is focused on finding the Kth largest or Kth smallest element in a collection. It can be solved using various methods such as sorting, heaps, or quickselect algorithms.

Use cases:

  • Finding the Kth largest or smallest element in a list.

  • Selecting the top K elements from a collection.

20. Matrix Traversal Pattern

Matrix traversal is about iterating through 2D arrays and performing specific operations on each element.

Use cases:

  • Pathfinding problems on grids (e.g., BFS/DFS).

  • Traversing all or some elements in a matrix.

21. Binary Indexed Tree (Fenwick Tree)

The Binary Indexed Tree (BIT) is a data structure that allows efficient updates and queries on prefix sums, making it useful for problems involving range sums or cumulative frequency tables.

Use cases:

  • Solving problems that involve range sum queries or cumulative sum problems.

22. Hash Map / Hashing Pattern

Hash maps are used for efficient key-value mapping and searching. They allow fast lookups, inserts, and deletions based on keys.

Use cases:

  • Problems that involve counting, grouping, or finding relationships between elements.

  • Problems where you need to store and quickly access elements.

23. Recursion Pattern

Recursion is when a function calls itself to break down a problem into smaller subproblems. Recursive solutions are often elegant and intuitive, especially for tree or graph traversal problems.

Use cases:

  • Problems that can be broken down into smaller instances of the same problem (e.g., factorial, Fibonacci).

  • Traversing trees and graphs.

24. Matrix DP Pattern

Dynamic Programming (DP) applied to problems involving matrices. These typically deal with finding paths, sums, or solutions to subproblems within a matrix or grid.

Use cases:

  • Problems involving the traversal of matrices where the solution builds up incrementally.

25. Monotonic Stack Pattern

A monotonic stack is a stack that maintains its elements in a monotonic order (increasing or decreasing). This technique is used to solve problems where maintaining order of elements helps optimize the solution.

Use cases:

  • Solving problems involving the next greater element or the previous smaller element.

26. Divide and Conquer (Binary Search Trees / AVL Trees)

A form of divide and conquer applied to balanced binary search trees (BSTs) or AVL trees, used to optimize searching, inserting, and deleting operations.

Use cases:

  • Efficient searching, insertion, and deletion operations in trees.