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.
At first, we loop through the array and find that our sum is 28. So, we update sum as below.
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.
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.
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.
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!
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! 🙂
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!…
medkcq
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
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.
I am truly grateful to the holder of this site who has shared this impressive paragraph at at
this place.
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!
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.
I have read so many content regarding the blogger lovers except this article is
really a fastidious paragraph, keep it up.
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.
Fabulous, what a web site it is! This web site provides valuable information to us, keep it up.
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.
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!
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!
This is a topic that is close to my heart…
Cheers! Exactly where are your contact details though?
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!
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!
You should be a part of a contest for one of the most useful sites on the net.
I will recommend this website!
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!
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.
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!
Very good write-up. I certainly love this website.
Stick with it!
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!
To the foolishhungry.com owner, Your posts are always insightful and valuable.
Dear foolishhungry.com administrator, You always provide valuable feedback and suggestions.
Hi foolishhungry.com owner, Your posts are always well-supported by research and data.
Dear foolishhungry.com admin, You always provide valuable information.
To the foolishhungry.com owner, Your posts are always well-balanced and objective.
Hi foolishhungry.com administrator, Your posts are always well organized and easy to understand.
To the foolishhungry.com admin, Your posts are always well-referenced and credible.
generic priligy We expect this situation to reverse from 2014, though there may be occasional shortfalls in the event of major equipment upgrade
Dear foolishhungry.com webmaster, Your posts are always informative and well-explained.
Hi foolishhungry.com owner, Great post!
6l1fl4
What a stuff of un-ambiguity and preserveness of valuable knowledge on the topic of unexpected feelings.
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.
Dear foolishhungry.com webmaster, Thanks for the well-researched and well-written post!
Thank you for your sharing. I am worried that I lack creative ideas. It is your article that makes me full of hope. Thank you. But, I have a question, can you help me? https://accounts.binance.com/ur/register-person?ref=T7KCZASX
To the foolishhungry.com administrator, Your posts are always well-supported by facts and figures.
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.
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
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
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.
Dear foolishhungry.com administrator, Thanks for the comprehensive post!
Thank you for your sharing. I am worried that I lack creative ideas. It is your article that makes me full of hope. Thank you. But, I have a question, can you help me? https://www.binance.com/it/register?ref=OMM3XK51
Can you be more specific about the content of your article? After reading it, I still have some doubts. Hope you can help me. https://www.binance.info/sv/join?ref=P9L9FQKY
Well-written article, very helpful!
To the foolishhungry.com webmaster, Your posts are always a great source of knowledge.
The 21st century presents unprecedented challenges and opportunities, demanding an educational paradigm that prepares students not just for today but equips them with the skills to navigate an ever-changing future.
Your article helped me a lot, is there any more related content? Thanks!
I don’t think the title of your article matches the content lol. Just kidding, mainly because I had some doubts after reading the article.
To the foolishhungry.com owner, Your posts are always well thought out.
Thank you for your sharing. I am worried that I lack creative ideas. It is your article that makes me full of hope. Thank you. But, I have a question, can you help me?
Buy Drugs
Wow, marvelous weblog structure! How long have you ever been blogging
for? you made running a blog look easy. The full look of
your web site is magnificent, as neatly as the content material!
You can see similar here sklep