Ahmed Radwan

Posted on Dec 25, 2022 • Originally published at nerdleveltech.com

How to Solve an Algorithm Problem? | With Examples

#algorithms #beginners #programming #tutorial

If you're stuck on an algorithm problem and not sure how to proceed, this blog post is for you! We'll go over some general tips on solving algorithm problems, as well as a specific example of an algorithm.

Table of content:

Introduction
What are the 4 steps of algorithmic problem solving?
Example #1
Example #2
Conclusion and References

Introduction

What is an Algorithm?

What is an algorithm? Put simply, an algorithm is a step-by-step procedure for solving a problem. Algorithms can be written in any programming language, but they all share some common characteristics. First and foremost, algorithms are sequence tasks. That means that the steps in the algorithm must be done in order, and each step depends on the results of the previous steps. Secondly, algorithms are deterministic: given the same input data, exactly the same program will produce the same output every time. Finally, there are some measures for an algorithm to be efficient. Time and space: those two measures determine how efficient your algorithm is.

How to Solve an Algorithm Problem?

We'll walk through some steps for solving a particular algorithm.

First, it's important to know the basics of algorithms: every problem can be broken down into a sequence of steps that can be solved. This is known as the analysis of algorithms. Sketch out the basic structure of your algorithm on paper first or a board to avoid confusion. write some thoughts about which does what.

If a problem involves mathematical operations, conceptualizing it in terms of equations may be helpful. Break down the equation into its component parts and see if any of those particular pieces can be simplified or eliminated altogether. If so, that will lead to a solution for the whole equation.

Another strategy is to try reversing what initially seems like an impossible task. Algorithms problems often have stages were doing something one-way results in an error message or produces no useful output at all. Reverse engineer those steps and see if anything productive comes out.

What are the 4 steps of algorithmic problem solving? and Example #1

Now that you know what an algorithm is, let's jump into some examples and take a look at how these techniques can be put into practice...

In the following we will use the problem challenge from leetcode number #387:

1) Understand the problem

The goal of any algorithm is to solve a problem. When solving an algorithm problem, it is important to understand the problem and the steps involved in solving it. This understanding will allow you to correctly follow the instructions and complete the task. Answer the common questions to be sure that you really understand the problem. Questions like what it does and what kind of input I'm expecting. what kind of output I should receive? Are there some exceptions I should be aware of? etc...

The goal of this challenge is to write a function that takes in a string and returns the index of the first letter in the string that does not repeat. For example, if the string is "nerd", the function should return 0, because the first letter "n" is the first non-repeating letter in the string. If the string is "abcdefg", the function should return 0, because the first letter "a" is the first non-repeating letter in the string.

If the string does not contain any non-repeating letters, the function should return -1. For example, if the input string is "abcabc", the function should return -1, because no letter in the string is unique or non-repeating.

2) Break the problem down

When solving algorithms problems, breaking them down into smaller parts is usually the best way to go. Once you understand how each part works and interacts with the others, you can solve the problem more quickly.

To solve this challenge, we need to do the following:

Iterate over the letters in the input string, and for each letter, keep track of how many times it appears in the string. We can do this using an object, dictionary, or map, where the keys are the letters in the string, and the values are the counts for each letter.
Once we have counted the occurrences of each letter in the string, we need to find the index of the first letter that has a count of 1 (i.e. the first non-repeating letter). To do this, we can iterate over the letters in the string again, and for each letter, check if its count in the object/dictionary is 1. If it is, we return the index of the letter.
If we reach the end of the loop without finding any value that has only 1 or non-repeating letters, we return -1 to indicate that no non-repeating letters were found.

3) Find your solution

We found one solution and the key steps in this solution are to keep track of the counts of each letter in the input string, and then to search for the first letter with a count of 1. If the count of this letter is 1 meaning that this letter only shows one time in the string. These steps can be implemented in a variety of ways, depending on the language and tools you are using to solve the challenge.

We will be demonstrating the solution with two programming languages JavaScript and Python:

The source code in JavaScript:

function firstNonRepeatingChar(s) {
  // Store the counts of each character in a dictionary
  const counts = {};
  for (const c of s) {
    if (c in counts) {
      counts[c] += 1;
    } else {
      counts[c] = 1;
    }
  }

  // Find the index of the first character with a count of 1
  for (let i = 0; i < s.length; i++) {
    const char = s[i];
    if (counts[char] === 1) {
      return i;
    }
  }

  // If no such character was found, return -1
  return -1;
}

