Algocademy Logo

Number of Distinct Values II in O(n) Time Complexity using JavaScript


Given an array of integers, count how many distinct values exist in the array.

Example:

Input: [1, 5, -3, 1, -4, 2, -4, 7, 7]
Output: 6
Explanation: the distinct values in the array are [1, 5, -3, -4, 2, 7]

Note:

Your algorithm should run in O(n) time and use O(n) extra space.


Understanding the Problem

The core challenge of this problem is to efficiently count the number of distinct values in an array. This is a common problem in data processing and analysis, where you need to identify unique elements from a dataset.

Potential pitfalls include not accounting for negative numbers or duplicates properly. Misconceptions might arise from misunderstanding the requirement for distinct values.

Approach

To solve this problem, we need to think about how to efficiently track unique values. A naive solution might involve nested loops to compare each element with every other element, but this would result in an O(n^2) time complexity, which is not optimal.

Instead, we can use a JavaScript Set to store unique values. The Set data structure automatically handles duplicates and allows for O(1) average time complexity for insertions and lookups.

Optimized Solution

Using a Set is optimal because it ensures that each element is processed only once, resulting in O(n) time complexity. The space complexity is also O(n) because, in the worst case, all elements are unique and need to be stored in the Set.

Algorithm

1. Initialize an empty Set.

2. Iterate through each element in the array.

3. Add each element to the Set.

4. The size of the Set at the end of the iteration is the number of distinct values.

Code Implementation

// Function to count distinct values in an array
function countDistinctValues(arr) {
    // Initialize a new Set to store unique values
    const uniqueValues = new Set();
    
    // Iterate through each element in the array
    for (let value of arr) {
        // Add the value to the Set
        uniqueValues.add(value);
    }
    
    // The size of the Set is the number of distinct values
    return uniqueValues.size;
}

// Example usage
const inputArray = [1, 5, -3, 1, -4, 2, -4, 7, 7];
console.log(countDistinctValues(inputArray)); // Output: 6

Complexity Analysis

The time complexity of this approach is O(n) because we iterate through the array once. The space complexity is O(n) because, in the worst case, all elements are unique and stored in the Set.

Edge Cases

Consider the following edge cases:

  • An empty array: The output should be 0.
  • An array with all identical elements: The output should be 1.
  • An array with negative and positive numbers: The algorithm should handle both correctly.

Examples:

// Edge case: empty array
console.log(countDistinctValues([])); // Output: 0

// Edge case: all identical elements
console.log(countDistinctValues([1, 1, 1, 1])); // Output: 1

// Edge case: negative and positive numbers
console.log(countDistinctValues([-1, -1, 2, 2, 3, -3])); // Output: 4

Testing

To test the solution comprehensively, include a variety of test cases:

  • Simple cases with a few elements.
  • Cases with all unique elements.
  • Cases with all identical elements.
  • Cases with a mix of positive and negative numbers.

Using a testing framework like Jest can help automate and manage these tests.

Thinking and Problem-Solving Tips

When approaching such problems, consider the following tips:

  • Break down the problem into smaller parts.
  • Think about data structures that can simplify the solution.
  • Consider edge cases and how your solution handles them.
  • Practice similar problems to improve your problem-solving skills.

Conclusion

In this blog post, we discussed how to count the number of distinct values in an array using an efficient O(n) time complexity algorithm with JavaScript. We explored the problem definition, approach, algorithm, code implementation, complexity analysis, edge cases, and testing strategies. Understanding and solving such problems is crucial for improving your coding and problem-solving skills.

Additional Resources