Created
December 28, 2024 16:00
-
-
Save ccampores-n26/29c60a066844283266188fc60828f6e7 to your computer and use it in GitHub Desktop.
DSA Cheat Sheet
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // Two pointers: one input, opposite ends | |
| fun twoPointers(arr: IntArray): Int { | |
| var left = 0 | |
| var right = arr.size - 1 | |
| val ans = 0 | |
| while (left < right) { | |
| // do some logic here with left and right | |
| if (CONDITION) { | |
| left++ | |
| } else { | |
| right-- | |
| } | |
| } | |
| return ans | |
| } | |
| // Two pointers: two inputs, exhaust both | |
| fun twoPointers(arr1: IntArray, arr2: IntArray): Int { | |
| var i = 0 | |
| var j = 0 | |
| val ans = 0 | |
| while (i < arr1.size && j < arr2.size) { | |
| // do some logic here | |
| if (CONDITION) { | |
| i++ | |
| } else { | |
| j++ | |
| } | |
| } | |
| while (i < arr1.size) { | |
| // do logic | |
| i++ | |
| } | |
| while (j < arr2.size) { | |
| // do logic | |
| j++ | |
| } | |
| return ans | |
| } | |
| class ListNode(val data: Int) { | |
| var next: ListNode? = null | |
| } | |
| // Linked list: fast and slow pointers | |
| fun linkedList(head: ListNode?): Int { | |
| var slow: ListNode? = head | |
| var fast: ListNode? = head | |
| val ans = 0 | |
| while (fast != null && fast.next != null) { | |
| // do logic | |
| slow = slow?.next | |
| fast = fast.next?.next | |
| } | |
| // slow points to the middle element | |
| val mid = slow | |
| return ans | |
| } | |
| // Reverse linked list | |
| fun reverseLinkedList(head: ListNode?): ListNode? { | |
| var curr: ListNode? = head | |
| var prev: ListNode? = null | |
| while (curr != null) { | |
| val nextNode: ListNode? = curr.next | |
| curr.next = prev | |
| prev = curr | |
| curr = nextNode | |
| } | |
| return prev | |
| } | |
| // Sliding window | |
| fun slidingWindow(arr: IntArray): Int { | |
| var left = 0 | |
| val ans = 0 | |
| var curr = 0 | |
| for (right in arr.indices) { | |
| curr += arr[right] | |
| while (WINDOW_CONDITION_BROKEN) { | |
| curr -= arr[left] | |
| left++ | |
| } | |
| // update ans | |
| } | |
| return ans | |
| } | |
| // Binary search | |
| fun binarySearch(arr: IntArray, target: Int): Int { | |
| if (arr.isEmpty()) | |
| return -1 | |
| var left = 0 | |
| var right = arr.size - 1 | |
| while (left <= right) { | |
| val mid = left + (right - left) / 2 // same as (start+end)/2 but avoids overflow | |
| if (arr[mid] == target) { | |
| return mid | |
| } | |
| if (arr[mid] > target) { | |
| right = mid - 1 | |
| } else { | |
| left = mid + 1 | |
| } | |
| } | |
| return -1 | |
| } | |
| // Build a prefix sum | |
| fun prefixSum(arr: IntArray): IntArray? { | |
| val prefix = IntArray(arr.size) | |
| prefix[0] = arr[0] | |
| for (i in 1 until arr.size) { | |
| prefix[i] = prefix[i - 1] + arr[i] | |
| } | |
| return prefix | |
| } | |
| // String building | |
| fun buildString(arr: CharArray): String? { | |
| val sb = StringBuilder() | |
| for (c in arr) { | |
| sb.append(c) | |
| } | |
| return sb.toString() | |
| } | |
| // DFS iterative | |
| fun dfs(root: TreeNode?): Int { | |
| val stack = mutableListOf<TreeNode?>() | |
| stack.add(root) | |
| val ans = 0 | |
| while (stack.isNotEmpty()) { | |
| val node = stack.removeLast() | |
| // do logic | |
| stack.add(node?.left) | |
| stack.add(node?.right) | |
| } | |
| return ans | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment