Goglides Dev 🌱

Nitish Kafle
Nitish Kafle

Posted on • Originally published at dev.to on

Solving Find Pivot Index from LeetCode + Explanation

Question Link: https://leetcode.com/problems/find-pivot-index/

Question:

Given an array of integers nums, calculate the pivot index of this array.

Explanation:

First lets look at the example and try to understand the logic behind it.

According to the example, we have an Array of numbers.

When we visualize it, along with index we get:

Example

Now, Looking at the image, if we add 3 elements on the left, and 2 elements on the right, we get 11. So, the element in between has an index which will be pivot index.

In our case,

Array[3] = 6, therefore, 3 is our pivot index.

Logic:

Now, lets walk through the problem on how we can check for the pivot index.

First, we need to know the sum of all elements in the array and denote it as totalSum, which in our case is 28.

Then lets have sum of all elements in the left index and denote it as leftSum

Now lets create a table with these element and also lets track the element on the index tht we have and denote it as Index[e] and check what it is equal to.

Logic behind the problem

Let's approach the problem from the right to the left.

Our leftSum currently is 0 because we did not add anything. And the Index[e] is the element of the array on that index.

Doing this for each item in the array, we end up in one condition where leftSum equals to the same number that is in leftSum. The next index after that condition is the pivot Index.

And our problem is to find that pivot Index.

Congrats! You have successfully diagnosed the problem!

Now, let's create the logic from the result we had:

totalSum - leftSum - Index[e] = leftSum

Now let's implement it in terms of code:

I'm using JavaScript

function(index){

  // initialize the sums, 0 because we don't know the sums yet.

   let totalSum = 0; 
   let leftSum = 0; 

   // now let's calculate the total sum

   nums.forEach((element) => totalSum += element);

/* 
now we have the sum, so we want to check for the condition.
but before that, we need to loop through each element in the array.
*/

   for(let e=0; e<nums.length; e++){
      if(totalSum - leftSum - index[e] === leftSum){
         return e;
      }
      leftSum += index[e]
   }
   return -1;
}

Enter fullscreen mode Exit fullscreen mode

We checked for that condition, and returned the index if it satisfied the condition since we were looking for that pivot index.

In case, the exact condition did not pass, we had to add another element of the array to the leftSum as we did in the exercise above.

And, if there was no pivot index, it would return -1 as per the question requirement.

Congrats! You did it!

The solution might not be optimal in terms of runtime and memory distribution, but hey, you figured out the concept behind it and implemented it!

Cover Photo by Arnold Francisca on Unsplash

Thanks for reading. If you have any questions, feel free to send them my way on Twitter @developernit

Top comments (0)