Essential DSA Patterns for Efficient Problem Solving
Learning DSA with countless approaches and techniques available, can be overwhelming. This is where we can make use of different DSA Patterns. They simplify our complex problem by providing frameworks to tackle the problem efficiently. It can be a game-changer to enhance our problem-solving skills.
In this article, We will learn about 14 essential DSA patterns, their use, how to identify them, example problems, etc. Whether you’re just getting started or sharpening your skills, these patterns will serve as your go-to toolkit for solving a wide range of challenges.
1. Sliding Window:
· Used to perform operations on particular window length
· Used in linear data structures (i.e arrays, linked list, string, etc).
· It efficiently finds subarrays or substrings within a given range by maintaining a “window” that slides over the input data.
· Keywords to identify in which problem we should use sliding window pattern are: linear data structure, substring, subarray.
Example: find the length of the longest substring without repeating characters.
Input: S = “abcabcbcb”
Output: 3
Explanation: answer is “abc” with length = 3
For this problem we are told to find length of longest substring. Here we use sliding window pattern. Where the substring will be represented as the window.
We use a hashmap and 2 pointers a left and a right pointer which will iterate through the window.
2. Two Pointer:
· It uses two pointers to traverse in both directions, i.e start and end. Used in array, linked list problems.
· We use 2 pointers in place of 1 pointer because it helps us to reduce the runtime.
Ways to identify when to use 2 Pointer Pattern:
· When we are given sorted arrays or Linked list and need to find set of elements that fulfil certain given condition
· Set of elements in array is pair, triplet or a subarray.
Some examples of problems where we use Two Pointer:
· Squaring a sorted array
· Triplet that sums up to zero
· 2 Sum, 3sum.
· Comparing strings containing backspaces
3. Fast and Slow pointer / hare and tortoise algorithm:
· Uses 2 pointers which moves through an array with different speeds.
· Fast pointer should catch slow pointer to get the desired solution.
When to use Fast and slow pointer pattern:
· Problems dealing with loop in a Linked list or array
· When we are told to find position of certain element or the over length of linked list
· Circular Linked list.
Problems where we use this pattern:
· Linked list cycle
· Palindrome in linked list
· Cycle in circular array
4. Merging Intervals:
· used to solve problems involving intervals.
· It involves overlapping intervals and requires merging, finding gaps, or other interval-based operations.
6 Types of overlapping:
1. ‘a’ and ‘b’ doesn’t overlap.
2. ‘a’ and ‘b’ overlap and ‘b’ end after ‘a’.
3. ‘a’ completely overlaps ‘b’.
4. ‘a’ and ‘b’ overlaps, ‘a’ ends after ‘b’.
5. ‘b’ completely overlaps ‘a’.
6. ‘a’ and ‘b’ do not overlap.
When to use this pattern:
· If asked to produce a list with only mutually exclusive intervals.
· If “overlapping intervals” this term is used in the problem.
· Merge intervals question.
5. Cyclic Sort:
· used for solving problems involving numbers in a range.
· Eg. Arrays containing numbers in a given range.
When to use this pattern:
· Problems involving sorted array with numbers in a given range.
· If problem asks to find missing, duplicate or smallest number in a sorted or rotated array.
Problems where we use this pattern:
· Finding Missing Number.
· Find Smallest Missing Positive Number.
Get Vaishnavi Parodkar| Software Engineer’s stories in your inbox
Join Medium for free to get updates from this writer.
6. In-place:
· used to optimize space usage.
· Directly modifies input data without using extra space another data structure, apart from few variables for temporary storage.
· Eg. Linked List Reversal.
Reverse the links between the set of nodes of linked list
Constraints: do it by using in-place i.e using existing node objects and without using extra memory.
When to use this pattern:
· If asked to reverse a linked list without using extra memory.
Problems where we use this pattern:
· Reverse Sub-list
· Reverse k-elements in a Linked list
7. Tree BFS (Breadth First Search):
· used in case of tree traversal and in graph and tree related algorithms.
· We need to traverse the tree and use queue to keep track of all nodes of a level before jumping to next level.
When to use this pattern:
· If asked to traverse a tree in a level-by level fashion or level order traversal.
Problems where we use this pattern:
· Binary Tree level order traversal
· Zig-zag traversal
8. Tree DFS (Depth First Search):
· using recursion to traverse a tree by visiting all nodes or exploring paths in a tree.
· Uses recursion or stack to keep track of all previous nodes, for iterative approach.
· Starts from root of the tree, if node is not equal to leaf then we need to do 3 things:
Decide whether to process current node now (pre-order) or between processing two children (in-order) or after processing both children(post-order).
· Make 2 recursive calls for both children of current node to process them
When to use this pattern:
· If asked to traverse a tree with in-order, pre-order or post-order DFS.
· If problem requires searching for something where node is closer to leaf.
Problems where we use this pattern:
· Sum of path numbers.
· All paths for sum
9. Two heaps:
· Used to solve problems involving median calculation, managing two distinct data groups, or efficiently processing data streams.
· In many problems we are given set of elements that we can divide in 2 parts: smallest element in 1 part and largest in other part.
· Min heap and max heap are the two types which are used to find smallest and largest element respectively.
· Median of current list of elements can be calculated from top element of 2 heaps.
When to use this pattern:
· In situations like priority queues and scheduling.
· If problem says to find the smallest/largest/median element of set.
· Useful in binary tree data structure.
Problems where we use this pattern:
· Find median of number stream.
10. Subsets:
· used to solve problems involving permutations, combinations, or subsets of a given set of elements.
· Is an efficient BFS approach to handle all these problems.
· Eg. S=[1,2,3]
¨ Start with an empty set: []
¨ Add 1st no. to all existing subsets to create new subset: { [ ], [1] }.
¨ Add 2nd no. to all existing subsets to create new subset: { [ ], [1], [2], [1,2] }.
¨ Add 3rd no. to all existing subsets to create new subset: { [ ], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3] }
When to use this pattern:
· Problems where we need to find permutation and combination of given set.
Problems where we use this pattern:
· Subsets with duplicates
· String permutations by changing case.
11.Modified Binary Search:
· when sorted array, linked list or matrix are given and are asked to find certain element we use Binary Search.
· It is an extension of the traditional binary search algorithm.
When to use this pattern:
· The input is given as sorted, rotated or ordered.
· We need to search a specific element.
Problems where we use this pattern:
· Search in a Rotated Sorted array.
· Find the First or Last Occurrence of an Element.
· Find Peak Element.
· Find the Minimum in a Rotated sorted array
12. Top K elements:
· used in problems involving finding the top, smallest or most frequent K element from given set.
· Uses heap priority queues, or sometimes sorting data structure.
When to use this pattern:
· Useful when working with large datasets.
· Problems requiring partial order or selection
· Data where k elements need continuous updates.
· To minimize sorting or traversal of unrelated data.
Problems where we use this pattern:
· To Find K largest/smallest elements.
· To find K frequent elements.
13. K-way Merge:
· involve merging multiple sorted arrays or lists into a single sorted array or list.
When to use this pattern:
· Multiple sorted input lists.
· Sorting efficiency.
· When handling large datasets.
· Real time or incremental processing.
Problems where we use this pattern:
· Merge K sorted lists.
· Streaming Data.
· Find Smallest/largest elements.
14. Topological sort:
· is a graph-based ordering of vertices such that for every directed edge (u → v), vertex u comes before vertex v in the ordering.
· Key concepts of this pattern are: Directed Acyclic Graph and Ordering.
When to use this pattern:
· When input graph is directed acyclic graph. If graph contains cycles, this pattern can’t be applied.
· Problem containing Prerequisite dependencies.
Problems where we use this Pattern:
· Given the total number of courses and a list of prerequisites, determine if it is possible to finish all courses.
· Given a set of tasks and their dependencies, find the order in which they can be completed such that no task is left undone.
