Arrays & Strings — TechForge

01How Arrays Live in Memory

An array is a block of contiguous memory cells, each the same size. When you write arr[i], the CPU computes base_address + i × element_size — a single arithmetic step. That is why access is O(1) regardless of array length.

0x100

10

[0]

0x104

20

[1]

0x108

30

[2]

0x10C

40

[3]

0x110

50

[4]

0x114

60

[5]

0x118

70

[6]

Each cell is 4 bytes apart (32-bit int). Address of arr[i] = 0x100 + i×4.

Why this matters for interviews: Interviewers love to ask "why is array access O(1) but search O(n)?" The answer — you can calculate any address directly, but finding a value requires checking each element one by one.

Python lists vs C arrays: Python's list is a dynamic array of pointers. Access is still O(1) (pointer lookup), but elements can be different types and sizes because the list stores pointers, not the values directly.

02Interactive Operations

// ARRAY OPERATIONS

Enter a value and index, then choose an operation.

Operations

Python Code

Quiz

01

Access by Index

O(1) — The CPU computes the address directly: base + i × size. No looping, no scanning. Instant, always.

x = arr[i] # constant time regardless of array size

02

Linear Search

O(n) worst case — scan left to right until found (or not). Best case O(1) if target is the first element.

for x in arr: if x == target: return

03

Append (end)

O(1) amortized — Python pre-allocates extra capacity. Occasional O(n) resizes are rare enough that the long-run average is O(1).

arr.append(x) # O(1) amortized

04

Insert at Index i

O(n) — all elements from index i onward must shift one position right. Inserting at index 0 is the worst case — shifts every element.

arr.insert(i, x) # shifts (n - i) elements right

05

Delete at Index i

O(n) — all elements after index i shift left to fill the gap. Deleting index 0 is worst case; deleting the last element is O(1).

arr.pop(i) # shifts (n - i - 1) elements left

06

Slice

O(k) — creates a new list of k elements. A common pitfall: arr[:] copies the entire array in O(n) time and space.

sub = arr[l:r] # O(r - l) time + space

python

# ── Creating arrays ──────────────────────────
arr = [10, 20, 30, 40, 50]
arr = list(range(1, 6))         # [1, 2, 3, 4, 5]
arr = [0] * 5                   # [0, 0, 0, 0, 0] — fixed-size init
matrix = [[0]*3 for _ in range(3)]  # 3×3 2D array

# ── Access & slicing ─────────────────────────
x    = arr[2]       # O(1) → 30
last = arr[-1]      # O(1) → 50  (negative indexing)
sub  = arr[1:4]     # O(k) → [20, 30, 40]  creates a copy!
rev  = arr[::-1]    # O(n) → [50, 40, 30, 20, 10]

# ── Mutations ────────────────────────────────
arr.append(60)      # O(1) amortized
arr.insert(0, 5)    # O(n) — prepend, shifts all!
arr.pop()           # O(1) — remove last
arr.pop(2)          # O(n) — remove at index
arr.remove(30)      # O(n) — remove first occurrence of value

# ── Searching & sorting ──────────────────────
idx = arr.index(40) # O(n) linear scan
arr.sort()          # O(n log n) Timsort, in-place
arr.sort(key=lambda x: -x)  # descending

# ── Useful built-ins ─────────────────────────
n       = len(arr)  # O(1) — cached
present = 30 in arr # O(n) — use set for O(1)
s_arr   = set(arr)  # O(n) build, then O(1) lookup

# ── Comprehensions ───────────────────────────
squares = [x**2 for x in arr]              # O(n)
evens   = [x for x in arr if x % 2 == 0]  # O(n)
flat    = [x for row in matrix for x in row]  # flatten

Q1 — Why is arr.insert(0, x) slower than arr.append(x)?

Q2 — What is the time complexity of arr[i:j]?

Q3 — You need to check if a value exists in a list 10,000 times. Best approach?

03Strings in Python

In Python, strings are immutable sequences of characters. Every "modification" creates a new string object. This is one of the most common sources of hidden O(n²) bugs in interview submissions.

Critical interview trap — string concatenation in a loop:

result = ""
for char in s:
    result += char  # Creates a brand new string every iteration → O(n²)!

