Problem Link - Count Distinct Values Practice Problem in Jump from 2* to 3*
Problem Statement:
In this problem, you are asked to determine two things:
- The worst-case time complexity of Chef’s naive solution for finding the number of distinct elements in an array.
- The actual number of distinct values in the array.
Approach:
-
Chef’s naive approach involves checking each element in the array against all previously encountered elements to determine if it has already been counted as distinct. For each element, this requires iterating through the entire list of previous elements, resulting in a nested loop structure. This leads to a time complexity of Θ(n^2) in the worst case because, for each of the
nelements, up ton−1comparisons are made. -
To optimize Chef’s solution, we can use a set or hash set to keep track of distinct elements. Inserting an element into a set has an average time complexity of
O(1)due to the underlying hash table data structure. This means the entire process of counting distinct elements can be done in linear time,O(n), by simply inserting each element into the set and then determining the size of the set.
Complexity:
- Time Complexity: using a set has a time complexity of
O(n). - Space Complexity:
O(n), because in the worst case, the set stores all distinct elements, which can be up tonelements.