Galactic Mineral Scanner — Problem Statement & Solution Guide
Problem Description
A deep-space probe has completed a survey of a nebula, returning a raw log of mineral signatures detected across various sectors. Each entry in the log represents a specific mineral type identified by a unique integer ID. Due to sensor redundancy, the same mineral ID may appear multiple times in the log if detected in different sectors or during overlapping scans.
Your task is to process this log and determine the total number of unique mineral types present. Essentially, you need to count how many distinct integer IDs exist in the provided list, ignoring the frequency of each occurrence.
Write a function that takes an array of integers representing the mineral IDs and returns a single integer: the count of distinct values in the array.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Galactic Mineral Scanner"
WHY DOES IT MATTER?
Frequency aggregation via hashing is a foundational pattern for deduplication, analytics, and real‑time monitoring; mastering it unlocks efficient solutions for massive streams where linear scans are the only viable option.
OPTIMIZATION CHALLENGE
The insight is that you don’t need to compare every pair—just maintain a running tally in a constant‑time structure, turning an O(n²) problem into O(n).
REAL-WORLD CONNECTION
Think of a distributed logging system that tags each event with a user ID; a central aggregator uses a hash table to count actions per user, similar to counting mineral signatures per sector in a telemetry pipeline.
During an interview, write the hash‑map update in one line, keep a separate variable for the current best, and early‑exit if the remaining elements can’t beat the best (optional for extra credit).
COMPLEXITY AT A GLANCE
O(n)O(k)Core Theory — Why This Approach?
Hash tables provide average‑case O(1) insert and lookup, making them ideal for frequency counting. A naive double‑loop that compares each element with every other runs in O(n²) and quickly exceeds time limits for n up to 10⁵ or more. By scanning the log once and updating a hash map of {mineralID → count}, we collapse the problem to linear time while keeping only distinct IDs in memory, which is optimal for this class of frequency‑aggregation tasks.
Interview Questions on This Problem
Q1How would you find the mineral ID that appears most frequently in the log?
Traverse the array once, maintain a hash map of counts, and track the ID with the highest count; this runs in O(n) time and O(k) space where k is the number of distinct IDs.
Q2If the log is sorted, can you solve the problem without extra space?
Yes—scan the sorted array, count consecutive equal IDs, and update the mode when the current run length exceeds the best seen; this uses O(1) extra space and O(n) time.
Q3What changes if the IDs can be as large as 10⁹ and you must output the count of distinct IDs only?
You still use a hash set (or unordered_set) to store each unique ID; the large value range doesn’t affect hash‑based solutions because they rely on the value’s hash, not its magnitude.
Examples
Input
mineralLog = [101, 205, 101, 309, 205, 412]
Output
4
Explanation: The distinct mineral IDs are 101, 205, 309, and 412. Although 101 and 205 appear twice, they are counted only once. Thus, the total distinct count is 4.
Input
mineralLog = [7, 7, 7, 7]
Output
1
Explanation: All entries in the log correspond to the same mineral ID (7). Therefore, there is only 1 distinct mineral type.
Input
mineralLog = [1, 2, 3, 4, 5]
Output
5
Explanation: Each mineral ID in the list is unique. No duplicates exist, so the count of distinct minerals equals the length of the array, which is 5.
Input
mineralLog = [100, 200, 100, 300, 200, 100]
Output
3
Explanation: The unique IDs are 100, 200, and 300. The repeated occurrences of 100 and 200 do not increase the distinct count. The result is 3.
Constraints
- 1 <= mineralLog.length <= 10^5
- 1 <= mineralLog[i] <= 10^9
- The array may contain duplicate values.
Optimal Approach & Strategy
Iterate once, update a hash map of frequencies, and maintain the current maximum frequency ID, achieving O(n) time.
Brute Force Approach
Use two nested loops to compare each mineral ID with every other and count occurrences, leading to O(n²) time.
Verified Code Solutions
/**
* @param {number[]} mineralLog - An array of integers representing mineral IDs detected in the nebula.
* @return {number} The number of unique mineral types detected.
*/
function countUniqueMinerals(mineralLog) {
const uniqueMinerals = new Set(mineralLog);
return uniqueMinerals.size;
}
// Example usage
const mineralLog = [101, 205, 101, 309, 205, 412];
console.log(countUniqueMinerals(mineralLog));#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;
/**
* @param mineralLog A vector of integers representing mineral IDs detected in the nebula.
* @return The number of unique mineral types detected.
*/
int countUniqueMinerals(vector<int>& mineralLog) {
unordered_set<int> uniqueMinerals;
for (int id : mineralLog) {
uniqueMinerals.insert(id);
}
return uniqueMinerals.size();
}
int main() {
// Example usage
vector<int> mineralLog = {101, 205, 101, 309, 205, 412};
cout << countUniqueMinerals(mineralLog) << endl;
return 0;
}import java.util.*;
public class Main {
/**
* @param mineralLog An array of integers representing mineral IDs detected in the nebula.
* @return The number of unique mineral types detected.
*/
public static int countUniqueMinerals(int[] mineralLog) {
Set<Integer> uniqueMinerals = new HashSet<>();
for (int id : mineralLog) {
uniqueMinerals.add(id);
}
return uniqueMinerals.size();
}
public static void main(String[] args) {
// Example usage
int[] mineralLog = {101, 205, 101, 309, 205, 412};
System.out.println(countUniqueMinerals(mineralLog));
}
}def count_unique_minerals(mineral_log):
"""
Process the mineral log to count unique mineral types.
Args:
mineral_log (list): A list of integers representing mineral IDs detected in the nebula.
Returns:
int: The number of unique mineral types detected.
"""
return len(set(mineral_log))
# Example usage
if __name__ == "__main__":
mineral_log = [101, 205, 101, 309, 205, 412]
print(count_unique_minerals(mineral_log))/**
* @param {number[]} mineralLog - An array of integers representing mineral IDs detected in the nebula.
* @return {number} The number of unique mineral types detected.
*/
function countUniqueMinerals(mineralLog) {
const uniqueMinerals = new Set(mineralLog);
return uniqueMinerals.size;
}
// Example usage
const mineralLog = [101, 205, 101, 309, 205, 412];
console.log(countUniqueMinerals(mineralLog));Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.