Steps of Problem-Solving in Data Structure and Algorithms

Published in

EnjoyAlgorithms

7 min readNov 21, 2021

Every solution starts with a strategy, and an algorithm is a strategy for solving the coding problem. So programmers must learn to design an efficient algorithm and translate this “algorithm” into the correct code to get the job done.

However there are many coding problems available in data structures and algorithms, and most of the time, these problems are new to us. As programmers, we need to develop ourselves into confident problem solvers who are not intimidated by the difficulty of the given problems.

Our long-term goal should be simple: to learn how to design correct and efficient code within a given timeframe. As we practice more and more, we will gain more experience in problem-solving, making our work easier. Here are some essential skills that we should practice for every coding problem:

Developing an approach to understanding the problem.
Thinking of a correct basic solution.
Designing a step-by-step pseudocode solution.
Analyzing the efficiency of the solution.
Optimizing the solution further.
Transforming pseudocode into correct code.

Now, the critical question would be: Is there a well-defined guided strategy to approach and solve a coding problem? If yes, then what are the critical steps? Let’s think and explore!

Step 1: Understanding the problem

Solving a problem requires a clear understanding of the problem. Unfortunately, sometimes we read the first few lines and assume the remaining part of the problem. Or sometimes, we ignore this step because of something similar we have seen in the past. We should believe these as an unfair practice and develop a clear approach to problem understanding.

During problem solving, every small detail can help us to design an efficient solution. Sometimes a tiny change in the question may change the solution approach. Taking short extra time in problem understanding will give us more confidence later. The fact is: we never want to find out halfway through that we misunderstood the problem.

It doesn’t matter if we have gone through a question in the past or not: we should read the question several times. So take a paper and write down everything while going through the problem. Exploring through some examples will also help us clarify how many cases our algorithm can handle and the possible input-output patterns. We should also explore the scenario for large input, edge cases, and invalid input. Sometimes it’s pretty common for a problem description to suffer from these types of deficiency:

The problem description may rely on some undefined assumptions
The problem description may be ambiguous or incomplete
The problem description has various contradictions

These deficiencies may be due to the abstract explanation of the problem description in our natural languages. So it’s our responsibility to identify such deficiency and work with the interviewer or problem provider to clarify it. We should start by seeking answers to the following questions:

What are the input and output?
What type is data is available?
What is the size or the scale of the input?
How is data stored? What is the data structure?
Are there some special conditions or orders in the data?
What rules exist for working with the data?

Step 2: Thinking of a correct basic solution

The best approach would be to think of a correct solution that comes immediately into our thought. It does not matter even it is in an inefficient approach i.e. having a correct and inefficient answer is much better than an incorrect solution or significant delay in the solution. This could help us in so many ways:

Help us to build good confidence or motivation in the start.
Provide an excellent point to start a conversation with the interviewer.
Sometimes, it provides a hint to improve efficiency by reducing some loops, removing some intermediate steps, or performing some operations efficiently.

Here are some examples of brute force patterns: three nested loops, two nested loops, solution using extra memory, solution using sorting, double traversal in the binary tree, considering all sub-array or substrings, exhaustive search, etc.

After thinking and communicating the brute force idea, the interviewer may ask for its time and space complexity. We need to work on paper, analyze each critical operation and write in the form of Big-O notation. A clear conceptual idea of time and space complexity analysis is essential at this stage. A good practice of various code pattern analyses (iterative, recursive, etc.) would help a lot.

Step 3: Designing efficient pseudocode solutions

This is a stage to use the best experience of problem-solving and apply various problem-solving strategies. One practical truth is: moving from a basic algorithm to the most efficient algorithm is a little difficult in a single step. Each time, we need to optimize the previous algorithm and stop when there is no further optimization possible. Revisiting the problem description and looking for some additional information can help a lot in further optimization. For example:

If the input array is sorted or similar to sorted order, we can think to apply a single loop, two pointers approach, the idea of binary search, etc.
If the input array is unsorted, we can use the divide and conquer approach, hash table, sorting with two pointers, etc.
If we need some output for subarray of size k, we can think to apply a hash table or sliding window concept, etc.
We can use a divide and conquer, dynamic programming, or greedy algorithm approach if we have an optimization problem.
If we need to search solution with a given constraint, we can think to use the idea of backtracking.

The idea would be simple: we should learn the use case of efficient problem-solving patterns on various data structures. Continuously thinking, analyzing, and looking for a better solution is the core idea.

Here are some best examples of problems where several levels of optimizations are feasible. Practicing such types of coding questions helps a lot in building confidence.

Find equilibrium index of an array

Using nested loops: Time = O(n²), Memory = O(1)
Using prefix sum array: Time = O(n), Memory = O(n)
Using single scan: Time = O(n), Memory = O(1)

Trapping rain water

Using nested loops: Time = O(n²), Memory = O(1)
Using Dynamic Programming: Time = O(n), Memory = O(n)
Using Stack: Time = O(n), Memory = O(n)
Using two pointers: Time = O(n), Memory = O(1)

Check for pair with a given sum

Using nested loops: Time = O(n²), Memory = O(1)
Using sorting and binary search: Time = O(nlogn), Memory = O(1)
Using sorting and Two Pointers: Time = O(nlogn), Memory = O(1)
Using a Hash Table: Time = O(n), Memory = O(n)

Find the majority element in an array

Using two nested loops: Time = O(n²), Memory = O(1)
Using Sorting: Time = O(nlogn), Memory = O(1)
Using the divide and conquer: Time = O(nlogn), Memory = O(logn)
Using a Hash Table: Time = O(n), Memory = O(n)
Using Bit Manipulation: Time = O(n), Memory = O(1)
Using Randomisation: Time = O(logn), Memory = O(1)
Note: If value of n is very large.
Boyer-Moore Voting Algorithm: Time = O(n), Memory = O(1)

Maximum Subarray Sum

Using three nested loops: Time = O(n³), Memory = O(1)
Using two nested loops: Time = O(n²), Memory = O(1)
Using divide and conquer: Time = O(nlogn), Memory = O(logn)
Using dynamic programming: Time = O(n), Memory = O(n)
Kadane algorithm: Time = O(n), Memory = O(1)

Additional problems to practice steps of problem-solving

Before you jump into the end-to-end code implementation, it’s good practice to write pseudocode on paper. It would be helpful in defining code structure and critical operations. Some programmers skip this step, but writing the final code becomes easier when we have well-designed pseudocode.

Step 4: Transforming pseudocode into a clean, correct, and optimized code

Finally, we need to replace each line of pseudocode with actual code in our favorite programming languages like C++, Java, Python, C#, JavaScript, etc. Never forget to test actual code with sample test data and check if the actual output is equal to the expected output. When writing the code in your interviews, discuss the sample data or test cases with the interviewer.

Simplifying and optimizing the code may require a few iterations of observation. We need to ask these questions once we are done writing the code:

Does this code run for every possible input, including the edge cases?
Can we optimize the code further? Can we remove some variables or loop or some extra space?
Are we repeating some steps a lot? Can we define it separately using another function?
Is the code readable or written with a good coding style?

EnjoyAlgorithms 16-Week Live DSA Course: Admission Open

EnjoyAlgorithms 10-Week Live DSA Course: Admission Open

Enjoy learning, Enjoy coding, Enjoy algorithms!