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
I appreciate you sharing this blog post. Thanks Again. Cool.
Dear foolishhungry.com owner, Well done!
Your article helped me a lot, is there any more related content? Thanks!
Dear foolishhungry.com webmaster, You always provide great information and insights.
Thanks for sharing. I read many of your blog posts, cool, your blog is very good.
To the foolishhungry.com admin, Your posts are always a great source of knowledge.
Dear foolishhungry.com webmaster, Thanks for the educational content!
Hey there! Do you know if they make any plugins to safeguard against hackers?
I’m kinda paranoid about losing everything I’ve worked hard on.
Any tips?
geinoutime.com
Fang Jifan은 “그럼 Tatars는 무섭습니까? “라고 편리하게 말했습니다.
geinoutime.com
Fang Jifan은 “아직도 무엇을하고 있습니까? 와서 도와주세요. “라고 외쳤습니다.
Hey! I know this is kinda off topic however , I’d figured I’d ask.
Would you be interested in exchanging links or
maybe guest writing a blog post or vice-versa? My website discusses a lot of the same topics as yours
and I think we could greatly benefit from each other. If you are interested feel free to send
me an e-mail. I look forward to hearing from you! Awesome
blog by the way!
geinoutime.com
강을 건너는 용은 말할 것도 없이 고개를 숙일 때가 있습니다… 샤오징은 그저 내시일 뿐입니다.
geinoutime.com
궁궐의 모든 한린들은 처음에는 어안이 벙벙했다.
geinoutime.com
그는 심지어… 오늘 내린 결정이… 광범위한 결과를 가져올 것이라는 것도 알고 있었습니다.
geinoutime.com
Fang Jifan은 도울 수 없었지만 “당신의 아버지, 당신은 정말 슬기로운 사람입니다 …”라고 말했습니다.
슬롯 게임
Xiao Jing은 이해하고 고개를 끄덕이며 고개를 끄덕였습니다. “이제 알아요.”
안전한 슬롯 사이트
이것이 계속된다면… 하나님은 그것이 어떤 것인지 아십니다.
Hi foolishhungry.com admin, Your posts are always well received by the community.
Dear foolishhungry.com administrator, You always provide clear explanations and step-by-step instructions.
월드 슬롯
이 Chen Wangzu는 Hongzhi 황제를 정말 실망 시켰습니다.
Dear foolishhungry.com webmaster, You always provide helpful diagrams and illustrations.
슬롯 꽁 머니
“봐라, 30등 75점! 아… 10등… 79점.”
프라그마틱 슬롯 사이트
Liu Jie가 Huangjinzhou에서 돌아왔을 때 그는 다른 사람처럼 보였습니다.
스핀 슬롯
Zhu Zaimo는 모든 젊은이들과 함께 절했습니다. “아이는 아버지와 선생님을 보았습니다.”
네라 벳
그의 뒤에 있던 수험생들은 이를 보고 모두 은근히 기뻐했다.뒤에서 누군가가 말했습니다. “선생님, 학생들이 와서 한번 해보세요.”
I loved as much as you will receive carried out right here The sketch is tasteful your authored subject matter stylish nonetheless you command get got an edginess over that you wish be delivering the following unwell unquestionably come further formerly again as exactly the same nearly very often inside case you shield this hike
Its like you read my mind You appear to know a lot about this like you wrote the book in it or something I think that you could do with some pics to drive the message home a little bit but instead of that this is fantastic blog An excellent read I will certainly be back
Nice blog here Also your site loads up very fast What host are you using Can I get your affiliate link to your host I wish my site loaded up as quickly as yours lol
you are in reality a good webmaster The website loading velocity is amazing It sort of feels that youre doing any distinctive trick Also The contents are masterwork you have done a fantastic job in this topic
you are truly a just right webmaster The site loading speed is incredible It kind of feels that youre doing any distinctive trick In addition The contents are masterwork you have done a great activity in this matter
Ive read several just right stuff here Certainly price bookmarking for revisiting I wonder how a lot effort you place to create this kind of great informative website
Thanks for finally talking about >Find Pivot Index – Foolish Hungry Blog <Liked it!
Great web site you have got here.. It’s hard to find good quality writing like yours these days.
I really appreciate people like you! Take care!!
I’m really enjoying the theme/design of your weblog.
Do you ever run into any browser compatibility problems? A
number of my blog readers have complained about my site not working correctly in Explorer but looks great in Chrome.
Do you have any ideas to help fix this problem?
see this http://www.ted.com/profiles/1076002
obviously like your website but you need to test the spelling on quite a few of your posts Several of them are rife with spelling problems and I to find it very troublesome to inform the reality on the other hand Ill certainly come back again
I have been browsing online more than three hours today yet I never found any interesting article like yours It is pretty worth enough for me In my view if all website owners and bloggers made good content as you did the internet will be a lot more useful than ever before
helloI really like your writing so a lot share we keep up a correspondence extra approximately your post on AOL I need an expert in this house to unravel my problem May be that is you Taking a look ahead to see you
helloI really like your writing so a lot share we keep up a correspondence extra approximately your post on AOL I need an expert in this house to unravel my problem May be that is you Taking a look ahead to see you
Thanks for sharing. I read many of your blog posts, cool, your blog is very good.
Wonderful blog! Do you have any recommendations for aspiring writers?
I’m hoping to start my own website soon but I’m a little
lost on everything. Would you recommend starting with a free platform like WordPress or go for a paid
option? There are so many choices out there that I’m completely confused ..
Any recommendations? Bless you!