Skip to content

Instantly share code, notes, and snippets.

@UNISERVO1
Created August 7, 2020 04:14
Show Gist options
  • Save UNISERVO1/1439114ae592031389b0673c18f3256d to your computer and use it in GitHub Desktop.
Save UNISERVO1/1439114ae592031389b0673c18f3256d to your computer and use it in GitHub Desktop.
August LeetCoding Challenge Week 1: Day 6 (using negative substitution for O(n))
import kotlin.math.abs
class Solution {
fun findDuplicates(nums: IntArray): List<Int> {
fun twiceFound(acc: Pair<List<Int>, MutableList<Int>>, num: Int): Pair<List<Int>, MutableList<Int>> {
val (uniques, negs) = acc
return if (negs[abs(num) - 1] < 0) {
uniques.plus(num) to negs
} else {
negs[abs(num) - 1] = -1 * negs[abs(num) - 1]
uniques to negs
}
}
val (twices, _) = nums.fold(listOf<Int>() to nums.toMutableList(), { t, num -> twiceFound(t, num) })
return twices
}
}
@UNISERVO1
Copy link
Author

Results for find_all_array_dups.kt:
Screen Shot 2020-08-06 at 8 24 04 PM

Results for find_all_array_dups_using_negs.kt:
Screen Shot 2020-08-06 at 9 09 44 PM

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment