Arrays & Strings Explained: Memory, Indexing & In-Place Tricks

Think of a cinema hall. Your ticket says J-14. You walk straight to row J, seat 14 — you never check seats J-1 to J-13 on the way. Why could you do that?

Because the seats are numbered AND placed side by side, in order. Now imagine the same 300 people seated randomly across a park, each person holding a chit that says where the next person sits. Finding person 14 now means visiting 13 people first.

Same people. Completely different cost to reach one of them. The cinema hall is an array. The park is a linked list — that's next lesson. Everything an array does brilliantly, and everything it does badly, follows from that one physical fact: the seats are adjacent.

What an array really is in memory

An array is a block of contiguous memory: element 0, then element 1 immediately after it, then element 2, each slot the same size. No gaps, no jumping around. That's the whole definition — and it's enough to derive everything else in this lesson.

Why is arr[4] instant? Let's see the actual step

Student question: when I write arr[4], does the computer walk past elements 0 to 3?

No — and this is the array's superpower. Because the slots are adjacent and equal-sized, the computer can calculate where element 4 lives:

# what arr[4] does internally:
address_of_item_4 = start_address + 4 * size_of_each_item
# one multiply, one add, one read.
# 10 items or 10 crore items - same three steps.

No walking, no searching — an address is computed the way you find seat J-14. That is why indexing is O(1), and why no other basic structure can match arrays at it. (Bonus, for later: CPU caches load neighbouring memory together, so scanning an array is even faster in practice than the step count suggests.)

The catch: what does adjacency cost us?

Nothing is free in DSA, so let's go looking for the bill. Suppose marks = [10, 20, 30, 40] and a new student joins whose mark must go at the front.

Pause for a second — where will the new value physically go? Slot 0 is occupied. Slot -1 doesn't exist. The array has no gaps by definition...

There is only one way: every element must shift one slot to the right to make room. Watch it happen:

Four elements, four moves. One crore elements? One crore moves — O(n) for a single insert at the front. The same adjacency that made reading instant makes front-insertion expensive. Deleting from the front is the mirror image: everything shifts left.

Inserting at the end, though, touches nobody — nothing needs to move. Keep that asymmetry in mind; it decides more real-world choices than any other fact in this lesson.

The full cost table

Read the table as a personality, not a list: arrays love reading and appending; they hate front-editing. A workload that constantly inserts and removes at the front is begging for a different structure — exactly the kind of matching we'll practise in lesson 12.

But Python lists grow — how?

Student question: an array is a fixed block of memory, yet I can append to a Python list forever. Who is lying?

Nobody — the list cheats gracefully. It secretly keeps some spare capacity at the end. Appends drop into the spare slots: O(1), nothing moves. When the spare runs out, the list allocates a bigger block — roughly double — and copies everything across. That one append costs O(n). See the capacity jumps yourself:

import sys

lst = []
last = sys.getsizeof(lst)
for i in range(20):
    lst.append(i)
    size = sys.getsizeof(lst)
    if size != last:                 # capacity just jumped
        print(f"len={len(lst):>3}  bytes={size}")
        last = size

len=  1  bytes=88
len=  5  bytes=120
len=  9  bytes=184
len= 17  bytes=248

But why double? Why not just add 10 slots each time? Good instinct — let's test it. With grow-by-10, a copy happens every 10 appends, and each copy re-moves everything: for n appends that's roughly n²/10 total work. With doubling, copies happen only at sizes 1, 2, 4, 8, ..., n — and the total copying across ALL n appends adds up to about 2n. Spread 2n work over n appends and each one averages O(1). That averaged figure has a name you met in lesson 1's FAQ: amortised O(1). Doubling makes the expensive event exponentially rare — that's the entire trick.

Strings: arrays with one twist

A string is an array of characters — same O(1) indexing, same O(n) scanning. The twist in Python (and Java): strings are immutable. You never edit a string; you can only build a new one.

That sounds like trivia until you meet this innocent loop. Predict its cost before reading on:

s = ""
for ch in data:        # n characters
    s = s + ch         # looks harmless...

Here's the trap. Since strings can't be extended in place, every s + ch builds a brand-new string, copying everything built so far: 1 copy, then 2, then 3, ... then n. Total: 1 + 2 + ... + n ≈ n²/2 character copies — O(n²) from a loop that looks O(n). For a 10-lakh character file, that's ~5 × 10¹¹ copies. The fix is a one-line idiom:

parts = []
for ch in data:
    parts.append(ch)   # amortised O(1) each - lists CAN extend
s = "".join(parts)     # one final O(n) pass

Collect in a list, join once: O(n) total. The same trap exists in Java (String + in a loop → use StringBuilder).

🎯 Selection-round radar: "this function is slow at scale — why?" code-review questions are very often string concatenation in a loop. Spotting it instantly, and saying why (immutability forces a full copy per +), is a reliably reported win at TCS, Infosys and product companies alike.

In-place tricks: the two-pointer swap

Suppose you must reverse an array of 1 crore elements on a memory-tight server. arr[::-1] gives a reversed copy — a second crore of elements. Not allowed. What would you do with zero extra memory?

Think physically: the first and last elements just need to trade places. Then the second and second-last. Keep walking inward until the two fingers meet:

