Skip to content

Find Pivot Index

Leetcode 724. Find Pivot Index

Table of Contents

Leetcode 724. Find Pivot Index

Problem

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

Source : Leetcode 724. Find Pivot Index

Solution

To solve this problem, we can go through the array and keep track of cumulative sum of elements appeared so far. Before doing this, we have to get the total sum of the array.

Now let’s say the total sum is sum and the cumulative sum is stored in sum_so_far.

At any index, sum_so_far is the cumulative sum so far before reaching to that index.

At any index, we can get the sum to the right of that index by subtracting (sum_so_far + value at that index) from the total sum, right? In other word, we can that at index i of nums array by doing sum – nums[i] – sum_so_far.

So, at the index we will find sum_so_far = sum – nums[i] – sum_so_far, that index is our pivot index!

To see the solution in action, let’s say we have an array nums and variables sum and sum_so_far as below.

Leetcode 724. Find Pivot Index
Leetcode 724. Find Pivot Index

At first, we loop through the array and find that our sum is 28. So, we update sum as below.

Leetcode 724. Find Pivot Index
Leetcode 724. Find Pivot Index

Now, for each element we have to calculate values as discussed. At i = 0, our sum_so_far is 0 and sum – nums[i] – sum_so_far is 27. So, there is no match and we increment i.

Leetcode 724. Find Pivot Index
Leetcode 724. Find Pivot Index

At i = 1, our sum_so_far is 1 and sum – nums[i] – sum_so_far is 20. So, there is no match and we increment i.

Leetcode 724. Find Pivot Index
Leetcode 724. Find Pivot Index

At i = 2, our sum_so_far is 8 and sum – nums[i] – sum_so_far is 17. So, there is no match and we increment i.

Leetcode 724. Find Pivot Index
Leetcode 724. Find Pivot Index

At i = 3, our sum_so_far is 11 and sum – nums[i] – sum_so_far is also 11. So, there is a match and our pivot index is i !

So, we will stop searching at this point and return i as our desired answer!

Leetcode 724. Find Pivot Index
Leetcode 724. Find Pivot Index

Remember, if there is no pivot index found, we will have to return -1.

Below code is straight forward and should not be too hard to understand.

Code
C++
class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int sum_so_far = 0;
        int sum = 0;
        int len = nums.size();
        
        for(int i = 0; i < len; i++)
            sum += nums[i];
        
        for(int i = 0; i < len; i++){
            if(sum_so_far == (sum - nums[i] - sum_so_far))
                return i;
            sum_so_far += nums[i];
        }
        return -1;
    }
};
Conclusion

Hope you enjoyed the solution, though it was an easy problem 🙂 Please let us know what difficulty you are facing solving leetcode problems. If you love our blog or hate it, please shout out!

Happu coding! 🙂

47 thoughts on “Find Pivot Index”

  1. I discovered your blog site on google and check a few of your early posts. Continue to keep up the very good operate. I just additional up your RSS feed to my MSN News Reader. Seeking forward to reading more from you later on!…

  2. Excellent beat ! I would like to apprentice whilst you amend your website, how can i subscribe for a blog
    website? The account helped me a acceptable deal. I have been a little bit acquainted of this your broadcast offered vivid transparent concept

  3. What’s up, every time i used to check blog posts here early in the morning, because i love to find out more and more.

  4. I am truly grateful to the holder of this site who has shared this impressive paragraph at at
    this place.

  5. I’m truly enjoying the design and layout of your site.
    It’s a very easy on the eyes which makes it much more enjoyable for me
    to come here and visit more often. Did you hire out a developer to create your theme?
    Great work!

  6. After going over a few of the articles on your blog, I seriously like your way
    of writing a blog. I book-marked it to my bookmark site list and will be checking back soon. Take a look at my website too and tell me what you
    think.

  7. I have read so many content regarding the blogger lovers except this article is
    really a fastidious paragraph, keep it up.

  8. Hey There. I discovered your blog using msn. That is a very neatly written article.
    I will make sure to bookmark it and come back to learn more of your useful information. Thank you for the post.
    I’ll definitely return.

  9. Fabulous, what a web site it is! This web site provides valuable information to us, keep it up.

  10. Just desire to say your article is as amazing. The clearness in your submit is just excellent and that i can suppose you are knowledgeable on this subject.
    Well along with your permission let me to clutch your feed
    to keep updated with forthcoming post. Thank you one million and please carry
    on the enjoyable work.

  11. Somebody essentially assist to make severely posts I’d state.
    That is the very first time I frequented your web page and to this point?
    I amazed with the research you made to create this actual submit extraordinary.
    Excellent process!

  12. Howdy are using WordPress for your site platform? I’m new to the blog world but I’m trying to get started
    and create my own. Do you need any html coding
    expertise to make your own blog? Any help would be greatly appreciated!

  13. This is a topic that is close to my heart…
    Cheers! Exactly where are your contact details though?

  14. This design is steller! You obviously know how to
    keep a reader entertained. Between your wit and your videos, I was almost moved
    to start my own blog (well, almost…HaHa!) Excellent job.

    I really loved what you had to say, and more than that, how you presented it.
    Too cool!

  15. That is a really good tip especially to those fresh to the
    blogosphere. Brief but very accurate information… Thanks for
    sharing this one. A must read article!

  16. You should be a part of a contest for one of the most useful sites on the net.
    I will recommend this website!

  17. Hello there! I could have sworn I’ve been to this web site before but after going through a few of the articles I realized
    it’s new to me. Anyhow, I’m definitely happy I discovered it and I’ll be book-marking it and checking back
    frequently!

  18. all the time i used to read smaller articles or reviews that as well clear
    their motive, and that is also happening with this paragraph which I am reading here.

  19. Today, while I was at work, my cousin stole my apple ipad and tested to see if it can survive a 40 foot
    drop, just so she can be a youtube sensation. My apple ipad is now destroyed and she has 83 views.

    I know this is entirely off topic but I had
    to share it with someone!

  20. Very great post. I just stumbled upon your weblog and wanted to mention that I’ve
    truly enjoyed surfing around your weblog posts. In any case I will be subscribing for your rss feed
    and I am hoping you write once more very soon!

  21. Hi there, You have done a great job. I will definitely digg it and personally suggest to my friends. I am sure they’ll be benefited from this web site.

  22. To the foolishhungry.com administrator, Your posts are always well-supported by facts and figures.

  23. I loved even more than you will get done right here. The picture is nice, and your writing is stylish, but you seem to be rushing through it, and I think you should give it again soon. I’ll probably do that again and again if you protect this walk.

  24. I do believe all the ideas youve presented for your post They are really convincing and will certainly work Nonetheless the posts are too short for novices May just you please lengthen them a little from subsequent time Thanks for the post

  25. I do not even know how I ended up here but I thought this post was great I do not know who you are but certainly youre going to a famous blogger if you are not already Cheers

  26. It was impossible for me to leave your website without expressing my gratitude for the excellent knowledge you give your visitors. Without a doubt, I’ll be checking back frequently to see what updates you’ve made.

Leave a Reply

Your email address will not be published. Required fields are marked *