How To Solve Algorithm And Data Structure Problems [Tips]

Nam Nguyen's photo
Nam Nguyen
·

5 min read

Table of contents

Are you struggling to solve coding problems? I’d like to share my own method to approach the solution. This is a reference on which I can build your own.

A. 5 Steps To Solve A Problem

1. Comprehend problem

  • Read the problem carefully (and underline keywords)
  • Extract rules from problem

2. Analyze Test Cases/Examples

  • Identify and evaluate Input/Output
  • Understand how the output is produced for each input

3. Define Data Structure

4. Design Algorithm

5. Implement Algorithm

  • Write algorithm in code

B. Example

Given an array A of integers of size n. Commute the maxim sum of s contiguous elements in the array. Return -1 if there is no valid output.

Input : A = [5,3,1,2], s = 2
Output: 8

Input : A = [1], s = 3
Output: -1

1. Comprehend Problem

Information extraction:

  • An array of integer
  • The maximum sum
  • Contiguous elements
  • Return -1 if no valid input

When you read the problem carefully, you can extract crucial information and make it explicit to solve the problem. If you don’t highlight out important terms, you will not be able to come to the correct output, which is time-consuming. For example, if you miss “contiguous” (consecutive), you will try to find a maximum combination from a set of combinations of the array, which is absolutely wrong.

However, sometimes you face strange terminology which the problem’s author uses to describe the problem, I recommend you check out the list of common terms, List of terms relating to algorithms and data structures

2. Analyze Test Cases/Examples

You utilize the above information extraction to apply on the input and return the correct output, so that you evaluate your understanding on the given problem. After that, you should try to think beyond on the given examples for edge cases. Edge cases are unexpected inputs which drive your algorithm to be incorrect.

Given A = [5,3,1,2], s = 2
Output: 5 + 3 = 8

3. Define Data Structure

In this problem, you can directly use the given array as a representation of data. In other problems, you should think of all possible data structures, list them out on paper, and choose the most efficient one. For example, if you want to map one item to another item (key-value relationship), a hash table is the best choice.

4. Design Algorithm

To make the game start easily, you can come up with a brute-force solution, which is the inefficient algorithm. Then you try to optimize it by thinking beyond it. You use and modify techniques or good algorithms to fit your certain problem. Therefore, reading articles, books and other codes is useful to improve your knowledge of algorithms.

In this example, I would solve it in the brute-force way, and then optimize it with a technique called “Window Sliding”.

# Brute-force solution

Initialize max_sum as INT_MIN
For every element `index` from 0 to (n-s+1)
    Set current_sum as 0
    For every `number` from 0 to s
        current_sum = current_sum + arr[index+number]
    max_sum = max(max_sum, current_sum)

The above solution, you need to use one loop and one inner loop to iterate through s elements to find the maximum sum. It takes O(ns) times to gain the correct output. But can we eliminate s to reduce only O(n). That’s where the “Window Sliding” technique comes to our playground.

Window Sliding is a technique of using a “window” with a specific length and run operation in this window. More specifically, consider a sub-array of length s, and move the sub-array by one element. Following the below figures to understand more:

Iteration 1 Iteration 1 Iteration 2 Iteration 2

# Optimal solution:
Initialize max_sum as INT_MIN
Initialize window_sum as 0

For every element `index` from 0 to s:
    window_sum += array[index]

max_sum = window_sum
For every element `index` from s to n:
    # Move to next window, and subtract the first
    # element in the previous window
    window_sum += arr[index] - arr[index - s]
    max_sum = max(max_sum, window_sum)

5. Implement Algorithm

Here’s is a C# implementation of the above algorithm:

public static int MaxContiguousSum(int[] arr, int n, int s) {
   if(n < s)
     return -1;

   int max_sum = Int32.MinValue;
   int window_sum = 0;
   for(int i = 0; i < s; i++)
     window_sum += arr[i];

   max_sum = window_sum;
   for(int i = s; i < n; i++) {
     window_sum += arr[i] - arr[i-s];
     max_sum = Math.Max(window_sum, max_sum);
   }

   return max_sum;
 }

C. Summary

I hope that my step-by-step instructions can help you to form your own method of solving future problems. Remember, here is only a tip of solving a problem, and it does not try to show this is the only technique you should use to cope with any problem. Therefore, the more important tip I want to give you is PRACTICE, PRACTICE, AND PRACTICE.

If you find any mistakes in my post, you can comment below to correct me. Thanks for reading.

data structuresalgorithmstips