2. Lists

A list is an ordered, mutable sequence.

Quick Reference: List methods

Method	Purpose	Returns	Complexity	Notes
`append(x)`	Add single element to end	`None`	O(1) amortized	Adds whole object as one element
`extend(iter)`	Add all elements from iterable	`None`	O(k)	Adds each element individually
`pop([i])`	Remove and return element	Element	O(1) end, O(n) start	Default is last item
`insert(i, x)`	Insert element at index	`None`	O(n)	Shifts elements right
`remove(x)`	Remove first matching value	`None`	O(n)	Raises `ValueError` if not found
`index(x)`	Find first matching value	Index	O(n)	Raises `ValueError` if not found
`count(x)`	Count occurrences of value	`int`	O(n)	Returns `0` if not found
`reverse()`	Reverse list in place	`None`	O(n)	Mutates original list
`clear()`	Remove all elements	`None`	O(n)	Keeps same list object
`copy()`	Shallow copy	New list	O(n)	Same as `lst[:]`
`sort(key=, reverse=)`	Sort in place	`None`	O(n log n)	Stable Timsort
`sorted(iter, key=)`	Return new sorted list	New list	O(n log n)	Built-in, works on any iterable

Quick Reference: Common list operations

Operation	Purpose	Returns	Complexity	Notes
`lst[i]`	Get item by index	Element	O(1)	Negative indexing supported
`lst[i] = x`	Update item by index	`None`	O(1)	Mutates list
`del lst[i]`	Delete item by index	`None`	O(n)	Shifts elements left
`len(lst)`	Number of elements	`int`	O(1)	Very common in interviews
`x in lst`	Membership check	`bool`	O(n)	Linear scan
`for x in lst`	Iterate through elements	Iterator behavior	O(n) total	Most common iteration pattern
`enumerate(lst)`	Iterate with index + value	Iterator	O(n) total	Common in loops
`lst[a:b]`	Slice list	New list	O(k)	`k` = slice size
`lst[a:b:c]`	Slice with step	New list	O(k)	Useful for stepping
`lst[::-1]`	Reversed copy	New list	O(n)	Creates new list
`lst1 + lst2`	Concatenate lists	New list	O(n + m)	Creates new object
`lst * n`	Repeat list	New list	O(n·k)	Copies references
`min(lst)`	Smallest value	Element	O(n)	Built-in
`max(lst)`	Largest value	Element	O(n)	Built-in
`sum(lst)`	Sum numeric values	Number	O(n)	Built-in

Example

nums = [1, 2, 3]

This means two important things:

Ordered: Each item has a stable position.
Mutable: lists can be changed in place.

nums[0]   # 1
nums[1]   # 2

# Unlike strings, lists can be changed in place.
nums[0] = 10   # [10, 2, 3]

`append()`

Adds a single element to the end of the list.

nums = [1, 2, 3]
nums.append(4)    # [1, 2, 3, 4]

Meaning if you append a list, it will be added as a single element to the list.

nums = [1, 2]
nums.append([3, 4])   # [1, 2, [3, 4]]

This is a common interview trap.

Complexity

O(1) amortized, because resizing happens occasionally.

O(1) amortized (amortized constant time) means that while a specific operation might occasionally take a long time O(n) or O(log n), the average cost per operation over a long sequence of operations is constant O(1)

`extend()`

Adds all elements from an iterable individually.

Very important distinction from append().

nums = [1, 2]
nums.extend([3, 4])   # [1, 2, 3, 4]

`pop()`

Used to remove and return an element.

nums = [1, 2, 3]
last = nums.pop()   # last = 3 and nums = [1, 2]

Pop specific index

nums.pop(0)

Removes the first element.

Complexity

`pop()`

nums.pop()    # Complexity: O(1)
nums.pop(0)   # Complexity: O(n) Because all elements shift left.

`insert()`

Inserts a single element before the specified index.

Modifies in place
No return value

nums = [1, 2, 3]
nums.insert(1, 99)   # [1, 99, 2, 3]

Complexity

O(n) Because all elements after the insertion point must shift right.

Interview context

If you need to insert many items, building a new list or using collections.deque is more efficient.

`remove()`

Remove the first occurrence of a value.

No return value
Raises error if not found

nums = [1, 2, 3, 2, 4]
result = nums.remove(2)   # [1, 3, 2, 4]
print(result)             # None
nums.remove(5)            # ValueError: list.remove(x): x not in list

This is different from pop(), which can use a default or raise with graceful handling.

Complexity

O(n) Because it must search through the list.

Interview tip

If you need to remove multiple items or iterate while removing, use a list comprehension instead:

nums = [1, 2, 3, 2, 4]
nums = [x for x in nums if x != 2]  # Remove all 2's

