Free lesson · DSA Mastery - Interview Prep, End to End
Array Manipulation - Introduction
Array Manipulation Introduction
Arrays are the most fundamental data structure in computer science, and they are by far the most common topic in coding interviews. Before we dive into specific problems, this section gives you the mental model for how arrays work, what operations are cheap and what is expensive, and the patterns that show up repeatedly in array problems.
If you can recognize these patterns quickly during an interview, you will solve most array problems faster and with less stress. This chapter is the foundation.
What Is an Array?
An array is a contiguous block of memory holding elements of the same type, accessed by index. The contiguity is the key property - every element sits next to its neighbors in memory, which gives arrays their performance characteristics.
graph LR
A["arr[0]<br/>5"] --- B["arr[1]<br/>2"]
B --- C["arr[2]<br/>8"]
C --- D["arr[3]<br/>1"]
D --- E["arr[4]<br/>9"]
E --- F["arr[5]<br/>3"]
style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
style B fill:#4338ca,stroke:#6366f1,color:#f1f5f9
style C fill:#4338ca,stroke:#6366f1,color:#f1f5f9
style D fill:#4338ca,stroke:#6366f1,color:#f1f5f9
style E fill:#4338ca,stroke:#6366f1,color:#f1f5f9
style F fill:#4338ca,stroke:#6366f1,color:#f1f5f9
This diagram shows a six-element array with indices zero through five, holding the values five, two, eight, one, nine, and three. The elements sit in contiguous memory, accessed by index.
The contiguity gives us:
- O(1) random access. Given an index, we can compute the memory address (base + index × element size) and read the value in constant time.
- Cache-friendly traversal. Walking through an array hits sequential memory addresses, which is exactly what CPU caches are optimized for.
The contiguity costs us:
- O(n) insertion in the middle. To insert at position k, we have to shift every element from k onwards one position to the right.
- O(n) deletion in the middle. Same shift, in reverse.
- Fixed size in some languages. Java arrays are fixed-size at allocation;
ArrayListand similar wrappers add dynamic resizing on top.
Interactive animation: Inserting in the middle: every element from index k on shifts right before the new value fits.
Common Operations and Their Costs
| Operation | Time Complexity | Notes |
|---|---|---|
| Access by index | O(1) | The defining property of arrays |
| Update by index | O(1) | Same |
| Search by value (unsorted) | O(n) | Have to scan |
| Search by value (sorted) | O(log n) | Binary search |
| Insert at end | O(1) amortized | If dynamic array has spare capacity |
| Insert at start | O(n) | Shift everything right |
| Insert in middle | O(n) | Shift the tail right |
| Delete at end | O(1) | Just decrement size |
| Delete at start | O(n) | Shift everything left |
| Delete in middle | O(n) | Shift the tail left |
The asymmetry between "end" and "middle/start" is important. If your problem allows you to operate only at the end (or only at a known index), the array is cheap. If your problem requires inserting and deleting at arbitrary positions, you might want a different data structure (linked list, deque).
Interactive animation: Insert and delete cost O(1) at the end and O(n) at the start or in the middle.
Common Patterns in Array Problems
Most array problems fall into one of a few patterns. Learning to recognize them is half the battle.
Pattern 1: Two Pointers
Use two indices that move through the array together. The most common variants:
- Same direction, different speeds. One pointer reads, another writes. Used in problems like Move Zeroes, Remove Element, Remove Duplicates.
- From both ends, moving inward. Used in palindrome checks, two-sum on sorted arrays, container-with-most-water style problems.
- Same direction, same speed, fixed offset. Used in sliding-window problems (covered in Section 12).
Two pointers usually turn O(n²) brute-force solutions into O(n) optimal solutions. They are the single most useful technique in array problems.
Interactive animation: The three ways two pointers move: read and write, from both ends, and a fixed-width window.
Pattern 2: In-Place Modification
Many problems require modifying the array without using extra space. The key trick: write to positions you have already read from. Once you have read arr[i], you can overwrite arr[j] for any j <= i without losing information.
Interactive animation: Overwriting is safe only at positions the read pointer has already passed.
Pattern 3: Prefix Sums / Running Computations
When a problem asks about sums or aggregates over ranges, computing a prefix sum array once lets you answer range-sum queries in O(1). Prefix sums get their own section later - but the pattern shows up here too.
Pattern 4: Sorting as a Tool
Many array problems become trivial after sorting. The classic example: "find duplicates" becomes a linear scan after sorting. Sorting costs O(n log n), but if the rest of your algorithm is O(n), the sort dominates and the total is O(n log n) - often better than the brute-force O(n²) alternative.
Pattern 5: Hash Map Lookup
When a problem requires checking "have I seen this value before?" or "where did I see this value?", a hash map gives you O(1) lookup. Trades O(n) extra space for O(1) per query. Used in Two Sum, Majority Element, and many others.
What Makes Array Problems Interview-Friendly
Interviewers love array problems for several reasons:
- Easy to state. "Given an array, find X." No esoteric data structures or domain knowledge required.
- Multiple optimization levels. A brute-force O(n²) solution often exists, but a clever O(n) solution also exists. This lets the interviewer see how you think about optimization.
- Edge cases are tractable. Empty arrays, single-element arrays, arrays with all duplicates - easy to enumerate.
- Tests fundamental coding skills. Loops, indexing, mutation, edge handling. The bread and butter of any engineer.
Array problems are usually the warm-up in coding interviews. If you cannot solve them quickly and cleanly, the interviewer never gets to the harder problems. Mastering this section is essential.
What This Module Covers
Interactive animation: The eighteen problems of Module 6, grouped by the pattern each group teaches.
The 18 problem topics in Module 6 are organized by pattern:
- Array Manipulation (5 topics): Move Zeroes, Remove Element, Shuffle the Array, Remove Duplicates (basic and II), Rotate Array. These teach in-place modification using two pointers.
- Finding and Counting (5 topics): Max Consecutive Ones, Third Maximum, Missing Ranges, Majority Element (basic and II). These teach scanning patterns and Boyer-Moore voting.
- Stock Problems (2 topics): Best Time to Buy and Sell Stock (basic and II). These teach the "single pass with running state" pattern.
- Subarrays and Subsequences (2 topics): Number of Zero-Filled Subarrays, Increasing Triplet Subsequence. These teach counting and three-pointer techniques.
- Advanced Techniques (3 topics): Product of Array Except Self, Next Permutation, First Missing Positive. These are the "trickier than they look" problems that show up in senior interviews.
By the end of this module, you will have seen the major patterns and be ready to apply them to any new array problem you encounter. The pattern recognition you build here carries forward into Strings (Section 7), Two Pointers (Section 10), Sliding Window (Section 12), and beyond.
A Note on the Format
Each topic from here on follows a consistent structure: problem statement, approach, code, walkthrough, complexity, and variations. The walkthroughs trace concrete inputs step-by-step so you can see exactly what the algorithm does. The complexity sections explain why the bounds are what they are - not just the Big O notation, but the reasoning behind it.
Code is in Java by default. The algorithms translate directly to Python, C++, JavaScript, and TypeScript with minor syntax changes.
Let's start with the first problem: Move Zeroes.