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

Real-world analogy

What is it?

Array, string, HashMap, Set, and two-pointer patterns are the foundational DSA toolkit tested in mobile engineering interviews. Mastering pattern recognition — knowing which data structure eliminates a nested loop — is more valuable than memorizing solutions.

Real-world relevance

In Tixio, finding duplicate message IDs uses a Set for O(1) dedup. Building channel member lookup uses Map for O(1) access. Sliding window detects typing burst rate. These exact patterns appear in mobile engineer interviews — connecting theory to real work you've already done.

Key points

• Array fundamentals and Dart List — Dart List is a dynamic array: O(1) access by index, O(1) amortized add() at end, O(n) insert/remove at arbitrary index (shifts elements). Fixed-length: List.filled(n, 0). Growable: []. In interviews, clarify whether the input is sorted — it unlocks faster algorithms.
• HashMap for O(1) lookup — Map in Dart gives O(1) average insert, delete, and lookup. The classic use: frequency count. Map freq = {}; for (var c in s.split('')) freq[c] = (freq[c] ?? 0) + 1; Replaces O(n) list searches with O(1) map lookups — transforms O(n²) brute force to O(n) in many problems.
• Set for uniqueness and membership — Set gives O(1) contains(), add(), remove(). Use instead of List when you only care about membership, not order or count. Finding duplicates in a list: brute force O(n²) nested loops → O(n) with Set: final seen = {}; for (var x in list) { if (!seen.add(x)) return true; } return false;
• Two-pointer technique — Two pointers work on sorted arrays or strings. Classic: two-sum in sorted array. left=0, right=n-1. While left<right: if arr[left]+arr[right]==target return [left,right]; if sum<target left++; else right--. O(n) vs O(n²) brute force. Also used for: removing duplicates in-place, palindrome check, container with most water.
• Sliding window intro — Sliding window is a subarray/substring technique. Fixed window: maintain a window of size k as you slide across the array — add new element, remove oldest. Variable window: expand right pointer, shrink left when constraint violated. Used for: max sum subarray of size k, longest substring without repeating characters.
• String manipulation patterns — Common patterns: reverse a string (two pointers), check anagram (frequency map), find all anagrams in string (sliding window + frequency comparison), valid palindrome (two pointers ignoring non-alphanumeric). Dart string → chars: s.split('') or s.runes. String → list for mutation since Dart strings are immutable.
• Prefix sum technique — Precompute cumulative sums: prefixSum[i] = arr[0]+...+arr[i-1]. Range sum query in O(1): sum(l,r) = prefixSum[r+1] - prefixSum[l]. Used for: subarray sum equals k (prefix sum + HashMap), number of subarrays with given sum. Transforms O(n) range queries to O(1) after O(n) preprocessing.
• Brute force first — always — In interviews, state the brute force before optimizing. Two-sum brute force: nested loops O(n²) O(1) space → then explain: 'We can trade space for time using a HashMap — store complement, check on each pass — O(n) time O(n) space.' This shows you understand the tradeoff, not just the trick.
• Two-sum pattern (foundational) — Most HashMap optimization problems are extensions of two-sum. Pattern: as you iterate, store what you've seen and check if the current element completes a pair/condition. Generalizes to: three-sum (sort + two pointer), four-sum, subarray with target sum (prefix sum + map), pair with given difference.
• Interview answer structure for DSA — State the problem in your own words. Give brute force with complexity. Identify the bottleneck (what are we doing repeatedly?). Propose the optimization and its tradeoff. Code it up with narration. Test with the given example + edge cases (empty, single element, duplicates, negatives). Time and space complexity at the end.
• Common mobile interview array problems — Top patterns seen in Flutter/Android interviews: 1) Find duplicate in list (Set). 2) Group items by category (Map). 3) Most frequent item (frequency map + max tracking). 4) Check if two lists have common items (Set intersection). 5) Sliding window max of last N events (queue). These map directly to real app logic.
• Dart-specific implementation tips — Use List.generate(n, (i) => 0) for initialized arrays. Map literals: {'a': 1, 'b': 2}. Set literals: {'x', 'y'}. list.fold(0, (acc, x) => acc + x) for reductions. list.where((x) => x > 0).toList() for filtering. list.asMap() to get index-value pairs. These are idiomatic Dart for interview whiteboard code.

Code example

// Pattern 1: Two Sum — brute force → optimized
// Brute force: O(n²) time, O(1) space
List<int> twoSumBrute(List<int> nums, int target) {
  for (int i = 0; i < nums.length; i++) {
    for (int j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] == target) return [i, j];
    }
  }
  return [];
}

// Optimized: O(n) time, O(n) space
List<int> twoSum(List<int> nums, int target) {
  final seen = <int, int>{}; // value → index
  for (int i = 0; i < nums.length; i++) {
    final complement = target - nums[i];
    if (seen.containsKey(complement)) return [seen[complement]!, i];
    seen[nums[i]] = i;
  }
  return [];
}

// Pattern 2: Longest substring without repeating chars
// Sliding window: O(n) time, O(min(n,charset)) space
int lengthOfLongestSubstring(String s) {
  final seen = <String, int>{}; // char → last index
  int maxLen = 0, left = 0;
  for (int right = 0; right < s.length; right++) {
    final c = s[right];
    if (seen.containsKey(c) && seen[c]! >= left) {
      left = seen[c]! + 1; // shrink window
    }
    seen[c] = right;
    maxLen = maxLen > right - left + 1 ? maxLen : right - left + 1;
  }
  return maxLen;
}

// Pattern 3: Group by category (mobile-relevant)
Map<String, List<String>> groupByWorkspace(List<Map<String,String>> messages) {
  final grouped = <String, List<String>>{};
  for (final msg in messages) {
    grouped.putIfAbsent(msg['workspace']!, () => []).add(msg['text']!);
  }
  return grouped;
}

Line-by-line walkthrough

1. 1. twoSum takes a list of numbers and a target sum
2. 2. seen Map stores each number mapped to its index as we iterate
3. 3. For each number, calculate its complement: target - nums[i]
4. 4. If complement is already in seen, we found our pair — return both indices
5. 5. Otherwise store current number's index in seen for future lookups
6. 6. This single pass replaces the nested loop — O(n) instead of O(n²)
7. 7. lengthOfLongestSubstring uses a sliding window with two pointers
8. 8. left marks the start of the current valid window
9. 9. When a duplicate char is found within the window, advance left past it
10. 10. seen Map tracks last index of each character for O(1) window shrinking
11. 11. maxLen is updated on every iteration — no need for a second pass
12. 12. groupByWorkspace uses putIfAbsent to lazily initialize lists — clean Dart pattern

Spot the bug

// Find all duplicates in a list
List<int> findDuplicates(List<int> nums) {
  final result = <int>[];
  for (int i = 0; i < nums.length; i++) {
    for (int j = 0; j < nums.length; j++) {
      if (i != j && nums[i] == nums[j] && !result.contains(nums[i])) {
        result.add(nums[i]);
      }
    }
  }
  return result;
}

Explain like I'm 5

Fun fact

Hands-on challenge

More resources

• Dart Collections — List, Map, Set (dart.dev)
• LeetCode Explore: Array and String (leetcode.com)
• Two Pointers Technique — NeetCode (neetcode.io)
• Sliding Window Pattern — Educative (educative.io)