This is clearer and safer than modifying during iteration.

`index()`

Returns the index of the first occurrence of the value.

nums = [10, 20, 30, 20]
pos = nums.index(20)   # 1

Raises error if not found

nums = [1, 2, 3]
nums.index(5)  # ValueError: 5 is not in list

Compare to `find()` pattern (from strings)

Strings have find() which returns -1 if not found. Lists don't have this:

# Strings
"hello".find("x")     # -1 (safe)

# Lists
nums = [1, 2, 3]
nums.index(5)        # ValueError (raises error)

To safely find in a list:

try:
    pos = nums.index(5)
except ValueError:
    pos = -1

Complexity

O(n): Must search from the beginning.

Interview context

Rarely used directly in problem-solving. More common: comprehensions, dictionary lookups, or set membership.

`count()`

Count occurrences of a value.

nums = [1, 2, 2, 3, 2, 4]
count = nums.count(2)   # 3

Works with any type

people = ["Alice", "Bob", "Alice", "Charlie"]
people.count("Alice")  # 2

Always returns a number (even if 0)

nums = [1, 2, 3]
nums.count(5)  # 0 (no error)

Complexity

O(n): Must scan entire list.

Interview context

Useful for frequency counting, but for larger datasets, collections.Counter is better:

from collections import Counter
nums = [1, 2, 2, 3, 2, 4]
freq = Counter(nums)
print(freq[2])  # 3 - faster for many lookups

`reverse()`

Reverses the order of elements in place. No return value.

nums = [1, 2, 3]
result = nums.reverse()
print(result)  # None
print(nums)    # [3, 2, 1]

Compare to slicing trick

# Method 1: reverse() - mutates original
nums = [1, 2, 3]
nums.reverse()
# nums is now [3, 2, 1]

# Method 2: slicing - creates new list
nums = [1, 2, 3]
reversed_nums = nums[::-1]
# nums is still [1, 2, 3]
# reversed_nums is [3, 2, 1]

Complexity

O(n): Must visit each element.

Interview context

Rarely asked directly. The slicing trick [::-1] is more Pythonic and more commonly seen in interviews.

`clear()`

Empties the list completely. In-place operation, no return value.

nums = [1, 2, 3]
nums.clear()   # []

Same as assigning empty list

# Method 1: clear()
nums.clear()

# Method 2: reassign (creates new empty list)
nums = []

The difference: clear() empties the object in place, while = [] creates a new list.

a = [1, 2, 3]
b = a          # b references same list as a
a.clear()
print(b)       # [] - b is now empty too

# vs
a = [1, 2, 3]
b = a
a = []         # a now references a NEW empty list
print(b)       # [1, 2, 3] - b still references old list

Complexity

O(n): Must deallocate n elements.

Interview context

Rarely used. More common to reassign or create a new list.

1.2.11 `copy()`

Create a shallow copy of the list.

nums = [1, 2, 3]
nums_copy = nums.copy()   # [1, 2, 3]

Compare to assignment

# Assignment: both reference same list
original = [1, 2, 3]
alias = original
original[0] = 99
print(alias)  # [99, 2, 3] - both changed!

# Copy: separate lists
original = [1, 2, 3]
copy = original.copy()
original[0] = 99
print(copy)   # [1, 2, 3] - unchanged

Shallow copy gotcha

If list contains mutable objects (like nested lists), they are not deep copied:

original = [[1, 2], [3, 4]]
copy = original.copy()

copy[0][0] = 99  # Modifies the inner list
print(original)  # [[99, 2], [3, 4]] - inner list changed!

Three ways to copy

# Method 1: .copy()
copy1 = nums.copy()

# Method 2: slicing
copy2 = nums[:]

# Method 3: list() constructor
copy3 = list(nums)

All three create a shallow copy.

Use copy.deepcopy() for nested structures:

import copy
original = [[1, 2], [3, 4]]
deep = copy.deepcopy(original)
deep[0][0] = 99
print(original)  # [[1, 2], [3, 4]] - unchanged!

Complexity

O(n): Must create a new list and copy all references.

Interview context

Shallow copy is critical to understand. Frequently tested when working with mutable objects and reference semantics.

Sorting

`sort()`

Sorts the list in place.

nums = [3, 1, 2]
nums.sort()   # [1, 2, 3]

How sorting works: comparison protocol

Python uses the comparison dunder methods to sort:

# Python calls __lt__ (less than) under the hood
# a < b  is equivalent to  a.__lt__(b)

For built-in types (int, str, etc.), these are defined:

# Numbers: compare by value
[3, 1, 2].sort()  # [1, 2, 3]

