How to access Subarray in Better Complexity

1

How can we access all possible subarrays in better time complexity than O(n^2). I was solving this question:-CodeChef: Practical coding for everyone
I had two pointers(i,j) initially at 0 and I kept on incrementing j and inserting the elements it encountered into a set. After that I checked the size of the Set. If it was K then I calculated the length of the subarray and then I incremented i to the next element and made j=i so that all subarrays can be accessed. I got AC in one case of Subtask 2 but not in the second case. I think the average case complexity is increased but not the worst case. Plz Help me with this.

What I basically wanted to know is how to access all the subarrays using two pointers or unordered_map because many people used unordered_map in this question.

2

It is not possible to find all the subarrays in less than O(N^2) since an array itself has N^2 subarrays.

The solution is different for the problem.

1 Like
3

Here’s a commented solution if you want:

https://www.codechef.com/submit/complete/32152512