Help with error

#1

prob: https://hack.codingblocks.com/app/contests/2022/734/problem

sol1: https://ide.codingblocks.com/s/418418
(resursive)

sol2: https://ide.codingblocks.com/s/418420
(iterative)

only one test case is passing in both

#2

your approach is not optimized
time complexity of your code is high
that’s why it is giving TLE in one case
it is giving run error in one case because of size of freq array
if you make the size of feq array 10^5
then it will give TLE in 2 test cases and one testcase passed

hence approach is correct but not optimised hence give TLE

An efficient solution is based on the fact that if we know all elements in a subarray arr[i…j] are distinct, sum of all lengths of distinct element subarrays in this sub array is ((j-i+1)(j-i+2))/2. How? the possible lengths of subarrays are 1, 2, 3,……, j – i +1. So, the sum will be ((j – i +1)(j – i +2))/2.

We first find largest subarray (with distinct elements) starting from first element. We count sum of lengths in this subarray using above formula. For finding next subarray of the distinct element, we increment starting point, i and ending point, j unless (i+1, j) are distinct. If not possible, then we increment i again and move forward the same way.

Reference Code

#3

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.