# Strings: compare alphabetically
["zebra", "apple"].sort()  # ["apple", "zebra"]

For custom objects, you need to define comparison methods:

class Person:
    def __init__(self, name, age):
        self.name = name
        self.age = age
    
    def __lt__(self, other):
        return self.age < other.age

people = [Person("Alice", 30), Person("Bob", 25)]
people.sort()  # Sorted by age (uses __lt__)

But it's cleaner to use the key parameter instead of defining dunder methods:

people.sort(key=lambda p: p.age)  # Same result, more readable

`sorted()`

The original list remains unchanged.

nums = [3, 1, 2]
new_nums = sorted(nums)   # [1, 2, 3]

Interview question: `sort()` vs `sorted()`

Strong answer:

sort() mutates the original list (in-place, method on list)
sorted() returns a new list (works on any iterable, built-in function)

Sorting reverse

nums.sort(reverse=True)

Sorting by key

people = [
    {"name": "A", "age": 30},
    {"name": "B", "age": 25}
]

people.sort(key=lambda x: x["age"])   # Sorts by age

This appears constantly in interviews.

Complexity

O(n log n): Python uses Timsort (hybrid of merge sort and insertion sort).

Strong verbal answer:

stable: equal elements keep original order
optimized: excellent for partially sorted data

Slicing

Lists use the same slicing syntax as strings.

nums = [1, 2, 3, 4, 5]

nums[1:4]   # [2, 3, 4]

Important rules

start inclusive
stop exclusive

Common slices

nums[:3]
nums[3:]
nums[::-1]   # Reverse list
nums[::2]

List comprehensions

One of the most important Pythonic tools.

Basic syntax

squares = [x * x for x in range(5)]   # [0, 1, 4, 9, 16]

Mental model

Equivalent to:

squares = []
for x in range(5):
    squares.append(x * x)

Conditional comprehensions

evens = [x for x in range(10) if x % 2 == 0]   # [0, 2, 4, 6, 8]

Nested comprehensions

pairs = [(x, y) for x in range(2) for y in range(2)]   # [(0, 0), (0, 1), (1, 0), (1, 1)]

Important list operations

Membership

3 in nums

Complexity: O(n)

Length

len(nums)

Iteration

for num in nums:
    ...

Key Concepts Summary

Mutability: Lists can change in place. Strings/tuples don't.

Passing by reference: Multiple variables can point to same list → modifications affect all references.

Shallow vs deep copy: .copy() / [:] copies structure only, not nested objects.

Comparison dunder methods: Sorting uses __lt__ (less than). Custom objects need either __lt__ or key= parameter.

Slicing: [start:stop:step] where start is inclusive, stop is exclusive.

List comprehensions: [expr for item in iter if condition] - more readable than loops.

Verbal interview questions

Difference between append() and extend()
Why is pop(0) slower than pop()
Difference between sort() and sorted()
Explain shallow copy with slicing
Why use comprehension over manual loop

Coding drills

Drill 1: remove duplicates

def remove_duplicates(nums: list[int]) -> list[int]:
    ...

Drill 2: flatten nested list

def flatten(matrix: list[list[int]]) -> list[int]:
    ...

Drill 3: sort people by age

def sort_people(people: list[dict]) -> list[dict]:
    ...

Use:

sorted(..., key=...)

Common interview problems

A large number of interview questions are really list problems in disguise.

Problem 1: Remove Duplicates

Question: Given a sorted list of integers, remove duplicates in place and return the length of the list with unique values.

def removeDuplicates(nums: list[int]) -> int:
    # [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
    # Return 5, nums becomes [0, 1, 2, 3, 4, ...]
    ...

Visual: [1, 1, 2, 2, 3] → first 3 elements are [1, 2, 3], return 3.

Key insight: Two pointers - fast pointer scans, slow pointer marks unique positions.

Problem 2: Reverse an Array

Question: Reverse a list in place without using built-in reverse methods.

def reverse(nums: list[int]) -> None:
    # [1, 2, 3, 4, 5] → [5, 4, 3, 2, 1]
    # Modify in place
    ...

Key insight: Two pointers from both ends, swap towards center.

Problem 3: Two Pointers - Container With Most Water

Question: Given a list of integers representing heights, find two lines that form a container capable of holding the maximum water.

def maxArea(heights: list[int]) -> int:
    # [1, 8, 6, 2, 5, 4, 8, 3, 7]
    # Container between index 1 (height 8) and 8 (height 7)
    # Width = 7, Height = min(8, 7) = 7
    # Area = 49
    ...

Key insight: Start at both ends, move the pointer with smaller height inward.

Problem 4: Sliding Window - Maximum in Window

Question: Given a list and window size k, find the maximum value in each sliding window.

