Given an integer array arr[], return the count of all distinct elements in the array.
Example 1
Input: arr = [10, 20, 20, 10, 30, 10]
Output: 3
Explanation: The different values are 10, 20, and 30. 10 and 20 are present twice but counted once. Therefore, the number of distinct elements is 3.
Example 2
Input: arr = [5, 5, 5, 5]
Output: 1
Explanation: All the elements are same, 5. So the answer is 1.
Brute Force Approach
The main idea is to count only the first occurrence of each element.
For every element, check whether the same value has already appeared before it. If it is, skip it. Otherwise, count it as a new distinct element.
Algorithm
If the array is empty, return 0.
Start from the first element and check one element at a time.
For the current element, look at all the elements that come before it and check if the same value is present.
If the same value is present, simply move to the next element, otherwise, this is the first time it is found, so increase the distinct count.
Continue this process and finally return the total number of distinct elements.
Dry Run
Brute
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Returns the number of distinct elements in the array. int countDistinct(vector<int>& arr) { int distinctCount = 0; // Check every element in the array. for (int i = 0; i < arr.size(); i++) { bool seenBefore = false; // Search for the same value among the previous elements. for (int j = 0; j < i; j++) { /* If the current value already appeared earlier, mark it as seen and stop searching. */ if (arr[j] == arr[i]) { seenBefore = true; break; } } // Count only the first occurrence of every distinct value. if (!seenBefore) { distinctCount++; } } return distinctCount; }};// Driver Code startsint main() { vector<int> arr = {10, 20, 20, 10, 30, 10}; Solution solution; // Call the function to count distinct elements. int answer = solution.countDistinct(arr); cout << answer << "\n"; return 0;}Complexity Analysis
Time Complexity: O(n2), because each element may be compared with every element before it, having up to n(n-1)/2 comparisons.
Space Complexity: O(1), because only counters and a Boolean flag are stored apart from the input.
Better Approach
Instead of checking the previous elements for every value, let's first sort the array. After sorting, all the duplicate values come together.
Now, instead of searching the entire array, just compare each element with the one just before it. If both values are different, this is a new distinct element.
Algorithm
If the array is empty, return 0.
Sort the array so that all duplicate values are placed next to each other.
Count the first element as a distinct element and go through the sorted array from the second element.
Compare the current element with the previous one. If they are different, count it as a new distinct element or simply move to the next element.
Continue this process, then return the total number of distinct elements.
Dry Run
Better
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Returns the number of distinct elements in the array. int countDistinct(vector<int>& arr) { // If the array is empty, there are no distinct elements. if (arr.empty()) { return 0; } // Sort the array so that duplicate values become adjacent. sort(arr.begin(), arr.end()); int distinctCount = 1; // Traverse the sorted array and count every new value. for (int i = 1; i < arr.size(); i++) { /* If the current value is different from the previous one, it is a new distinct element. */ if (arr[i] != arr[i - 1]) { distinctCount++; } } return distinctCount; }};// Driver Code startsint main() { vector<int> arr = {10, 20, 20, 10, 30, 10}; Solution solution; // Call the function to count distinct elements. int answer = solution.countDistinct(arr); cout << answer << "\n"; return 0;}Complexity Analysis
Time Complexity: O(nlog(n)), because sorting takes O(nlog(n)) time and the subsequent scan takes O(n) time.
Space Complexity: O(1), because some variables are used only.
Optimal Approach
In the previous approach, the array was sorted to bring duplicate values together. But sorting isn't really necessary. The important thing is to know whether an element has appeared before or not.
A hash set stores only the unique values, so duplicate elements are ignored automatically. So simply insert every element into the hash set, and once the traversal is complete, the size of the hash set gives the number of distinct elements.
Algorithm
Create an empty hash set to store the distinct elements.
Traverse the array from beginning to end.
For every element , try to insert it into the hash set. If it is already there, it will be ignored.
By the end of the traversal, the size of the hash set will give the number of distinct elements.
Dry Run
Optimal
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Returns the number of distinct elements in the array. int countDistinct(const vector<int>& arr) { // Store only unique elements. unordered_set<int> distinctValues; // Insert every element into the hash set. for (int value : arr) { // Insert the current element into the hash set. distinctValues.insert(value); } // Return the number of unique elements stored in the hash set. return distinctValues.size(); }};// Driver Code startsint main() { vector<int> arr = {10, 20, 20, 10, 30, 10}; Solution solution; // Call the function to count distinct elements. int answer = solution.countDistinct(arr); cout << answer << "\n"; return 0;}Complexity Analysis
Time Complexity: O(n) on average, because each of the n values is inserted once and a hash-set insertion takes average O(1) time. But in the worst-case scenario, frequent collisions can significantly slow down operations.
Space Complexity: O(k), where k is the number of distinct values stored in the set. At the worst case all the elements can be stored in set, so the worst-case space complexity is O(n).
Interview follow-up Questions
A distinct element is counted only once, no matter how many times it appears in the array. An element that appears only once has a frequency of exactly 1. For example, in [2, 2, 3], the distinct elements are 2 and 3. However, only 3 appears exactly once.
Be the first to add a comment.