Algorithms
Iteration Patterns on Arrays/Strings
Difficulty: Beginner
Look at almost any solved interview problem and you will see the same six or seven shapes of for loop reappearing: a single sweep that finds a max, a nested pair that compares every element to every other, a single sweep that fills a...
Iteration Patterns on Arrays/Strings
Look at almost any solved interview problem and you will see the same six or seven shapes of for loop reappearing: a single sweep that finds a max, a nested pair that compares every element to every other, a single sweep that fills a frequency table. Before you can recognize when two pointers or sliding window will help, you have to recognize these primitive shapes on sight.
Iteration Patterns on Arrays/Strings catalogs those shapes. You will work through single-pass templates (running sum, find max/min, counting), nested-loop templates that consider all pairs in O(n^2) time, frequency counting with a hash map, early termination with break, sentinel values, and the choice between in-place modification and building a new array. Classic transformations like reverse, rotate, and partition appear as named patterns rather than puzzles solved from scratch each time.
In Arrays & Strings, you saw that arrays give you constant-time indexed access and contiguous memory. This lesson turns that storage model into actual movement: how an index walks across an array, what it costs, and when one walk is enough.
Next you will use these patterns directly in Prefix Sum & Difference Array, where a single preprocessing pass replaces many later range-sum loops.
Prerequisites:
Arrays & StringsTopics:
What You'll Learn
By the end of this lesson, you will be able to:
Implement single-pass patterns (find max/min, running sum, counting) to solve problems in O(n).
Write nested-loop patterns (all pairs, brute-force substring search) and explain their O(n^2) complexity.
Use a hash map for frequency counting and element lookups.
Apply early termination and sentinel values to optimize iterations.
Distinguish in-place modification from creating a new array and choose the appropriate approach.
Implement common array transformations: reverse, rotate, and partition.
Why This Matters
01
Iteration patterns are the foundation of every array and string algorithm. You cannot solve problems efficiently until you can iterate correctly and recognize which pattern fits.
02
Understanding when a single pass suffices versus when nested loops are needed is the first step toward algorithmic efficiency.
03
These patterns appear in over 80% of coding interview problems — mastering them gives you a reliable starting point for any array or string question.
04
Recognizing iteration patterns helps you quickly estimate time complexity and decide whether a brute-force approach is acceptable or a more advanced technique is required.
Key Terms
8 terms you'll encounter in this lesson
Single pass
Iterating through an array exactly once from start to end, processing each element as you go. Time complexity: O(n).
Nested loop
A loop inside another loop that typically examines all pairs of elements. Time complexity: O(n^2) for two nested loops over the same array.
Frequency map
A hash map (dictionary) that stores how many times each element appears in a collection. Also called a frequency counter or histogram.
Early termination
Exiting a loop as soon as a condition is met (using break or return), avoiding unnecessary iterations.
Sentinel value
A special value placed at the end of a data structure to eliminate boundary checks inside a loop, simplifying the code.
In-place modification
Changing an array's contents without allocating a new array. Uses O(1) extra space but mutates the original data.
Accumulator pattern
Maintaining a running result (sum, product, max, etc.) that is updated as you iterate through the array.
Partition
Rearranging array elements so that all elements satisfying a condition come before those that do not.
Related Problems
Coding problems that put this lesson's concepts into practice
Heads Up
Common misconceptions to watch out for
"Nested loops always mean bad code"
Nested loops are O(n^2), which is fine for small inputs (n < 1000). Many problems have no better solution than O(n^2). The key is recognizing when a nested loop is necessary versus when a single pass with a hash map can do the same job in O(n).
"Frequency counting requires sorting first"
A hash map counts frequencies in O(n) without sorting. Sorting first would cost O(n log n) and is unnecessary for frequency counting.
"In-place modification is always better because it uses less memory"
In-place modification saves space but mutates the original data. If you need the original array later (or if the array is shared/immutable), creating a new array is the safer choice.
"A for loop and a while loop have different performance"
for and while loops compile to the same machine instructions. The difference is readability and when you know the number of iterations in advance (for) versus when you do not (while).