Fix: collect into a list, then "".join(chars) at the end — O(n) total.

python

# Strings are immutable
s = "hello"
s[0] = "H"       # ✗ TypeError — cannot modify in place

# ── Common operations ────────────────────────
s.lower()        # "hello" — O(n)
s.upper()        # "HELLO" — O(n)
s.strip()        # trim whitespace — O(n)
s.split(", ")    # split into list — O(n)
", ".join(lst)   # list → string — O(total chars)
s.replace("l","x")  # O(n) — new string
s[::-1]          # reverse — O(n)
len(s)           # O(1) — cached by Python

# ── Efficient string building ────────────────
def build_string(s):
    chars = []
    for ch in s:
        chars.append(ch.upper())  # O(1) per append
    return "".join(chars)       # single O(n) join — correct!

# ── Two-pointer palindrome check ─────────────
def is_palindrome(s):
    l, r = 0, len(s) - 1
    while l < r:
        if s[l] != s[r]: return False
        l += 1; r -= 1
    return True  # O(n) time, O(1) space

04Essential Interview Patterns

Most array and string interview problems reduce to one of these four patterns. Recognise the pattern → apply the template → optimise.

01

Two Pointers

O(n) · O(1)

Use two indices — l and r — that move toward each other or in the same direction. Eliminates nested loops. Best on sorted arrays or when looking for a pair satisfying some condition.

def two_sum_sorted(arr, target):
    l, r = 0, len(arr) - 1
    while l < r:
        s = arr[l] + arr[r]
        if s == target: return [l, r]
        elif s < target: l += 1
        else: r -= 1
# Use for: Two Sum II, 3Sum, Container With Most Water, Valid Palindrome

02

Sliding Window

O(n) · O(1–k)

Maintain a window [l, r] that expands right and contracts left. Instead of recalculating the window each step, add the new element entering and remove the element leaving. Use for subarray or substring problems with a constraint.

def max_sum_subarray(arr, k):
    window = sum(arr[:k]); best = window
    for i in range(k, len(arr)):
        window += arr[i] - arr[i-k] # slide: add new, drop old
        best = max(best, window)
    return best
# Use for: Longest Substring, Min Window Substring, Max Sum Subarray

03

Prefix Sums

O(n) build · O(1) query

Pre-compute cumulative sums so any subarray sum query sum(arr[l:r]) answers in O(1). The key identity: sum[l:r] = prefix[r] - prefix[l].

prefix = [0] * (len(arr) + 1)
for i, x in enumerate(arr):
prefix[i+1] = prefix[i] + x

# sum(arr[l:r]) = prefix[r] - prefix[l] → O(1) per query
# Use for: Product of Array Except Self, Range Sum Query, Subarray Sum = K

04

Kadane's Algorithm

O(n) · O(1)

At each position: extend the current subarray, or start fresh? Key insight — if the running sum goes negative, it can only hurt future subarrays. Reset to 0 and start over.

def max_subarray(arr):
    curr = best = arr[0]
    for x in arr[1:]:
        curr = max(x, curr + x) # extend or restart?
        best = max(best, curr)
    return best
# Use for: Maximum Subarray, Maximum Product Subarray, Best Time to Buy/Sell

05Complexity Reference

          
            OperationTimeSpaceNotes

            arr[i]O(1)O(1)Direct address calculation
arr.append(x)O(1)*O(1)Amortized — occasional O(n) resize
arr.pop() — lastO(1)O(1)No shifting needed
arr.insert(i, x)O(n)O(1)Shifts n–i elements right
arr.pop(i) — at iO(n)O(1)Shifts n–i–1 elements left
x in arrO(n)O(1)Linear scan; convert to set for O(1)
arr[l:r] sliceO(k)O(k)k = r–l; creates a new list
arr.sort()O(n log n)O(n)Timsort; stable, in-place
len(arr)O(1)O(1)Cached by the list object
min / maxO(n)O(1)Full linear scan required
a + b concatO(n+m)O(n+m)Creates a brand new list
arr.extend(b)O(k)O(1)k = len(b); faster than + for merging

          
        

