DSA I: Arrays, Strings, HashMaps, Sets & Two Pointers

Real-world analogy

What is it?

Arrays, HashMaps, Sets, and the Two-Pointer technique form the foundation of coding interviews. Together, they solve the majority of easy and medium problems. The core insight is that nested loops (O(n^2)) can almost always be replaced by a single pass with a HashMap or two-pointer scan (O(n)). Mastering these patterns means recognizing the shape of a problem and immediately knowing which data structure breaks the inner loop.

Real-world relevance

In the Hazira Khata app, attendance deduplication was implemented using a HashSet of (employeeId + date) composite keys. The initial implementation used a nested loop to check existing records — O(n^2) and causing UI jank on large attendance sheets. The fix used a HashSet populated at load time, making duplicate detection O(1) per record — O(n) total. This is the two-sum pattern applied to a real product.

Key points

• Array Manipulation Fundamentals — Arrays give O(1) index access and O(n) search. Know your Kotlin idioms: indices, lastIndex, first(), last(), getOrNull(), slice(), subList(). Common patterns: prefix sum (precompute cumulative sums for O(1) range queries), in-place modification (use index variables to avoid extra allocation), and sentinel values to simplify edge cases.
• HashMap for O(1) Lookup — The Core Pattern — Replace any O(n) inner loop with a HashMap. The universal template: iterate once to build the map (key = what you want to find, value = index or count or data). Then iterate again (or simultaneously) doing O(1) lookups. This transforms O(n^2) to O(n) for most frequency, existence, and pairing problems.
• Two-Sum Pattern (HashMap Classic) — Given an array and a target, find two indices whose values sum to target. Brute force: O(n^2) nested loops. Optimized: single pass HashMap storing complement-to-index. For each element x, check if (target - x) is in the map. If yes, found the pair. If no, add x to the map. O(n) time, O(n) space.
• HashSet for Uniqueness — Use a HashSet when you care about existence, not frequency. Contains-duplicate: add each element to a HashSet; if add returns false, duplicate found — O(n) time. Longest consecutive sequence: put all elements in a set, then only start counting from elements with no predecessor (num-1 not in set). Avoids redundant traversals.
• String as a Character Array — Strings are immutable in Kotlin/Java. Never concatenate in a loop — use StringBuilder (amortized O(1) append, O(n) total). To check anagrams: sort both strings and compare (O(n log n)), or use frequency maps (O(n)). Palindrome check: two pointers from both ends comparing characters. sliding window for substring problems.
• Two-Pointer Technique — Use two indices that start at different positions and move toward each other (or in the same direction). Requires a sorted array for most problems. Reduces the inner loop of O(n^2) brute force to O(n) single pass. Template: left=0, right=n-1. Compute result. If too small, left++. If too large, right--. If match, record and move both.
• Two-Sum II (Sorted Array) — Two Pointers — Given a sorted array, find a pair summing to target. Brute force: O(n^2). Two pointers: start at both ends. If sum target, move right pointer left. If equal, done. O(n) time, O(1) space — better than HashMap when the input is already sorted.
• Container With Most Water — Given heights at each index, find two lines that hold the most water. Brute force: O(n^2) check all pairs. Insight: the water held is min(height[L], height[R]) * (R - L). Two pointers from both ends: always move the pointer with the SMALLER height (moving the larger height pointer can only decrease the width without increasing the height). O(n) time.
• Sliding Window Intro — For substring or subarray problems with a contiguous constraint, use a sliding window: expand the right pointer to grow the window, shrink the left pointer to maintain the constraint. Max sum subarray of size k: initialize window sum for first k elements, then slide right and subtract left. O(n) instead of O(n*k). Requires careful boundary management.
• Frequency Map Pattern — Count occurrences with a HashMap or IntArray (if chars are ASCII). Anagram check: frequency map of s1 subtracted by s2 must be all zeros. Group anagrams: use sorted string as the HashMap key. Top-K frequent elements: frequency map + min-heap of size K (O(n log k)). This pattern appears in at least 20% of interview problems.
• Prefix Sum Array — Build a cumulative sum array where prefixSum[i] = sum of all elements from index 0 to i. After O(n) preprocessing, any range sum query [L, R] is O(1): prefixSum[R] - prefixSum[L-1]. Used for: subarray sum equals k (pair the prefix sum with a HashMap), product of array except self, and range minimum queries.
• Interview Pattern Recognition — When you see: 'find two elements that...' — think HashMap or two pointers. 'Find a subarray/substring that...' — think sliding window or prefix sum. 'Contains duplicate / unique elements' — think HashSet. 'Sorted array, find pair' — think two pointers (O(1) space vs HashMap O(n) space). Stating the brute force first, then optimizing, shows structured thinking even if you don't finish.

