2Brute2Best
🔥0

Contains Duplicate II

Easy·LeetCode #219 Pro OnlyBasic Reinforcement
LeetCode
01

Problem Statement

You are given an integer array nums and an integer k.

Return true if there are two different indices i and j with the same value (nums[i] == nums[j]) that are at most k apart (|i − j| ≤ k). Otherwise return false.

Input

An integer array nums and an integer k.

Output

true if some value repeats within distance k, else false.

Example 1
Input: nums = [1, 2, 3, 1], k = 3
Output: true

The two 1s are at indices 0 and 3. They are 3 apart, and 3 ≤ 3.

Example 2
Input: nums = [1, 0, 1, 1], k = 1
Output: true

The 1s at indices 2 and 3 are 1 apart.

Example 3
Input: nums = [1, 2, 3, 1, 2, 3], k = 2
Output: false

Every value repeats, but each repeat is exactly 3 apart, which is more than 2.

Constraints
  • • 1 ≤ nums.length ≤ 10^5
  • • −10^9 ≤ nums[i] ≤ 10^9
  • • 0 ≤ k ≤ 10^5
02

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“nums[i] == nums[j]”
→ The partner of `x` is `x` itself. Look up the same value, not `target − x`.
“|i − j| ≤ k”
→ Distance matters, so a set of values is not enough. Store an index with each value.
“two distinct indices”
→ Look up before inserting, so an element is not compared with itself.
03

Approach Complexity Ladder

Brute Force — check the next k elementsO(N · min(N, K))O(1)

For each i, compare with the next k elements

Optimal — map of value → last indexO(N)O(N)

For each x, compare with the last index of x; then overwrite it

Brute Force Intuition

A useful partner for nums[i] must be within k steps. So for each i, look at nums[i+1] … nums[i+k] (stopping at the end of the array) and return true on any equal value.

Recognition rule for this sub-pattern:

For each element, ask "what partner do I need?" and check if that partner is already in the map.
Remember this · Arrays & Hashing
Trigger
"Have I seen X before?", pairs that add up to a target, grouping things that look alike, counting occurrences.
Think
Instead of scanning again for each element, can I remember earlier elements in a map?
Key question
What exactly do I store as the key, and what as the value?
Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms
Interactive step-by-step playback with pointer & array state transitions
52 comprehensive LLD chapters
Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions
40 C++ basics labs & hardware memory models
Vtables, byte layouts, assembly insights, and multi-threading race conditions
Production-ready C++23 source code
Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways
Create Free AccountLog in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Arrays & Hashing translate into production architectures and low-level memory mechanics.

LLD Machine Coding

In-Memory LRU / LFU Cache

Hash map combined with doubly linked list for O(1) eviction and lookup.

Explore Track
C++ Internals

STL unordered_map Internals & Rehashing

Bucket arrays, collision chaining, load factors, and custom hash functors.

Explore Track
Two SumMax Number of K-Sum Pairs