Any Duplicate Within K Distance Using C#

Sandhiya Priya

1. Introduction

The Any Duplicate Within K Distance problem is a common array and HashSet problem.

Given an integer array arr[] and an integer k, we need to check whether there are two different indices i and j such that:

arr[i] == arr[j]
|i - j| <= k

In simple words, we need to find whether any element appears more than once within a distance of k indices.

We can solve this problem efficiently using a HashSet and Sliding Window technique.

2. Example

Input:

arr = [1, 5, 4, 5, 1]
k = 3

Output:

true

Explanation:

The element 5 occurs at two different indices:

First occurrence: Index 1
Second occurrence: Index 3

Distance:

|3 - 1| = 2

Since 2 <= 3, a duplicate exists within the given distance.

Therefore, the answer is true.

3. Understanding the Concepts

What is a HashSet?

A HashSet is a collection that stores only unique elements.

For example:

HashSet<int> set = new HashSet<int>();

set.Add(10);
set.Add(20);
set.Add(10);

The HashSet contains:

[10, 20]

The duplicate value 10 is not stored twice.

Important HashSet operations:

Method	Purpose
Add()	Adds an element
Contains()	Checks whether an element exists
Remove()	Removes an element

These operations take O(1) average time.

What is the Sliding Window technique?

Sliding Window is a technique where we maintain a limited range of elements while traversing an array.

In this problem, we only need to remember the previous k elements.

When we move to the next index:

Check whether the current element already exists.
If it exists, return true.
Otherwise, add it to the HashSet.
Remove the element that is outside the allowed window.

This ensures that we only check elements within the required distance.

4. C# Implementation

class Solution
{
    public bool checkWithinK(int[] arr, int k)
    {
        HashSet<int> set = new HashSet<int>();

        for (int i = 0; i < arr.Length; i++)
        {
            // Check whether the current element already exists
            if (set.Contains(arr[i]))
            {
                return true;
            }

            // Add the current element
            set.Add(arr[i]);

            // Maintain the previous k elements
            if (set.Count > k)
            {
                set.Remove(arr[i - k]);
            }
        }

        return false;
    }
}

5. Step-by-Step Code Explanation

Step 1: Create a HashSet

HashSet<int> set = new HashSet<int>();

We create a HashSet to store the elements from the previous indices.

Step 2: Traverse the array

for (int i = 0; i < arr.Length; i++)

We iterate through every element in the array.

Step 3: Check for duplicates

if (set.Contains(arr[i]))
{
    return true;
}

Before inserting the current element, we check whether it already exists in the HashSet.

If it exists, the same value has appeared within the previous k indices. Therefore, we return true.

Step 4: Add the current element

set.Add(arr[i]);

If the element is not already present, add it to the HashSet.

Step 5: Maintain the Sliding Window

if (set.Count > k)
{
    set.Remove(arr[i - k]);
}

We remove the element that is no longer within the allowed distance.

This keeps the HashSet limited to the previous k elements after processing each index.

Step 6: Return false

return false;

If the loop finishes without finding any duplicate, return false.

6. Dry Run

Let's understand the execution with this example:

arr = [1, 5, 4, 5, 1]
k = 3

Index	Element	HashSet before checking	Action
0	1	{}	Add 1
1	5	{1}	Add 5
2	4	{1, 5}	Add 4
3	5	{1, 5, 4}	Duplicate found

At index 3:

Current element = 5
Previous occurrence = Index 1

Distance = |3 - 1|
         = 2

2 <= 3

Therefore:

Output = true

7. Another Example

Input:

arr = [10, 2, 3, 4, 10, 5]
k = 3

The element 10 appears at index 0 and index 4.

Distance = |4 - 0|
         = 4

Since 4 > 3, the duplicate is outside the allowed distance.

The HashSet removes the first 10 before processing index 4.

Output:

false

8. Complexity Analysis

Time Complexity: O(n)

We traverse the array only once.
HashSet Contains() takes O(1) average time.
HashSet Add() takes O(1) average time.
HashSet Remove() takes O(1) average time.

Therefore, the overall expected time complexity is O(n).

Auxiliary Space Complexity: O(min(n, k))

The HashSet stores at most k previous elements.

Therefore, the space complexity is O(min(n, k)).

9. Important Interview Points

Why do we use HashSet?
To check duplicate elements efficiently.
Why do we use Sliding Window?
Because we only need to consider the previous k indices.
Why do we remove old elements?
To avoid considering duplicates that are farther than k positions away.
Why do we check Contains() before Add()?
To identify whether the current element already appeared within the allowed range.
What happens if all elements are unique?
The method returns false.

10. Conclusion

The Any Duplicate Within K Distance problem can be solved efficiently using the HashSet and Sliding Window technique.

Instead of comparing every pair of elements using nested loops, we maintain a limited window of previous elements and check duplicates in constant average time.

Key Takeaway:

Whenever a problem asks you to find duplicates within a specific index distance, think about using:

Arrays
HashSet
Sliding Window

This approach helps reduce the time complexity from O(n²) to O(n) average time.

Visual understanding of the sliding window

Array: [1, 5, 4, 5, 1]

k = 3

Index 0

Index 1

Index 2

Index 3

Index 4

Duplicate

5 appears at indices 1 and 3

Distance = 2, which is within k = 3.

Practice challenge: Try implementing the same problem using a Dictionary<int, int> that stores each element's most recent index. This is another useful approach for interviews.

C#HashSetsliding windowduplicate detectionarraysalgorithmstime complexity

Comments

Join the conversation! Your thoughts help the community grow.

