Arrays, Lists, and Strings in Python

Python calls it a "list," which is a lie of omission. A Python list is a dynamic array: a contiguous block of pointers in memory. Understanding that one fact tells you why some operations are instant and others quietly cost you the whole array. This chapter is about reading a list for what it is, and about the two patterns — two pointers and sliding window — that turn "loop inside a loop" into a single clean pass.

Lists Are Arrays Wearing a Costume

Because a list is a contiguous array of references, indexing is O(1). nums[5] is pointer arithmetic: base address plus five slots. It does not matter if the list has ten elements or ten million.

The trap is at the front. Every operation that shifts elements is O(n).

nums.append(4)       # O(1) amortized — grows at the end
nums.pop()           # O(1) — removes the end
nums.insert(0, 4)    # O(n) — shifts every element right
nums.pop(0)          # O(n) — shifts every element left
4 in nums            # O(n) — scans until found

That nums.pop(0) looks harmless. Put it inside a loop and you have written an accidental O(n²) algorithm that will pass your three test cases and time out on the real input. When you need to remove from the front repeatedly, reach for collections.deque, which is built for exactly that — more on it in the stacks and queues chapter.

"Amortized O(1)" for append means the list occasionally doubles its underlying capacity and copies everything over, but averaged across many appends the cost per call is constant. You do not pay it every time, so you can treat append as cheap.

Slicing Copies. Every Time.

Slicing is the most-loved and most-misunderstood tool in Python.

first_three = nums[:3]     # new list, O(k) where k = slice length
reversed_ = nums[::-1]     # new list, O(n)
copy = nums[:]             # full copy, O(n)

A slice always allocates a new list and copies the references into it. It is convenient and readable, and it is also where hidden costs hide. If you slice inside a loop, you are copying inside a loop.

# Looks innocent. Is O(n^2).
while nums:
    process(nums[0])
    nums = nums[1:]        # copies the entire remaining list every iteration

The fix is almost always an index that walks forward instead of a slice that rebuilds. Track a position; do not rebuild the array.

Strings Have the Same Shape, Plus One Rule

A string is a contiguous, indexable sequence, so slicing and indexing behave exactly like lists. The extra rule: strings are immutable. You cannot change a character in place. Every "edit" builds a new string.

# O(n^2): each += allocates a whole new string
result = ""
for ch in text:
    result += transform(ch)

# O(n): build a list, join once
parts = []
for ch in text:
    parts.append(transform(ch))
result = "".join(parts)

"".join(...) is the correct way to assemble a string from pieces. Build a list, join at the end. Interviewers watch for this specifically, and it is a real bug in production code, not just a stylistic nit.

Two Pointers: One Pass, Two Indices

The two-pointer pattern replaces a nested loop with two indices moving through the array. Use it when the data is sorted, or when you care about a relationship between two positions.

Pointers from opposite ends — reversing in place, or checking a palindrome — cost O(1) extra space:

def is_palindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True

Pointers moving the same direction let you filter or dedupe in place. Here, slow marks where the next kept element goes while fast scans ahead:

def remove_duplicates(nums):   # nums is sorted
    if not nums:
        return 0
    slow = 0
    for fast in range(1, len(nums)):
        if nums[fast] != nums[slow]:
            slow += 1
            nums[slow] = nums[fast]
    return slow + 1

That is O(n) time, O(1) space, and no slicing. The whole family — "pair that sums to target," "reverse in place," "merge two sorted arrays" — is the same idea wearing different clothes.

Sliding Window: The Subarray Special

When a problem asks about a contiguous subarray or substring — longest, shortest, sum, "contains all of" — reach for a sliding window before you write a nested loop. You expand a right edge to include more, and contract a left edge when a constraint breaks. Each element enters and leaves the window at most once, so the whole thing is O(n).

def longest_unique_substring(s):
    seen = {}          # char -> last index seen
    left = 0
    best = 0
    for right, ch in enumerate(s):
        if ch in seen and seen[ch] >= left:
            left = seen[ch] + 1     # jump past the repeat
        seen[ch] = right
        best = max(best, right - left + 1)
    return best

The tell that a window fits: the answer is about a run of adjacent elements, and you can describe when the window is "valid." If both are true, the naive O(n²) scan of every start and end collapses into one forward pass. That hash map holding seen is doing the heavy lifting, which is a preview of why the next chapter treats hash maps as your default tool.

What to Actually Remember

• Index and append are cheap. Insert-at-front, pop-at-front, and in are O(n) — never bury them in a loop.
• Every slice is a copy. Convenient, but not free, and lethal inside a loop.
• Build strings with a list and "".join(...), never repeated +=.
• Sorted input or a positional relationship points to two pointers. A contiguous subarray points to a sliding window. Both turn O(n²) into O(n) with O(1) extra space.

These patterns are maybe eighty percent of the array and string problems you will see in interviews, and they show up constantly in real code that touches text or ordered data. If you want more reps in Python itself before pushing further, the DSA with Python and Advanced Python Programming courses drill the same muscles with interactive exercises.