Operation	Time	Space	Notes
`arr[i]`	O(1)	O(1)	Direct address calculation
`arr.append(x)`	O(1)*	O(1)	Amortized — occasional O(n) resize
`arr.pop()` — last	O(1)	O(1)	No shifting needed
`arr.insert(i, x)`	O(n)	O(1)	Shifts n–i elements right
`arr.pop(i)` — at i	O(n)	O(1)	Shifts n–i–1 elements left
`x in arr`	O(n)	O(1)	Linear scan; convert to set for O(1)
`arr[l:r]` slice	O(k)	O(k)	k = r–l; creates a new list
`arr.sort()`	O(n log n)	O(n)	Timsort; stable, in-place
`len(arr)`	O(1)	O(1)	Cached by the list object
`min / max`	O(n)	O(1)	Full linear scan required
`a + b` concat	O(n+m)	O(n+m)	Creates a brand new list
`arr.extend(b)`	O(k)	O(1)	k = len(b); faster than + for merging

O(1)

Index Access

Arrays' superpower — direct address math

O(1)*

Append

Amortized — rare resizes balance out

O(n)

Insert / Delete

Shifting is the price of contiguity

O(n log n)

Sort

Timsort — best-in-class for real-world data

06Real-World Applications

Image Processing

Images are 2D (or 3D) arrays of pixel values. Filters, crops, and transforms all operate using sliding window patterns on these arrays.

2D ARRAY

Stock Price Analysis

Time-series data lives in arrays. Sliding window finds max profit windows; prefix sums compute moving averages in O(1) per query.

SLIDING WINDOW

Search Engines

Inverted indices map terms to arrays of document IDs. Intersecting two sorted arrays with two-pointers finds docs matching multiple terms.

TWO POINTERS

DNA Sequencing

DNA is a string of characters (A, T, G, C). Finding repeated patterns, longest common subsequences, and mutations all use string algorithms.

STRING PATTERNS

Game State Boards

Chess, Go, and Sudoku boards are 2D arrays. Efficient state-checking uses direct index access — O(1) per cell read or write.

2D GRID

Database Aggregation

SQL aggregations (SUM, AVG) over column ranges use prefix sum techniques for O(1) window queries rather than re-scanning the whole table.

PREFIX SUMS

07Practice Problems

Your Progress 0 / 26 solved

26 problems · 18 PBC · 8 Startup

#001 Two SumEasy Google · Amazon PBC→

#002 Best Time to Buy and Sell StockEasy Apple · Amazon PBC→

#003 Maximum Subarray (Kadane's)Medium Meta · Amazon PBC→

#004 Product of Array Except SelfMedium Adobe · Meta PBC→

#005 Maximum Product SubarrayMedium Amazon · Google PBC→

#006 Search in Rotated Sorted ArrayMedium Google · Microsoft PBC→

#007 3SumMedium Amazon · Adobe PBC→

#008 Trapping Rain WaterHard Google · Anthropic PBC→

#009 Merge IntervalsMedium Amazon · Google PBC→

#010 Container With Most WaterMedium Google · Meta PBC→

#011 Find Minimum in Rotated Sorted ArrayMedium Microsoft · Google PBC→

#012 Subarray Sum Equals KMedium Meta · Amazon PBC→

#013 Rotate ArrayMedium Stripe · Airbnb STARTUP→

#014 Sort Colors (Dutch National Flag)Medium Snapchat · Pinterest STARTUP→

#015 Kth Largest Element in ArrayMedium Freshworks · LinkedIn STARTUP→

#016 Find the Duplicate NumberMedium Razorpay · Cogoport STARTUP→

#017 Maximum Sum Circular SubarrayMedium Meesho · Flipkart STARTUP→

#018 Longest Substring Without Repeating CharsMedium Netflix · Microsoft PBC→

#019 Group AnagramsMedium Amazon · Google PBC→

#020 Longest Palindromic SubstringMedium Microsoft · Google PBC→

#021 Minimum Window SubstringHard Meta · Amazon PBC→

#022 Valid AnagramEasy Adobe · Amazon PBC→

#023 Valid PalindromeEasy Amazon · Apple PBC→

#024 Equilibrium IndexEasy Zomato · Ola STARTUP→

#025 Count Inversions in ArrayHard Razorpay · PhonePe STARTUP→

#026 Merge Sorted Arrays Without Extra SpaceHard Cure.fit · Groww STARTUP→