DSA with Kotlin

Loops

Forward Loop

for (i in 0 until 10) {
    println(i) // prints 0 to 9
}

Reverse Loop

for (i in 9 downTo 0) {
    println(i) // prints 9 to 0
}

Arrays

Types of Arrays

Array<Int>

• Stores objects (Integer in JVM).
• Higher memory usage due to boxing.
• Use when nullable values are needed (Array<Int?>).

val arr: Array<Int> = arrayOf(10, 20, 30)

IntArray

• Stores primitive int values directly.
• Better performance and less memory usage.
• Cannot hold null.

val arr = intArrayOf(1, 2, 3) // Creates IntArray (not boxed Array<Int>)

Common Methods

val arr = intArrayOf(5, 2, 9, 1, 7, 2)

// Size and Indices
println("Size: ${arr.size}")
println("Indices: ${arr.indices}")

// Accessing Elements Safely
println("Element at 10: ${arr.getOrNull(10)}")  // null-safe access

// First and Last Elements
println("First: ${arr.first()}")
println("Last: ${arr.last()}")

// Min and Max
println("Min: ${arr.minOrNull()}")
println("Max: ${arr.maxOrNull()}")

// Sum and Average
println("Sum: ${arr.sum()}")
println("Average: ${arr.average()}")

// Sorting
println("Sorted: ${arr.sorted()}")
println("Sorted Desc: ${arr.sortedDescending()}")

// Distinct Elements
println("Distinct: ${arr.distinct()}")

// Counting Elements
println("Count of 2s: ${arr.count { it == 2 }}")

// Mapping and Filtering
val doubled = arr.map { it * 2 }
val evens = arr.filter { it % 2 == 0 }
println("Doubled: $doubled")
println("Evens: $evens")

// Checking Conditions
println("Any > 8? ${arr.any { it > 8 }}")
println("All > 0? ${arr.all { it > 0 }}")

// Index Operations
println("First index of 2: ${arr.indexOf(2)}")
println("Last index of 2: ${arr.lastIndexOf(2)}")

// Contains
println("Contains 9? ${arr.contains(9)}")

// Iterating
print("Elements: ")
arr.forEach { print("$it ") }
println()

// Reduce and Fold
val product = arr.reduce { acc, i -> acc * i }
val sumFold = arr.fold(10) { acc, i -> acc + i }  // 10 as initial
println("Product (reduce): $product")
println("Sum +10 (fold): $sumFold")

// Taking and Dropping
println("Take 3: ${arr.take(3)}")
println("Drop 3: ${arr.drop(3)}")

// Reversing
println("Reversed: ${arr.reversed()}")

// Indexed Iteration
for ((i, v) in arr.withIndex()) {
    println("Index $i → $v")
}

// Conversions
val asSet = arr.toSet()
val asList = arr.toList()
println("As Set: $asSet")
println("As List: $asList")

// Copying
val copy = arr.copyOf()
val clone = arr.clone()
println("Copied: ${copy.toList()}")
println("Cloned: ${clone.toList()}")

// Equality Check
println("Equals copy? ${arr.contentEquals(copy)}")

Strings

Properties and Behavior

• Immutable: Methods like replace(), uppercase(), trim(), etc., return a new string.
• Properties (.length) represent state.
• Functions (.isEmpty()) represent behavior.

Common Methods

val input = "  A man, a plan, a canal: Panama  "

// Trim and Case Conversion
val trimmed = input.trim()
val lower = trimmed.lowercase()

// Filtering and Palindrome Check
val cleaned = lower.filter { it.isLetterOrDigit() }
val isPalindrome = cleaned == cleaned.reversed()
println("Is palindrome: $isPalindrome")

// Contains, StartsWith, EndsWith
println("Contains 'canal'? -> ${input.contains("canal")}")
println("Starts with '  A'? -> ${input.startsWith("  A")}")
println("Ends with 'Panama  '? -> ${input.endsWith("Panama  ")}")

// Index Operations
println("First index of 'a': ${input.indexOf('a')}")
println("Last index of 'a': ${input.lastIndexOf('a')}")

// Safe Access
println("Char at index 100 (safe): ${input.getOrNull(100)}")

// Replace
val noColon = input.replace(":", "")
println("Removed colon: $noColon")
val digitsOnly = "a1b2c3".replace(Regex("[^0-9]"), "")
println("Digits only: $digitsOnly") // 123

// Mapping and Counting
val upperMapped = input.map { it.uppercaseChar() }.joinToString("")
val countA = input.count { it.lowercaseChar() == 'a' }
println("Uppercased: $upperMapped")
println("Count of 'a': $countA")

// Splitting and Joining
val words = input.split(" ")
val wordParts = input.split(Regex("[^A-Za-z]+"))
println("Split by space: $words")
println("Split by non-letters: $wordParts")
val joined = wordParts.filter { it.isNotEmpty() }.joinToString("-")
println("Joined parts: $joined")

