Top 5 Data Structures and Algorithms to Master Competitive Programming!
This article is contributed by Bharat Khanna, Co-founder of Programming Pathshala, who has previously worked at Tower Research Capital as SDE-II.
The Competitive Programming World is really vast. There are many Data Structures and Algorithms that are consistently used in solving many problems. So, sometimes, it is really overwhelming for a beginner to know which Data Structures and Algorithms they should focus on to excel in Competitive Programming.
Here is a list of top Data Structures and Algorithms to master in order to move ahead at a good pace with Competitive Programming:
Dynamic Programming
Difficulty: Medium to Hard
This would be the one algorithmic paradigm you would have heard about a lot and also the one that people find the most difficult.
Steps to master Dynamic Programming (DP):
- Master Recursion and Backtracking first. This is a very important prerequisite to understand DP. Generally people tend to directly start with DP without understanding that DP is just one step ahead of Recursion.
- Understand the concepts of State and Memoization. Next step after learning Recursion is to understand what Overlapping Subproblems are and how Memoization can help in optimising Time Complexity in comparison to recursive approach.
- Learn how to write iterative DP now that you have mastered recursive DP.
- Read about some standard DP problems like Longest Increasing Subsequence, 0/1 Knapsack, Chain Matrix Multiplication, etc and understand their recursive and iterative solutions.
- Learn how to optimise Space Complexity in Dynamic Programming Solutions.
- Go for advanced DP techniques like DP on Trees, DP on Bitmasks, etc.
Graph Traversal Algorithms
Difficulty: Medium to Hard
Many Competitive Programming problems directly say “You are given a Graph with n nodes and m edges”. Many others, though not explicitly mentioned, can be modelled in the form of a graph. All these problems are mostly solved using graph traversal techniques like Depth First Search and Breadth First Search.
Steps to master Graph Traversal:
- Get some basic knowledge about Graphs like what are nodes, edges, connected components, degrees, etc.
- Learn how graphs are stored in different forms, be it adjacency lists or adjacency matrices
- Just like DP, understanding Recursion and Backtracking is very important to understand certain graph traversals, especially Depth First Search (DFS).
- Understanding how DFS works and why marking nodes visited is important to avoid infinite recursions. Solving simple problems like Cycle Detection, Bipartite Coloring will solidify your learning of this algorithm.
- Learn about Breadth First Search (BFS). Realise how BFS ensures that we always get the shortest path in an unweighted graph. For understanding BFS, a prerequisite might be to understand Queue Data Structure.
Binary Search Algorithm
Difficulty: Easy to Medium
Now, reading this you might have thought “Oh! I know what Binary Search is. It works on Sorted Arrays”. But, wait! There is much more to the story as Binary Search may be used in a lot of more cases and not just searching an element in a sorted array
Steps to master Binary Searching:
- Realise why Binary Search works on a sorted array. And, why it does not on an unsorted array.
- Understanding what separating conditions are and how that is the main reason for Binary Search working. Solve problems like Finding Single Element in a Sorted Array, H-index, etc. These problems will open you up to how vast Binary Search’s reach is
- Understand what are monotonic functions and how Binary Search can be used to find a certain value in a monotonic function where a threshold value is passed.
- Learn about Binary Search on Answer technique and how it relates to the monotonic function idea above. Solve many problems on Binary Search on answer. This is a common theme in CP
- More to explore: ideas related to how Binary Search works on doubles, what is ternary search and where that is used.
Mathematical Algorithms
Difficulty: Easy to Medium
Competitive Programming goes hand in hand with Mathematics. You can’t proceed in CP if you don’t understand certain concepts in Mathematics well enough.
Steps to master Mathematical Algorithms:
- Learn concepts of Permutations and Combinations. There are bound to be a lot of questions from time to time based on the ideas of Combinatorics. Make sure you are good with these ideas, specifically the basic ones like the product rule, sum rule, etc.
- Understand modular arithmetic. Any mathematical problem will generally ask you to give the answer modulo a number. The reason for this is to avoid overflows. For that, you need to understand how modular arithmetic works with operations like addition, subtraction, multiplication, division and powers.
- Learn about different ways to do primality testing using a simple loop, an optimised version of it, using a sieve of Eratosthenes, etc. Sieve can be expanded to a whole lot of categories of problems specially related to divisors and multiples.
- Decode the ideas of Greatest Common Divisors and Lowest Common Multiples. Understand the Euclid’s GCD Algorithm.
Range Queries: Sparse Tables and Segment Trees
Difficulty: Hard
From time to time, doing Competitive Programming, you will encounter numerous problems which seem simple but were made complicated by introducing multiple queries.
There are multiple techniques to master these types of problems.
Steps to master Range Query Problems:
- Learn certain Precomputation Techniques like Prefix/Suffix computation, etc to solve simpler multiple query problems.
- Learn about online and offline query handling techniques. Also, learn about interactive problems.
- Understand the ideas behind Sparse Tables and in what cases they are used. Extend this knowledge to understand the Lowest Common Ancestor problem on trees.
- Learn about Segment Trees and their use cases. Understand what Lazy Propagation is and the algorithm behind using it.
- Understand offline query answering techniques like sorting queries, Mo’s Algorithms, etc that are used in some advanced problems more often.
In conclusion, these are the techniques which we encounter more frequently while attempting the Competitive Programming problems on common platforms like Codeforces, Spoj, Atcoder, etc. But, this is by no means an exhaustive list of all that is to be studied for Competitive Programming.
Other, less frequently asked techniques like Shortest Path Algorithms, Flow Algorithms, Game Theory, Trie Data Structures, etc are also very important but are much less frequently asked than these techniques. So, these data structures and algorithms mentioned above could be taken as a very good starting point if you are stuck at not-so-good ratings in the world of CP to learn and revise.
Are you preparing for Top Tech Interviews, Explore our program, Renaissance, where Bharat teaches these five Data Structures and algorithms and much more.