def maxSlidingWindow(nums: list[int], k: int) -> list[int]:
    # nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
    # [1, 3, -1] → 3
    # [3, -1, -3] → 3
    # [-1, -3, 5] → 5
    # [-3, 5, 3] → 5
    # [5, 3, 6] → 6
    # [3, 6, 7] → 7
    # Return [3, 3, 5, 5, 6, 7]
    ...

Key insight: Use a deque to maintain indices of useful elements.

Problem 5: Find Duplicates

Question: Given a list with n+1 integers where each is between 1 and n, find a duplicate (may be multiple).

def findDuplicate(nums: list[int]) -> int:
    # [1, 3, 4, 2, 2]
    # Return 2 (appears twice)
    ...

Constraint: Cannot modify the list, O(1) space preferred (Floyd's cycle detection).

Key insight: Treat it as a linked list problem - the duplicate creates a cycle.

Problem 6: Sort Objects by Property

Question: Given a list of dictionaries (people), sort by age, then by name if ages are equal.

def sortPeople(people: list[dict]) -> list[dict]:
    # people = [
    #     {"name": "Carol", "age": 29},
    #     {"name": "Alice", "age": 30},
    #     {"name": "Bob", "age": 28}
    # ]
    # Return sorted by age ascending
    ...

Key insight: Use sorted() with key=lambda x: (x["age"], x["name"]) for multiple criteria.

Problem 7: Merge Intervals

Question: Given a list of intervals, merge overlapping ones.

def merge(intervals: list[list[int]]) -> list[list[int]]:
    # [[1, 3], [2, 6], [8, 10], [15, 18]]
    # Return [[1, 6], [8, 10], [15, 18]]
    ...

Key insight: Sort by start time, then iterate and merge when overlapping.

Problem 8: Flatten Nested List

Question: Given a nested list structure, flatten it into a single list.

def flatten(matrix: list[list[int]]) -> list[int]:
    # [[1, 2], [3, 4], [5, 6]]
    # Return [1, 2, 3, 4, 5, 6]
    ...

Key insight: List comprehension or recursion for truly nested structures.

Problem 9: Frequency Counting

Question: Given a list of words, find the k most frequent elements.

def topKFrequent(words: list[str], k: int) -> list[str]:
    # words = ["apple", "banana", "apple", "cherry", "banana", "apple"]
    # k = 2
    # Return ["apple", "banana"] (apple: 3, banana: 2)
    ...

Key insight: Use collections.Counter, then sort by frequency.

Problem 10: Stack Problem Disguised as List

Question: Given a list of opening/closing brackets, determine if they're valid.

def isValid(s: str) -> bool:
    # "()" → True
    # "([{}])" → True
    # "(" → False
    # "([)]" → False (mismatch)
    ...

Key insight: Use a list as a stack to track opening brackets, pop on closing.

Lists

2. Lists

Quick Reference: List methods

Quick Reference: Common list operations

Example

append()

Complexity

extend()

pop()

Pop specific index

Complexity

pop()

insert()

Complexity

Interview context

remove()

Complexity

Interview tip

index()

Raises error if not found

Compare to find() pattern (from strings)

Complexity

Interview context

count()

Works with any type

Always returns a number (even if 0)

Complexity

Interview context

reverse()

Compare to slicing trick

Complexity

Interview context

clear()

Same as assigning empty list

Complexity

Interview context

1.2.11 copy()

Compare to assignment

Shallow copy gotcha

Three ways to copy

Complexity

Interview context

Sorting

sort()

How sorting works: comparison protocol

sorted()

Interview question: sort() vs sorted()

Sorting reverse

Sorting by key

Complexity

Slicing

Important rules

Common slices

List comprehensions

Basic syntax

Mental model

Conditional comprehensions

Nested comprehensions

Important list operations

Membership

Length

Iteration

Key Concepts Summary

Verbal interview questions

Coding drills

Drill 1: remove duplicates

Drill 2: flatten nested list

Drill 3: sort people by age

Common interview problems

Problem 1: Remove Duplicates

Problem 2: Reverse an Array

Problem 3: Two Pointers - Container With Most Water

Problem 4: Sliding Window - Maximum in Window

Problem 5: Find Duplicates

Problem 6: Sort Objects by Property

Problem 7: Merge Intervals

Problem 8: Flatten Nested List

Problem 9: Frequency Counting

Problem 10: Stack Problem Disguised as List

`append()`

`extend()`

`pop()`

`pop()`

`insert()`

`remove()`

`index()`

Compare to `find()` pattern (from strings)

`count()`

`reverse()`

`clear()`

1.2.11 `copy()`

`sort()`

`sorted()`

Interview question: `sort()` vs `sorted()`