Any Duplicate Within K Distance Using C#

Sandhiya Priya

3h4.3k00100Article

1. Introduction

The Any Duplicate Within K Distance problem is a common array and HashSet problem.

Given an integer array arr[] and an integer k, we need to check whether there are two different indices i and j such that:

arr[i] == arr[j]
|i - j| <= k

In simple words, we need to find whether any element appears more than once within a distance of k indices.

We can solve this problem efficiently using a HashSet and Sliding Window technique.

2. Example

Input:

arr = [1, 5, 4, 5, 1]
k = 3

Output:

true

Explanation:

The element 5 occurs at two different indices:

First occurrence: Index 1
Second occurrence: Index 3

Distance:

|3 - 1| = 2

Since 2 <= 3, a duplicate exists within the given distance.

Therefore, the answer is true.

3. Understanding the Concepts

What is a HashSet?

A HashSet is a collection that stores only unique elements.

For example:

HashSet<int> set = new HashSet<int>();

set.Add(10);
set.Add(20);
set.Add(10);

The HashSet contains:

[10, 20]

The duplicate value 10 is not stored twice.

Important HashSet operations:

Method	Purpose
Add()	Adds an element
Contains()	Checks whether an element exists
Remove()	Removes an element

These operations take O(1) average time.

What is the Sliding Window technique?

Sliding Window is a technique where we maintain a limited range of elements while traversing an array.

In this problem, we only need to remember the previous k elements.

When we move to the next index:

Check whether the current element already exists.
If it exists, return true.
Otherwise, add it to the HashSet.
Remove the element that is outside the allowed window.

This ensures that we only check elements within the required distance.

4. C# Implementation

class Solution
{
    public bool checkWithinK(int[] arr, int k)
    {
        HashSet<int> set = new HashSet<int>();

        for (int i = 0; i < arr.Length; i++)
        {
            // Check whether the current element already exists
            if (set.Contains(arr[i]))
            {
                return true;
            }

            // Add the current element
            set.Add(arr[i]);

            // Maintain the previous k elements
            if (set.Count > k)
            {
                set.Remove(arr[i - k]);
            }
        }

        return false;
    }
}

5. Step-by-Step Code Explanation

Step 1: Create a HashSet

HashSet<int> set = new HashSet<int>();

We create a HashSet to store the elements from the previous indices.

Step 2: Traverse the array

for (int i = 0; i < arr.Length; i++)

We iterate through every element in the array.

Step 3: Check for duplicates

if (set.Contains(arr[i]))
{
    return true;
}

Before inserting the current element, we check whether it already exists in the HashSet.

If it exists, the same value has appeared within the previous k indices. Therefore, we return true.

Step 4: Add the current element

set.Add(arr[i]);

If the element is not already present, add it to the HashSet.

Step 5: Maintain the Sliding Window

if (set.Count > k)
{
    set.Remove(arr[i - k]);
}

We remove the element that is no longer within the allowed distance.

This keeps the HashSet limited to the previous k elements after processing each index.

Step 6: Return false

return false;

If the loop finishes without finding any duplicate, return false.

6. Dry Run

Let's understand the execution with this example:

arr = [1, 5, 4, 5, 1]
k = 3

Index	Element	HashSet before checking	Action
0	1	{}	Add 1
1	5	{1}	Add 5
2	4	{1, 5}	Add 4
3	5	{1, 5, 4}	Duplicate found

At index 3:

Current element = 5
Previous occurrence = Index 1

Distance = |3 - 1|
         = 2

2 <= 3

Therefore:

Output = true

7. Another Example

Input:

arr = [10, 2, 3, 4, 10, 5]
k = 3

The element 10 appears at index 0 and index 4.

Distance = |4 - 0|
         = 4

Since 4 > 3, the duplicate is outside the allowed distance.

The HashSet removes the first 10 before processing index 4.

Output:

false

8. Complexity Analysis

Time Complexity: O(n)

We traverse the array only once.
HashSet Contains() takes O(1) average time.
HashSet Add() takes O(1) average time.
HashSet Remove() takes O(1) average time.

Therefore, the overall expected time complexity is O(n).

Auxiliary Space Complexity: O(min(n, k))

The HashSet stores at most k previous elements.

Therefore, the space complexity is O(min(n, k)).

9. Important Interview Points

Why do we use HashSet?
To check duplicate elements efficiently.
Why do we use Sliding Window?
Because we only need to consider the previous k indices.
Why do we remove old elements?
To avoid considering duplicates that are farther than k positions away.
Why do we check Contains() before Add()?
To identify whether the current element already appeared within the allowed range.
What happens if all elements are unique?
The method returns false.

10. Conclusion

The Any Duplicate Within K Distance problem can be solved efficiently using the HashSet and Sliding Window technique.

Instead of comparing every pair of elements using nested loops, we maintain a limited window of previous elements and check duplicates in constant average time.

Key Takeaway:

Whenever a problem asks you to find duplicates within a specific index distance, think about using:

Arrays
HashSet
Sliding Window

This approach helps reduce the time complexity from O(n²) to O(n) average time.

Visual understanding of the sliding window

Array: [1, 5, 4, 5, 1]

k = 3

Index 0

Index 1

Index 2

Index 3

Index 4

Duplicate

5 appears at indices 1 and 3

Distance = 2, which is within k = 3.

Practice challenge: Try implementing the same problem using a Dictionary<int, int> that stores each element's most recent index. This is another useful approach for interviews.

C#HashSetsliding windowduplicate detectionarraysalgorithmstime complexity

Comments

Join the conversation! Your thoughts help the community grow.