Pattern Recognition & Problem-Solving Strategy

1// Pattern matching examples
2
3// PATTERN: When you see "subarray with sum = K" → Prefix sum + HashMap
4fun subarraySum(nums: IntArray, k: Int): Int {
5    val prefixCount = mutableMapOf(0 to 1) // prefix_sum → count
6    var sum = 0
7    var count = 0
8    for (num in nums) {
9        sum += num
10        count += prefixCount.getOrDefault(sum - k, 0)
11        prefixCount[sum] = prefixCount.getOrDefault(sum, 0) + 1
12    }
13    return count
14}
15// Trigger identified: "subarray" + "sum equals K"
16// Pattern: Prefix sum with HashMap
17
18// PATTERN: When you see "generate all subsets" → Backtracking
19fun subsets(nums: IntArray): List<List<Int>> {
20    val result = mutableListOf<List<Int>>()
21    
22    fun backtrack(start: Int, current: MutableList<Int>) {
23        result.add(current.toList()) // Add current subset
24        for (i in start until nums.size) {
25            current.add(nums[i])       // Choose
26            backtrack(i + 1, current)  // Explore
27            current.removeAt(current.lastIndex) // Un-choose
28        }
29    }
30    
31    backtrack(0, mutableListOf())
32    return result
33}
34
35// PATTERN: When you see "K-th largest" → Min-heap of size K
36fun findKthLargest(nums: IntArray, k: Int): Int {
37    val minHeap = PriorityQueue<Int>() // Min-heap
38    for (num in nums) {
39        minHeap.offer(num)
40        if (minHeap.size > k) minHeap.poll() // Remove smallest
41    }
42    return minHeap.peek() // K-th largest is at top
43}
44// O(n log k) time, O(k) space
45
46// PATTERN: When you see "minimum in rotated sorted" → Modified binary search
47fun findMin(nums: IntArray): Int {
48    var lo = 0
49    var hi = nums.lastIndex
50    while (lo < hi) {
51        val mid = lo + (hi - lo) / 2
52        if (nums[mid] > nums[hi]) lo = mid + 1
53        else hi = mid
54    }
55    return nums[lo]
56}