Here are some examples of how this function can be used:

console.log(firstNonRepeatingChar("nerdlevel"))
// Returns 0, because the first character "n" is the first non-repeating character in the string

console.log(firstNonRepeatingChar("abcdefg"))
// Returns 0, because the first character "a" is the first non-repeating character in the string

console.log(firstNonRepeatingChar("abcabc"))
// Returns -1, because no character in the string is non-repeating

The source code in Python:

def first_non_repeating_char(s: str) -> int:
    # Store the counts of each character in a dictionary
    counts = {}
    for c in s:
        if c in counts:
            counts[c] += 1
        else:
            counts[c] = 1

    # Find the index of the first character with a count of 1
    for i, c in enumerate(s):
        if counts[c] == 1:
            return i

    # If no such character was found, return -1
    return -1

Here are some examples of how this function can be used:

print(first_non_repeating_char("nerdlevel"))
# Returns 0, because the first character "n" is the first non-repeating character in the string

print(first_non_repeating_char("abcdefg"))
# Returns 0, because the first character "a" is the first non-repeating character in the string

print(first_non_repeating_char("abcabc"))
# Returns -1, because no character in the string is non-repeating

print(first_non_repeating_char("Level"))
# Returns 0, because the first character "L" is the first non-repeating character in the string
# That's a problem because we all know the the letter L is l just different cases

4) Check your solution

Checking your solution again answers some questions like can I write a better code? by better I mean is the code I provided covering all cases of inputs? is it efficient? and by efficient, I mean using fewer computer resources when possible. If you're comfortable with your answers then check if there is another solution out there for the same problem you solved, if any are found. go through them I learned a lot by doing that. Also get some feedback on your code, that way you'll learn many ways of approaching a problem to solve it.

As we mentioned above we asked ourselves these questions but the algorithm we wrote couldn't go through all the different cases successfully: for example, The code can't handle the case when we handled two cases of the same character "L" and "l" in the word "Level"

So we need to address that in the following:

Now let's revisit the code that we wrote up and see if we can come up with another solution that will cover the all different cases of a character.

The source code in JavaScript:


function firstNonRepeatingChar(s) {
  // Store the string after converting it into lowercase
  let newS = s.toLowerCase()
  
  // Store the counts of each character in a dictionary
  const counts = {};
  for (const char of newS) {
    if (char in counts) {
      counts[char] += 1;
    } else {
      counts[char] = 1;
    }
  }

  // Find the index of the first character with a count of 1
  for (let i = 0; i < s.length; i++) {
    const char = newS[i];
    if (counts[char] === 1) {
      return i;
    }
  }

  // If no such character was found, return -1
  return -1;
}

Here are some examples of how this function can be used:

console.log(firstNonRepeatingChar("Level"))
// Returns 2, because the character "e" is the first non-repeating character in the string

The source code in Python:

def first_non_repeating_char(s: str) -> int:
    # Store the string after converting it into lowercase
    newS = s.lower()
  
    # Store the counts of each character in a dictionary
    counts = {}
    for char in newS:
        if char in counts:
            counts[char] += 1
        else:
            counts[char] = 1

    # Find the index of the first character with a count of 1
    for index, char in enumerate(newS):
        if counts[char] == 1:
            return index

    # If no such character was found, return -1
    return -1

Here are some examples of how this function can be used:

print(first_non_repeating_char("Level"))
# Returns 0, because the character "e" is the first non-repeating character in the string

Example #2

Now that you learned from the first example, let's jump into another challenge and apply the same techniques we used above:

This example from leetcode problem #125 Valid Palindrome

1) Understand the problem

Learn as much information as you can about the problem what is a Palindrome? Ask yourself what input you expect and what output is expected.

The Palindrome is a word, phrase, or sentence that is spelled backward as forwards. We expect a string and we can do a function that first cleans that string from any non-alphanumeric, then reverses it and compares it with the original string.

2) Break the problem down

Here is a step-by-step explanation of the algorithm in plain English:

