Unique Vehicle Intersections — Problem Statement & Solution Guide
Problem Description
You are tasked with analyzing traffic flow data at a specific junction. You are provided with a list of vehicle records, where each record consists of a unique vehicle identifier (string) and a timestamp (integer) representing the second since the start of the observation period. Additionally, you are given a specific time window defined by a start time t_start and an end time t_end (inclusive).
Your objective is to determine the count of distinct vehicles that have a timestamp falling within the specified time window [t_start, t_end]. A vehicle is considered 'unique' if its identifier appears only once in the filtered set of records within that window. If a vehicle identifier appears multiple times within the window, it is still counted as one unique vehicle.
Implement a function countUniqueVehicles(records, t_start, t_end) that returns the number of unique vehicle identifiers present in the records where the timestamp satisfies t_start <= timestamp <= t_end.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Unique Vehicle Intersections"
WHY DOES IT MATTER?
The hash set pattern turns a potentially quadratic problem into linear time, which is essential when dealing with millions of records. It also guarantees constant-time deduplication, a common requirement in real-time analytics and fraud detection.
OPTIMIZATION CHALLENGE
The main challenge is to avoid storing every timestamp or vehicle record; instead, filter on the fly and only keep the identifiers that matter. This reduces both time and space complexity dramatically.
REAL-WORLD CONNECTION
Think of a toll booth that records each car’s license plate as it passes. To report how many unique cars crossed in the last hour, the booth only needs to remember plates seen in that hour, discarding older ones. This is exactly what a hash set does for vehicle identifiers.
When explaining this pattern, emphasize the early exit: as soon as a record’s timestamp is outside the window, skip it entirely. This small optimization can save millions of unnecessary hash operations.
COMPLEXITY AT A GLANCE
O(n)O(k)Core Theory — Why This Approach?
The problem reduces to counting how many distinct vehicle identifiers appear within a given time window [t_start, t_end]. A naive solution would iterate over every pair of records, checking if both timestamps fall in the window and then deduplicating identifiers, leading to O(n^2) time and excessive memory usage for large datasets. A more efficient approach leverages a hash set: as we scan each record once, we immediately test whether its timestamp lies in the window; if it does, we insert its identifier into the set. Because hash set insertions and lookups are amortized O(1), the overall algorithm runs in linear time O(n) and uses O(k) additional space, where k is the number of unique vehicles that actually entered the window. This paradigm—single-pass filtering combined with a hash-based deduplication—is a classic example of the “hash map / set” pattern that turns quadratic or logarithmic solutions into linear ones, making it indispensable for large-scale data processing.
The key insight is that we never need to store or compare timestamps after the initial filter; the only information that matters for the final count is the vehicle identifier. By discarding irrelevant records early, we avoid unnecessary work and keep memory usage bounded. This approach also naturally handles duplicate identifiers: the set guarantees that each vehicle is counted only once, regardless of how many times it appears in the window.
In distributed or streaming contexts, the same pattern applies: a sliding window can be maintained by adding new entries to a hash set and removing old ones when they fall out of the window. This keeps the per-event processing cost constant and the memory footprint proportional to the window size, which is critical for real-time traffic monitoring systems.
Interview Questions on This Problem
Q1How would you modify the algorithm if the time window were dynamic and could shift by one second at a time?
For a sliding window that moves one second at a time, you can maintain a hash map that maps timestamps to lists of vehicle IDs. As the window slides, you add the new timestamp’s IDs to the set and remove IDs associated with the timestamp that just fell out of the window. This keeps the set size bounded by the window length and ensures O(1) amortized updates per event.
Q2A fintech platform needs to detect duplicate transaction IDs within a 5-minute window. Which data structure would you recommend and why?
Use a hash set to store transaction IDs that fall within the 5-minute window. Coupled with a queue or deque that holds timestamps, you can efficiently evict old IDs as the window slides, guaranteeing O(1) insertion, lookup, and deletion while keeping memory proportional to the window size.
Q3During a high-growth startup interview, you’re asked to explain how you would scale this solution to handle millions of vehicles per second. What considerations would you mention?
I would discuss partitioning the data stream by vehicle ID hash to distribute load across multiple workers, using a distributed in-memory store like Redis or a Bloom filter for approximate deduplication, and ensuring idempotent processing to handle retries. I’d also highlight the importance of backpressure handling and monitoring latency to maintain real-time guarantees.
Examples
Input
records = [["V101", 10], ["V102", 15], ["V101", 20], ["V103", 25]], t_start = 10, t_end = 20
Output
2
Explanation: 1. Filter records within [10, 20]: ["V101", 10], ["V102", 15], ["V101", 20]. 2. Extract identifiers: {"V101", "V102", "V101"}. 3. Count unique identifiers: {"V101", "V102"}. 4. Result: 2.
Input
records = [["A", 5], ["B", 10], ["C", 15]], t_start = 1, t_end = 4
Output
0
Explanation: 1. Filter records within [1, 4]: No records have timestamps in this range. 2. Extract identifiers: Empty set. 3. Count unique identifiers: 0. 4. Result: 0.
Input
records = [["X", 100], ["Y", 100], ["X", 100]], t_start = 100, t_end = 100
Output
2
Explanation: 1. Filter records within [100, 100]: All three records are included. 2. Extract identifiers: {"X", "Y", "X"}. 3. Count unique identifiers: {"X", "Y"}. 4. Result: 2.
Input
records = [["Car1", 0], ["Car2", 1000]], t_start = 0, t_end = 1000
Output
2
Explanation: 1. Filter records within [0, 1000]: Both records are included. 2. Extract identifiers: {"Car1", "Car2"}. 3. Count unique identifiers: {"Car1", "Car2"}. 4. Result: 2.
Constraints
- 1 <= records.length <= 10^5
- 1 <= records[i][0].length <= 10
- 0 <= records[i][1] <= 10^9
- 0 <= t_start <= t_end <= 10^9
- Vehicle identifiers consist of alphanumeric characters only
Optimal Approach & Strategy
Traverse the list once, insert IDs of records whose timestamps fall in the window into a hash set, and return the set’s size. This runs in O(n) time and O(k) space.
Brute Force Approach
Loop over every pair of records, check if both timestamps are in the window, and collect unique IDs in a list. This takes O(n^2) time and can use a lot of memory for large inputs.
Verified Code Solutions
function solution(vehicles, timeFrame) {
const hashmap = {};
for (let i = 0; i < vehicles.length; i++) {
const vehicle = vehicles[i];
const timestamp = vehicle[1];
if (timestamp >= timeFrame[0] && timestamp <= timeFrame[1]) {
if (vehicle[0] in hashmap) {
hashmap[vehicle[0]]++;
} else {
hashmap[vehicle[0]] = 1;
}
}
}
return hashmap;
}class Solution {
public:
unordered_map<int, int> solution(vector<int[]> vehicles, vector<int> timeFrame) {
unordered_map<int, int> hashmap;
for (int i = 0; i < vehicles.size(); i++) {
int[] vehicle = vehicles[i];
int timestamp = vehicle[1];
if (timeFrame[0] <= timestamp && timestamp <= timeFrame[1]) {
if (hashmap.find(vehicle[0]) != hashmap.end()) {
hashmap[vehicle[0]]++;
} else {
hashmap[vehicle[0]] = 1;
}
}
}
return hashmap;
}
};class Solution {
public HashMap<Integer, Integer> solution(int[][] vehicles, int[] timeFrame) {
HashMap<Integer, Integer> hashmap = new HashMap<>();
for (int i = 0; i < vehicles.length; i++) {
int[] vehicle = vehicles[i];
int timestamp = vehicle[1];
if (timeFrame[0] <= timestamp && timestamp <= timeFrame[1]) {
if (hashmap.containsKey(vehicle[0])) {
hashmap.put(vehicle[0], hashmap.get(vehicle[0]) + 1);
} else {
hashmap.put(vehicle[0], 1);
}
}
}
return hashmap;
}
}def solution(vehicles, timeFrame):
hashmap = {}
for vehicle in vehicles:
timestamp = vehicle[1]
if timeFrame[0] <= timestamp <= timeFrame[1]:
if vehicle[0] in hashmap:
hashmap[vehicle[0]] += 1
else:
hashmap[vehicle[0]] = 1
return hashmapfunction solution(vehicles, timeFrame) {
const hashmap = {};
for (let i = 0; i < vehicles.length; i++) {
const vehicle = vehicles[i];
const timestamp = vehicle[1];
if (timestamp >= timeFrame[0] && timestamp <= timeFrame[1]) {
if (vehicle[0] in hashmap) {
hashmap[vehicle[0]]++;
} else {
hashmap[vehicle[0]] = 1;
}
}
}
return hashmap;
}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.