Lesson 3: Programs 11-15: Arrays and Lists

How to use this lesson. Read the question and try it yourself for ten minutes before you read the approach. In a real interview, say your idea out loud, mention the edge cases (empty input, one item, duplicates, negative numbers), then code, then test with an example.

Problem 11: Two Sum

Question. Given a list of numbers and a target, return the positions of two numbers that add up to the target (or None).

Examples.

• [2, 7, 11, 15], target 9 → (0, 1)

Approach. Checking every pair is O(n squared). Instead, as you walk through the list, ask: have I already seen the number that completes this one (target - x)? A dictionary from value to position answers that in O(1).

def two_sum(nums, target):
    seen = {}
    for i, x in enumerate(nums):
        need = target - x
        if need in seen:
            return seen[need], i
        seen[x] = i
    return None

print(two_sum([2, 7, 11, 15], 9))
print(two_sum([3, 2, 4], 6))
print(two_sum([3, 3], 6))
print(two_sum([1, 2], 10))
print(two_sum([], 0))

Output:

(0, 1)
(1, 2)
(0, 1)
None
None

Complexity. O(n) time, O(n) space.

Follow-up an interviewer may ask. What if the list is sorted and you must use O(1) space? (Two pointers moving inward.)

Problem 12: Find the Second Largest Number

Question. Return the second largest distinct value in a list, or None if there is not one.

Examples.

• [10, 5, 20, 20, 8] → 10
• [5, 5] → None

Approach. Sorting works but costs O(n log n). One pass is enough: keep the largest and the second largest so far. Skip values equal to the largest so duplicates do not count.

def second_largest(nums):
    largest = second = None
    for x in nums:
        if largest is None or x > largest:
            second, largest = largest, x
        elif x != largest and (second is None or x > second):
            second = x
    return second

for data in [[10, 5, 20, 20, 8], [5, 5], [1, 2], [7], [], [-3, -1, -2], [4, 4, 3]]:
    print(data, "->", second_largest(data))

Output:

[10, 5, 20, 20, 8] -> 10
[5, 5] -> None
[1, 2] -> 1
[7] -> None
[] -> None
[-3, -1, -2] -> -2
[4, 4, 3] -> 3

Complexity. O(n) time, O(1) space.

Follow-up an interviewer may ask. How would you find the k-th largest? (A min-heap of size k, or heapq.nlargest.)

Problem 13: Maximum Subarray Sum (Kadane's Algorithm)

Question. Find the largest sum of any contiguous part of a list of integers.

Examples.

• [-2, 1, -3, 4, -1, 2, 1, -5, 4] → 6 (the part [4, -1, 2, 1])

Approach. Walk through the list keeping the best sum of a subarray ending here. At each number either extend the previous subarray or start fresh, whichever is bigger: current = max(x, current + x). The answer is the largest value seen. This is Kadane's algorithm.

def max_subarray(nums):
    best = current = nums[0]
    for x in nums[1:]:
        current = max(x, current + x)
        best = max(best, current)
    return best

print(max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]))
print(max_subarray([5]))
print(max_subarray([-3, -1, -2]))
print(max_subarray([1, 2, 3]))

Output:

6
5
-1
6

Complexity. O(n) time, O(1) space.

Follow-up an interviewer may ask. How do you also return which subarray it is? (Track the start index when you restart, and the best start and end.)

Problem 14: Flatten a Nested List

Question. Turn a list that contains lists (to any depth) into one flat list.

Examples.

• [1, [2, [3, [4]], 5]] → [1, 2, 3, 4, 5]

Approach. Go through the items: if an item is a list, flatten it recursively; otherwise keep it. A generator with yield from keeps the code short and memory-friendly.

def flatten(items):
    for item in items:
        if isinstance(item, list):
            yield from flatten(item)
        else:
            yield item

print(list(flatten([1, [2, [3, [4]], 5]])))
print(list(flatten([])))
print(list(flatten([[], [[]], [1]])))
print(list(flatten(["a", ["b", ["c"]]])))

Output:

[1, 2, 3, 4, 5]
[]
[1]
['a', 'b', 'c']

Complexity. O(n) time for n items in total, O(d) stack for nesting depth d.

Follow-up an interviewer may ask. How would you avoid recursion for very deep nesting? (Use an explicit stack.)

Problem 15: Rotate a List

Question. Rotate a list to the right by k places: the last k items move to the front.

Examples.

• [1, 2, 3, 4, 5, 6, 7], k = 3 → [5, 6, 7, 1, 2, 3, 4]

Approach. Use k % n so large k wraps around and an empty list is handled. Then slicing does the job: the last k items followed by the rest. The in-place trick is to reverse the whole list, then reverse the first k and the remaining items.

def rotate_right(nums, k):
    if not nums:
        return []
    k %= len(nums)
    return nums[-k:] + nums[:-k] if k else nums[:]

print(rotate_right([1, 2, 3, 4, 5, 6, 7], 3))
print(rotate_right([1, 2, 3], 4))
print(rotate_right([1, 2, 3], 0))
print(rotate_right([], 5))
print(rotate_right([9], 100))

Output:

[5, 6, 7, 1, 2, 3, 4]
[3, 1, 2]
[1, 2, 3]
[]
[9]

Complexity. O(n) time, O(n) space (the in-place reversal approach uses O(1) extra space).

Follow-up an interviewer may ask. Rotate it in place with O(1) extra space. (Three reversals.)