ARRAY SUM PROBLEM

#1

what is sliding windows algoritham ,i mean it is also having nested loops ,then why the time complexity reduces to O(n) instead of O(n^2) ?
and where and when we have do contraction and expansion of the windows?
what is the intuition behind ?
i read article in gfg about but i cannot understand?
all these questions using slideing windows approch–>
https://practice.geeksforgeeks.org/problems/smallest-window-in-a-string-containing-all-the-characters-of-another-string-1587115621/1


https://practice.geeksforgeeks.org/problems/length-of-the-longest-substring/0
i have seen the videos of prateek bhaiya still cannot understand , why and when do we do contraction and expansion of windows , and how the time complaxity reduces to O(n)
but yet having nested loop inside it?

#2

two nested loop doesn’t mean O(n^2)
you have to analyze the no of operations
It seems more than O(n) at first look. It can be observed that every element of array is added and removed at most once. So there are total 2n operations.
hence time complexity is O(n) not O(n^2)

for sliding algorithm
read this article
https://levelup.gitconnected.com/an-introduction-to-sliding-window-algorithms-5533c4fe1cc7
very well explained the algorithm

#3

question–>
https://practice.geeksforgeeks.org/problems/length-of-the-longest-substring/0
code–>


all testcases are not passing

#4

@asaurabh_26 are u there??

#5

yes
but you said all test cases are passing

also the code you have provided is of different question

#6

sorry typing mistake

#7

so what is your doubt now
and where is correct code

#8

i read the article u referred , i was doing this question given in that(longest unique substring)
question–>
https://practice.geeksforgeeks.org/problems/length-of-the-longest-substring/0#
code–>


i am doing something wrong ,so the testcases are not passing help me what is wrong in the code

#9

okay i did a silly mistake i was expanding the rightwindow before calculating the length of the current window

#10

If your doubt is resolved, plz mark it as resolved from your side

#11

@asaurabh_26 the sliding window algoritham is an optimization of the two pointers approach right, but in this question we not using left window here the right window is i, what will be the left window ?
here we cannot do it i this using two pointers

#12

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.