Scrolls
5 min read
On this page

Arrays, Strings & Hash Maps

These three data structures account for the majority of coding interview questions. Not because they are complex — they are the simplest structures you will encounter — but because they form the building blocks of almost every solution. If you cannot confidently manipulate arrays, parse strings, and use hash maps for constant-time lookups, you will struggle with every other topic. Master these first.

Arrays

An array is a contiguous block of memory with indexed access. The key properties that matter in interviews:

Operation          Time Complexity
─────────────────────────────────
Access by index    O(1)
Search (unsorted)  O(n)
Search (sorted)    O(log n) with binary search
Insert at end      O(1) amortized (dynamic arrays)
Insert at middle   O(n) — must shift elements
Delete at middle   O(n) — must shift elements

Most interview problems involving arrays come down to a few patterns:

Two Pointers

When you need to find a pair of elements satisfying some condition, or process an array from both ends toward the middle.

Problem: Given a sorted array, find two numbers that sum to a target.

Approach:
  left = 0
  right = length - 1

  while left < right:
      current_sum = arr[left] + arr[right]
      if current_sum == target:
          return [left, right]
      elif current_sum < target:
          left += 1      # need a bigger sum
      else:
          right -= 1     # need a smaller sum

Why it works: Because the array is sorted, moving left increases
the sum and moving right decreases it. We systematically eliminate
impossible pairs without checking all O(n^2) combinations.

Sliding Window

When you need to find a subarray or substring with some property (maximum sum, minimum length, contains all characters).

Problem: Find the maximum sum of any subarray of size k.

Approach:
  Compute the sum of the first k elements.
  Then slide the window: add the next element, remove the first.

  window_sum = sum(arr[0:k])
  max_sum = window_sum

  for i in range(k, length):
      window_sum += arr[i] - arr[i - k]
      max_sum = max(max_sum, window_sum)

This is O(n) instead of O(n*k) because we reuse the previous
sum rather than recomputing from scratch each time.

In-Place Modification

Some problems ask you to modify an array without extra space. The key technique is using the array itself as storage, often with a write pointer.

Problem: Remove duplicates from a sorted array in-place.

Approach:
  write = 1   # position to write next unique element

  for read in range(1, length):
      if arr[read] != arr[read - 1]:
          arr[write] = arr[read]
          write += 1

  return write  # new length

The read pointer scans forward. The write pointer marks where
the next unique element should go. Elements before write are
the deduplicated array.

Strings

Strings are arrays of characters with additional constraints: they are often immutable (in Python, Java, Go), which means "modifying" a string creates a new one. This has performance implications.

String gotchas in interviews:
  - Concatenation in a loop is O(n^2) in many languages because
    each concatenation creates a new string
  - Use a list/array of characters and join at the end: O(n)
  - String comparison is O(n), not O(1) — comparing two strings
    requires checking every character
  - Substring extraction is O(k) where k is the substring length

Common String Patterns

Anagram detection: Two strings are anagrams if they have the same character frequencies. Sort both and compare (O(n log n)), or count characters with a hash map (O(n)).

Problem: Are "listen" and "silent" anagrams?

Approach with frequency counting:
  count = {}
  for char in string1:
      count[char] = count.get(char, 0) + 1
  for char in string2:
      count[char] = count.get(char, 0) - 1

  return all(v == 0 for v in count.values())

Palindrome checking: Compare the string to its reverse, or use two pointers from the ends toward the middle.

Problem: Is "racecar" a palindrome?

  left = 0
  right = length - 1
  while left < right:
      if s[left] != s[right]:
          return False
      left += 1
      right -= 1
  return True

Substring search: When you need to find a pattern in a text. The brute force is O(n*m). For interviews, brute force is usually acceptable unless the interviewer specifically asks for optimization, in which case mention KMP or Rabin-Karp.

Hash Maps

The hash map is the single most important data structure in coding interviews. It provides O(1) average-case lookup, insertion, and deletion. When you are stuck on an interview problem, the first question to ask yourself is: "Can a hash map help here?"

Hash map operations (average case):
  Insert:    O(1)
  Lookup:    O(1)
  Delete:    O(1)
  Iteration: O(n)

Hash map operations (worst case, hash collisions):
  Insert:    O(n)
  Lookup:    O(n)
  For interviews, assume average case unless asked about collisions.

The Two-Sum Pattern

This is the canonical hash map problem and one of the most common interview questions:

Problem: Given an array and a target, find two indices whose
values sum to the target.

Brute force: Check all pairs. O(n^2).

Hash map approach:
  seen = {}   # value -> index

  for i, num in enumerate(arr):
      complement = target - num
      if complement in seen:
          return [seen[complement], i]
      seen[num] = i

Why this works: For each number, we check if we have already
seen the number that would complete the pair. The hash map
turns the "have we seen X?" question from O(n) to O(1).

Time: O(n). Space: O(n).

