Method Explained for Distinct N in Window(CODE THIS ON YOUR OWN)


#1

Method-1 T.C-N^2
using map
this is intutive you can easily think about this.

Method-2 T.C-N

map<int,int> in this
we will store number(key) and its LATEST INDEX(value)
(this is the beauty of solution)

eg) A- [1,3,1,3,2]
index i- 0,1,2,3,4
N=3
vector ans

step1-insert starting 3 number
i=0 AND j=N-1=2

insert 1 with index 0
3 with index 1
1-update previous index to 2

step-2)
now,map.size=2(put in ans)
TO SLIDE THE WINDOW,HAVE TO REMOVE PREVIOUS i
remove i from map if the index in map is same(IMP)

eg=i=0 i.e A[i]=1
but the map[A[i]]==2
so dont remove as this index would be used to calculate distinct for future windows(THINK WHY)

SLIDE WINDOW-i++
j++

NOW join the new j,
if j already present then update and if not insert with its index

eg-j=3 i.e A[j]=3
as alreay present in map,so update its value in map
(from 1 to 3)

repeat step 2(TILL j<A.size())

HAPPY CODING