15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
Topic 2 of 12 in the free DSA Basics course · 6 lessons
This lesson covers arrays: sequences of values stored in indexed positions. It covers array storage, reading and scanning elements, changing contents while preserving order, preprocessing range information, inspecting fixed-size ranges, and rearranging elements in place.
Each operation is tied to its cost. Count the positions a loop visits, identify when elements shift, and distinguish operations that use extra arrays from those that need only a few variables.
There are no required prerequisites.
You should be comfortable reading numbered positions such as 0, 1, and 2, and following a step-by-step update to a small list of values.
Use A = [4, 1, 7, 3] as the running array. Suppose it has logical length 4 but allocated capacity 5, so one unused position is available at the end.
Its storage positions are:
0 holds 41 holds 12 holds 73 holds 34 is allocated but unusedAn index identifies a position; it is not the value stored there. For example, A[2] reads the value 7.
A forward traversal visits indices 0, 1, 2, and 3. While traversing, you can compute a sum: start at 0, then add 4, 1, 7, and 3 to get 15.
If you insert 9 at index 2, first shift the suffix right:
[4, 1, 7, 3, unused]
[4, 1, 7, 3, 3]
[4, 1, 7, 7, 3]
[4, 1, 9, 7, 3]
The two existing values at and after index 2 move, so the insertion takes more than constant time.
For the original array, prefix sums are [4, 5, 12, 15]. Each prefix position stores the sum from the start through that index. A length-2 window moves through [4, 1], [1, 7], and [7, 3]. Reversing the original array swaps values from the ends inward and produces [3, 7, 1, 4].
Array Memory Allocation establishes the storage model: capacity, logical length, occupied positions, and unused positions. The model determines whether an append fits and explains why an index can address an element.
Indexing and Traversal uses valid indices to read elements one at a time, forward or backward. Later array operations use the same movement pattern.
Insertion & Deletion in Arrays applies traversal in a controlled direction to shift a contiguous suffix right for insertion or left for deletion.
Prefix and Suffix Techniques turns repeated traversals into reusable summaries built from the left or from the right.
Sliding Window Basics uses a moving contiguous region. A running value updates as one element leaves and another enters instead of recomputing the whole window.
Array Reversal and Rotation combines indices, traversal boundaries, and swaps to transform array order without requiring a second full array.
Array work starts with storage because every operation uses positions. Before reading A[2], index 2 must refer to a valid occupied location. Before appending, distinguish length from capacity.
Traversal visits each logical element once. A full scan of an array of length n performs about n reads, so it takes linear time, O(n). A sum, maximum, or reverse scan uses this pattern.
Insertion and deletion add element movement. To insert at index i, values from the end through i move right. To delete at i, values after i move left. The work is proportional to the number of shifted elements. Operations at the end may require no shifts, while operations near the front can shift nearly the whole array.
Prefix and suffix techniques use scans to prepare answers for later questions. Building a prefix-sum array takes one left-to-right pass and extra storage proportional to the array length. When several range sums are needed, each valid inclusive range can be answered from a small number of prefix values after preprocessing.
Sliding windows use contiguous positions and often avoid storing a full summary array. For a fixed window size, keep its current sum. When the window moves right by one position, subtract the outgoing value and add the incoming value. The scan remains linear overall, while the auxiliary space can stay constant.
Reversal and rotation use index boundaries. Reversal uses two indices, one at each end, and swaps until they meet. Rotation can be completed through three reversals of contiguous segments. The transformations visit array elements a constant number of times and use only a few temporary variables, giving O(n) time and O(1) auxiliary space.
Draw a fixed-capacity array with capacity 5 and length 4. Mark which positions are occupied and which are unused. Decide whether one append fits.
For A = [4, 1, 7, 3], write the values read at indices 0 through 3, then trace a forward sum and a reverse traversal.
Insert 9 at index 2 in an array with one free capacity slot. Then delete the value at index 1. Write every shift, not only the final result.
Build prefix sums and suffix sums for A. Use the prefix sums to find the inclusive sum from index 1 through index 3.
List all windows of size 2 and size 3. For each size, trace the running sum as the window moves, naming the outgoing and incoming values.
Reverse A using swaps between the left and right indices. Then choose a nonnegative right-rotation count, reduce it using the array length, and trace the three reversals used for rotation.