Leetcode Solution #7

1. Count Subarrays With Score Less Than K

The Problem

Always try making sense out of the description though most the time its just trash but still try, so the description is given as,

The score of an array is defined as the product of its sum and its length.

For example, the score of [1, 2, 3, 4, 5] is (1 + 2 + 3 + 4 + 5) * 5 = 75.

Given a positive integer array nums and an integer k, return the number of non-empty subarrays of nums whose score is strictly less than k.

A subarray is a contiguous sequence of elements within an array.

blah blah blah blah......

So, basically the question is saying that you have to find the score of an array, now the first question should be what is the meaning of score of an array, so well it is defined as the product of the sum of elements given in array and the size of array.
So, in question a positive integer array is given, we have to return the number of non-empty subarrays whose score is strictly less than k, k is a already given integer.

Look at the examples given below to make sense of the summary I gave above,

Now, here I am assuming that you have understood what I am trying to explain if not try youtube.

The Approach

Well though this marked as hard level problem on leetcode but the approach does not feels like it because it is pretty basic.

1. Traverse the array and calculate the cumulative sum (coz subarray duhh!).

2. Calculate the score of the array by calculating it's size and sum.

3. Count the valid subarrays.

4. Return count of subarray.

Now, I know you have understood nothing till here or even if you have and don't know how to write the code don't worry, I got you and if everything is making sense for you then damn I am getting good at this.

The Solution

If you have understood nothing till here, try to look at the code and I am writing the steps below try to make sense of it.

1. Declare variable sum, result and start, initialise them with 0, use sum for storing the cumulative sum of array and result to store the valid subarrays and start for pointing beginning of window.

2. Traverse the array, add current elements to sum to take cumulative sum.

3. Calculate size which is i-start+1 i.e. from start to i.

4. Calculate score by multiplying size with sum.

5. We will use while loop to ensure that k is less than score, if it exceeds we will shrink the window by incrementing start.

6. Each time we shrink window, reduce sum by the element at start.

7. Recalculate the size and score for new window.

8. After adjusting window add the count of valid subarrays.

9. Return result.

Hope you have understood till here if yes thank you, you people are making this labour worth and if you don't once again try youtube.

2. Daily Temperatures

The Problem

Well repeat the drill here read the description first.

Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the i th day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

Well if you are able to make sense out of this description well congrats you are better at english than me and if you don't I got you covered again homie.

Description is basically saying that an array is given and which represents the daily temperatures and we have to return an array answer which will have the number of days we have to wait after the i th day to get a warmer temperature. If there is no future day for this just return 0 on that index.

Refer to below given examples for a better understanding,

Hope this made sense for you and you are understanding it, if not try youtube.

The Approach

Like every other question approach is basic for this one too and try to think hard and understand by yourself everything will make sense, so the approach goes like:

1. Use stack (well it is the most optimised approach for this) to store indices of the temperatures array.

2. When a warmer day is found, it pops the stack and calculates number of days until that warmer temperature.

3. Remaining indices in stack will have 0 in result because no warmer day exists for them.

I hope till here you are getting me, if not lets move towards the solution look at the code and try to form a basic understanding from the steps given below.

The Solution

Is this making sense? No? Try to figure it from the below given steps.

1. Declare a stack st to store indices of the temperatures array.

2. Declare vector answer with size n and all elements set to 0.

3. Traverse the array temperatures.

4. Use while loop to check whether stack is non empty and current day temperature is greater than temperature at top of stack.

5. Declare a integer variable index to store top index from stack.

6. Remove top element when we found warmer temperature for that day.

7. Calculate number of days between.

8. Push i into stack because we have not found a warmer day yet.

9. Return answer.

Was this question easy? Was this approach easy to understand, if yes thank you.

So, this was it for today, I hope both the questions were easy to understand if yes do not keep this thought to yourself please comment down below, it can motivate me a lot. If you were not able to understand and have a better approach for this comment it down below too. I ain't no celeb I will reply. But do comment it helps.

Connect to me on Linkedin and Github

Come on I deserve some fame.

Thank you, if you are genuinely reading till here.

KEEP CODING!!!