// Substring and Windowed
println("Substring(2, 6): ${input.substring(2, 6)}")
val substrings = cleaned.windowed(5, 1)
println("Windowed substrings of size 5: $substrings")

// ZipWithNext
val diffs = cleaned.zipWithNext { a, b -> "$a->$b" }
println("Adjacent pairs: $diffs")

Stack

Example Usage

val stack = mutableListOf<Int>()

// Push
stack.add(10)
stack.add(20)

// Pop
val top = stack.removeLast()
println(top) // 20

// Peek
val peek = stack.last()
println(peek) // 10

Null-Safety

Example Usage

val len = userName?.length ?: 0

Comparisons

Find Minimum

val result = minOf(10, 20) // 10

Find Maximum

val result = maxOf(10, 20) // 20

Constants

val intMax = Int.MAX_VALUE
val intMin = Int.MIN_VALUE
val floatMax = Float.MAX_VALUE
val floatMin = -Float.MAX_VALUE
val charMin = Char.MIN_VALUE

Filtering String or Array

Example Usage

val clean = s.filter { it.isLetterOrDigit() }

val arr = intArrayOf(1, 2, 3, 4, 5)
val evens = arr.filter { it % 2 == 0 }  // List<Int>: [2, 4]

Char Extensions

Methods

• isLetterOrDigit()
• isLetter()
• isDigit()
• isUpperCase()
• isLowerCase()

DFS (Depth-First Search)

• DFS is a recursive algorithm for traversing or searching tree/graph data structures.
• It explores as far as possible along each branch before backtracking.
• Useful for problems like flood fill, connected components, pathfinding, etc.
• Can be implemented recursively or with an explicit stack.

Flood Fill Example

class Solution {
    fun floodFill(image: Array<IntArray>, sr: Int, sc: Int, color: Int): Array<IntArray> {
        val originalColor = image[sr][sc]
        fun dfs(r: Int, c: Int) {
            if (r < 0 || c < 0 || r > image.lastIndex || c > image.first().lastIndex) return
            if (image[r][c] == color || image[r][c] != originalColor) return
            image[r][c] = color
            dfs(r + 1, c)
            dfs(r - 1, c)
            dfs(r, c + 1)
            dfs(r, c - 1)
        }
        dfs(sr, sc)
        return image
    }
}

Sliding Window

What is Sliding Window?

• The Sliding Window technique is used to efficiently solve problems involving subarrays or substrings within a larger array or string.
• It maintains a window (range) that slides over the data structure, updating results as it moves.
• Useful for optimizing time complexity from O(n*k) to O(n) in many cases.

Common Use Cases

• Maximum/minimum sum of subarray of size k
• Longest substring with unique characters
• Counting elements in a moving range
• Problems involving continuous segments

Example: Maximum Sum of Subarray of Size k

fun maxSumSubarray(arr: IntArray, k: Int): Int {
    if (arr.size < k) return 0
    var maxSum = 0
    var windowSum = 0
    // Compute sum of first window
    for (i in 0 until k) {
        windowSum += arr[i]
    }
    maxSum = windowSum
    // Slide the window
    for (i in k until arr.size) {
        windowSum += arr[i] - arr[i - k]
        maxSum = maxOf(maxSum, windowSum)
    }
    return maxSum
}

val arr = intArrayOf(2, 1, 5, 1, 3, 2)
val k = 3
println("Max sum of subarray of size $k: ${maxSumSubarray(arr, k)}") // Output: 9

Tips

• Use variables to track the window's start and end indices.
• Update results incrementally to avoid recomputation.
• Works for arrays and strings.

Binary Search

What is Binary Search?

• Binary Search is an efficient algorithm for finding an element in a sorted array or list.
• It works by repeatedly dividing the search interval in half, comparing the target value to the middle element.
• Time complexity: O(log n).

Common Use Cases

• Searching for a value in a sorted array
• Finding the insertion point for a value
• Solving problems involving monotonic functions (e.g., minimum/maximum feasible value)

Example: Binary Search in a Sorted Array

fun binarySearch(arr: IntArray, target: Int): Int {
    var left = 0
    var right = arr.lastIndex
    while (left <= right) {
        val mid = left + (right - left) / 2
        when {
            arr[mid] == target -> return mid // Found
            arr[mid] < target -> left = mid + 1
            else -> right = mid - 1
        }
    }
    return -1 // Not found
}

val arr = intArrayOf(1, 3, 5, 7, 9, 11)
val target = 7
println("Index of $target: ${binarySearch(arr, target)}") // Output: 3

Tips

• The array must be sorted for binary search to work.
• Can be adapted for searching in lists, strings, or custom conditions.
• Useful for optimization problems (e.g., finding boundaries).

BFS (Breadth-First Search)

• BFS is an algorithm for traversing or searching tree/graph data structures level by level.
• It explores all neighbors at the current depth before moving to nodes at the next depth level.
• Useful for finding the shortest path, connected components, and level-order traversal.
• Typically implemented using a queue.