This pattern — "store what you have seen, check if the complement exists" — appears in dozens of variations.

Frequency Counting

When you need to count occurrences, group elements, or find the most/least common item.

Problem: Find the first non-repeating character in a string.

  count = {}
  for char in s:
      count[char] = count.get(char, 0) + 1

  for char in s:
      if count[char] == 1:
          return char

  return None

Grouping

When you need to group elements by some property.

Problem: Group anagrams from a list of strings.

  groups = {}
  for word in words:
      key = tuple(sorted(word))   # anagrams share the same sorted form
      if key not in groups:
          groups[key] = []
      groups[key].append(word)

  return list(groups.values())

Input:  ["eat", "tea", "tan", "ate", "nat", "bat"]
Output: [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]

Hash Sets

A hash set is a hash map without values. Use it when you only need to check membership.

Problem: Find the intersection of two arrays.

  set1 = set(arr1)
  result = []
  for num in arr2:
      if num in set1:
          result.append(num)
          set1.remove(num)   # avoid duplicates in result

  return result

When to Use Which

Choosing the right structure is a recurring interview decision:

Use an array when:
  - You need ordered data with index access
  - You are doing sliding window or two-pointer operations
  - The problem involves contiguous subarrays
  - Space is constrained and you need to work in-place

Use a hash map when:
  - You need O(1) lookups by key
  - You are counting frequencies
  - You need to check if you have "seen" something before
  - You need to group elements by some property
  - You are caching computed results (memoization)

Use a hash set when:
  - You need O(1) membership checking
  - You need to find duplicates
  - You need intersections or unions of collections

Use a string (as character array) when:
  - The problem involves text manipulation
  - Pattern matching or substring operations
  - Character-level analysis (frequencies, palindromes)

Combined Patterns

Many interview problems combine these structures:

Problem: Find the length of the longest substring without
repeating characters.

Approach: Sliding window + hash set.

  char_set = set()
  left = 0
  max_length = 0

  for right in range(len(s)):
      while s[right] in char_set:
          char_set.remove(s[left])
          left += 1
      char_set.add(s[right])
      max_length = max(max_length, right - left + 1)

  return max_length

This combines a sliding window (two pointers) with a hash set
(checking for repeats in O(1)).

Problem: Given an array, find if any value appears at least twice
within k indices of each other.

Approach: Sliding window + hash set/map.

  window = set()

  for i in range(len(arr)):
      if arr[i] in window:
          return True
      window.add(arr[i])
      if len(window) > k:
          window.remove(arr[i - k])

  return False

Complexity Tradeoffs

Most interview problems involve a tradeoff between time and space:

Approach                Time      Space     Example
─────────────────────────────────────────────────────
Brute force (nested)    O(n^2)    O(1)      Check all pairs
Sort first              O(n logn) O(1)*     Sort + two pointers
Hash map                O(n)      O(n)      Store seen values

* Depending on whether in-place sorting is allowed.

In interviews, the hash map approach is usually preferred because O(n) time is better than O(n log n), and O(n) space is acceptable. But always discuss the tradeoff: "I can do this in O(n) time with O(n) space using a hash map, or O(n log n) time with O(1) space by sorting first. Which would you prefer?" This shows engineering judgment.

Common Pitfalls

  • Forgetting hash map for O(1) lookups: When you find yourself writing a nested loop to "find if X exists," stop. A hash map or set almost certainly solves it in O(n) instead of O(n^2).
  • Off-by-one errors in sliding windows: The window boundaries are the most common source of bugs. Trace through a small example (3-4 elements) before coding.
  • String concatenation in loops: Building a string by concatenation in a loop is O(n^2) in most languages. Use a list of characters and join at the end.
  • Not handling empty input: Arrays can be empty, strings can be empty, hash maps can have no entries. Check for these cases first.
  • Assuming sorted input: Unless the problem states the array is sorted, do not assume it. If your approach requires sorted data, sort it first and account for the O(n log n) cost.
  • Hash map key choice: Choosing the wrong key for a hash map is a subtle bug. For anagram grouping, the key must be something that is the same for all anagrams (sorted characters, frequency tuple). Think carefully about what property you are grouping by.
  • Modifying a collection while iterating: This causes bugs in most languages. If you need to remove elements while iterating, iterate over a copy or collect indices to remove afterward.

Key Takeaways

  • Arrays, strings, and hash maps appear in the majority of coding interview problems. Fluency with these three structures is non-negotiable.
  • The hash map is your most powerful tool. When stuck, ask: "Can I use a hash map to turn an O(n) search into O(1)?" The answer is usually yes.
  • Two pointers and sliding window are the fundamental array patterns. Learn to recognize when a problem is asking for one of these.
  • Frequency counting with a hash map solves a huge class of problems: anagrams, duplicates, most/least frequent elements, and substring problems.
  • Always discuss the time-space tradeoff. Showing that you can identify multiple approaches and reason about tradeoffs is strong interview signal.