Best way to solve DSA problems!!- Become a pro

Solving a DSA (Data Structures and Algorithms) problem can be pretty tough. This article should help you understand how to go about solving a DSA problem on websites like Leetcode, InterviewBit, and Geeksforgeeks.

These are the steps that you should follow:

Disclaimer: It is a pretty big article. Make sure to bookmark it and reference it from time to time.

Understand the question completely

Look at the question and try to understand it completely. Make sure to run through the examples to verify that your understanding of the problem is correct. How to do that? The input should give the required output. You should be able to verify that.

Write down stuff on paper if required. You need to be completely sure that you understand the problem before moving ahead.

Get an estimate of the required complexity

Look at the constraints and time limit. This should give you a rough idea of the expected time and space complexity. Use this step to reject the solutions that will not pass the limits. With some practice, you will be able to get an estimate within seconds of glancing at the constraints and limits.

Example

For an estimate, ~108 operations will take:

• 1s in C/C++
• 2s in Java
• 4s in Python

Most DSA problems will have the above time limits as well.

Learn how to estimate the required time complexity.

Example: For the above constraints and limits, anything worse than O(n) won’t pass.

Come up with edge cases

This is one of the most important stages. Most people miss this and get WA (wrong answers).

In most problems, you would be provided with sample input and output with which you can test your solution. These tests would most likely not contain the edge cases. Edge cases are the boundary cases that might need additional handling. Before jumping on to any solution, write down the edge cases that your solution should work on.

What are the edge/boundary cases and how to find them?

Boundary cases are the test cases that you can create based on the start and end boundary of the different constraint variables.

Example

In the above constraints, the boundary cases are:

• T (No. of test cases per run): 0, 1, and 1000
• N (No. of array elements per test): 1, 2, and 10000
• Array element value: -100000 and 100000. Should also test on -1, 0, and 1.

Create test cases (input and expected output) based on these values.

Note: Test cases mean both input and expected output.

There are different types of cases that you can create. It will be based on the use case. Learn the patterns and take care of them as you miss them on different problems.

Examples: Let’s say that the array elements can contain duplicates. Make sure to take a small test case with duplicates.

Note: It is not practical to create tests for large input sizes (T or N values) so avoid those if they are very big. Creating tests for large array element values is easy and so definitely create those.

Come up with a brute-force solution

Come up with a solution that solves this problem correctly. It should not be the most optimal one. This solution is the one that you can come up with in less than a minute.

When you start practicing DSA, it would most likely be an exponential or polynomial solution. With sufficient practice, your brute force solution would also be pretty optimal and close to the required solution.

This is generally not the solution you are going to code.

Steps:

• Try to come up with a correct solution as soon as possible.
• Dry run your solution on the sample test cases to verify if your solution is correct.
• Verify if your solution is optimal based on the time and memory limits. Do this by computing the approx number of operations based on the constraints. If it will pass then this is the required solution.
• Even if it is passing, give a minute to see if you can think of a more optimal solution.

Optimize your current solution (Repeat until required optimal solution)

Optimize your current solution if it is not going to pass based on the constraints and limits. This is one of the hardest parts of solving the problem. It gets easier with practice and comfort in the required DSA.

If you’ve already computed the estimated time complexity, you can easily accept/reject the optimization ideas that come up. You would generally come up with an optimal solution after multiple iterations.

For every optimization that you come up with, compute the time and space complexity of your solution and see if it would pass. Make sure that every optimization is sending you closer to a solution that will pass the limits.