def reverse(arr):
    left = 0                   # left finger
    right = len(arr) - 1       # right finger
    while left < right:        # stop when the fingers meet
        arr[left], arr[right] = arr[right], arr[left]
        left += 1
        right -= 1
    return arr

Dry run on a tiny input — follow it with a pen:

[10, 20, 30, 40, 50]     left=0, right=4
 L               R       swap 10,50
[50, 20, 30, 40, 10]     left=1, right=3
     L       R           swap 20,40
[50, 40, 30, 20, 10]     left=2, right=2 -> fingers met, stop

n/2 swaps, two integer variables: O(n) time, O(1) extra space. This "two fingers moving toward each other" shape is one of the most reused moves in all of DSA — it reverses, it checks palindromes, it finds pairs in sorted arrays, and it gets a full lesson in the Algorithms course (two pointers & sliding window). Its flashiest cousin — rotating an array using three reversals — is waiting for you in the Practice Zone with a full trace.

What if...?

What if I reverse an empty array, or one element? Check the loop condition: left < right is false immediately (0 < −1? 0 < 0?), so nothing happens — correct by design. Always run your loop condition on the tiny cases in your head; well-written conditions handle them for free.

What if I slice — arr[1:], arr[::-1], sorted(arr)? Each of these silently builds a full O(n) copy. They aren't wrong — sorted() is often exactly right — but claiming "O(1) space" while slicing is the mistake. Say which you chose: "I'll slice for clarity, costing O(n) space" or "I'll swap in place to keep O(1)".

What if I delete elements from a list while looping over it? Elements shift left underneath your loop index and items get skipped silently. Loop over a copy, or build a new list with the survivors.

What if the rotation amount k is bigger than the array? Rotating 7 elements by 10 is the same as rotating by 3 — take k %= n first. Forgetting this crashes rotation code on a favourite hidden test case.

Common mistakes

• Building strings with + in a loop — O(n²); collect parts and join.
• Using lst.insert(0, x) or lst.pop(0) in hot code — each one is O(n); a deque (lesson 4) does both ends in O(1).
• Claiming O(1) space while slicing — every slice is a copy.
• Forgetting k %= n in rotation problems.
• Mutating a list while iterating over it.
• Forgetting that arr.sort() changes the caller's list — use sorted(arr) when the original must survive.

How do I recognise array problems?

Clues that this lesson's tools are the right ones:

• "in place" / "O(1) extra space" — the two-pointer swap family, or the read/write pointer pattern (move zeroes, remove duplicates).
• "reverse" / "rotate" — in-place reversal, and the three-reversal rotation trick.
• index-heavy access ("the i-th element", "position k") — arrays are home ground; a linked list would pay O(n) per access.
• a string being "edited" repeatedly — immutability alarm: collect-and-join.

And the counter-clue: constant insertion/removal at the front or middle → arrays are the wrong tool; keep reading this course.

Quick revision

One thing to remember

An array trades flexibility for adjacency: reaching any seat is instant, but making room in the middle means everyone shifts. Every array question — and half the structures in this course — is a response to one side of that trade.

Practice Zone — PYQs from real selection rounds

Six MCQs, then three classics: second largest in one pass, move zeroes in place, and the three-reversal rotation — each with a full trace in the solution.

Q1Arrayseasy

Why is reading arr[7] O(1) regardless of the array's size?

Asked in

aThe computer searches very fastbArrays are contiguous, so the address is computed directly: start + 7 × element_sizecThe first 10 elements are cacheddIt is not O(1); it is O(n)

Q2Arrayseasy

Inserting a new element at the FRONT of an array of n elements costs:

Asked in

aO(1) — the front is easy to reachbO(n) — every existing element must shift one position rightcO(log n)dO(n²)

Q3Dynamic arraysmedium

A Python list grows automatically when it runs out of room. Why is append still called O(1)?

Asked in

aGrowing never actually happensbThe list doubles its capacity when full, so expensive copies are rare and average out — amortised O(1)cPython lists are linked lists internallydAppend is actually O(n) and the docs are wrong

Q4Stringsmedium

In Python, s = s + "x" inside a loop that runs n times is O(n²) overall. Why?

Asked in

aString concatenation is slow because of UnicodebStrings are immutable — each + builds a brand-new string, copying everything so farcThe loop itself is O(n²)dIt is actually O(n); the question is wrong

Q5Arraysmedium

You need to reverse an array of 1 crore elements on a memory-tight server. The right approach is:

Asked in

aBuild a new reversed copy with slicingbSwap arr[left] and arr[right], moving both pointers inward until they meet — in place, O(1) extra spacecSort the array in descending orderdConvert to a linked list first

Q6Arrayshard

arr = [10, 20, 30, 40, 50, 60, 70] rotated LEFT by 3 becomes:

Asked in

a[50, 60, 70, 10, 20, 30, 40]b[40, 50, 60, 70, 10, 20, 30]c[70, 60, 50, 10, 20, 30, 40]d[30, 20, 10, 40, 50, 60, 70]

Hands-on tasks:

FAQ

You now know what adjacency buys and what it costs. Next: give up adjacency completely and see what the park full of chits is actually good at — Lesson 3: Linked Lists →