Convert all uppercase letters in the string to lowercase. This is done so that the case of the letters in the string does not affect the outcome of the comparison.
Remove all non-alphanumeric characters from the string. This is done because only alphanumeric characters are relevant for determining if a string is a palindrome.
Reverse the resulting string. This is done so that we can compare the reversed string with the original string.
Compare the reversed string with the original string. If they are the same, then the original string is a palindrome. Otherwise, it is not.

Here is an example of how this algorithm would work on the string "A man, a plan, a canal: Panama":

The string is converted to lowercase, so it becomes "a man, a plan, a canal: panama".
All non-alphanumeric characters are removed, so the string becomes "amanaplanacanalpanama".
The string is reversed, so it becomes "amanaplanacanalpanama".
The reversed string is compared with the original string, and since they are the same, the function returns true, indicating that the original string is a palindrome.

3) Find your solution

According to the steps we wrote in the previous stage, let's put them into action and code it up.

The source code in JavaScript:

function isPalindrome(s) {
  // Convert all uppercase letters to lowercase
  s = s.toLowerCase();

  // Remove all non-alphanumeric characters
  s = s.replace(/[^a-z0-9]/g, "");

  // Reverse the string
  let reversed = s.split("").reverse().join("");

  // Compare the reversed string with the original
  return s == reversed;
}

Here are some examples of how this function can be used:

console.log(isPalindrome("A man, a plan, a canal: Panama")) // returns true
console.log(isPalindrome("race a car") )// returns false
console.log(isPalindrome("Never odd or even")) // returns true

The source code in Python:

def is_palindrome(s):
  # Convert all uppercase letters to lowercase and remove the spaces
  s = s.lower().replace(" ", "")

  # Create a translation table that maps non-alphanumeric characters to None
  trans_table = str.maketrans("", "", "'!#$%&\'()*+,-./:;<=>?@[\]^_`{|}~'")
  
  # Apply trans_table to remove non-alphanumeric characters
  s = s.translate(trans_table)
  
  # Reverse the string
  reversed = s[::-1]

  # Compare the reversed string with the original
  return s == reversed

Here are some examples of how this function can be used:

print(is_palindrome("A man, a plan, a canal: Panama")) # returns True
print(is_palindrome("race a car")) # returns False
print(is_palindrome("Never odd or even")) # returns True

4) Check your solution

We can make it more efficient by using the pointers method let's break it down into a few points below:

Create left and right pointers (will be represented by indices)
Make each pointer move to the middle direction
While moving to check each letter for both pointers are the same

The source code in JavaScript:

function isPalindrome(s) {
  // Convert all uppercase letters to lowercase & Remove all non-alphanumeric characters
  s = s.toLowerCase().replace(/[^a-z0-9]/g, "");

  // Creating the two pointers the left at beginning, right at the end.
  let left = 0
  let right = s.length -1

  while (left < right) {
    // Check if pointers having same values 
    if (s[left] != s[right]) return false

    // Move left pointer forward  
    left += 1

    // Move left pointer backword  
    right -= 1
  }
  return true
}

The source code in Python:

def is_palindrome(s):
  # Cleaning the string from all non-alphanumeric
  s = ''.join(filter(str.isalnum, s)).lower()

  # Creating the two pointers the left at beginning, right at the end.
  left = 0
  right = len(s) -1
  
  while left < right:
    # Check if pointers having same values 
    if s[left] != s[right]:
      return False
    
      # Move left pointer forward  
    left = left + 1
    
    # Move left pointer backword
    right = right -1
    
  return True

Conclusion and references

There are many resources available to help you out, and with more practice, you'll be able to solve many algorithm problems that come your way. This video is one of the great resources to learn about algorithms and data structures from FreeCodeCamp

It is important to keep a cool head and not get bogged down in frustration. Algorithms problems can be difficult, but with patience and perseverance, they can be solved.

When you are solving an algorithm problem, it is important to be able to check your solution against other solutions if possible to see how others approach the same problem. This is will help you to retain and understand the logic behind the different solutions so you'll need this kind of knowledge in the future solving problems.

By following the steps outlined in this article, you will be able to solve algorithm problems with ease. Remember to keep a notebook or excel sheet with all of your solutions so that you can revisit them later on that way you will gain maximum retention of the logic.

If you want to learn more about algorithms and programming, sign up for our mailing list. We'll send you tips, tricks, and resources to help you improve your skills.