Detect Duplicate Packages — Problem Statement & Solution Guide
Problem Description
Given an integer array packages and an integer k, decide whether there exist two different positions i and j such that packages[i]==packages[j] and |i-j|<=k. If k is negative, the distance condition is ignored, meaning any duplicate anywhere in the array satisfies the requirement. Return true when such a pair exists; otherwise return false.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Detect Duplicate Packages"
WHY DOES IT MATTER?
Detecting near‑by duplicates is a recurring pattern in rate‑limiting, cache invalidation, and fraud detection where recent repetitions matter more than distant ones. Mastering this pattern teaches you to combine hashing with a bounded window, a technique that appears in many sliding‑window problems.
OPTIMIZATION CHALLENGE
The key insight is that you don’t need to remember all previous elements—only those that could still satisfy the distance constraint. By evicting elements that fall outside the window, you keep the set size bounded by k, turning O(n²) work into O(n).
REAL-WORLD CONNECTION
Think of a security camera that flags a person if they re‑enter the same zone within a short time window; the camera only needs to remember who was seen in the last k seconds, not the entire day's footage. The hash‑set acts as the short‑term memory of that zone.
During the interview, implement the sliding window first, then add the special case for k<0. Keep the code clean: use a set for O(1) checks and a queue (or index arithmetic) for eviction, which makes the logic obvious and bug‑free.
COMPLEXITY AT A GLANCE
O(n)O(min(n,k))Core Theory — Why This Approach?
The problem is a classic sliding‑window duplicate detection task that can be solved efficiently with a hash‑set. A naive O(n²) scan compares every pair of indices, which quickly becomes infeasible for n in the millions because the number of comparisons grows quadratically. By observing that we only need to know whether a value has appeared within the last k positions, we can maintain a moving window of size k and store the elements of that window in a hash‑set, giving O(1) average‑time membership checks. When k is negative we drop the window constraint entirely, reducing the problem to a simple duplicate‑existence check, which is also O(n) with a hash‑set. This approach leverages the optimal paradigm of using constant‑time look‑ups to avoid repeated scanning, turning a potentially exponential blow‑up into linear time with linear (or bounded) extra space.
Interview Questions on This Problem
Q1How would you modify the solution if the array were a stream of integers that cannot be stored entirely in memory?
Use a fixed‑size sliding window hash‑set that only retains the last k elements; as each new element arrives, evict the element that falls out of the window and check the set for a duplicate before insertion.
Q2What is the time‑space trade‑off if you need to support queries for any arbitrary distance d instead of a fixed k?
You would need a data structure that can answer “has this value appeared within d positions?” for varying d, such as a hash‑map from value to its most recent index; each query becomes O(1) but you must store the latest index for every distinct value, yielding O(n) space in the worst case.
Q3Can you solve the problem without extra space while still achieving better than O(n²) time?
Yes, by sorting a copy of the array (O(n log n)) and then scanning for equal adjacent values while tracking original indices to verify the distance constraint; this uses O(1) extra space beyond the sort buffer but incurs O(n log n) time.
Examples
Input
packages = [5,1,3,5,2,3], k = 3
Output
true
Explanation: The value 5 occurs at indices 0 and 3. Their index distance is |0-3|=3, which does not exceed k=3, so the condition is satisfied. Hence the answer is true.
Input
packages = [1,2,3,4,5], k = 2
Output
false
Explanation: All elements are distinct, so no pair of equal values can be found regardless of the window size. The result is false.
Input
packages = [7,8,9,7,8], k = -1
Output
true
Explanation: k is negative, so the distance restriction is removed. The value 7 appears at indices 0 and 3 (and 8 appears at 1 and 4), providing a duplicate anywhere in the array. Thus the answer is true.
Constraints
- 1 <= packages.length <= 100000
- -10^9 <= packages[i] <= 10^9
- -10^9 <= k <= 10^9
Optimal Approach & Strategy
Maintain a sliding window hash‑set of size at most k and iterate once, checking membership before insertion and evicting the element that slides out of the window.
Brute Force Approach
Check every pair of indices i and j, and if packages[i]==packages[j] and |i‑j|<=k (or ignore k when it’s negative) return true; otherwise after all pairs return false.
Verified Code Solutions
function containsNearbyDuplicate(packages, k) {
const lastIdx = new Map(); // value -> last index
for (let i = 0; i < packages.length; ++i) {
const val = packages[i];
if (lastIdx.has(val)) {
if (k < 0 || i - lastIdx.get(val) <= k) return true;
}
lastIdx.set(val, i);
}
return false;
}
// Driver (same as template)
const fs = require('fs');
const input = fs.readFileSync(0, 'utf8').trim().split(/\s+/).map(Number);
let idx = 0;
const n = input[idx++];
const packages = input.slice(idx, idx + n);
idx += n;
const k = input[idx];
console.log(containsNearbyDuplicate(packages, k) ? "true" : "false");#include <bits/stdc++.h>
using namespace std;
bool containsNearbyDuplicate(const vector<int>& packages, int k) {
unordered_map<int,int> lastIdx; // value -> last position
for (int i = 0; i < (int)packages.size(); ++i) {
int val = packages[i];
auto it = lastIdx.find(val);
if (it != lastIdx.end()) {
if (k < 0 || i - it->second <= k) return true;
}
lastIdx[val] = i;
}
return false;
}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);
int n; if(!(cin>>n)) return 0; vector<int> packages(n); for(int i=0;i<n;++i)cin>>packages[i]; int k;cin>>k; cout<<(containsNearbyDuplicate(packages,k)?"true":"false"); return 0; }import java.io.*;
import java.util.*;
public class Main {
public static boolean containsNearbyDuplicate(int[] packages, int k) {
Map<Integer, Integer> lastIdx = new HashMap<>(); // value -> last index
for (int i = 0; i < packages.length; i++) {
int val = packages[i];
if (lastIdx.containsKey(val)) {
if (k < 0 || i - lastIdx.get(val) <= k) return true;
}
lastIdx.put(val, i);
}
return false;
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int[] packages = new int[n];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
packages[i] = Integer.parseInt(st.nextToken());
}
int k = Integer.parseInt(br.readLine().trim());
System.out.println(containsNearbyDuplicate(packages, k));
}
}import sys
def contains_nearby_duplicate(packages, k):
last_idx = {}
for i, val in enumerate(packages):
if val in last_idx:
if k < 0 or i - last_idx[val] <= k:
return True
last_idx[val] = i
return False
def main():
data = list(map(int, sys.stdin.read().strip().split()))
if not data:
return
n = data[0]
packages = data[1:1+n]
k = data[1+n]
print(str(contains_nearby_duplicate(packages, k)).lower())
if __name__ == "__main__":
main()function containsNearbyDuplicate(packages, k) {
const lastIdx = new Map(); // value -> last index
for (let i = 0; i < packages.length; ++i) {
const val = packages[i];
if (lastIdx.has(val)) {
if (k < 0 || i - lastIdx.get(val) <= k) return true;
}
lastIdx.set(val, i);
}
return false;
}
// Driver (same as template)
const fs = require('fs');
const input = fs.readFileSync(0, 'utf8').trim().split(/\s+/).map(Number);
let idx = 0;
const n = input[idx++];
const packages = input.slice(idx, idx + n);
idx += n;
const k = input[idx];
console.log(containsNearbyDuplicate(packages, k) ? "true" : "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.