Code example

// ─── TWO SUM (HashMap, O(n)) ───
fun twoSum(nums: IntArray, target: Int): IntArray {
    val seen = HashMap<Int, Int>() // value -> index
    for (i in nums.indices) {
        val complement = target - nums[i]
        if (seen.containsKey(complement)) {
            return intArrayOf(seen[complement]!!, i)
        }
        seen[nums[i]] = i
    }
    return intArrayOf() // no solution found
}

// ─── TWO SUM II — SORTED ARRAY (Two Pointers, O(n), O(1) space) ───
fun twoSumSorted(numbers: IntArray, target: Int): IntArray {
    var left = 0
    var right = numbers.size - 1
    while (left < right) {
        val sum = numbers[left] + numbers[right]
        when {
            sum == target -> return intArrayOf(left + 1, right + 1) // 1-indexed
            sum < target -> left++
            else -> right--
        }
    }
    return intArrayOf()
}

// ─── CONTAINS DUPLICATE (HashSet, O(n)) ───
fun containsDuplicate(nums: IntArray): Boolean {
    val seen = HashSet<Int>()
    for (num in nums) {
        if (!seen.add(num)) return true // add returns false if already present
    }
    return false
}

// ─── CONTAINER WITH MOST WATER (Two Pointers, O(n)) ───
fun maxWater(height: IntArray): Int {
    var left = 0
    var right = height.size - 1
    var maxArea = 0
    while (left < right) {
        val area = minOf(height[left], height[right]) * (right - left)
        maxArea = maxOf(maxArea, area)
        if (height[left] < height[right]) left++ else right--
    }
    return maxArea
}

// ─── SLIDING WINDOW — MAX SUM SUBARRAY OF SIZE K ───
fun maxSumSubarrayK(nums: IntArray, k: Int): Int {
    var windowSum = nums.take(k).sum() // initial window
    var maxSum = windowSum
    for (i in k until nums.size) {
        windowSum += nums[i] - nums[i - k] // slide: add new, remove old
        maxSum = maxOf(maxSum, windowSum)
    }
    return maxSum
}

Line-by-line walkthrough

1. 1. twoSum iterates nums once. For each nums[i], the complement is target - nums[i] — if the complement was seen before, we have our pair.
2. 2. seen[nums[i]] = i stores the current element's value as key and its index as value — we store AFTER checking so an element doesn't pair with itself.
3. 3. twoSumSorted uses left and right pointers starting at both ends. If the sum is too small, we need a larger number so left moves right. If too large, right moves left.
4. 4. containsDuplicate uses HashSet.add() which returns false if the element already exists — this is cleaner than checking contains() then add() which would be two operations.
5. 5. maxWater computes area as min(height[L], height[R]) * (R - L). Moving the smaller height pointer is the key insight — moving the larger one cannot possibly improve the minimum.
6. 6. maxSumSubarrayK initializes the window sum for the first k elements, then for each new position adds nums[i] (new right) and subtracts nums[i-k] (old left) — the window slides in O(1) per step.
7. 7. The sliding window avoids recomputing the entire window sum each time — without it, each window computation would be O(k), making the total O(n*k).
8. 8. All HashMap-based solutions trade O(n) extra space for O(n) time — always mention this space-time tradeoff in interviews and confirm whether space constraints exist.

Spot the bug

fun twoSum(nums: IntArray, target: Int): IntArray {
    val seen = HashMap<Int, Int>()
    for (i in nums.indices) {
        val complement = target - nums[i]
        seen[nums[i]] = i
        if (seen.containsKey(complement)) {
            return intArrayOf(seen[complement]!!, i)
        }
    }
    return intArrayOf()
}

// Test: nums = [3, 3], target = 6
// Expected: [0, 1]
// Actual: ???

Explain like I'm 5

Fun fact

Hands-on challenge

More resources

• LeetCode — Two Sum (LeetCode)
• LeetCode — Container With Most Water (LeetCode)
• Neetcode — Arrays & Hashing Roadmap (Neetcode)
• LeetCode — Sliding Window Pattern (LeetCode)
• Kotlin Collection Operations (Kotlin)