Medieval Kingdom Package Tracker — Problem Statement & Solution Guide
Problem Description
Given an integer array packages and an integer k, determine whether there exist two distinct indices i and j such that packages[i] equals packages[j] and the absolute difference between i and j does not exceed k. Return true if at least one such pair exists; otherwise return false. The algorithm must run in linear time relative to the array size.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Medieval Kingdom Package Tracker"
WHY DOES IT MATTER?
The sliding‑window hash set pattern is essential for any problem that asks about relationships constrained by index distance, such as duplicate detection within a range, rate‑limiting logs, or detecting near‑by anomalies. It turns a potentially quadratic scan into a linear pass, which is critical for real‑time systems handling massive streams.
OPTIMIZATION CHALLENGE
The key insight is to maintain only the relevant portion of the data—the last k elements—using a hash set, and to evict stale entries as the window slides. This ensures constant‑time membership checks while bounding auxiliary space to O(k).
REAL-WORLD CONNECTION
Think of a network firewall that only keeps track of the last k IP addresses to detect repeated malicious requests. As new packets arrive, the firewall adds the source IP to a set and evicts the oldest entry, instantly spotting a repeat within the recent window.
During an interview, write the sliding‑window logic first, then add the eviction step. Use clear variable names like "windowSet" and "left" to avoid off‑by‑one errors, and remember to check the set before inserting the current element.
COMPLEXITY AT A GLANCE
O(n)O(k)Core Theory — Why This Approach?
The problem asks whether any duplicate value appears within a sliding window of size k in an array. A naive solution would compare each element with every other element up to k positions away, leading to O(n·k) time, which quickly becomes infeasible for large n (e.g., n = 10^6) because the inner loop repeats many times. The optimal paradigm leverages a hash‑based set to keep track of the most recent k elements while scanning the array once. As we iterate, we insert the current value into the set; if the value already exists, we have found two equal elements whose indices differ by at most k, and we can return true immediately. To maintain the window size, when the index exceeds k we remove the element that falls out of the window (i‑k) from the set. This sliding‑window hash set yields a linear O(n) time algorithm with O(k) auxiliary space.
The underlying theory combines two classic concepts: (1) the pigeonhole principle guarantees that if a duplicate exists within distance k, it must be encountered while the set holds at most k distinct elements, and (2) hash tables provide O(1) average‑case insert, lookup, and delete operations, making them ideal for maintaining the dynamic window. By continuously pruning stale entries, we ensure the set never grows beyond k, preserving both time and space efficiency. This approach is a textbook example of using a hash‑based sliding window to transform a potentially quadratic problem into linear time.
Interview Questions on This Problem
Q1How would you modify the solution if the array could contain null values and you needed to treat nulls as a valid package identifier?
Use a HashMap<Integer, Integer> (or HashSet<Integer> with special handling) that can store null as a key. When encountering null, check if null already exists in the set; if so, return true. Ensure removal of the element that slides out of the window also handles null correctly.
Q2What is the time‑space trade‑off if you replace the HashSet with a fixed‑size boolean array assuming package IDs are bounded between 0 and M?
A boolean array gives O(1) operations with O(M) space, which can be more memory‑intensive than the O(k) space of a HashSet when M >> k. The trade‑off is lower constant factors for lookups at the cost of potentially huge memory usage, making it viable only when M is reasonably small.
Q3Can you extend this algorithm to find the maximum distance between any two equal packages, not just ≤ k, while still staying linear?
Maintain a HashMap<Integer, Integer> that records the first occurrence index of each package. As you iterate, compute the distance between the current index and the stored first index; update a global maximum distance. This runs in O(n) time and O(n) space because you keep one entry per distinct value.
Examples
Input
packages = [1,2,3,1,2,3], k = 3
Output
true
Explanation: The value 1 appears at indices 0 and 3. The distance |0-3| = 3 which is ≤ k, so the condition is satisfied.
Input
packages = [4,1,2,3,4], k = 3
Output
false
Explanation: The only duplicate value is 4 at indices 0 and 4. Their distance is |0-4| = 4, which exceeds k, so no valid pair exists.
Input
packages = [5,5], k = 1
Output
true
Explanation: Both elements are 5 and their indices are 0 and 1. The distance |0-1| = 1 ≤ k, meeting the requirement.
Constraints
- 1 <= packages.length <= 100000
- -1000000000 <= packages[i] <= 1000000000
- 1 <= k <= packages.length - 1
Optimal Approach & Strategy
Maintain a hash set of the last k elements while scanning; on each step, if the current value is in the set return true, otherwise add it and evict the element that fell out of the k‑window.
Brute Force Approach
Check every pair of indices i and j where |i‑j| ≤ k and compare packages[i] with packages[j]; stop when a matching pair is found.
Verified Code Solutions
function containsNearbyDuplicate(packages, k) {
const window = new Set();
for (let i = 0; i < packages.length; ++i) {
if (window.has(packages[i])) return true;
window.add(packages[i]);
if (window.size > k) {
window.delete(packages[i - k]);
}
}
return false;
}
function main(){
const fs = require('fs');
const data = fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
if(data.length===0) return;
let idx=0;
const n=data[idx++];
const packages=data.slice(idx, idx+n); idx+=n;
const k=data[idx];
const res=containsNearbyDuplicate(packages,k);
process.stdout.write(res?"true":"false");
}
main();#include <bits/stdc++.h>
using namespace std;
bool containsNearbyDuplicate(const vector<int>& packages, int k) {
unordered_set<int> window;
for (size_t i = 0; i < packages.size(); ++i) {
if (window.find(packages[i]) != window.end()) return true;
window.insert(packages[i]);
if (window.size() > (size_t)k) {
window.erase(packages[i - k]);
}
}
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) {
Set<Integer> window = new HashSet<>();
for (int i = 0; i < packages.length; i++) {
if (window.contains(packages[i])) return true;
window.add(packages[i]);
if (window.size() > k) {
window.remove(packages[i - k]);
}
}
return false;
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
List<Integer> tokens = new ArrayList<>();
String line;
while ((line = br.readLine()) != null) {
if (line.isEmpty()) continue;
StringTokenizer st = new StringTokenizer(line);
while (st.hasMoreTokens()) tokens.add(Integer.parseInt(st.nextToken()));
}
if (tokens.isEmpty()) return;
int idx = 0;
int n = tokens.get(idx++);
int[] packages = new int[n];
for (int i = 0; i < n; i++) packages[i] = tokens.get(idx++);
int k = tokens.get(idx);
System.out.print(containsNearbyDuplicate(packages, k) ? "true" : "false");
}
}
def contains_nearby_duplicate(packages, k):
window = set()
for i, val in enumerate(packages):
if val in window:
return True
window.add(val)
if len(window) > k:
window.remove(packages[i - k])
return False
if __name__ == "__main__":
import sys
data = list(map(int, sys.stdin.read().strip().split()))
if not data:
sys.exit(0)
n = data[0]
packages = data[1:1+n]
k = data[1+n]
print("true" if contains_nearby_duplicate(packages, k) else "false")
function containsNearbyDuplicate(packages, k) {
const window = new Set();
for (let i = 0; i < packages.length; ++i) {
if (window.has(packages[i])) return true;
window.add(packages[i]);
if (window.size > k) {
window.delete(packages[i - k]);
}
}
return false;
}
function main(){
const fs = require('fs');
const data = fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
if(data.length===0) return;
let idx=0;
const n=data[idx++];
const packages=data.slice(idx, idx+n); idx+=n;
const k=data[idx];
const res=containsNearbyDuplicate(packages,k);
process.stdout.write(res?"true":"false");
}
main();
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.