Skip to content
Tutorials Center
My learning

Topics

Lesson 44 of 77 ยท CS Fundamentals Interview Questions

Array and String Patterns

Learn the four array and string patterns behind most interview problems: two pointers, sliding window, prefix sums and hash-map counting, with Python.

Hundreds of array and string problems reduce to a handful of patterns. If you can recognize the pattern from the wording of the question, the code nearly writes itself, and the brute force that costs O(nยฒ) becomes O(n). This lesson teaches four patterns, the clue that signals each one, and a runnable example for each.

Background: Two pointers, Sliding window, Prefix sums and Hashing patterns.

Spot the pattern

Two pointers Sorted input or a pair.
Sliding window Contiguous subarray or substring.
Prefix sums Many range-sum queries.
Hash map Counting or "seen before?".
1 / 2

Two pointers

Clue: the input is sorted, or you need a pair, or you work from both ends (palindromes, reversing). Put one pointer at each end and move them toward each other based on a comparison. Each step discards at least one element, so the scan is O(n) time and O(1) space.

Q: In a sorted list, find two numbers that sum to a target. If the sum is too small, move the left pointer right to get a bigger number. If it is too large, move the right pointer left.

Python Pair sum and palindrome with two pointers

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The sorted requirement matters. If the list is unsorted, either sort first (O(n log n)) or use a hash map as in Python: Classic Coding Questions.

Sliding window

Clue: "longest", "shortest" or "maximum" over a contiguous subarray or substring. Keep a window [left, right], grow it by moving right, and shrink it from left when it breaks a rule. Every index enters and leaves the window at most once, so it is O(n) even though there is a loop inside a loop.

Q: Longest substring without repeating characters. Track the last index where each character was seen. When a repeat appears inside the window, jump left just past the earlier copy.

Python Longest substring without repeats, and a fixed window

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The second function shows the fixed-size variant: add the new element and subtract the one that left, instead of re-summing k numbers every time.

Prefix sums

Clue: many queries for the sum of a range, or "subarray with sum equal to k". Precompute prefix[i], the sum of the first i items. Then the sum of items from index a up to b (inclusive) is prefix[b + 1] - prefix[a]. Preprocessing is O(n); each query is O(1).

Q: Count subarrays whose sum equals k. Combine prefix sums with a hash map. A subarray ending here sums to k if some earlier prefix equals current - k. Count how many times each prefix value has occurred. Start with {0: 1} so subarrays that begin at index 0 are counted. This also works with negative numbers, where a sliding window does not.

Python Range sums and subarray-sum counting

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Hash-map counting

Clue: "how many times", "first repeated", "are these the same multiset", "group by". A dictionary or Counter turns a nested search into one pass. The pattern has two moves: count first, then look up; or look up as you go and insert afterward.

Q: Find the first non-repeating character, and check whether a ransom note can be built from a magazine. For the note, count the magazine letters and spend one for every letter in the note.

Python Counting with Counter

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Choosing the right pattern

If the problem sounds like it needs two nested loops over the same array, ask which of these removes one loop. Sorted or palindrome: two pointers. Contiguous and optimizing a length: window. Repeated range sums: prefix sums. Counting or membership: hash map. Always state the complexity after the code, and test an empty input and a single element.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which pattern fits "longest substring with at most two distinct characters"?

    The answer is a contiguous substring whose validity can be maintained while the window grows and shrinks.
  2. 2. After building prefix with a leading 0, how do you get the sum of nums[a..b] inclusive?

    prefix[b + 1] holds the sum of items 0..b; subtracting the sum of items before a leaves a..b.
  3. 3. Why does the sliding window solution run in O(n) despite having a loop inside a loop?

    Total pointer movement is at most 2n, so the work adds up linearly.
  4. 4. Why start the prefix-count dictionary with {0: 1} when counting subarrays that sum to k?

    An empty prefix has sum 0; without it, a subarray from the start would find no matching earlier prefix.

Summary

  • Two pointers: sorted input, pairs and palindromes, O(n) with O(1) space.
  • Sliding window: contiguous subarrays and substrings; grow right, shrink left.
  • Prefix sums: O(1) range sums after O(n) setup; pair with a hash map to count subarrays.
  • Hash-map counting: replace a nested search with one pass.
  • Name the pattern, state the complexity, test edge cases.

Next: Trees and Graphs Questions.