Skip to content

Instantly share code, notes, and snippets.

@cyrilnoah1
Last active November 26, 2019 03:58
Show Gist options
  • Save cyrilnoah1/6b72a34c29a39ae6f31f7d64a24f8734 to your computer and use it in GitHub Desktop.
Save cyrilnoah1/6b72a34c29a39ae6f31f7d64a24f8734 to your computer and use it in GitHub Desktop.
Find duplicates in an array where an index K is provided such that each window size with indices I and J satisfy abs(J - I) <= K.
import kotlin.system.*
fun main() {
val l = mutableListOf<Int>()
for(i in 1..23){
l.add(i)
}
fun findDupes(arr: List<Int>, k : Int) : Boolean {
val s : MutableSet<Int> = mutableSetOf()
var x = 0
var y = k
if(arr.size < 1 || k < 0){
return false
}
if(k == 0 || k >= arr.size -1){
for(i in 0 until arr.size){
if(s.contains(arr[i])){
return true
}
s.add(arr[i])
}
}else{
while(y < arr.size -1 && x < y){
for(i in x..y){
if(s.contains(arr[i])){
return true
}
s.add(arr[i])
}
x = if(y + 1 < arr.size - 1) y + 1 else x + 1
y = if (y + k < arr.size - 1) y + k else arr.size -1
}
}
return false
}
print(" Time: ${measureTimeMillis(){ print(findDupes(l, 5))}} milliseconds")
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment