Given an array, count the subarrays with all elements unique.
Anonymous
The length of subarray was varied using a for loop. For each fixed length of subarray, ranging from array size to 1, I used map whose key was the element of subarray and value was count of that element. If while traversing through the subarray, any elements count exceeds 1, a variable named "repeat" was incremented. After traversing the subarray and storing the count of each number in the map, the value of repeat is checked. If the repeat=0, then this subarray has all the elements unique. Then using sliding window technique, we shift the window one element forward and update the map by reducing the count of number which window just left and incrementing count of the number just included in the window. If the element just left by the window had count>1 in the map, the repeat variable value is decremented and if the count of variable just included exceeds 1, the value of repeat variable is incremented. Then we check if value of repeat variable is zero or not. This solves the problem in O(n^2) time complexity with O(n) space complexity for map.
Check out your Company Bowl for anonymous work chats.