Algorithms - Basic Patterns - Kotlin

README.md

Basic algorithms patterns to solve leetcode in Kotlin:

• Two Pointers
• Sliding Window
• Binary Search
• Divide and Conquer
• Breadth-first Search (BFS)
• Depth-first Search (DFS)
• Backtracking
• Dynamic Programming
• Priority Queue / Heap
• Trie
• Union Find (DSU)
• Greedy

SlidingWindowTest.kt

import org.junit.jupiter.api.Assertions.assertEquals
import org.junit.jupiter.api.Test

class SlidingWindowTest {
    class Solution {
        fun strStr(haystack: String, needle: String): Int {
            if (haystack.length < needle.length) return -1

            val maxWindowSize = needle.length
            val lastWindowIndex = haystack.length - needle.length

            for (left in 0..lastWindowIndex) {
                var matched = true
                for (w in 0..<maxWindowSize) {
                    if (haystack[left + w] != needle[w]) {
                        matched = false
                        break
                    }
                }
                if (matched) return left
            }
            return -1
        }
    }

    @Test
    fun tests() {
        val scenarios = setOf<Array<Any>>(
            arrayOf(4, "mississippi", "issip"),
            arrayOf(0, "sadbutsad", "sad"),
            arrayOf(-1, "leetcode", "leeto"),
            arrayOf(0, "a", "a"),
            arrayOf(-1, "b", "a"),
            arrayOf(2, "hello", "ll"),
            arrayOf(2, "abc", "c"),
            arrayOf(0, "abc", "a"),
        )
        scenarios.forEach { (result, haystack, needle) ->
            assertEquals(
                result,
                Solution().strStr(haystack as String, needle as String),
                "Failed: $result -> $haystack, $needle",
            )
        }
    }
}

TwoPointersTest.kt

import org.junit.jupiter.api.Assertions.assertEquals
import org.junit.jupiter.api.Test
import kotlin.test.assertContentEquals

class TwoPointersTest {
    class Solution {
        fun removeElement(nums: IntArray, `val`: Int): Int {
            var count = 0
            for (i in 0..<nums.size) {
                if (nums[i] != `val`) {
                    nums[count++] = nums[i]
                }
            }
            return count
        }
    }

    @Test
    fun tests() {
        val scenarios = setOf<Array<Any>>(
            arrayOf(2, intArrayOf(2, 2), intArrayOf(3, 2, 2, 3), 3),
            arrayOf(5, intArrayOf(0, 1, 3, 0, 4), intArrayOf(0, 1, 2, 2, 3, 0, 4, 2), 2),
            arrayOf(0, intArrayOf(), intArrayOf(1, 1, 1, 1), 1),
            arrayOf(1, intArrayOf(1), intArrayOf(1, 2, 2, 2), 2),
            arrayOf(1, intArrayOf(1), intArrayOf(2, 2, 2, 1), 2),
            arrayOf(0, intArrayOf(), intArrayOf(2), 2),
            arrayOf(1, intArrayOf(2), intArrayOf(2), 1),
        )
        scenarios.forEach { (result, expectedNums, nums, `val`) ->
            assertEquals(
                result as Int,
                Solution().removeElement(nums as IntArray, `val` as Int),
                "$result -> $nums, $`val`",
            )
            assertContentEquals(expectedNums as IntArray, nums.copyOfRange(0, result))
        }
    }
}