Day 20 of Studying LeetCode Solution until I Can Solve One on My Own: Problem#724. Find Pivot Index(Easy/JavaScript)
Tags: javascript, webdev, programming, algorithms
Published: 2022-03-03 07:54:50

**Intro:** I am a former accountant turned software engineer graduated from coding bootcamp. Algorithms and Data Structure is an unavoidable part of interviews for most of the tech companies now. And one of my friends told me that you need to solve a medium leetcode problem under 60 seconds in order to get into the top tech companies.So I thought I'd start learning how to do it while job searching.

Since I have no clue on how to solve any of the problems (even the easy ones), I thought there is no point for me to waste hours and can't get it figured out. **Here is my approach:**
- Pick a leetcode problem randomly or Online Assessment from targeted companies.
- Study 1-2 solutions from Youtube or LeetCode discussion section. One brute force solution, another one more optimal.
- Write a blog post with detailed explanation and do a verbal walk through to help understand the solutions better.
- Code out the solution in LeetCode without looking at the solutions
- **Combat the forgetting curve:** Re-do the question for the next three days. And come back regularly to revisit the problem.

******************************************

**724. Find Pivot Index**
`Difficulty: Easy` `Language: JavaScript` 

<!--Goldman Sachs Interview-->

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

The **pivot index** is the index where the sum of all the numbers **strictly** to the left of the index is equal to the sum of all the numbers **strictly** to the index's right.

If the index is on the left edge of the array, then the left sum is `0` because there are no elements to the left. This also applies to the right edge of the array.

Return the **leftmost pivot index**. If no such index exists, return -1.

Example 1:
```
Input: nums = [1,7,3,6,5,6]
Output: 3
Explanation:
The pivot index is 3.
Left sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11
Right sum = nums[4] + nums[5] = 5 + 6 = 11
```
Example 2:
```
Input: nums = [1,2,3]
Output: -1
Explanation:
There is no index that satisfies the conditions in the problem
statement.
```
Example 3:
```
Input: nums = [2,1,-1]
Output: 0
Explanation:
The pivot index is 0.
Left sum = 0 (no elements to the left of index 0)
Right sum = nums[1] + nums[2] = 1 + -1 = 0
 ```

Constraints:
- `1 <= nums.length <= 104`
- `-1000 <= nums[i] <= 1000`
 

Note: This question is the same as 1991: https://leetcode.com/problems/find-the-middle-index-in-array/

******************************************

**Solution:**
Key to the solution below is to initially sum up all elements in the given array except index 0 as sum of right elements. Meanwhile, initialize sum of left elements as 0. Then keep reducing nums[i] from 'right' element and add nums[i] from 'left' element until a balance is found. 
```
var pivotIndex = function(nums) {
    
    let left = 0
    let right = 0

//initialize variables for sum of left and right elements
    
    for (let i = 1; i < nums.length; i++){

//loop (note 1) through 'nums' array starting from index 1

        right += nums[i]

//for each index i, add value of the element nums[i] to the
//'right' vaiable.
//sum up (note 2) all elements in the given array except index 0
//as sum of right elements.
        
    }

    if (right == 0) return 0

//Edge case: [2,-1,1]. If (note 3) elements starting from index 1
//add up to 0, we will return 0. Because there is no elements to
//the left of index 0.
    
    for (let i = 0, j = 1; j < nums.length; i++, j++){
        right -= nums[j]
        left += nums[i]   

//keep reducing nums[j] from 'right' element and add (note 2)
//nums[i] from 'left' element until the pivot index is found.
        
        if(left == right) return i+1

//If at index i, sum of left elements equals (note 4) to the
//right, the pivot index will be i+1 or j-1. For example, in given
//array [1,7,3,6,5,6], when we get to index i = 2, Left sum =
//nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11 which equals to the
//right sum. We will return the index of the number next to 3,
//which is the first 6 in the array. 
//Index of that first 6 is 3 (i + 1).

    }
    
    return -1

//Return -1 if there is no index that satisfies the conditions in
//the problem statement. 

};
```
**Solution Submission detail as of 3/3/2022** 
(Data below could vary since there are new tests/submissions daily)
- Runtime: 79 ms
- Memory Usage: 44.3 mb

******************************************

**References:**
[LeetCode Problem Link](https://leetcode.com/problems/find-pivot-index/)
[Note 1: Loop and Iteration](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Guide/Loops_and_iteration)
[Note 2: Addition assignment (+=)](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Addition_assignment)
[Note 3: if...else](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Statements/if...else)
[Note 4: Equality (==)](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Equality)
[Blog Cover Image Credit](https://www.istockphoto.com/portfolio/monsitj?mediatype=photography)