The O(n) Club: Sliding Window Buckets and the Art of Almost-Duplicates (LeetCode 220)

The O(n) Club: Sliding Window Buckets and the Art of Almost-Duplicates (LeetCode 220)

⚡ TL;DR

Don’t want to wreck your runtime with O(nk) brute force for ‘almost duplicates’? Use buckets—each value gets a seat, and we only ask the neighbors for trouble. Here’s how not to embarrass yourself in Java:

// Brute force (send thoughts and prayers to your CPU):
for (int i = 0; i < nums.length; i++) {
    for (int j = Math.max(0, i - k); j < i; j++) {
        if (Math.abs((long)nums[i] - nums[j]) <= t) return true;
    }
}
return false;

🧠 How Devs Usually Mess This Up

Classic rookie mistake: you use a HashSet (like in LeetCode 219) and high-five yourself for finding ‘nearby’ duplicates—only, oops, this problem wants almost duplicates in value, not identity. Swing the brute-force bat? Enjoy timing out like it’s 1999. Bonus goof: forget to yeet values outside the sliding k-window and watch your memory balloon faster than a bad query on production Friday.

🔍 What’s Actually Going On

Imagine a suspicious bank: for every transaction, the system bins recent amounts into buckets—each covering a $t+1$-sized range. New amount arrives? The bot looks in three places only: same bucket (someone in your exact value clique?), neighbor buckets (that sneaky almost-twin?) No need to shake down the entire building. And when the queue gets too long (past k), toss out the oldest so you’re STILL respecting that sliding window.

🛠️ PseudoCode

• Soften edge cases: If k<=0 or t<0, exit faster than you order takeout.
  

  if (k <= 0 || t < 0) return false;

• For real work, set bucket width to t+1.
  

  long width = (long)t + 1;
  Map<Long, Long> buckets = new HashMap<>();

• For each value:
  • Find bucket id (use weird negative tricks to avoid Java modulo sadness):

    long id = num >= 0 ? num / width : ((num + 1) / width) - 1;

  • Nab the value if its bucket is taken already. Easy win.
  • Check next-door buckets: are we almost twins?

    // Check id - 1 and id + 1 for close values

  • Shove number in its bucket, unapologetically.
  • If our window grew too big (i >= k): evict the bucket holding nums[i-k]—window discipline, people.

    long outId = getBucketId(nums[i-k], width);
    buckets.remove(outId);

• If nobody matched after all that? No (almost) duplicates for you!

💻 The Code

public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
    if (k <= 0 || t < 0) return false;
    Map<Long, Long> buckets = new HashMap<>();
    long width = (long)t + 1;
     for (int i = 0; i < nums.length; i++) {
        long num = (long)nums[i];
        long id = getBucketId(num, width);
        if (buckets.containsKey(id)) return true;
        if (buckets.containsKey(id - 1) && Math.abs(num - buckets.get(id - 1)) <= t) return true;
        if (buckets.containsKey(id + 1) && Math.abs(num - buckets.get(id + 1)) <= t) return true;
        buckets.put(id, num);
        if (i >= k) {
            long outId = getBucketId((long)nums[i - k], width);
            buckets.remove(outId);
        }
    }
    return false;
}
 private long getBucketId(long num, long width) {
    return num >= 0 ? num / width : ((num + 1) / width) - 1;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Edge shakes: k=0 or t<0? Instantly false. You can’t compare with nobody, nor with negative tolerance (unless your boss likes negative bonuses).
• Buckets too wide, buckets too narrow: If you mess up width math, values fall between the cracks. Use t+1 or you’ll get uninvited bucket guests.
• Forgot window clean-up: Always evict the number exiting the window. Otherwise, memory goes brrrr and results go ouch.
• Negative integer heartbreak: Java division of negatives is weird; don’t trust your instincts here—use the ugly formula.
• Complexity: You only ever look in three buckets; O(n) time, O(k) space. If you see O(nk) in your profile, congratulations: you have a pet snail algorithm.

🧠 Interviewer Brain-Tattoo

Whenever the words window and almost sneak into a problem, do yourself a favor: bucketize before you terrorize your call stack. O(nk) belongs in interviews past. “If it feels like brute force, it probably is.”