BFS Example: Graph Traversal

fun bfs(graph: Map<Int, List<Int>>, start: Int): List<Int> {
    val visited = mutableSetOf<Int>()
    val queue = ArrayDeque<Int>()
    val order = mutableListOf<Int>()
    queue.add(start)
    visited.add(start)
    while (queue.isNotEmpty()) {
        val node = queue.removeFirst()
        order.add(node)
        for (neighbor in graph[node].orEmpty()) {
            if (neighbor !in visited) {
                visited.add(neighbor)
                queue.add(neighbor)
            }
        }
    }
    return order
}

val graph = mapOf(
    0 to listOf(1, 2),
    1 to listOf(0, 3),
    2 to listOf(0, 3),
    3 to listOf(1, 2)
)
println("BFS order: ${bfs(graph, 0)}") // Output: [0, 1, 2, 3]

BFS Example: Shortest Path in Unweighted Graph

fun shortestPath(graph: Map<Int, List<Int>>, start: Int, end: Int): List<Int> {
    val queue = ArrayDeque<List<Int>>()
    val visited = mutableSetOf<Int>()
    queue.add(listOf(start))
    visited.add(start)
    while (queue.isNotEmpty()) {
        val path = queue.removeFirst()
        val node = path.last()
        if (node == end) return path
        for (neighbor in graph[node].orEmpty()) {
            if (neighbor !in visited) {
                visited.add(neighbor)
                queue.add(path + neighbor)
            }
        }
    }
    return emptyList() // No path found
}

println("Shortest path from 0 to 3: ${shortestPath(graph, 0, 3)}") // Output: [0, 1, 3] or [0, 2, 3]

Tips

• Use a queue to process nodes in FIFO order.
• Track visited nodes to avoid cycles.
• BFS guarantees the shortest path in unweighted graphs.

Two Pointer Technique

What is Two Pointer?

- The Two Pointer technique uses two indices to traverse a data structure, often to find pairs, subarrays, or solve partitioning problems efficiently. - Commonly used for problems involving sorted arrays, linked lists, or strings.

Common Use Cases

- Finding pairs with a given sum - Removing duplicates - Partitioning arrays - Merging sorted arrays

Example: Pair Sum in Sorted Array

fun hasPairWithSum(arr: IntArray, target: Int): Boolean {
    var left = 0
    var right = arr.lastIndex
    while (left < right) {
        val sum = arr[left] + arr[right]
        when {
            sum == target -> return true
            sum < target -> left++
            else -> right--
        }
    }
    return false
}

Topological Sort

What is Topological Sort?

• Topological Sort is an ordering of the vertices in a Directed Acyclic Graph (DAG) such that for every directed edge u -> v, vertex u comes before v in the ordering.
• Used in scheduling tasks, resolving dependencies, and more.
• Only possible if the graph has no cycles.

Common Use Cases

• Task scheduling with dependencies
• Course prerequisite resolution
• Build systems (compilation order)

Example: Kahn's Algorithm (BFS-based)

fun topologicalSort(graph: Map<Int, List<Int>>): List<Int> {
    val inDegree = mutableMapOf<Int, Int>()
    graph.keys.forEach { inDegree[it] = 0 }
    graph.values.flatten().forEach { inDegree[it] = inDegree.getOrDefault(it, 0) + 1 }
    val queue = ArrayDeque<Int>()
    inDegree.forEach { (node, deg) -> if (deg == 0) queue.add(node) }
    val order = mutableListOf<Int>()
    while (queue.isNotEmpty()) {
        val node = queue.removeFirst()
        order.add(node)
        for (neighbor in graph[node].orEmpty()) {
            inDegree[neighbor] = inDegree[neighbor]!! - 1
            if (inDegree[neighbor] == 0) queue.add(neighbor)
        }
    }
    return if (order.size == inDegree.size) order else emptyList() // empty if cycle
}

val graph = mapOf(
    5 to listOf(2, 0),
    4 to listOf(0, 1),
    2 to listOf(3),
    3 to listOf(1),
    0 to listOf(),
    1 to listOf()
)
println("Topological order: ${topologicalSort(graph)}") // Output: [4, 5, 2, 3, 1, 0] (one possible order)

Example: DFS-based Topological Sort

fun topologicalSortDFS(graph: Map<Int, List<Int>>): List<Int> {
    val visited = mutableSetOf<Int>()
    val stack = mutableListOf<Int>()
    fun dfs(node: Int) {
        if (node in visited) return
        visited.add(node)
        for (neighbor in graph[node].orEmpty()) {
            dfs(neighbor)
        }
        stack.add(node)
    }
    graph.keys.forEach { dfs(it) }
    return stack.reversed()
}

println("Topological order (DFS): ${topologicalSortDFS(graph)}")

Tips

• Use Kahn's algorithm for cycle detection (returns empty if cycle exists).
• DFS-based approach is simple and works well for small graphs.
• Always check for cycles before using topological sort for scheduling.