## The Problem:

Given an array of integers `nums`

and an integer `k`

, determine whether there are two distinct indices `i`

and `j`

in the array where`nums[i] = nums[j]`

and the absolute difference between `i`

and `j`

is less than or equal to `k`

.

**Example**

- For
`nums = [0, 1, 2, 3, 5, 2]`

and`k = 3`

, the output should be

`containsCloseNums(nums, k) = true`

.There are two

`2`

s in`nums`

, and the absolute difference between their positions is exactly`3`

. - For
`nums = [0, 1, 2, 3, 5, 2]`

and`k = 2`

, the output should be`containsCloseNums(nums, k) = false`

.The absolute difference between the positions of the two

`2`

s is`3`

, which is more than`k`

.

**Input/Output**

**[time limit] 4000ms (py)**

**[input] array.integer nums***Constraints:*

`0 ≤ nums.length ≤ 55000`

,

`-2`

.^{31}- 1 ≤ nums[i] ≤ 2^{31}- 1**[input] integer k***Constraints:*

`0 ≤ k ≤ 35000`

.**[output] boolean**

## The Solution:

## The Explanation:

First of all, we can solve this by running two loops, one is **i** from **1 to k** and the other **j** from **0 to len(nums)-i** and compare nums[j] and nums[i+j]. If we find an equality, return 1. If none found, return 0.

However, we would receive **Time Limit Exceeded** Error. So, we need a better solution. We know that when we sort numbers, the same numbers will be consecutive in sorted order. So, if we store the original locations of all elements, we will have the same elements together and also know their original location. All we have to do now is to check if any consecutive equal numbers have a smaller distance than **k+1**.

This reduces our complexity from, let’s say **len(nums) = n**. Then, **O(n*k)** to **O( n*log(n) )**

limit of **n **is 55000 so, **logn **is approximately 16. Where k could be 35000. So, our worst case scenario becomes 55000*35000 to 55000*16.

How we do this is simple. First,generate a new array with numbers and their original addressses. Then, sort them using their values. Then, for each element, check if the previous element has the same value, if so, check their original location distances. If smaller than k+1, return 1

Otherwise, return 0