Leetcode Problem

#1

I have written a O(n^3) code can u plz help me to optimize to O(N^2)
Problem link >> https://leetcode.com/problems/number-of-subarrays-with-bounded-maximum/

my code

#2

This is a brute+brute force, this can be solved in O(N^2) as well but in order to pass this problem you have to do this question in O(N). Do you know sliding window approach? if yes then try to implement using that.

#3

I am ready to face TLE but interview me seeda O(n3) see O(n) me jump maarna will totally show u crammed solution I hope u understand that and I think O(n3) solution of mine can be optimized to O(N2) SO PLZZZZZZZ help me to optimize it
PS: O(n) wala solution submit krliya maine !!!

#4

make a 2-d array and for index of i,j place dp[i][j] = maximum element in range from i to j.
this can be done in O(N^2)
now you can do this operation in O(1)

                int mx=INT_MIN;
                for(int k=i;k<=j;k++){
                    mx=max(mx,nums[k]);
                }
                if(mx>=left&& mx<=right)
                    ans++;

by finding maximum between range of i to j. So overall complexity will be O(N^2).
Ps: if you will directly approach a question which can be solved in O(N) in your interview. Then interviewer would be more impressed.

#5

if you will directly approach a question which can be solved in O(N) in your interview. Then interviewer would be more impressed. well honestly I have heard this first time because everyone wants the thought process should be from worst to best solution

#6

If this question is cleared then you can mark this doubt as resolved.

1 Like
#7

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.