Table of Contents
Leetcode 2393. Count Strictly Increasing Subarrays
Problem
You are given an array nums consisting of positive integers.
Return the number of subarrays of nums that are in strictly increasing order.
A subarray is a contiguous part of an array.
Example 1:
Input: nums = [1,3,5,4,4,6] Output: 10 Explanation: The strictly increasing subarrays are the following: - Subarrays of length 1: [1], [3], [5], [4], [4], [6]. - Subarrays of length 2: [1,3], [3,5], [4,6]. - Subarrays of length 3: [1,3,5]. The total number of subarrays is 6 + 3 + 1 = 10.
Example 2:
Input: nums = [1,2,3,4,5] Output: 15 Explanation: Every subarray is strictly increasing. There are 15 possible subarrays that we can take.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 106
Source: Leetcode 2393. Count Strictly Increasing Subarrays
Solution
We can solve this problem by running two nested loops and counting strictly increasing subarrays. But that will give us an O(N2) time complexity which we do not want.
There is a better approach.
To apply that, we need to understand the fact that, for any element in an array, if we count how many contiguous elements before that element is passed, we can know the number of contiguous subarrays starting from some point up to that element.
Sounds complex?
Let’s examine this fact by looking at the below image. Let’s say we have a variable increment_so_far initialized by 1 at the beginning.
Now, we will go from index 1 up to the end of the array as long as we find an element is strictly greater than it’s previous element. Also we will increment increment_so_far by 1 when that condition is fulfilled.
At index 1, 3 is > 1, so we do increment_so_far += 1 or increment_so_far = 2 now.
At index 2, 5 > 3, we again do increment_so_far += 1 or increment_so_far = 3 now.
Looking at the below image you see, how the updated value of increment_so_far tells us how many distinct contiguous subarrays are there starting from index 0 to index 2. There are three arrays, i.e. [5], [3,5] and [1,3,5] which are strictly increasing, contiguous and unique.
Let’s practice this idea by simulating a test case from the problem description.
Let’s say, we have an array as below. We initialize increment_so_far = 1 and result = 1. Why increment_so_far = 1? Because, if there is no increasing subsequence, we have to add an element’s count considering it a single element array. Why result = 1? If there is only one element in the array, the program will not go into the loop, so we should have a result ready for that edge case.
Now, let’s start with index 1. At this point, nums[1] > nums[0]. So, we increment increment_so_far by 1 and update our result.
After that, at index 2. At this point, nums[2] > nums[1]. So, we increment increment_so_far by 1 and update our result.
At index 3. At this point, nums[3] is NOT > nums[2]. So, we reinitialize increment_so_far = 1 and update our result.
The process will continue until we reach end of the array.
Code
class Solution {
public:
long long countSubarrays(vector<int>& nums) {
long long result = 1;
long long increment_so_far = 1;
for(int i = 1; i < nums.size(); i++)
{
if(nums[i] > nums[i - 1])
increment_so_far += 1;
else
increment_so_far = 1;
result += increment_so_far;
}
return result;
}
};
Time and Space Complexity
We are looping through the entire array once. So, the time complexity is essentially the length of the array or O(N) where N = array length. We are not using any extra space that can change size by the input size. So, we have an O(1) space complexity.
Conclusion
Hope you enjoyed the solution. Please write in the comment section if you didn’t like it or you have any suggestion to improve it.
Till our next post, Happy coding! 😀
Bonus – System Design!
ByteByteGo is by far the best system design resource found on the internet. They are growing like crazy!
We suggest you checkout their course if you really want to dive deep in system design and want to have a better interview.
Here is the link: ByteByteGo!
Disclaimer: this is a genuine suggestion, but we have some benefits too! We get commission if you buy their course. However, there are other courses online which we do not promote. Because we promote only things that are the best in our opinion and those we really feel like helpful for our audience.
Your article gave me a lot of inspiration, I hope you can explain your point of view in more detail, because I have some doubts, thank you.
Hi foolishhungry.com owner, Your posts are always well researched.
Dear foolishhungry.com owner, You always provide clear explanations and step-by-step instructions.
To the foolishhungry.com administrator, Your posts are always informative and well-explained.
Hello foolishhungry.com owner, You always provide great resources and references.
Dear foolishhungry.com webmaster, Keep the good content coming!
Hi foolishhungry.com owner, Thanks for the well written post!
Hello foolishhungry.com administrator, Your posts are always well-structured and logical.
Bonito Designs, Building No 1182 Floor, 2, 5th Main Rd, 7th Sector, HSR Layout, Bengaluru, Karnataka 560102 Phone: 080660 85646 bonito.in/interior-designers-in-bangalore/
To the foolishhungry.com administrator, You always provide clear explanations and step-by-step instructions.
Hi foolishhungry.com admin, You always provide useful links and resources.
w530s7
Thank you very much for sharing, I learned a lot from your article. Very cool. Thanks. nimabi
Thank you very much for sharing, I learned a lot from your article. Very cool. Thanks. nimabi
We absolutely love your blog and find the majority of your post’s to be exactly I’m looking for. Does one offer guest writers to write content available for you? I wouldn’t mind publishing a post or elaborating on a few of the subjects you write regarding here. Again, awesome website!
I am glad to be a visitant of this stark web site! , thankyou for this rare information! .
Hi foolishhungry.com admin, Your posts are always well-supported and evidence-based.
To the foolishhungry.com administrator, Your posts are always well-formatted and easy to read.
Wow amazing blog layout How long have you been blogging for you made blogging look easy The overall look of your web site is magnificent as well as the content
Your point of view caught my eye and was very interesting. Thanks. I have a question for you. https://www.binance.info/it/join?ref=V3MG69RO
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/en/join?ref=IJFGOAID
Your article helped me a lot, is there any more related content? Thanks! https://www.binance.com/pt-BR/join?ref=W0BCQMF1
I like the efforts you have put in this, regards for all the great content.
Your article helped me a lot, is there any more related content? Thanks! https://www.binance.com/uk-UA/join?ref=YY80CKRN
Touche. Great arguments. Keep up the great spirit.
This asset is fabulous. The radiant data reveals the publisher’s interest. I’m dumbfounded and anticipate further such astonishing presents.
This resource is fabulous. The wonderful data exhibits the publisher’s earnestness. I’m stunned and expect more such astonishing substance.
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. https://www.binance.info/ur/join?ref=P9L9FQKY
Can you be more specific about the content of your article? After reading it, I still have some doubts. Hope you can help me.
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
I have read some excellent stuff here Definitely value bookmarking for revisiting I wonder how much effort you put to make the sort of excellent informative website
It seems like you’re repeating a set of comments that you might have come across on various websites or social media platforms. These comments typically include praise for the content, requests for improvement, and expressions of gratitude. Is there anything specific you’d like to discuss or inquire about regarding these comments? Feel free to let me know how I can assist you further!
Thanks for your personal marvelous posting! I definitely enjoyed reading it, you’re a great author.I will make sure to bookmark your blog and definitely will come back very soon. I want to encourage that you continue your great work, have a nice evening!
I’m so happy to read this. This is the type of manual that needs to be given and not the accidental misinformation that’s at the other blogs. Appreciate your sharing this greatest doc.
Thank you for reaching out! If you have any specific questions or topics in mind, please feel free to share them, and I’ll do my best to assist you. Whether you’re curious about a particular technology, scientific concept, literary work, or anything else, I’m here to provide information, advice, or engage in a discussion. Don’t hesitate to let me know how I can help you further!
I do not even know how I ended up here but I thought this post was great I dont know who you are but definitely youre going to a famous blogger if you arent already Cheers.
I have recommended your blog to all of my friends and family Your words have the power to change lives and I want others to experience that as well
Hi there would you mind stating which blog platform you’re working with? I’m planning to start my own blog in the near future but I’m having a difficult time making a decision between BlogEngine/Wordpress/B2evolution and Drupal. The reason I ask is because your layout seems different then most blogs and I’m looking for something completely unique. P.S Apologies for getting off-topic but I had to ask!
Thanks for sharing. I read many of your blog posts, cool, your blog is very good.
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?
What i do not understood is in truth how you are not actually a lot more smartlyliked than you may be now You are very intelligent You realize therefore significantly in the case of this topic produced me individually imagine it from numerous numerous angles Its like men and women dont seem to be fascinated until it is one thing to do with Woman gaga Your own stuffs nice All the time care for it up.
Somebody essentially lend a hand to make significantly articles Id state That is the very first time I frequented your website page and up to now I surprised with the research you made to make this actual submit amazing Wonderful task.
helloI like your writing very so much proportion we keep up a correspondence extra approximately your post on AOL I need an expert in this space to unravel my problem May be that is you Taking a look forward to see you.
I sincerely enjoyed what you have produced here. The design is refined, your authored material trendy, yet you appear to have obtained a degree of apprehension regarding what you aim to offer next. Certainly, I shall return more frequently, just as I have been doing almost constantly, provided you uphold this incline.
I genuinely admired what you’ve accomplished here. The outline is elegant, your written content fashionable, however, you seem to have acquired some unease about what you wish to present going forward. Undoubtedly, I’ll revisit more often, similar to I have nearly all the time, in case you sustain this ascent.
I really enjoyed what you have accomplished here. The outline is elegant, your written content is stylish, yet you seem to have acquired a bit of apprehension over what you aim to convey next. Undoubtedly, I will revisit more frequently, just as I have been doing nearly all the time in case you sustain this upswing.
I truly enjoyed what you’ve achieved here. The design is stylish, your written content fashionable, yet you appear to have acquired some apprehension regarding what you intend to present going forward. Undoubtedly, I’ll return more frequently, similar to I have almost constantly, in the event you sustain this ascent.
I truly appreciated the work you’ve put forth here. The sketch is tasteful, your authored material stylish, yet you appear to have developed some nervousness regarding what you intend to deliver next. Rest assured, I’ll return more regularly, much like I’ve done almost constantly, should you maintain this upward trajectory.
I genuinely enjoyed the work you’ve put in here. The outline is refined, your written content stylish, yet you appear to have obtained some apprehension regarding what you wish to deliver thereafter. Assuredly, I will return more frequently, akin to I have almost constantly, provided you maintain this climb.
I truly admired the work you’ve put in here. The design is refined, your authored material stylish, however, you seem to have acquired some trepidation about what you intend to present next. Undoubtedly, I’ll revisit more regularly, similar to I have nearly all the time, in the event you sustain this rise.
I sincerely admired what you’ve produced here. The sketch is elegant, your written content chic, yet you appear to have developed some anxiety regarding what you aim to offer thereafter. Certainly, I shall return more frequently, just as I have been doing almost constantly, should you uphold this incline.
I genuinely savored the work you’ve put forth here. The outline is refined, your authored material trendy, however, you seem to have obtained some trepidation about what you wish to deliver next. Assuredly, I will revisit more regularly, akin to I have nearly all the time, provided you maintain this upswing.
The breadth of knowledge compiled on this website is astounding. Every article is a well-crafted masterpiece brimming with insights. I’m grateful to have discovered such a rich educational resource. You’ve gained a lifelong fan!
Thank you for your openness to explore various topics! If you have any specific questions or areas of interest you’d like to discuss, feel free to share them. Whether it’s about the latest advancements in technology, recent scientific breakthroughs, thought-provoking literature, or any other subject, I’m here to offer insights and assistance. Just let me know how I can be of help, and I’ll do my best to provide valuable information and engage in meaningful discussions!
Thank you for your response! I’m grateful for your willingness to engage in discussions. If there’s anything specific you’d like to explore or if you have any questions, please feel free to share them. Whether it’s about emerging trends in technology, recent breakthroughs in science, intriguing literary analyses, or any other topic, I’m here to assist you. Just let me know how I can be of help, and I’ll do my best to provide valuable insights and information!
What Is Puravive? The Puravive weight loss aid is formulated using eight clinically proven natural ingredients.
The breadth of knowledge compiled on this website is astounding. Every article is a well-crafted masterpiece brimming with insights. I’m grateful to have discovered such a rich educational resource. You’ve gained a lifelong fan!
Your article helped me a lot, is there any more related content? Thanks!
Would you be enthusiastic about exchanging hyperlinks?
Wow, fantastic weblog layout! How lengthy have you been running a blog for?
you made running a blog glance easy. The whole look of
your web site is excellent, as neatly as the content material!
You can see similar here dobry sklep
Wow, marvelous weblog structure! How lengthy have
you been running a blog for? you made running a blog look easy.
The whole look of your site is magnificent, as neatly
as the content! You can see similar here sklep online
Hey very cool blog!! Man .. Beautiful .. Amazing .. I’ll bookmark your blog and take the feeds also…I am happy to find so many useful info here in the post, we need develop more strategies in this regard, thanks for sharing. . . . . .
Wow, superb blog format! How long have you ever been running a blog for?
you make running a blog glance easy. The total look of your website
is fantastic, let alone the content material! You can see similar here dobry sklep
Wow, wonderful blog layout! How long have you been running
a blog for? you made blogging glance easy. The whole look of your site is excellent, as smartly as the content material!
You can see similar here sklep internetowy
Wow, fantastic weblog format! How long have you ever been running a blog for?
you made blogging look easy. The full look of your web site is magnificent, as well
as the content material! You can see similar here najlepszy sklep
Wow, fantastic blog layout! How lengthy have you ever been blogging
for? you made blogging look easy. The whole look of your website is great, let
alone the content! You can see similar here ecommerce
Wow, superb blog format! How lengthy have you been running a blog for?
you made running a blog look easy. The overall glance of your website is fantastic,
as neatly as the content material! You can see
similar here sklep online
Nice post. I learn something more challenging on different blogs everyday. It will always be stimulating to read content from other writers and practice a little something from their store. I’d prefer to use some with the content on my blog whether you don’t mind. Natually I’ll give you a link on your web blog. Thanks for sharing.
Wow that was unusual. I just wrote an very long comment but after I clicked submit my comment didn’t appear. Grrrr… well I’m not writing all that over again. Regardless, just wanted to say excellent blog!
Good day! Do you use Twitter? I’d like to follow you if that would be okay. I’m absolutely enjoying your blog and look forward to new updates.
Wow, marvelous blog structure! How lengthy have you been running a blog for?
you make running a blog look easy. The overall look of
your web site is wonderful, let alone the content!
You can see similar here sklep internetowy
Lottery Defeater Software? Lottery Defeater is a software application created to help people win lotteries