Pythagorean Algorithm explained.

I remember watching one of my friends solve a Rubik's Cube in high school, and just baffled at how he was able to solve it consistently under a minute. I would ask him and he would just tell me "You just need to know the algorithm!", as he proceeded to show me the site that tells you the exact steps you need to take to solve it. After about a month of studying and practice, I can proudly say that I was able to reach under 30 seconds during one of my Spanish 3 lectures.

As I prepare for interviews, I've had the chance to look over many different interview questions. At this point, they all look difficult to the point where I would not know how they could even come up with a solution just like when I first tried to solve the Rubik's Cube. However, just like back in high school, I remember that I never knew why those steps led to the solution, I just knew that they did what I needed them to do.

As I continue to prepare for interviews, I wanted to take a look at some of the more challenging algorithm problems that might be asked in an interview. So with that, let's take a look at a problem I found on a site for popular interview questions.

Here's the problem:

Given an array of integers, write a function that returns true if there is a triplet (a, b, c) that satisfies a^2 + b^2 = c^2.

This problem is checking for if there are any Pythagorean triplets, which is essentially looking for if the squared results of two numbers equal the squared result of the third number. In solving this problem, first thing to recognize is that we would probably have to check 3 different numbers at a time, and then set a condition to check whether the sum of those two of those numbers squared would match up with the third number squared.

In the case of using for loops, we are capable of checking only one element of the array at a time, doing something to that element in the array until we reach the end. Here's an example.

for(i = 0; i < array.length; i++){
   array[i] = array[i] ** 2
}

However, in our case, one for loop won't do. What we'd want is to have 3 different elements being checked at the same time so 3 nested for loops.

Let's take some time to put what 3 different for loops would be doing into words. First off, when we are doing a check, we can probably keep one index the same until the other two indexes have completed checking the combination of two numbers that don't include that number. Given the combination doesn't satisfy our conditions, we can move to a different number for our first index and check the other numbers for a combination of two that doesn't include our first number.

A set of 3 nested for loops all with conditions that start off with the index at 0 and then increment to the end of the array would cause the inner loops to check indexes that the first index is also on. You would get check to check elements array[0], array[0], array[0], and then move on to array[0], array[0], array[1]. Since we don't want any repeat numbers, and only want to check combination of unique numbers, we'd want to set each index to one above the parent loop. Then we can let the inner loop run to the last index, and then move up the index of outside loop when inside loop/loops are finished with all combinations. This way we can loop through all the unique combinations.

One other thing we should remember is that just like how we don't want the inner loop to ever access the first element, we don't want the first loop to ever access the last element. In order to do that we set the condition for the loop as array.length - 1 and array.length - 2.

Here's the code for checking each unique combination when using 3 indexes:

function pythagoreanCheck(array){
  for(i = 0; i < array.length - 2; i++){
    for(j = i + 1; j < array.length - 1; i++){
      for(k = j + 1; k < array.length; k++){
        *condition for returning true*
      }
    }
  }
}

Next we have the condition for passing the test. First of all, each element that we are checking needs to be squared. We are not checking for the element itself, but the element squared. We can go ahead and make variable that can square each index element we are checking for.

The variables would be for each index:

x = arr[i] * arr[i] 
y = arr[j] * arr[j]
z = arr[k] * arr[k]

Our remaining requirement is to check whether the variables we are using fit the pythagorean theorem requirement. For it to meet this, we would simply need to have a sum of any two to equal the remaining variable.

This condition would look like this:

if (x + y == z || x + z == y || z + y == x) 

To wrap it up, if these conditions we just defined are met in any of the combinations we've checked, that should return true. If we don't meet this requirement after checking all combinations, this function does not have a pythagorean triplet and should return false.

Here is the final solution:

function pythagoreanCheck(array){
  for(i = 0; i < array.length - 2; i++){
    for(j = i + 1; j < array.length - 1; i++){
      for(k = j + 1; k < array.length; k++){
        let x = arr[i] * arr[i], y = arr[j] * arr[j], z = arr[k] * arr[k]

        if(x + y == z || x + z == y || z + y == x){
          return true
        } 

      }
    }
  }
  return false
}

I do want to make a small note about this problems Big O Notation. This is not the most efficient way to do this problem, as it is a O(n^3) notation (uses a loop within a loop... within a loop). Using 3 loops within each other means you have to check an element x number of times, x being the length of the array to the power of 3. For now I will leave it with this solution.