Detect Duplicate Packages — Problem Statement & Solution Guide
Problem Description
Given a stream of package identifiers and a window size, implement a function to identify duplicate packages within the window. If the window size is not specified, consider the entire array.
Examples
Input
[1, 2, 3, 1], 3
Output
true
Explanation: Step-by-step: with input [1, 2, 3, 1] and window size 3, we check each package in the window. Since package 1 appears twice within the window, we return true.
Input
[1, 2, 3, 4], 2
Output
false
Explanation: Step-by-step: with input [1, 2, 3, 4] and window size 2, we check each package in the window. Since no package appears twice within the window, we return false.
Constraints
- 1 <= n <= 10^5
- 0 <= k <= 10^5
Optimal Approach & Strategy
Use a hash set to store packages, allowing for constant time complexity O(1) lookup
Brute Force Approach
Check each package in the list to see if it matches the new package
Verified Code Solutions
function solution(nums, windowSize) {
if (windowSize === undefined) {
windowSize = nums.length;
}
for (let i = 0; i <= nums.length - windowSize; i++) {
let window = nums.slice(i, i + windowSize);
let packageSet = new Set();
for (let j = 0; j < window.length; j++) {
if (packageSet.has(window[j])) {
return true;
}
packageSet.add(window[j]);
}
}
return false;
}class Solution {
public:
bool solution(vector<int>& nums, int windowSize) {
if (windowSize == -1) {
windowSize = nums.size();
}
for (int i = 0; i <= nums.size() - windowSize; i++) {
vector<int> window(nums.begin() + i, nums.begin() + i + windowSize);
unordered_set<int> packageSet;
for (int j = 0; j < window.size(); j++) {
if (!packageSet.insert(window[j]).second) {
return true;
}
}
}
return false;
}
};import java.util.HashSet;
import java.util.Set;
class Solution {
public boolean solution(int[] nums, Integer windowSize) {
if (windowSize == null) {
windowSize = nums.length;
}
for (int i = 0; i <= nums.length - windowSize; i++) {
int[] window = new int[windowSize];
System.arraycopy(nums, i, window, 0, windowSize);
Set<Integer> packageSet = new HashSet<>();
for (int j = 0; j < window.length; j++) {
if (!packageSet.add(window[j])) {
return true;
}
}
}
return false;
}
}def solution(nums, window_size=None):
if window_size is None:
window_size = len(nums)
for i in range(len(nums) - window_size + 1):
window = nums[i:i + window_size]
package_set = set()
for package in window:
if package in package_set:
return True
package_set.add(package)
return Falsefunction solution(nums, windowSize) {
if (windowSize === undefined) {
windowSize = nums.length;
}
for (let i = 0; i <= nums.length - windowSize; i++) {
let window = nums.slice(i, i + windowSize);
let packageSet = new Set();
for (let j = 0; j < window.length; j++) {
if (packageSet.has(window[j])) {
return true;
}
packageSet.add(window[j]);
}
}
return false;
}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.