Skip to content
Data Structures & Algorithms

Arrays interview questions and answers

60 questions, 43 with code. About 4 h 44 min to read them all.

By TestLab · Updated

Plan for an interview
60 questions

Track what you know and what to revise.

Sign in to track progress

You can open a few full answers without signing in. Sign in to read all

1

What is an array in data structures?

An array is a fundamental data structure that stores a fixed-size sequential collection of elements of the same type in contiguous memory locations, allowing constant-time access by index.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Static vs Dynamic Arrays

  • Static array: Size fixed at allocation; cannot grow or shrink. Languages like C, C++, Java (primitive arrays) use this model.

  • Dynamic array: Resizes automatically when capacity is exceeded (e.g., Python list, C++ std::vector, Java ArrayList). Growth typically doubles capacity, making append amortized O(1).

  • Python list is a dynamic array of object references; the underlying buffer holds pointers, not the objects themselves.

Memory Layout and Access

  • Elements stored contiguously: address of element i = base_address + i * element_size.

  • Index access O(1): direct address calculation, no traversal.

  • Cache-friendly: sequential access exploits spatial locality.

  • Homogeneous type (in static arrays): each slot same size; dynamic arrays of references can hold any object type.

Common Operations and Complexities

Operation Static Array Dynamic Array (append at end) Dynamic Array (insert/delete middle)
Access by index O(1) O(1) O(1)
Search (unsorted) O(n) O(n) O(n)
Insert at end N/A (fixed size) Amortized O(1) O(n)
Delete at end N/A O(1) O(n)
Insert/delete at index i N/A O(n - i) O(n - i)
Space O(n) O(n) (capacity ≥ size) O(n)

Reasoning: Insert/delete in middle shifts all subsequent elements; dynamic array resize copies entire buffer (amortized cost spread over many appends).

Typical Array Patterns

  • Two pointers: left/right indices moving toward center (e.g., two-sum on sorted array, palindrome check).

  • Sliding window: maintain a subarray [left, right) satisfying a condition; expand right, contract left.

  • Prefix sums: precompute prefix[i] = sum(arr[:i]) for O(1) range-sum queries.

  • Kadane’s algorithm: maximum subarray sum in O(n) time, O(1) space.

  • In-place swaps / cyclic sort: place each value at its correct index (for permutations 1..n).

  • Dutch national flag: three-way partition around a pivot (used in quicksort, sort colors).

Common Pitfalls

  • Off-by-one errors: loop bounds range(len(arr)) vs range(len(arr) - 1); inclusive vs exclusive endpoints.

  • Mutating input unintentionally: many interview problems allow in-place modification, but confirm with interviewer.

  • Confusing Python list with linked list: list.pop(0) and list.insert(0, x) are O(n); use collections.deque for queue operations.

  • Shared-row bug in 2D arrays: [[0] * n] * m creates m references to the same row; use [[0] * n for _ in range(m)].

  • Assuming dynamic array append is always O(1): it is amortized; a single append that triggers resize takes O(n).

  • Interview follow-ups: “How would you implement a dynamic array from scratch?” “When would you choose a linked list over an array?” “How does memory fragmentation affect large arrays?”

2

What is a dynamic array in data structures?

A dynamic array is an array that can grow or shrink at runtime: it keeps a contiguous buffer that is usually larger than the number of stored elements, and when that buffer fills up it allocates a bigger one and copies the elements over. Python’s built-in list is a dynamic array.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

A static array has a fixed length decided at allocation. A dynamic array wraps one with two numbers:

  • Length / size: how many elements the user has stored.

  • Capacity: how many slots the buffer currently has.

The steps for insertion are:

  1. If length < capacity, write the element at index length and increment length. This is O(1).

  2. Otherwise the buffer is full: allocate a new buffer with a larger capacity (doubling, or about 1.125x in CPython, 1.5x in Java’s ArrayList, and implementation-defined but typically 2x in C++ std::vector).

  3. Copy the length elements into the new buffer, release the old one, then append the new element.

Copying looks expensive, but because capacity grows geometrically, the copies over n appends total n + n/2 + n/4 + ... < 2n. Dividing the total work by n operations gives amortized O(1) per append. The doubling rule is what makes this work: growing by a fixed amount instead would make appends O(n) amortized.

Note that a Python list stores pointers to objects, not the objects themselves, which is why it can hold mixed types while still supporting O(1) indexing.

Complexity

Operation Time Reason
Index arr[i] O(1) Contiguous buffer, address arithmetic
Append to end Amortized O(1); worst case O(n) Occasional resize copies all elements
Pop from end O(1) Only length changes
Insert/delete in middle O(n) Shifts every element after the position
Search (unsorted) O(n) Must scan
Binary search (sorted) O(n log n) to sort, O(log n) per lookup Requires sorted data

Space is O(n) for the stored elements (the input itself is counted here); during a resize there is a transient extra O(n) for the old and new buffers existing at once. The overallocated capacity is still O(n).

Static vs Dynamic Arrays

Aspect Static array Dynamic array
Size Fixed at creation Grows/shrinks at runtime
Append Not possible Amortized O(1)
Memory Exact Overallocated (up to ~2x)
Examples C int a[10], Java int[] Python list, Java ArrayList, C++ std::vector

Patterns Built on Arrays

  • Two pointers: one pointer from each end (reverse, palindrome check) or fast/slow (remove duplicates from a sorted array); O(n) time, O(1) space.

  • Sliding window: maintain a running aggregate over a contiguous range (longest substring without repeats, max sum of size k).

  • Prefix sums: precompute cumulative sums so any range sum is O(1) after O(n) preprocessing.

  • Kadane’s algorithm: running maximum subarray sum in O(n), resetting the running sum when it goes negative.

  • In-place swaps / Dutch national flag: partition into three regions with three pointers, as in sorting 0s, 1s and 2s.

  • Cyclic sort: place each value at index value - 1 to find missing or duplicate numbers in O(n).

Many of these deliberately modify the input array in place to reach O(1) extra space; say so out loud in an interview and confirm mutating the input is allowed, since the caller may still need the original order.

Common Pitfalls

  • list.pop(0) and list.insert(0, x) are O(n) — use collections.deque for queue behaviour.

  • Constructing 2D lists with [[0] * n] * m shares one row object across all rows; write [[0] * n for _ in range(m)] instead. A 2D array is O(m*n) in both time and space per full traversal.

  • Assuming append is worst-case O(1) — a single append can trigger an O(n) copy; the guarantee is amortized.

  • Shrinking is not automatic — a list that grew large keeps its capacity until rebuilt.

  • Mutating while iterating skips or repeats elements; iterate over a copy or build a new list.

  • Off-by-one in windows: decide up front whether your left/right bounds are inclusive and keep it consistent.

  • Interviewers often follow up with “what is the amortized cost and why?”, “how would you implement your own growable array?”, or “why not use a linked list instead?” (linked lists give O(1) insert at a known node but lose O(1) indexing and cache locality).

3

What is an associative array or dictionary?

An associative array, commonly called a dictionary or mapping, stores data as key–value pairs. Each key uniquely identifies its associated value, enabling keyed lookup without scanning for a positional index.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Concept

A dictionary maps unique, hashable keys to values of any type. In Python, dict is the standard implementation:

  • Keys: unique identifiers such as strings, numbers, or tuples

  • Values: associated data such as counts, records, or lists

  • Lookup: retrieves a value using its key

  • Insertion: adds a new key–value pair

  • Update: replaces the value for an existing key

  • Deletion: removes a key and its value

  • Membership test: determines whether a key exists

Keys must be hashable and usually immutable. Python dictionaries preserve insertion order, so iteration follows the order in which keys were first inserted. Updating an existing key does not change that key’s position.

How Dictionary Lookup Works

Conceptually, a dictionary uses a hash table:

  1. The key’s hash() produces an integer hash value.

  2. That hash determines the key’s initial bucket or table position.

  3. Python compares the stored key with the requested key to confirm equality.

  4. If a collision occurs, the implementation probes other positions until it finds the key or an available slot.

Because the table can expand, insertions include occasional resizing. Resizing is expensive for one operation, but its cost is distributed across many insertions, making a sequence of insertions amortized O(1).

A tree-backed ordered dictionary is a different implementation that guarantees sorted key order, typically with O(log n) operations. Python’s built-in dict instead guarantees insertion order and relies on hashing for fast lookups.

Time and Space Complexity

For a dictionary containing n entries:

Operation Best Average Worst Reason
Get by key O(1) O(1) O(n) Hashing usually identifies a slot directly; many collisions may require extensive probing
Insert or update O(1) O(1) amortized O(n) Collisions and table resizing add work
Delete by key O(1) O(1) O(n) The key must first be located
Membership test O(1) O(1) O(n) Uses the same hashing and collision handling
Iteration O(n) O(n) O(n) Every entry must be visited

A dictionary holding n entries uses O(n) total space for its keys, values, and internal table. If it is built from an input, that dictionary adds O(n) space beyond the input; if the dictionary itself is the input, its storage is not auxiliary space. No recursion stack is involved.

Static and Dynamic Arrays

A static array has a fixed capacity when allocated and typically stores elements in contiguous memory. Index access is O(1) because the element address can be calculated directly. Inserting or deleting within its fixed capacity generally costs O(n) because elements must be shifted, and storing n elements requires O(n) space.

A dynamic array can grow or shrink as needed. Python’s list is a dynamic array:

  • Index access is O(1).

  • append() is amortized O(1); an occasional resize copies O(n) elements.

  • Inserting or deleting in the middle is O(n) because existing elements must be shifted.

  • Storage for n elements is O(n), including any overallocated capacity.

Dictionaries Compared with Arrays

Property Python list Python dict
Organization Ordered sequence Ordered key–value mapping
Access Integer index Unique key
Index or lookup O(1) O(1) average, O(n) worst
Duplicate elements Allowed Keys are unique
Typical mutation Positional insertion or deletion Insertion, update, or deletion by key
Common uses Positional collections Records, counts, caching, lookup tables

A dictionary is not merely an array with a different name; it is a mapping data structure, commonly implemented with hashing.

Practical Uses

Dictionaries are appropriate when data is naturally identified by a key:

  • Counting word frequencies

  • Mapping user IDs to user records

  • Grouping items by category

  • Caching previously calculated results

  • Representing JSON objects, whose keys are strings

  • Tracking visited nodes in graph algorithms

For repeated grouping or counting, Python also provides collections.Counter and collections.defaultdict, both specialized dictionary types.

Common Pitfalls

  • Mutating a dictionary during iteration can raise RuntimeError; iterate over a copy or collect the changes and apply them after iteration.

  • Using an unhashable key, such as a list, raises TypeError; use a hashable value such as a tuple.

  • Assuming guaranteed constant-time worst-case lookup is incorrect when hash collisions occur.

  • Confusing membership syntax: key in dictionary checks keys, while value in dictionary.values() scans values.

  • Overwriting an existing key updates its value but retains its original insertion position.

  • Interviewers may follow up by asking how hashing works, why keys must be hashable, how resizing affects performance, or how a dictionary differs from a balanced search tree.

4

What determines the dimensionality of an array?

The dimensionality of an array is the number of indices, or subscripts, required to address a single element; equivalently, it is the number of axes in the array’s shape. It describes how elements are organised and accessed, not how many elements the array contains.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

What Dimensionality Measures

  • One dimension: one index selects an element, as in values[i].

  • Two dimensions: two indices are needed, as in matrix[row][col] or a C declaration such as int grid[3][4].

  • Three dimensions: three indices, as in cube[layer][row][col].

  • Rank: another name for the number of dimensions; a 2D array has rank 2.

  • Shape: the length of each axis, such as (3, 4) for 3 rows and 4 columns.

  • Size: the total number of elements, the product of the shape; (3, 4) means 3 * 4 = 12 elements.

A common misconception is that the element count determines the dimensionality. It does not: six elements could be a 1D array of length 6, a 2D array of shape (2, 3), or a 3D array of shape (1, 2, 3).

Shape, Size and Rank

For a rectangular 2D array with m rows and n columns:

  • The number of dimensions is 2.

  • The shape is (m, n).

  • The size is m * n.

  • A valid element requires 0 <= row < m and 0 <= col < n.

A dimension may also have length zero, such as a shape (0, 3): it is still a 2D array, but it contains no elements. Likewise, an empty 1D array has length 0 but remains one-dimensional.

Memory Layout and Strides

A true multidimensional array normally stores its elements in one contiguous block and computes an offset from the indices. In row-major order, used by C and by NumPy by default, the offset of matrix[row][col] in an m x n array is:

offset = row * n + col

Column-major order, used by Fortran and MATLAB, varies the fastest index first. The stride of each axis is the number of elements skipped when that index increases by one. This layout is why accessing one element is constant time rather than a search.

Static, Dynamic and Nested Arrays

  • Static array: the dimension lengths are fixed at compile time or allocation time, as with C arrays.

  • Dynamic array: the length can grow, as with a Python list. A Python list is a one-dimensional dynamic array of references; append is amortized O(1), while inserting or deleting in the middle is O(n).

  • Nested list: [[0] * n for _ in range(m)] creates m separate row lists and is the usual Python way to model a matrix. It is not necessarily rectangular or contiguous, and rows can be ragged.

  • True multidimensional array: libraries such as NumPy provide a single array object with a rank, shape and strides.

Structure Indices used Shape and size Storage
1D dynamic array (list) 1 length n, size n Contiguous references, resized as needed
2D static array 2 m x n, size m * n One contiguous block in row-major order
Python list of lists 2 in code Rows may have different lengths References to separate row lists

Complexity

  • Indexing one element: O(1) time in the best, average and worst case, because the offset is computed arithmetically; O(1) extra space.

  • Scanning a full m x n matrix: O(m * n) time, since every element is visited once; O(1) extra space if only reading, excluding the input itself.

  • Dynamic array append: amortized O(1) time, with O(n) worst case when resizing; indexing remains O(1).

  • Middle insertion or deletion in a dynamic array: O(n) time because later elements shift.

  • Space for a new m x n matrix: O(m * n) for the array itself; if an existing input is only read, the algorithm’s extra space may be O(1) and the input is not counted.

Common Pitfalls

  • Confusing the number of dimensions with the number of elements; shape, not size, defines dimensionality.

  • Swapping rows and columns: an m x n matrix has m rows and n columns.

  • Creating a 2D list with [[0] * n] * m; all rows alias the same inner list, so writing one cell changes every row. Use a comprehension instead.

  • Assuming a Python list of lists is rectangular or contiguous; ragged rows are legal and must be handled.

  • Forgetting that a zero-length dimension still counts as a dimension.

  • In an interview, expect follow-ups about row-major versus column-major layout, flattening a 2D index into a 1D offset, and whether a solution modifies the input matrix in place.

5

What are the advantages and disadvantages of arrays?

Arrays store elements in a contiguous block of memory, making indexed access fast and predictable. Their main trade-off is that efficient lookup comes at the cost of expensive insertion and deletion in the middle of the sequence.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Static and Dynamic Arrays

  • Static array: Has a fixed size determined when it is created. Its capacity cannot grow automatically.

  • Dynamic array: Has resizable capacity and can grow or shrink according to its implementation policy. Python’s list is a dynamic array of object references.

  • Contiguous storage: Elements are stored next to one another in memory, which generally improves cache locality compared with structures such as linked lists.

  • Indexed access: Both types support direct access by position, provided the index is within the valid range.

Advantages

  • Fast indexing: Reading or writing an element at a valid index takes O(1) time in the best, average, and worst cases because the address can be calculated directly.

  • Good cache performance: Contiguous storage reduces the number of memory accesses needed during traversal.

  • Simple implementation: Arrays are easy to create, iterate, and use for fixed-size collections.

  • Compact representation: Static arrays avoid per-element node allocations and linked-list overhead. Primitive-element arrays also avoid per-element reference storage, whereas arrays of objects or references still store those references.

  • Predictable memory use: A static array’s capacity is known in advance, which can be useful in embedded systems and low-level programming.

  • Flexible growth in dynamic arrays: Python’s list.append() supports adding elements without specifying a capacity in advance.

Disadvantages

  • Costly middle insertion and deletion: Inserting or removing an element requires shifting subsequent elements. This takes O(n) time in the average and worst cases. The best case is O(1) when no shift is needed, such as removing the final element; a static array cannot use that best case to append beyond its fixed capacity.

  • Resize overhead: A dynamic array may need to allocate a larger buffer and copy its elements. A single append can therefore take O(n) in the worst case, but repeated appends take O(1) amortized time.

  • Fixed capacity in static arrays: Adding elements beyond the allocated size requires creating a new array and copying the old contents.

  • Potential wasted capacity: A dynamic array may reserve more memory than it currently uses, particularly after shrinking.

  • Less flexible than general-purpose containers: Python lists can contain heterogeneous objects, while typed or low-level arrays may restrict elements to a fixed type.

  • Linear searching: Finding a value without additional indexing information requires a scan. An unsorted search takes O(1) in the best case and O(n) in the average and worst cases.

Complexity Comparison

Operation Static array Dynamic array, such as Python list Space
Read by valid index O(1) best/average/worst O(1) best/average/worst O(1) auxiliary
Append Not supported when full; allocating and copying costs O(n) O(1) best; O(1) amortized per append; O(n) worst for one append O(1) auxiliary normally; O(n) temporary during a resize
Insert or delete in the middle O(n) average/worst O(n) average/worst when elements must shift O(1) for shifting; O(n) temporary if deletion triggers a shrink or copy
Remove from the end O(1) when only the logical size changes; O(n) if copied into a new array O(1) best and amortized; O(n) worst when shrinking or copying O(1) auxiliary normally; O(n) temporary during a shrink or copy
Linear search O(n) average/worst O(n) average/worst O(1) auxiliary

Storing n elements requires O(n) space for the array itself. The complexity table treats that input storage separately from auxiliary space. These operations do not use recursion, so the recursion stack is O(1).

Common Use Cases and Patterns

Arrays are especially effective when elements are accessed by position or processed in a fixed number of passes. Common patterns include:

  • Two pointers: Efficiently compare or process elements from opposite ends.

  • Sliding window: Maintain a contiguous range while scanning an array.

  • Prefix sums: Precompute cumulative totals for repeated range queries.

  • Kadane’s algorithm: Find the maximum-sum contiguous subarray in O(n) time.

  • In-place swaps: Rearrange elements using O(1) auxiliary space.

  • Cyclic sort: Place each element at its correct index when the value range is known.

  • Dutch national flag: Partition an array into three groups using one pass.

Common Pitfalls

  • Do not confuse dynamic-array append, which is O(1) amortized, with the worst-case O(n) resize operation.

  • Remember that Python’s list.insert(0, value) and list.pop(0) shift all remaining elements and are O(n); use collections.deque for efficient front insertion or removal.

  • An array access is O(1) only for a valid index. Out-of-range access is an error rather than a successful operation.

  • Decide explicitly whether modifying the input is allowed before using an in-place algorithm.

  • Test empty arrays, single-element arrays, duplicates, negative values, and already sorted inputs.

  • In other languages, account for integer overflow when calculating indices, sizes, or cumulative sums.

6

What is the difference between sparse and dense arrays?

A dense array stores an element at every valid index, conventionally in a contiguous block, whereas a sparse array omits default-valued elements and keeps only meaningful entries together with their indices. Dense storage favors constant-time indexing and sequential access; sparse storage saves space when the number of meaningful elements is much smaller than the logical index range.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Ideas

  • Dense array: Every valid index maps to a stored element. Conventional implementations allocate the elements contiguously, giving constant-time index access and good locality.

  • Sparse array: Missing entries are represented implicitly and read as a chosen default, usually zero or None. The implementation stores non-default values and their indices, so its memory use depends more on the number of stored entries k than on the logical size n.

  • Static versus dynamic: A static array has a fixed capacity; a dynamic array can grow or shrink. Dense versus sparse describes how much of the logical range is populated, so an array can independently be static or dynamic, and dense or sparse.

  • Python list: A Python 3.12 list is a dynamic array. Indexing is O(1), append is amortized O(1), and insertion or deletion in the middle is O(n) because elements must shift. CPython 3.12 uses over-allocation rather than a simple doubling strategy.

Representations and Trade-offs

Common sparse representations include:

  • Dictionary keyed by index: Provides average O(1) lookup and insertion, with O(k) storage under the usual machine-word model.

  • Sorted list of (index, value) pairs: Binary search takes O(log(k + 1)); insertion takes O(k) because existing pairs must shift.

  • Compressed sparse row (CSR): Stores row pointers, column indices, and values. For an m × n matrix with k non-default entries, it uses O(k + m) space rather than O(m × n).

  • Runs or linked blocks: Useful for long regular gaps, such as mostly empty boards or calendars.

For example, [0, 0, 0, 7, 0, 0, 0, 0, 3] has n = 9 logical slots but only k = 2 meaningful entries.

Aspect Dense array Sparse array
Stored data One element per valid index Non-default elements plus index metadata
Space O(n) Usually O(k); CSR adds row overhead
Index access O(1) for a valid index Dict: average O(1), worst O(k); sorted pairs: O(log(k + 1))
Iteration O(n) O(k) over stored entries; O(n) over the full logical range
Mutation Assignment O(1); middle insertion or deletion O(n) Dict insertion is amortized average O(1); sorted-pair insertion is O(k)
Locality Usually high Representation-dependent

Time and Space Complexity

  • Dense indexing: Best, average, and worst case are O(1), because the element address is computed directly from the base address and index.

  • Dense append: Best case O(1), amortized O(1), and worst case O(n) when the underlying buffer must be copied.

  • Dense middle insertion or deletion: Best, average, and worst case are O(n), because a suffix must shift.

  • Dictionary lookup: Best and average O(1), but worst O(k) if many keys collide. Insertion is amortized average O(1), with a worst case of O(k).

  • Sparse storage: Dense O(n) versus sparse O(k), assuming machine-sized indices. CSR uses O(k + m). These bounds count the array representation itself; any separate source buffer used to construct it is excluded. There is no recursion, so the stack term is O(1).

When to Choose Which

  • Choose dense storage when most positions are meaningful, the index range is manageable, or algorithms benefit from contiguous access and sequential scans. Common patterns include two pointers, sliding windows, prefix sums, Kadane’s algorithm, in-place swaps, cyclic sort, and the Dutch national flag.

  • Choose sparse storage when the logical range is large but only a small fraction is populated, such as a large counter with few touched keys or a mostly empty matrix.

  • For dense 2D data, use matrix[row][col]; an m × n matrix requires O(m × n) space and traversal.

  • When k is close to n, dense storage is usually more space-efficient and simpler. A sparse representation may still be justified when iteration is restricted to stored entries or when direct dense allocation is impractical.

Common Pitfalls and Interview Tips

  • Define whether “sparse” means mostly default values, omitted entries, or a particular library representation before discussing its complexity.

  • State whether an operation mutates or replaces the input; no in-place algorithm is required merely to choose a representation.

  • Distinguish iterating stored entries from scanning the entire logical range.

  • Never construct a dense 2D list with [[0] * n] * m, because the rows are shared. Use [[0] * n for _ in range(m)].

  • Consider empty input, one element, all-default data, all non-default data, duplicate indices, negative values, and already sorted pair lists. Negative values are meaningful unless zero is deliberately chosen as the default.

  • “Sparse Arrays” can also name a frequency-counting problem: for n strings and m queries, a hash-map solution takes O(n + m) time; that is different from the storage concept discussed here.

  • Likely follow-ups include choosing a representation, handling ordered traversal, converting between representations, and multiplying or transposing sparse matrices.

7

What are the pros and cons of keeping an array sorted?

A sorted array is a contiguous, index-addressable sequence whose elements are maintained in a defined order, usually non-decreasing. Sorting makes searching and ordered processing efficient, but middle insertions and deletions remain O(n) because later elements must be shifted.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How a Sorted Array Behaves

  • Static array: A fixed-size block of allocated memory. Its capacity is chosen when it is created, so growth requires allocating a larger array and copying the elements.

  • Dynamic array: Python’s list is a dynamic array. Appending is amortized O(1), although an occasional resize copies the elements and costs O(n).

  • Order invariant: For a non-decreasing array, a[i] <= a[i + 1] after every operation that preserves sorted order.

Operation Best Average Worst Reason
Index a[i] O(1) O(1) O(1) Direct address arithmetic
Binary search O(1) O(log n) O(log n) Each comparison halves the remaining search interval
Append while preserving order O(1) amortized O(1) O(n) A dynamic array may resize and copy
Insert at a specified position O(1) at the end O(n) O(n) Elements after the position are shifted
Delete at a specified position O(1) at the end O(n) O(n) Elements after the position are shifted
Python list.sort() O(n) for an already sorted array or one run O(n log n) O(n log n) Timsort exploits runs and merges them efficiently
Merge two sorted arrays O(n+m) O(n+m) O(n+m) A two-pointer pass examines each element once

Binary search and two-pointer scans use O(1) auxiliary space. Sorting a copy costs O(n) additional space, and Python’s list.sort() may use O(n) auxiliary memory for Timsort’s temporary storage. A normal merge into a separate result array uses O(n+m) output storage, with O(1) working space beyond that output; an O(1)-space in-place merge requires special constraints. These figures exclude the original input arrays.

Advantages

  • Fast search: Binary search takes O(log n), compared with O(n) for scanning an unsorted array. Python’s bisect module implements this technique.

  • Efficient range processing: bisect_left and bisect_right find boundaries in O(log n), after which processing k matching elements takes O(k).

  • Two-pointer algorithms: Pair-sum, deduplication, and merging can use O(1) auxiliary space. For some tasks, such as pair-sum, an unsorted array instead requires a hash set with O(n) additional space.

  • Linear set operations: Union, intersection, and difference can process two sorted arrays in O(n+m) without hashing.

  • Fast selection after sorting: Minimum, maximum, median, and k-th smallest element are each accessible in O(1) once the array is sorted; the initial sorting cost is separate.

  • Cache-friendly access: Contiguous storage and predictable ordering make sequential traversal efficient.

Disadvantages

  • Expensive middle updates: Insertion and deletion in the middle are O(n) because the remaining elements must be shifted.

  • Poor construction pattern: Repeated middle insertion takes O(n²). Repeatedly appending values and sorting once is preferable when the order permits it.

  • No constant-time key lookup: Membership through binary search takes O(log n), while hash-set membership is O(1) on average.

  • Frequent-update workloads: A balanced search tree is often better for mixed lookup and update workloads; a heap is useful when only minimum or maximum extraction is needed; a hash set is best for membership.

  • Capacity management: Static arrays cannot grow without reallocation, while dynamic arrays occasionally copy all elements during growth.

Need Sorted array Unsorted array Hash set or dictionary
Find one value O(log n) O(n) O(1) average, O(n) worst
Insert at the end O(1) amortized O(1) amortized O(1) average
Insert in the middle O(n) O(n) Not position-based
Delete by value O(log n) search + O(n) shift O(n) O(1) average
Minimum or maximum O(1) O(n) O(n)
Produce sorted output O(n) O(n log n) sort O(n log n) sort

Step-by-Step Example

For [2, 5, 8, 12, 16, 23, 38, 56, 72, 91], search for 23:

  1. Set left = 0, right = 9, and mid = 4. The value is 16, so set left = 5.

  2. Compute mid = 7. The value is 56, so set right = 6.

  3. Compute mid = 5. The value is 23, which is found after three probes. A linear scan of this particular array would make six comparisons; ten is only its worst-case count.

To insert 17, its insertion index is 5, between 16 (index 4) and 23 (index 5). The five elements currently at indices 5 through 9 must each move one position, producing the O(n) update cost.

Interview Tips

  • State the trade-off: O(log n) search and ordered access versus O(n) middle updates.

  • Ask before sorting in place: list.sort() mutates the caller’s list; use sorted() when the original list must remain unchanged.

  • Handle duplicates precisely: bisect_left returns the index of the first equal element, while bisect_right returns the insertion point after all equal elements.

  • Cover edge cases: Empty input, one element, duplicate values, negative numbers, and already sorted input.

  • Clarify linked-list searches: A sorted linked list can support a modified binary-search-like procedure, but ordinary binary search is impractical because midpoint access is O(n), making the total O(n log n).

  • Common follow-ups: Which structure wins when insertions dominate, how pair-sum works with two pointers, and why ordered iteration may require sorting a hash-based collection.

8

Why Choose Heaps Instead of Sorted Arrays?

A heap is usually more suitable than a sorted array when the primary goal is repeatedly accessing or removing the smallest or largest element. It provides fast priority-queue operations while using a compact array-based representation, although sorted arrays are better for ordered searches and traversal.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How the Structures Differ

  • Heap: A complete binary tree stored in an array. In a min-heap, each parent is no greater than its children; the minimum is always at the root.

  • Sorted array: Elements are stored in ascending or descending order, so every element is in its final relative position.

  • Dynamic vs static array: Python’s list is a dynamic array: append is amortized O(1), indexing is O(1), and inserting or deleting in the middle is O(n). A static array has fixed capacity, so appending may require an O(n) resize.

  • Partial ordering: A heap guarantees ordering only between a node and its parent/children. It does not keep all elements globally sorted.

Complexity Comparison

Operation Min/Max heap Sorted array
Access minimum or maximum O(1) O(1)
Insert an element O(log n) worst; O(1) best when no sift is needed O(n) average and worst for middle insert; amortized O(1) at the end of a dynamic array
Remove minimum or maximum O(log n) O(n) when removing from the beginning of an ascending array; O(1) from the end of a dynamic array
Search for a specific value O(1) best (root); O(n) average and worst O(1) best (middle); O(log n) average and worst using binary search
Build from unsorted input O(n) with heapify O(n) best for already-sorted adaptive sort; O(n log n) average and worst comparison sort
Traverse in sorted order Not supported efficiently O(n)
Auxiliary space O(1) for in-place operations O(1) for in-place operations, excluding sorting overhead

The O(n) storage counts the n elements themselves; auxiliary space excludes the input. Heap insertion and removal restore order along one tree path, O(log n), while a sorted array must shift elements to preserve global ordering.

Main Advantages

  • Efficient priority access: A min-heap supports extracting the smallest element in O(log n) time.

  • Cheaper updates than a sorted array: Inserting into a heap generally moves an element along one tree path, while inserting into a sorted array can require shifting many elements.

  • Compact representation: The heap is stored in a dynamic array, avoiding separate node objects and pointer overhead.

  • Fast batch construction: Bottom-up heap construction is O(n), making heaps effective when many items are loaded before processing begins.

  • Suitable for scheduling: Priority queues, Dijkstra’s algorithm, merge operations, and task schedulers commonly need repeated minimum or maximum extraction rather than arbitrary sorted lookup.

When a Sorted Array Is Better

A sorted array is preferable when the application requires:

  • Binary search for an arbitrary key.

  • Iteration in ascending or descending order.

  • Finding the next or previous element.

  • Range queries over sorted values.

  • Simple duplicate handling or stable ordered storage.

Therefore, heaps are not universally superior. They optimize priority-queue operations, while sorted arrays optimize searching and ordered access.

Small Example

Suppose the values are inserted in the order 7, 3, 9.

  1. A min-heap starts as [7].

  2. Inserting 3 places it at the end and swaps it upward, producing [3, 7].

  3. Inserting 9 leaves it below the smaller root, producing [3, 7, 9].

  4. Removing the minimum reads 3 in O(1), replaces the root with the last element, and sifts it down in O(log n).

The sorted equivalent is [3, 7, 9], but removing 3 requires shifting 7 and 9, taking O(n) time.

Interview Tips

  • Mention that heaps provide only a partial order, not a fully sorted collection.

  • Distinguish O(1) root access from O(log n) insertion and root removal.

  • State that heap storage is O(n) total, with O(1) auxiliary space for in-place operations and no recursion stack.

  • Explain that Python’s heapq implements a min-heap; negate values to simulate a max-heap.

  • Test edge cases: empty structure, one element, duplicates, negative values, and already sorted input. For an empty heap, extraction is invalid; for one element, no sift is needed; duplicates and negative values are handled normally.

  • When discussing alternatives, emphasize that a sorted array wins for binary search and ordered traversal.

9

How does array indexing work in memory?

Array indexing works by computing an element’s memory address arithmetically from the array’s base address and the index, so any element can be read or written in constant time — this is called random (direct) access.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How Indexing Works

A static array occupies one contiguous block of memory, and every slot has the same fixed size s bytes. The address of element i is:

address(i) = base + i * s

Because the compiler or interpreter performs one multiplication and one addition, indexing does not scan memory. That is why arr[0] and arr[999999] cost the same, while finding a value by content still requires a linear scan.

  1. values = [10, 20, 30, 40, 50] is created.

  2. In CPython the list object holds a contiguous array of pointers; each pointer is 8 bytes on a 64-bit build.

  3. Suppose the pointer block starts at address 1000. Then values[3] lives at 1000 + 3 * 8 = 1024.

  4. The interpreter loads the pointer at 1024 and follows it to the int object holding 40 — still O(1).

Python adds a convenience: a negative index -k is translated to len(array) - k, so values[-1] reads the last element. This is still a single arithmetic step, not a scan.

Static vs Dynamic Arrays

  • Static array (C arrays): fixed capacity, values stored inline, element size known at compile time. Indexing is a raw address computation. Python’s array module (array('i')) also stores values inline and contiguously, but it is resizable.

  • Dynamic array (Python list): a resizable buffer of references to objects. Appending usually writes to the next free slot — amortized O(1) — but when the buffer is full it allocates a larger block and copies every pointer, which is O(n). Indexing stays O(1) throughout, because the buffer is always contiguous and the base pointer is updated after a resize.

Operation Static array Python list (dynamic array)
Read/write arr[i] O(1) O(1)
Append at end not applicable (fixed) amortized O(1)
Insert/delete in the middle O(n) shift O(n) shift
Search by value O(n) O(n)
Extra space none up to ~2x capacity slack

Row-Major Order for 2D Arrays

A 2D array is one contiguous block sliced into rows. With rows x cols elements, the address of matrix[row][col] is:

base + (row * cols + col) * element_size

Rows are laid out one after another, so scanning a row is cache-friendly while jumping down a column is not. Complexity is stated as O(m * n) for the whole matrix.

Complexity

  • Index access: O(1) time, best/average/worst identical, because the address is computed directly — no dependence on n.

  • Access space: O(1) auxiliary; the input array is not counted as extra space.

  • Slicing arr[l:r]: O(k) time and O(k) extra space for k = r - l, because Python copies references into a new list.

  • Search by value: O(n) time, O(1) space — worst and average.

Common Pitfalls

  • Off-by-one: valid indices are 0 to len(arr) - 1; arr[len(arr)] raises IndexError.

  • Assuming negative indexing is universal: Python and Ruby allow arr[-1]; C, Java and Go do not — they throw or read garbage.

  • Shared rows: [[0] * cols] * rows creates rows references to the same inner list, so writing one cell changes a whole column.

  • Confusing O(1) indexing with O(1) search: looking up a value or an unsorted key still needs O(n).

  • Forgetting slicing copies: arr[:] is O(n) time and space, unlike indexing one element.

  • Mutating the input: in-place indexing swaps (two pointers, Dutch national flag) change the caller’s array — confirm with the interviewer that this is allowed, otherwise copy first.

  • Interview follow-ups: why is append amortized O(1), what happens to existing references during a resize, and how would you index a ragged list or a sparse matrix differently.

10

How do you merge two sorted arrays into one sorted array?

Two-pointer merge combines two arrays already sorted in non-decreasing order by repeatedly selecting the smaller of their current elements. It runs in linear time and does not modify either input array.

Read full answer

Applies toPython 3.12

How the Merge Works

Maintain one pointer in each input array:

  1. Compare the elements at both pointers.

  2. Add the smaller element to the result and advance that array’s pointer.

  3. Continue until one array is exhausted.

  4. Append the remaining elements from the other array.

Choosing the left element when values are equal preserves the left element’s relative position, which is useful for stable merges.

Python lists are dynamic arrays: indexing is O(1), appending is amortized O(1), and inserting or deleting in the middle is O(n). The implementation below preallocates the result list to avoid repeated resizing.

The inputs remain unchanged. The same algorithm could write directly into a preallocated destination when modifying a separate array is allowed.

Complexity

Let n and m be the input lengths and k = n + m.

Approach Best Time Average Time Worst Time Space
Two-pointer merge O(k) O(k) O(k) O(k) for output, O(1) auxiliary
Concatenate and generically sort O(k log k) O(k log k) O(k log k) O(k)
  • Time: Every input element is examined once, and initializing the result takes O(k).

  • Auxiliary space: O(1) beyond the returned result.

  • Output space: O(k).

  • Input space: The two inputs are not counted.

  • Recursion stack: O(1) because the algorithm is iterative.

The sort comparison uses general comparison-sort bounds. Python’s sorted may perform better because its adaptive algorithm can detect presorted runs.

Edge Cases

  • Empty input: If either list is empty, the result contains the other list’s elements.

  • One element: The result is the single non-empty element.

  • Duplicates: Equal values appear once per occurrence.

  • Negative numbers: Comparisons work normally.

  • Already sorted input: No special processing is required.

  • Unsorted input: The algorithm cannot guarantee a sorted result unless the inputs are sorted first.

Example Walkthrough

Merge [1, 2, 5] with [2, 3, 8]:

  1. Compare 1 and 2; add 1.

  2. Compare 2 and 2; add the left 2.

  3. Compare 5 and 2; add 2.

  4. Compare 5 and 3; add 3.

  5. Compare 5 and 8; add 5.

  6. The right array remains; add 8.

The result is [1, 2, 2, 3, 5, 8].

Code Example

def merge_sorted_arrays(left: list[int], right: list[int]) -> list[int]:
    """Merge two non-decreasing integer lists without modifying the inputs."""
    left_index = 0
    right_index = 0
    merged = [0] * (len(left) + len(right))
    output_index = 0

    while left_index < len(left) and right_index < len(right):
        if left[left_index] <= right[right_index]:
            merged[output_index] = left[left_index]
            left_index += 1
        else:
            merged[output_index] = right[right_index]
            right_index += 1
        output_index += 1

    while left_index < len(left):
        merged[output_index] = left[left_index]
        left_index += 1
        output_index += 1

    while right_index < len(right):
        merged[output_index] = right[right_index]
        right_index += 1
        output_index += 1

    return merged


print(merge_sorted_arrays([1, 2, 5], [2, 3, 8]))
# [1, 2, 2, 3, 5, 8]

Common Pitfalls

  • Off-by-one errors: Use <, not <=, when checking whether an input is exhausted.

  • Lost elements: After one array is exhausted, copy the remainder of the other.

  • Unnecessary mutation: This version returns a new list and leaves both inputs unchanged.

  • Incorrect complexity claims: Reading and writing every element requires O(n + m) time, not O(n) unless one input’s length is known to be zero.

  • Integer overflow: Python integers do not overflow, but implementations using fixed-width integers must ensure the value type can hold every input and output value.

  • Typical follow-up: Interviewers may ask about stable merging, merging more than two arrays with a min-heap, or writing into an existing destination array.

11

How can three stacks share one array in Python?

Three stacks in one array can be implemented by dividing a single fixed-capacity backing array into three contiguous regions. Each stack maintains its own top pointer and size, allowing every push, pop, and peek operation to use direct indexing.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Array Layout and Operations

For a capacity of c per stack, the backing array is divided as follows:

Stack Occupied indices
Stack 0 0 through c - 1
Stack 1 c through 2c - 1
Stack 2 2c through 3c - 1

Each stack stores:

  • Top pointer: the index where its next value will be inserted.

  • Size: the number of values currently stored.

  • Base index: the first index belonging to that stack.

A push writes directly into the stack’s region. A pop reads its current top, clears that position, and decrements the pointer. No values are moved between stacks.

Although Python lists are normally dynamic arrays, this implementation preallocates a fixed logical length and never resizes it. Consequently, stack operations are worst-case O(1) rather than relying on list growth.

Complexity

Let n = 3c be the total capacity of the shared array.

Operation Best Average Worst Reason
push O(1) O(1) O(1) Direct index calculation and assignment
pop O(1) O(1) O(1) Direct access to the stored top index
peek O(1) O(1) O(1) Direct read without modifying storage
is_empty O(1) O(1) O(1) Reads the stack’s size
Initialization O(n) O(n) O(n) Allocates and initializes all n positions
  • Total space: O(n) for the shared backing array.

  • Auxiliary space: O(1) for the top and size metadata.

  • The backing array is part of the data structure’s state, so it is included in total space.

  • No recursion is used, so there is no O(n) recursion stack.

Example Walkthrough

With capacity 2 per stack, the regions are [0, 1], [2, 3], and [4, 5].

Action Stack 1 storage Stack 1 next insertion
Initially Empty 2
Push 100 [100] 3
Push 200 [100, 200] 4
Pop [100] 3
Pop Empty 2

Code Example

from typing import Generic, TypeVar, cast

T = TypeVar("T")
_EMPTY = object()


class ThreeStacks(Generic[T]):
    """Three fixed-capacity LIFO stacks sharing one preallocated array."""

    def __init__(self, capacity_per_stack: int) -> None:
        if capacity_per_stack < 1:
            raise ValueError("capacity_per_stack must be at least 1")

        self._capacity = capacity_per_stack
        self._storage: list[object] = [_EMPTY] * (3 * capacity_per_stack)

        # Each pointer identifies the next insertion position.
        self._tops = [0, capacity_per_stack, 2 * capacity_per_stack]
        self._sizes = [0, 0, 0]

    def _validate_index(self, stack_index: int) -> None:
        if stack_index not in range(3):
            raise IndexError("stack_index must be 0, 1, or 2")

    def push(self, stack_index: int, value: T) -> None:
        self._validate_index(stack_index)

        next_position = self._tops[stack_index]
        region_end = (stack_index + 1) * self._capacity

        if next_position >= region_end:
            raise IndexError(f"stack {stack_index} is full")

        self._storage[next_position] = value
        self._tops[stack_index] = next_position + 1
        self._sizes[stack_index] += 1

    def pop(self, stack_index: int) -> T:
        self._validate_index(stack_index)

        if self.is_empty(stack_index):
            raise IndexError(f"stack {stack_index} is empty")

        top_position = self._tops[stack_index] - 1
        value = cast(T, self._storage[top_position])

        self._storage[top_position] = _EMPTY
        self._tops[stack_index] = top_position
        self._sizes[stack_index] -= 1

        return value

    def peek(self, stack_index: int) -> T:
        self._validate_index(stack_index)

        if self.is_empty(stack_index):
            raise IndexError(f"stack {stack_index} is empty")

        return cast(T, self._storage[self._tops[stack_index] - 1])

    def is_empty(self, stack_index: int) -> bool:
        self._validate_index(stack_index)
        return self._sizes[stack_index] == 0


stacks = ThreeStacks[int](capacity_per_stack=2)
stacks.push(1, 100)
stacks.push(1, 200)
print(stacks.pop(1))  # 200

Common Pitfalls

  • Off-by-one errors: Define the top pointer consistently as either the last occupied index or the next insertion index. This implementation uses the next insertion index.

  • Boundary violations: Every push and pop must check that it stays within the selected stack’s region.

  • Empty or full stacks: Popping or peeking an empty stack and pushing to a full stack should raise a clear IndexError.

  • Shared-storage mistakes: Do not use separate lists, and do not allow one stack to overwrite another stack’s region.

  • Input mutation: The shared backing array is modified in place, but the caller’s value objects are not mutated.

  • Value edge cases: Duplicate and negative values are valid stack elements. A one-element stack works normally.

  • Irrelevant cases: Sorted input, disconnected graphs, and cycles have no special meaning for stack operations.

A common interview follow-up is how to support unequal capacities or allow one nearly full stack to borrow unused space from another. The fixed-partition design is simpler, predictable, and keeps every operation strictly O(1).

12

How do you rotate an array, and what are its applications?

Array rotation cyclically shifts elements by a specified number of positions without discarding any elements. A right rotation by k moves the last k elements to the front; it can be implemented efficiently with three in-place reversals in O(n) time and O(1) auxiliary space.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Rotation Methods

For an array of length n:

  • Right rotation by k: move the last k elements to the front.

  • Left rotation by k: move the first k elements to the end.

  • Normalized rotation amount: use k % n, so rotating by n positions leaves the array unchanged.

  • Slicing approach: values[-k:] + values[:-k] creates a rotated copy after normalizing k to the range 0 through n - 1.

  • Three-reversal approach: reverse the entire array, reverse the first k elements, then reverse the remaining elements.

The three-reversal method preserves the cyclic ordering while avoiding a second array.

Complexity and Array Representation

Approach Time Auxiliary space Mutates input When to use
Slicing and concatenation O(n) because it copies all elements O(n) for the slices and result No Simple Python code where memory is available
Three reversals O(n) because it performs a linear number of swaps O(1) using only a few indexes Yes In-place rotation with limited memory
Repeated single-position shifts O(nk) for k > 0 because each of the k shifts costs O(n); O(1) for k = 0 O(1) because it reuses the input Yes Educational use; generally inefficient

For the three-reversal approach, the best, average and worst cases are all O(n) for a nontrivial rotation because each element is swapped a constant number of times. A rotation of zero positions returns immediately in O(1).

Auxiliary space excludes the input array. The reversal implementation uses O(1) extra space, including an O(1) call stack because it is iterative.

A static array has a fixed capacity, so rotation usually requires rearranging elements in place or copying them into another fixed-size array. A Python list is a dynamic array: indexing is O(1), append is amortized O(1), and inserting or deleting in the middle is O(n).

Step-by-Step Example

Rotate [1, 2, 3, 4, 5] right by 2:

Step Array
Reverse the entire array [5, 4, 3, 2, 1]
Reverse the first two elements [4, 5, 3, 2, 1]
Reverse the remaining elements [4, 5, 1, 2, 3]

Applications

  • Circular buffers: Represent logical queue positions using (head + offset) % capacity instead of physically moving elements.

  • Round-robin scheduling: Rotate through processes, workers or tasks in repeating order.

  • Signal and image processing: Cyclic shifts are used in convolution and circular-correlation algorithms.

  • Rotated sorted-array searches: Binary-search variants identify the sorted half of an array that was rotated at an unknown pivot.

  • Offset-based indexing: Store a start or pivot index and access elements cyclically, avoiding repeated data movement.

Code Example

def rotate_array(values: list[int], k: int) -> None:
    """Rotate values right by k positions in place."""
    length = len(values)

    if length < 2:
        return

    k %= length
    if k == 0:
        return

    def reverse_range(start: int, end: int) -> None:
        while start < end:
            values[start], values[end] = values[end], values[start]
            start += 1
            end -= 1

    reverse_range(0, length - 1)
    reverse_range(0, k - 1)
    reverse_range(k, length - 1)


numbers = [1, 2, 3, 4, 5]
rotate_array(numbers, 2)
print(numbers)  # [4, 5, 1, 2, 3]

Common Pitfalls

  • Skipping normalization: Always use k % n; otherwise, a large rotation may access invalid positions.

  • Using k = 0 directly with negative slicing: values[-0:] has special semantics, so handle k == 0 explicitly.

  • Unexpected mutation: The reversal implementation changes the input. Use slicing or copy the list when mutation is not allowed.

  • Off-by-one errors: Reversal boundaries are inclusive, and the final reversal begins at index k.

  • Ignoring edge cases: Empty and one-element arrays remain unchanged. Duplicates and negative elements need no special handling. Negative k is normalized by Python’s k % length. Already sorted input also needs no special handling, although a nontrivial rotation can make the result unsorted.

  • Overflow concerns: Python integers do not overflow, but fixed-width languages must safely calculate length - k and related offsets.

  • Interview follow-ups: Common questions ask for a left rotation, rotation without extra memory, circular indexing, or searching a rotated sorted array.

13

How do you reverse an array in place in Python?

Reversing an array in place means modifying the original list without allocating a new one, typically using a two-pointer approach. This technique swaps elements from both ends and moves toward the center until the list is reversed.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

  • Initialize pointers: left at the start (index 0) and right at the end (index len(arr) - 1).

  • Swap elements: While left is less than right, swap the elements at these indices.

  • Move pointers: Move left forward and right backward.

  • Repeat: Repeat until the pointers meet or cross, which means the array is fully reversed.

Complexity

  • Time: O(n) best, average, and worst case. Each element is visited once, and the number of swaps is n/2.

  • Space: O(1) auxiliary. Only a constant amount of extra memory is used for the pointers. The input list itself is not counted as extra space.

Edge Cases

  • Empty list: The loop does not execute, leaving the list unchanged.

  • Single element: The loop does not execute, leaving the list unchanged.

  • Already reversed: The algorithm still performs the swaps, but the result is the same.

  • Duplicates and negative numbers: The algorithm works regardless of values, as it only swaps positions.

Step-by-Step Walkthrough

Example: arr = [1, 2, 3, 4, 5]

Step left right arr before swap Action arr after swap
1 0 4 [1, 2, 3, 4, 5] swap arr[0] and arr[4] [5, 2, 3, 4, 1]
2 1 3 [5, 2, 3, 4, 1] swap arr[1] and arr[3] [5, 4, 3, 2, 1]
3 2 2 [5, 4, 3, 2, 1] left == right, stop [5, 4, 3, 2, 1]

Code Example

def reverse_array_in_place(arr: list[int]) -> None:
    """Reverse the input list in place using the two-pointer technique.

    Args:
        arr: The list to reverse. Modified in place.
    """
    left, right = 0, len(arr) - 1
    while left < right:
        arr[left], arr[right] = arr[right], arr[left]
        left += 1
        right -= 1

# Example call:
# reverse_array_in_place([1, 2, 3, 4, 5])  # Output: [5, 4, 3, 2, 1]

Common Pitfalls

  • Off-by-one errors: Ensure the loop condition is left < right, not left <= right, which would cause an unnecessary swap or index error.

  • Creating a copy: Using slicing like arr = arr[::-1] creates a new list, which is not in-place.

  • Mutating input: Always confirm the interviewer allows modification of the input list; if not, you must return a new list.

14

How do you remove duplicates from a sorted array in place?

Use the two-pointer algorithm to overwrite the array with its unique values while using only constant auxiliary space. The array must already be sorted, and the input is modified in place.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

Maintain two indexes:

  • read scans every element in the array.

  • write marks the next position where a unique value should be stored.

For each value read, compare it with the last unique value at write - 1. If they differ, copy the value to values[write] and advance write.

Because the input is sorted, equal values occur consecutively. Therefore, comparing against the last stored unique value is sufficient; a set or hash table is unnecessary.

After the scan:

  • values[0:write] contains the unique values.

  • write is the number of unique elements.

  • Elements from write onward may still contain old values and should be ignored.

Complexity

Case Time Reason
Best O(n) The entire array is scanned once.
Average O(n) The entire array is scanned once.
Worst O(n) The entire array is scanned once.
  • Auxiliary space: O(1). Only a fixed number of indexes are used.

  • Input storage: O(n) for the array itself, which is not counted as auxiliary space.

  • Recursion stack: O(1), because the algorithm is iterative.

The same algorithm works for static and dynamic arrays. A Python list is a dynamic array: indexing is O(1), append is amortized O(1), and insertion or deletion in the middle is O(n). This algorithm does not append or insert elements, so it avoids those costs.

Example Walkthrough

For [1, 1, 2, 2, 3, 3]:

read write Compared values Action
1 1 1 and 1 Skip duplicate
2 1 2 and 1 Store 2; write becomes 2
3 2 2 and 2 Skip duplicate
4 2 3 and 2 Store 3; write becomes 3
5 3 3 and 3 Skip duplicate

The first three positions become [1, 2, 3], and the function returns 3.

Code Example

def remove_duplicates_in_place(values: list[int]) -> int:
    """Remove duplicates from a sorted list in place and return its unique length."""
    if not values:
        return 0

    write = 1

    for read in range(1, len(values)):
        if values[read] != values[write - 1]:
            values[write] = values[read]
            write += 1

    return write


numbers = [1, 1, 2, 2, 3, 3]
unique_length = remove_duplicates_in_place(numbers)

print(unique_length)       # Expected output: 3
print(numbers[:unique_length])  # Expected output: [1, 2, 3]

Common Pitfalls

  • Empty input: Return 0 before accessing the first element.

  • One element: The loop does not run, and the function correctly returns 1.

  • Duplicates: Consecutive duplicates are skipped.

  • Negative numbers: The algorithm works because it relies on equality and sorted order, not value magnitude.

  • Already unique input: Every element is copied to the same or an earlier position, and the returned length equals the original length.

  • Unsorted input: The algorithm does not remove every duplicate because nonadjacent equal values may not be compared correctly.

  • Input mutation: The function modifies the original list. Only use it when the caller permits in-place modification.

  • Result interpretation: Return the new length rather than deleting the tail, since removing elements from a Python list’s middle would cost O(n).

15

How do you implement a queue using an array?

A queue can be implemented with a fixed-capacity circular array, commonly called a circular buffer. It keeps a front index for removals and a size counter, allowing both enqueue and dequeue to run in constant time without shifting elements.

Read full answer

Applies toPython 3.12

How It Works

The array stores queue elements in contiguous slots, but the indices wrap around when they reach the end.

  • front: index of the next element to remove.

  • size: number of elements currently stored.

  • capacity: maximum number of elements the queue can hold.

  • Enqueue: calculate the insertion position with (front + size) % capacity.

  • Dequeue: read the element at front, clear that slot, and advance front circularly.

  • Peek: return the element at front without removing it.

A static array has a fixed allocation size, whereas a Python list is a dynamic array: indexing is O(1), append is amortized O(1), and insertion or deletion in the middle is O(n). This implementation preallocates its slots and never appends to the list, so the queue has a fixed logical capacity and does not incur list-resizing costs.

Only the queue’s internal storage is modified. Enqueued objects are not mutated, and a caller’s collection is not modified in place; such mutation is neither required nor allowed by this implementation’s contract.

Complexity

For a queue with maximum capacity k:

Operation Best Case Average Case Worst Case Reason
Construction O(k) O(k) O(k) Allocates and initializes k slots
enqueue O(1) O(1) O(1) Computes one index and assigns one slot
dequeue O(1) O(1) O(1) Reads one slot and advances an index
peek O(1) O(1) O(1) Reads the front slot
size, is_empty, is_full, capacity O(1) O(1) O(1) Uses stored counters or attributes

The queue uses O(k) auxiliary space, excluding the memory owned by the queued objects. There is no recursion stack. Since the implementation never resizes its storage, its operations do not have amortized complexity.

Example Walkthrough

With capacity 3:

Operation Array Slots front size
Initial [None, None, None] 0 0
Enqueue A ["A", None, None] 0 1
Enqueue B ["A", "B", None] 0 2
Enqueue C ‘[“A”, “B”, “C”] 0 3
Dequeue A ‘[None, “B”, “C”] 1 2
Enqueue D ‘[“D”, “B”, “C”] 1 3

The enqueue of D wraps around to index 0, demonstrating why circular index calculation is necessary.

Code Example

from typing import Generic, TypeVar, cast

T = TypeVar("T")


class ArrayQueue(Generic[T]):
    """Fixed-capacity FIFO queue backed by a circular array."""

    def __init__(self, capacity: int) -> None:
        if capacity <= 0:
            raise ValueError("capacity must be greater than zero")

        self._items: list[object] = [None] * capacity
        self._capacity = capacity
        self._front = 0
        self._size = 0

    @property
    def capacity(self) -> int:
        return self._capacity

    @property
    def size(self) -> int:
        return self._size

    def is_empty(self) -> bool:
        return self._size == 0

    def is_full(self) -> bool:
        return self._size == self._capacity

    def enqueue(self, item: T) -> None:
        if self.is_full():
            raise OverflowError("queue is full")

        rear = (self._front + self._size) % self._capacity
        self._items[rear] = item
        self._size += 1

    def dequeue(self) -> T:
        if self.is_empty():
            raise IndexError("queue is empty")

        item = self._items[self._front]
        self._items[self._front] = None
        self._front = (self._front + 1) % self._capacity
        self._size -= 1

        return cast(T, item)

    def peek(self) -> T:
        if self.is_empty():
            raise IndexError("queue is empty")

        return cast(T, self._items[self._front])


def example() -> None:
    """Demonstrate FIFO order and reuse of a freed circular slot."""
    queue = ArrayQueue[str](3)
    queue.enqueue("A")
    queue.enqueue("B")
    queue.enqueue("C")

    print(queue.dequeue())
    print(queue.peek())
    print(queue.size)

    queue.enqueue("D")  # Reuses index 0 after A was removed.
    print(queue.peek())
    print(queue.dequeue())


if __name__ == "__main__":
    example()  # Expected output: A, B, 2, B, B

Common Pitfalls

  • Using pop(0): Removing the first Python list element is O(n) because the remaining elements shift.

  • Forgetting modulo arithmetic: The index must wrap around to reuse freed slots.

  • Incorrect empty or full checks: Use size == 0 for empty and size == capacity for full; inspecting slots alone is insufficient.

  • Confusing FIFO and LIFO: A queue removes the oldest inserted element; a stack removes the newest.

  • Ignoring capacity limits: This implementation raises OverflowError when full. An unbounded queue can use a dynamic list with an index-based head and occasional compaction.

  • Edge values: A one-element queue dequeues that element normally; duplicates and negative values are ordinary items and preserve FIFO order.

  • Mutating inserted objects: The queue stores references and does not copy or mutate the referenced objects.

  • Production use: Prefer collections.deque for ordinary application code unless an array-backed implementation is specifically required.

16

Check whether parentheses in a string are balanced

A string containing only ( and ) is balanced when every closing parenthesis has a preceding unmatched opening parenthesis, and no opening parentheses remain unmatched. Because only one parenthesis type is involved, a counter provides a linear-time, constant-space solution without needing a stack.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

Maintain an integer depth representing the number of unmatched opening parentheses:

  • On (, increment depth.

  • On ), decrement depth.

  • If depth becomes negative, a closing parenthesis appeared without a matching opening parenthesis, so return False immediately.

  • After processing the string, return True only if depth == 0.

For example, (()()) is balanced: the counter never becomes negative and finishes at zero. In contrast, )( becomes negative at the first character.

Complexity

Let n be the string length.

  • Best case: O(1) when an unmatched closing parenthesis is found immediately.

  • Average case: O(n) because the string is scanned once.

  • Worst case: O(n) because every character may need to be inspected.

  • Auxiliary space: O(1) for one counter. The input string is not counted, and there is no recursion stack.

The solution does not modify the input and is safe to use when mutation is prohibited.

Code Example

def is_balanced(text: str) -> bool:
    """Return whether all '(' and ')' characters are correctly balanced."""
    depth = 0

    for character in text:
        if character == "(":
            depth += 1
        elif character == ")":
            depth -= 1
            if depth < 0:
                return False

    return depth == 0


print(is_balanced("(()())"))  # True
print(is_balanced("(()"))     # False
print(is_balanced(")("))      # False
print(is_balanced(""))        # True

This implementation treats only ( and ) as structural characters; other characters are ignored. If strings can contain multiple bracket types such as (), [], and {}, a stack is normally required to ensure each closing bracket matches the most recent opening bracket.

Example Walkthrough

For "(()())":

Character depth after processing Meaning
( 1 One opening parenthesis is unmatched
( 2 Two opening parentheses are unmatched
) 1 One pair is closed
( 2 Another opening parenthesis is unmatched
) 1 One pair is closed
) 0 All opening parentheses are closed

The final depth is 0, so the string is balanced.

Common Pitfalls

  • Checking only the final count: )( also ends with a count of zero, but it is invalid. Rejecting as soon as the count becomes negative prevents this.

  • Off-by-one errors: The counter represents unmatched openings, so increment before processing nested structures and decrement for every closing parenthesis.

  • Empty input: By the standard definition, the empty string is balanced.

  • Single or unmatched parentheses: A lone ( or ) is not balanced.

  • Multiple bracket types: A single counter cannot validate [] and {}; use a stack for that requirement.

  • Common follow-up: Explain why no stack is necessary when validating only one parenthesis type and how the solution would change for multiple bracket types.

17

How do you find the longest consecutive sequence in an unsorted array?

The optimal approach inserts every element into a hash set and, for each value that has no predecessor (value - 1) in the set, walks upward counting the run; since each element is visited at most once by the counting walk, the whole scan is O(n) average time and O(n) extra space.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

The key insight: a value can only be the start of a consecutive run if value - 1 is not present. Checking that guard means the inner walk never re-scans a run, so the total work stays linear instead of quadratic.

  1. Build a set from the array, which removes duplicates and gives O(1) average membership tests.

  2. Iterate over the set (not the list, so duplicates are skipped).

  3. Skip any value whose predecessor value - 1 is also in the set — it is inside a run that another start will cover.

  4. Otherwise expand upward: length = 1, then keep testing value + length until it is missing.

  5. Track the maximum length seen and return it.

Step-by-Step Trace

Input [100, 4, 200, 1, 3, 2], set {1, 2, 3, 4, 100, 200}:

value value - 1 in set? action run found longest
1 no (0) count up 1, 2, 3, 4 → 4 4
2 yes (1) skip — 4
3 yes (2) skip — 4
4 yes (3) skip — 4
100 no (99) count up 100 → 1 4
200 no (199) count up 200 → 1 4

Approach Comparison

Approach Time Space When to use
Brute force (scan all, search with in list) O(n²) O(1) Never in an interview; only as the baseline you improve on
Sort, then scan adjacent pairs O(n log n) O(1) if in-place sort allowed, else O(n) Input may be sorted in place, or you need a streaming-friendly answer
Hash set with start guard O(n) average, O(n²) worst case under pathological hash collisions O(n) The expected answer

The set approach is average O(n) because membership tests rely on good hashing; adversarial collisions degrade lookups to O(n). Space O(n) is the set itself — the input array is not counted, and it is not modified, since set(numbers) copies.

Code Example

def longest_consecutive_sequence(numbers: list[int]) -> int:
    """Return the length of the longest run of consecutive integers."""
    if not numbers:                     # empty input -> no sequence
        return 0

    values = set(numbers)               # dedupe + O(1) average lookups
    longest = 0

    for value in values:
        if value - 1 in values:         # not the start of a run -> skip
            continue

        length = 1
        while value + length in values: # expand the run upward
            length += 1
        longest = max(longest, length)

    return longest


print(longest_consecutive_sequence([100, 4, 200, 1, 3, 2]))  # 4  -> 1, 2, 3, 4
print(longest_consecutive_sequence([1, 1, 1, 1]))            # 1  (duplicates)
print(longest_consecutive_sequence([-2, -1, 0, 1]))          # 4  (negative numbers)

Edge Cases

  • Empty array: returns 0; guard before building the set.

  • Single element: returns 1, because that element has no predecessor.

  • Duplicates: collapse in the set, so they never inflate a run or cause double counting.

  • Negative numbers and zero: work unchanged, since the logic is arithmetic, not indexing.

  • Already sorted or reversed input: no special handling; the set removes any ordering.

  • Huge single run (e.g. 1..n): fine, because only the start triggers the walk.

Common Pitfalls

  • Forgetting the start guard: iterating every value and counting upward from each gives O(n²) on a long run — the exact thing the guard prevents.

  • Mutating the input: sorting in place would modify the caller’s array; say explicitly whether that is allowed, and use sorted(numbers) if it is not.

  • Counting from the wrong direction: expanding both down and up without the guard double counts.

  • Using range(min, max) to test membership: O(max - min) explodes on sparse input such as [1, 10**9].

  • Follow-up questions: “What if the array doesn’t fit in memory?” (sort chunks externally, or sort the stream), “Return the sequence itself, not just its length”, and “What if the numbers were sorted?” — then a single O(n) pass over adjacent pairs is enough.

18

How do you find the Kth largest element in an array?

The Kth largest element is the value at position k when the array is sorted in descending order, with duplicates counted separately. A randomized quickselect finds it in expected O(n) time and O(1) auxiliary space by partitioning the array and continuing only in the range containing the target rank.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How Quickselect Works

Quickselect converts the requested rank into an index in ascending order:

target_index = n - k

For example, the third-largest element in a six-element array has ascending index 6 - 3 = 3.

Each iteration:

  1. Selects a random pivot.

  2. Partitions the active range into values smaller than, equal to, and greater than the pivot.

  3. Determines which partition contains target_index.

  4. Discards the other partitions.

The implementation uses an iterative three-way partition, which handles duplicate values efficiently.

Approach Comparison

Approach Best Time Average Time Worst Time Auxiliary Space Mutates Input
Sort descending O(n log n) O(n log n) O(n log n) O(n) No, when using sorted()
Randomized quickselect O(n) O(n) expected O(n²) O(1) Yes
Fixed-size min-heap O(n log(k + 1)) O(n log(k + 1)) O(n log(k + 1)) O(k) No
  • Quickselect is preferred when only the ranked value is needed and the input may be modified.

  • Sorting is simpler and appropriate when the entire sorted order is required.

  • A heap is useful for streaming data or maintaining the largest k elements under memory constraints.

Quickselect’s worst case occurs when pivots repeatedly create highly unbalanced partitions. Randomization makes this case extremely unlikely.

Example Walkthrough

For values = [7, 3, 5, 2, 6, 4] and k = 3:

  1. The descending order is [7, 6, 5, 4, 3, 2], so the target is 5.

  2. The zero-based ascending target index is 6 - 3 = 3.

  3. In one possible partition using pivot 5:

  4. Smaller values: [2, 3, 4]

  5. Equal values: [5]

  6. Greater values: [6, 7]

  7. Target index 3 falls in the equal partition, so the answer is 5.

Code Example

from random import randrange


def kth_largest(values: list[int], k: int) -> int:
    """Return the one-based kth largest value, counting duplicates; mutates values."""
    if not 1 <= k <= len(values):
        raise ValueError("k must be between 1 and the number of elements")

    target_index = len(values) - k
    left, right = 0, len(values) - 1

    while left <= right:
        pivot_index = randrange(left, right + 1)
        pivot = values[pivot_index]

        lower = left
        current = left
        upper = right

        # Three-way partition: smaller, equal, and greater than the pivot.
        while current <= upper:
            if values[current] < pivot:
                values[lower], values[current] = values[current], values[lower]
                lower += 1
                current += 1
            elif values[current] > pivot:
                values[current], values[upper] = values[upper], values[current]
                upper -= 1
            else:
                current += 1

        if target_index < lower:
            right = lower - 1
        elif target_index >= current:
            left = current
        else:
            return values[target_index]

    raise RuntimeError("Unable to select the requested rank")


values = [3, 2, 1, 5, 6, 4]
print(kth_largest(values, 2))  # 5

Common Pitfalls

  • Off-by-one errors: k is one-based, while target_index = n - k is zero-based.

  • Duplicate semantics: This implementation counts duplicates. Finding the kth distinct largest value requires different logic.

  • Invalid input: Empty arrays, k = 0, and k > n raise ValueError.

  • Unexpected mutation: Quickselect rearranges the original list. Use values.copy() if mutation is not allowed.

  • Integer overflow in Java or C++: Ensure that both rank calculations and index types can represent the array size.

  • Negative or sorted values: Comparisons work unchanged; negative values and already sorted input require no special handling.

Interview Tips

Explain that quickselect is the randomized selection variant of quicksort: it partitions only once per iteration and does not sort both sides. Common follow-up questions ask how to find the kth smallest element, handle distinct ranks, avoid input mutation, or maintain the largest k values from a stream.

The space complexity is O(1) auxiliary space because the implementation is iterative and has no recursion stack. Input storage is not included in auxiliary space; counting the input itself gives O(n) total storage.

19

How to perform binary search on a sorted array?

Binary search finds a target value in a sorted array by repeatedly comparing it with the middle element and discarding the half that cannot contain the target. It requires random-access indexing and a sorted array, usually in ascending order.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

  1. Initialize two pointers: left at the first element and right at the last element.

  2. Calculate the middle index using left + (right - left) // 2.

  3. Compare the middle element with the target:

  4. If they are equal, return the middle index.

  5. If the middle element is smaller, move left to middle + 1.

  6. If the middle element is larger, move right to middle - 1.

  7. Continue until the search interval becomes empty.

The search works because the sorted order tells us which half can be eliminated. The returned index may be any occurrence when duplicates exist.

Conceptually, the structure is a sorted random-access array. Python lists are dynamic arrays, but they still provide constant-time indexing, which allows binary search to run in logarithmic time.

Complexity

Case Time Reason
Best O(1) The target is found at the first middle position.
Average O(log n) Each comparison reduces the remaining search interval by about half.
Worst O(log n) The target is absent or found near the end of the search path.
  • Auxiliary space: O(1), because only a few variables are used.

  • Input storage: O(n), if the input array itself is counted.

  • The implementation below does not modify the input array.

Example Walkthrough

Search for 7 in [1, 3, 5, 7, 9, 11]:

  1. left = 0, right = 5; middle index 2 contains 5. Since 5 < 7, set left = 3.

  2. left = 3, right = 5; middle index 4 contains 9. Since 9 > 7, set right = 4.

  3. left = 3, right = 4; middle index 3 contains 7. The target is found at index 3.

Code Example

def binary_search(values: list[int], target: int) -> int | None:
    """Return an index of target in a sorted list, or None if it is absent."""
    left, right = 0, len(values) - 1

    while left <= right:
        middle = left + (right - left) // 2

        if values[middle] == target:
            return middle
        elif values[middle] < target:
            left = middle + 1
        else:
            right = middle - 1

    return None


print(binary_search([1, 3, 5, 7, 9, 11], 7))  # 3
print(binary_search([1, 3, 5, 7, 9, 11], 4))  # None

The code handles an empty list, a one-element list, negative numbers, duplicates, and targets that are absent. Duplicate values do not guarantee a particular matching index; the function returns the first index it encounters during its search.

In Python, bisect_left and bisect_right from the bisect module are efficient alternatives when the list is already sorted. They can also distinguish the first and last possible positions of a duplicated value.

Common Pitfalls

  • Unsorted input: Binary search may return an incorrect result. Sort the array first, or use another algorithm if the data is not ordered.

  • Off-by-one errors: Use left <= right in the loop and update boundaries to middle + 1 and middle - 1.

  • Integer overflow in fixed-width languages: Prefer left + (right - left) // 2 over (left + right) // 2.

  • Duplicate handling: Decide whether any matching index is sufficient, or use bisect_left and bisect_right to find the complete range of duplicates.

  • Mutating input: This version leaves the array unchanged. If you also need the sorted array, sorting it separately costs O(n log n) time.

  • Common follow-up: Discuss when binary search is preferable to a linear scan. Use binary search for repeated lookups in a sorted random-access structure; use linear search for unsorted data or a single pass.

20

How do you implement heap sort on an array?

Heap sort sorts an array in place by first rearranging the elements into a max-heap (a complete binary tree stored in the array, where every parent is ≥ its children), then repeatedly swapping the root—the largest remaining value—to the end of the array and restoring the heap property on the shrinking prefix. Because the heap lives in the array itself and sift_down runs iteratively, it needs only O(1) extra space.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

A binary heap maps onto an array with no pointers: for index i, the left child is 2*i + 1, the right child is 2*i + 2, and the parent is (i - 1) // 2. This works identically on a static array with fixed capacity, such as a C, C++, or Java array, and on a dynamic array such as a Python list, because random access by index is O(1) in both.

A Python list is a dynamic array: indexing is O(1), append is amortized O(1), and inserting or deleting an element in the middle is O(n). Heap sort instead uses indexed reads and writes, so its O(n log n) time does not depend on list appends.

  1. Build a max-heap: call sift_down on every internal node from n // 2 - 1 down to 0. Leaves are already valid heaps, so they are skipped. Building bottom-up costs O(n), not O(n log n).

  2. Extract the maximum repeatedly: swap array[0] with the last element of the current heap, shrink the heap by one, and sift_down the new root over the reduced range. The sorted region grows from the right.

  3. Stop when the heap has one element—the array is sorted.

sift_down pushes a value down by repeatedly swapping it with its larger child until it is ≥ both children or reaches a leaf. It touches one path of height O(log n).

Complexity

Case Time Reason
Best O(n log n) Heap sort does not adapt; even sorted input requires all extractions
Average O(n log n) There are n − 1 extractions, each with an O(log n) sift-down bound
Worst O(n log n) No adversarial input degrades the bound beyond O(n log n)
  • Time: build-heap O(n) + n−1 extractions × O(log n) = O(n log n) overall.

  • Space: O(1) auxiliary with the iterative sift_down below; the input array is not counted. A recursive sift_down would add O(log n) call-stack space.

  • Not stable: equal elements can change relative order; use merge sort when stability matters.

Step-by-Step Walkthrough

Array [4, 10, 3, 5, 1]:

  1. Build heap: sift_down(1)—10 beats children 5 and 1, so no move. sift_down(0)—4 swaps with 10, then with 5—producing [10, 5, 3, 4, 1].

  2. Swap root 10 with last element 1, producing [1, 5, 3, 4, 10]; sift 1 down over indices 0–3, producing [5, 4, 3, 1, 10].

  3. Swap 5 and 1, producing [1, 4, 3, 5, 10]; sift over indices 0–2, producing [4, 1, 3, 5, 10].

  4. Swap 4 and 3, producing [3, 1, 4, 5, 10]; sift over indices 0–1, with no move required.

  5. Swap 3 and 1, producing [1, 3, 4, 5, 10]. The heap now has one element, so sorting is complete.

Code Example

from typing import List


def heap_sort(nums: List[int]) -> List[int]:
    """Sort nums in place in ascending order using heap sort; returns nums."""
    n = len(nums)

    def sift_down(root: int, end: int) -> None:
        """Restore max-heap property for the subtree rooted at root, within [0, end]."""
        while 2 * root + 1 <= end:
            child = 2 * root + 1
            if child + 1 <= end and nums[child] < nums[child + 1]:
                child += 1
            if nums[root] >= nums[child]:
                return
            nums[root], nums[child] = nums[child], nums[root]
            root = child

    # Build a max-heap bottom-up in O(n).
    for start in range(n // 2 - 1, -1, -1):
        sift_down(start, n - 1)

    # Move the maximum to the end of the unsorted prefix in O(n log n).
    for end in range(n - 1, 0, -1):
        nums[0], nums[end] = nums[end], nums[0]
        sift_down(0, end - 1)

    return nums


print(heap_sort([5, 3, 8, 1, 9, 2]))  # [1, 2, 3, 5, 8, 9]
print(heap_sort([]))                  # []
print(heap_sort([7]))                 # [7]

Edge cases handled: the empty list and single element (both loops are empty ranges), duplicates (the >= comparison stops needless swaps), negative numbers, and already-sorted or reverse-sorted input. The function sorts in place, which is normally acceptable for sorting questions; if the caller’s array must be preserved, copy it first with nums = nums.copy().

Common Pitfalls

  • Wrong build-loop range: Start at n // 2 - 1, not n // 2 or n; leaves need no sifting.

  • Sifting past the heap: After each swap, the sorted suffix must be excluded, so sift_down takes a shrinking end; forgetting it corrupts the sorted part.

  • Choosing between equal children: Using < or <= only changes which equal-valued child is selected; neither causes equal elements to be swapped because the nums[root] >= nums[child] check returns first.

  • Forgetting the second phase: Building a heap alone leaves a max-heap, not a sorted array.

  • Assuming adaptivity or stability: Heap sort is O(n log n) even on sorted input and is not stable. It also has poorer cache locality than quicksort despite the same O(n log n) worst-case time.

  • Follow-ups interviewers ask: Bottom-up heap construction running in O(n); heap sort versus heapq (Python’s heapq is a min-heap, so negate values to simulate a max-heap); finding the k largest elements with a size-k min-heap in O(n log(k + 1)); and why sorting by repeatedly removing elements from Java’s PriorityQueue still takes O(n log n).

21

What are the advantages and disadvantages of linked lists over arrays?

A linked list stores elements in separate nodes connected by references, while an array stores elements in contiguous memory. Linked lists give O(1) insertion or deletion once the insertion point or predecessor is known, but arrays provide faster random access, better memory locality, and simpler implementation.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Differences

An array has a fixed number of elements and places them in contiguous memory. A dynamic array, such as Python’s list, automatically grows its capacity when elements are appended.

A linked list consists of nodes containing data and one or more references to neighboring nodes:

  • A singly linked list connects each node to the next node.

  • A doubly linked list also stores a reference to the previous node.

  • The first node is usually called the head, and the last is the tail.

Neither structure changes the logical fact that both store n elements.

Complexity Comparison

Operation Array / Python list Linked List
Access by index O(1) best, average, and worst O(1) best for the head/index 0; O(n) average and worst (O(k) for the kth node)
Search for a value Unsorted: O(1) best, O(n) average and worst. Sorted: O(1) best, O(log n) average and worst with binary search O(1) best if the head matches; O(n) average and worst
Insert at the beginning O(n) for Python list O(1) with a head reference
Insert after a known node O(n) because elements must be shifted O(1) once the node is known
Delete after a known node O(n) because elements must be shifted O(1) once the node is known
Append at the end O(1) amortized for Python list O(1) with a tail reference
Remove from the end O(1) amortized for Python list O(1) only for a doubly linked list with a tail; O(n) for a singly linked list even with a tail
Iteration O(n) best, average, and worst O(n) best, average, and worst

Python’s list.append() is amortized O(1) because occasional capacity growth copies existing elements. The cost of one append may be O(n), but the total cost of n appends is O(n). Operations such as insert(0, value) or pop(0) are O(n) because existing elements must be shifted.

Advantages of Linked Lists

  • Efficient structural changes: Inserting after a known node or deleting after a known predecessor takes O(1) time.

  • No element shifting: Updating references does not require moving the remaining elements.

  • Flexible rearrangement: Nodes can be moved between lists by changing references; intrusive designs with extra link fields can link one node into several lists.

  • Constant-time head operations: Inserting or removing at the head is O(1) with a maintained head reference.

These benefits matter when a program frequently inserts or deletes records after already locating them, such as in some queues, schedulers, or adjacency-list implementations.

Disadvantages of Linked Lists

  • No random access: Accessing the kth element requires following k references, taking O(k) time and O(n) worst-case time.

  • Poor cache locality: Nodes may be allocated separately, so traversal causes more cache misses than scanning a contiguous array.

  • Higher memory overhead: Each node stores data plus one or more references.

  • Extra implementation complexity: Head and tail references, pointer updates, and handling the final node require additional care.

  • Limited use of binary search: Even a sorted linked list cannot support efficient binary search without additional indexing.

Space and Edge Cases

Both structures require O(n) total space when the stored input is included. A linked list has a larger constant factor because every node includes reference fields. An array usually has less per-element overhead.

An iterative traversal uses O(1) auxiliary space for both structures, excluding the input, and does not use a recursion stack. An iterative traversal of an empty structure performs zero visits; a one-element structure performs one visit. Duplicate and negative values do not affect traversal complexity. For an already sorted array, binary search takes O(log n) average and worst time, whereas a linked list still requires O(n) sequential access.

Common Pitfalls

  • Do not confuse having a reference to a linked-list node (reading its data is O(1)) with finding the kth node (O(k), O(n) worst).

  • A singly linked list deletion is O(n) overall if the predecessor must be found; it is O(1) only when the predecessor is already available. A doubly linked list can delete a known node in O(1).

  • Inserting into the middle of Python’s list is O(n), not O(1).

  • Head and tail references make append O(1) in a singly linked list, but removing the tail still requires finding the predecessor, so it remains O(n); a doubly linked list makes tail removal O(1).

  • Avoid list.pop(0) and list.insert(0, value) inside loops because each operation shifts the list and can make the overall algorithm O(n²).

  • In production Python, prefer collections.deque for queue-like behavior rather than implementing a linked list unless custom node behavior is specifically required.

22

How do array-based and linked-list stack implementations compare?

An array-based stack keeps its elements in contiguous storage and tracks the top with an index; a linked-list stack keeps a pointer to the head node as the top. Both are LIFO, but they differ in resize behavior, worst-case latency, memory overhead and cache performance.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How They Work

  • Array-based stack: elements occupy a contiguous block, and top is the index of the last element. Push writes at top + 1; pop reads and removes the last element.

  • Dynamic array: when full, it allocates a larger block, usually double the capacity, copies the existing elements, then writes the new one. Python’s list is a dynamic array: append and pop() at the end are the stack operations, while insert/delete in the middle are O(n).

  • Static array: capacity is fixed. Push is O(1) until full, then it overflows unless the implementation resizes.

  • Linked-list stack: each node stores a value and a next pointer. The top is the head, so push creates a node pointing to the old head, and pop moves the head to head.next. Keeping the top at the tail of a singly linked list would make pop O(n), so the head is the standard choice.

  • Trace: pushing 1, 2, 3 into a dynamic array of capacity 2 gives [1], then [1, 2], then a resize to capacity 4 followed by [1, 2, 3]; popping returns 3. A linked list instead gives head -> 3 -> 2 -> 1; popping returns 3 and leaves head -> 2 -> 1.

Complexity Comparison

Operation Array-based stack, dynamic array Linked-list stack
Push O(1) best/average amortized; O(n) worst on resize O(1) best/average/worst
Pop O(1) best/average/worst O(1) best/average/worst
Peek O(1) O(1)
Search for a value O(1) best if top matches; O(n) average/worst O(1) best if top matches; O(n) average/worst
Space O(n) for elements plus O(n) capacity slack; no recursion stack O(n) for nodes plus O(n) pointer overhead; no recursion stack
  • Push: dynamic-array push is amortized O(1) because resizes are rare; the worst case is O(n) when copying all elements. Linked-list push is O(1) in all cases, though node allocation adds a constant-factor cost.

  • Pop and peek: both are O(1) because neither implementation scans for the top.

  • Space: O(n) for n stored elements. The pushed input values are the stack’s contents, so they are counted; a separate caller input is not counted unless copied in. There is no recursion stack. A dynamic array may reserve up to O(n) extra capacity, and a linked list spends extra memory per node on pointers and allocator metadata.

Memory and Performance Trade-offs

  • Cache locality: array elements are contiguous, so traversal and top operations are cache-friendly. Linked-list nodes are scattered, so pointer chasing is slower in practice.

  • Memory per element: arrays usually have lower overhead. Linked lists typically use one or more pointers per node plus allocation metadata.

  • Worst-case latency: a dynamic array occasionally performs an O(n) resize copy. A linked-list stack avoids that large copy but allocates a node on every push.

  • Fragmentation and allocation: linked lists can grow one node at a time without a large contiguous block; arrays need a contiguous block and may need to reallocate as they grow.

  • Fixed capacity: a static array stack is simple and fast but must handle overflow explicitly.

When to Use Each

  • Use an array-based stack by default: it is simpler, more memory-efficient and faster in practice for most workloads. Python’s list with append and pop() is the standard choice.

  • Use a linked-list stack when strict per-operation worst-case latency matters more than memory overhead and cache locality, for example in some real-time or embedded settings where a large resize pause is unacceptable.

  • Use a static array stack when capacity is known and fixed, such as a small fixed-size undo buffer, and overflow can be rejected safely.

  • Clarify in-place mutation: using an input list itself as the stack modifies that input; copy it first if the caller’s data must remain unchanged.

Common Pitfalls and Interview Tips

  • Do not use list.pop(0) or list.insert(0, x) for a stack; those are O(n). Push and pop at the end only.

  • Check for an empty stack before pop or peek. list.pop() raises IndexError; a linked-list implementation must handle top is None.

  • In a linked-list push, set the new node’s next to the old head before reassigning the head; otherwise the rest of the stack is lost.

  • Do not claim dynamic-array push is O(1) worst case; say O(1) amortized with O(n) worst case on resize.

  • Expect follow-ups such as implementing a min stack, a stack with two queues, balanced-parentheses checking, postfix evaluation, or undo/redo. Interviewers often ask you to compare amortized versus worst-case guarantees.

23

How do dynamic arrays compare with linked lists?

A dynamic array stores elements in a contiguous, resizable buffer, while a linked list stores elements in separate nodes linked by pointers or references. Dynamic arrays give O(1) indexing and better cache locality; linked lists give O(1) insertion or deletion once the relevant node (and, for singly linked deletion, its predecessor) is known.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Differences

Characteristic Dynamic array Linked list
Storage layout Contiguous memory Non-contiguous nodes
Element access by index O(1) O(n); O(1) for the head
Linear search by value O(1) best, O(n) average/worst O(1) best, O(n) average/worst
Insert/delete at an arbitrary index O(n) worst; O(1) at the end O(1) after the node/predecessor is located; locating it is O(n)
Append to the end O(1) amortized O(1) if a tail pointer is maintained
Memory overhead Spare capacity plus small metadata Extra pointer/reference field per node
Cache locality Excellent Usually poor

The input itself contains n elements and is counted as O(n) space in both structures. Dynamic arrays may reserve spare capacity, while linked lists require extra metadata per node. Neither comparison uses a recursion stack.

Complexity Details

  • Dynamic-array indexing: O(1) best, average and worst because the address is computed from the buffer base and index.

  • Dynamic-array linear search: O(1) best if the first element matches; O(n) average and worst because up to every element may be inspected. If the array is sorted, binary search is O(log n) average and worst, O(1) best.

  • Dynamic-array insertion or deletion at an arbitrary index: O(n) worst because elements shift; O(1) best at the end (append is amortized O(1)).

  • Dynamic-array append: O(1) amortized. An individual append is O(1) with spare capacity but O(n) when a resize copies the whole buffer; geometric resizing keeps a sequence of appends amortized O(1).

  • Linked-list traversal or search: O(1) best if the target is the head; O(n) average and worst. Access by index is O(1) for the first node and O(n) for an arbitrary index.

  • Linked-list insertion or deletion: O(1) once the correct node and predecessor are known; finding that location still costs O(n). A singly linked list generally needs the predecessor for deletion, whereas a doubly linked list can remove a known node directly.

These bounds are worst-case unless a best or average case is named.

Python 3.12 Example

A Python list is a dynamic array of object references: its buffer is contiguous, but the referenced objects need not be stored contiguously.

Inserting 15 at index 1 in [10, 20, 30] shows the difference:

  1. Dynamic array: Elements at indices 1 and 2 shift one position right, costing O(n) worst case.

  2. Linked list: The list traverses to the node containing 10, then links a new node containing 15 after it, costing O(n) to locate the position and O(1) to insert.

Inserting into a Python list modifies it in place; this is allowed because the operation is defined to mutate the list, but copy first if the original must be kept. Linked-list insertion changes node links in place but does not move existing elements.

Practical Trade-offs

  • Prefer dynamic arrays for frequent access by position, fast iteration, and lower memory overhead. Python lists, Java ArrayList, C++ std::vector, and JavaScript arrays are common examples.

  • Prefer linked lists only when stable node references or O(1) insertion/deletion after locating a node matter, such as linked-list-backed queues or some adjacency-list designs.

  • Avoid linked lists by default for general collections because pointer chasing, poor cache locality, and per-node overhead often outweigh the theoretical insertion advantage.

  • Static arrays have fixed capacity: they avoid resizing but cannot grow automatically, so dynamic arrays are usually more flexible.

Common Pitfalls

  • Claiming linked-list insertion is always O(1): locating the insertion position is still O(n).

  • Ignoring the occasional O(n) resize cost when discussing dynamic-array appends.

  • Confusing contiguous storage of a Python list’s references with contiguous storage of the referenced objects.

  • Using list.insert(0, value) or list.pop(0) in a loop: each call shifts the remaining elements and costs O(n).

  • Forgetting that inserting or deleting in a Python list mutates the input in place and may invalidate stored indices.

  • Interviewers often follow up on memory overhead, cache locality, why Python lists are not linked lists, and how to implement a singly linked list without losing references to removed nodes.

24

How do you uniformly shuffle an array with Fisher-Yates?

The Fisher-Yates shuffle uniformly randomizes an array by repeatedly selecting an index at random and swapping the selected element with the element at the current position. Each labeled element has probability 1 / n of occupying any final position.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Algorithm and Uniformity

Process the array from right to left:

  1. Start with index i = n - 1.

  2. Choose an index j independently and uniformly from 0 through i.

  3. Swap arr[i] and arr[j].

  4. Decrease i and repeat until i == 0.

The crucial detail is choosing from [0, i], including the current index. Choosing only from indices after i would reuse already-finalized positions and would not produce a uniform permutation.

There are n × (n - 1) × ... × 1 = n! possible sequences of choices. Because the choices are independent and uniform, every sequence has the same probability. Each sequence corresponds to one positional permutation, so every permutation of the labeled elements is equally likely.

Array Context

A static array has a fixed size, while a Python list is a dynamic array:

  • Indexing a Python list is O(1).

  • append() is amortized O(1).

  • Inserting or deleting in the middle is O(n) because elements must be shifted.

  • Fisher-Yates performs only indexed reads and writes, so each swap is O(1).

The implementation below modifies the list in place without changing its length.

Complexity

Case Time Auxiliary space
Best O(n) O(1)
Average O(n) O(1)
Worst O(n) O(1)
  • Time: For a nonempty array, every run performs exactly n - 1 iterations with O(1) work per iteration; an empty array performs no iterations.

  • Auxiliary space: O(1); only a loop index and random index are needed. The input list is not counted.

  • Including input: The total occupied space is O(n).

  • If a shuffled copy is required, copying first requires O(n) time and O(n) additional space.

Example Walkthrough

Starting with [1, 2, 3, 4, 5]:

Current index Random index Array after swap
4 3 [1, 2, 3, 5, 4]
3 1 [1, 2, 5, 3, 4]
2 0 [5, 1, 2, 3, 4]
1 0 [5, 1, 2, 3, 4]

The particular result varies, but every permutation is equally likely.

Code Example

import random


def shuffle_in_place(values: list[int]) -> None:
    """Shuffle values uniformly in place using the Fisher-Yates algorithm."""
    for i in range(len(values) - 1, 0, -1):
        j = random.randrange(i + 1)  # Uniform integer from 0 through i
        values[i], values[j] = values[j], values[i]


if __name__ == "__main__":
    values = [1, 2, 3, 4, 5]
    shuffle_in_place(values)
    print(values)
    # Expected: any permutation of [1, 2, 3, 4, 5]; exact order varies.

Python also provides random.shuffle(values), which performs an in-place Fisher-Yates shuffle. Use it for normal applications. It is not suitable when cryptographic unpredictability is required; Python 3.12 has no secrets.shuffle, so use secrets.randbelow(i + 1) in the same Fisher-Yates loop instead.

Common Pitfalls and Interview Tips

  • Choosing j from only [0, i - 1] can leave an element unswapped and breaks uniformity.

  • Swapping randomly selected position pairs does not generally produce a uniformly random permutation, even though the result remains a permutation of the original elements.

  • Removing elements with pop(0) or inserting with insert(0, value) causes O(n) shifts; neither belongs in the shuffle loop.

  • Empty and one-element lists require no swaps and are handled safely.

  • Duplicate values are shuffled by position, so individual labeled occurrences remain uniformly distributed even when their visible arrangements are indistinguishable.

  • Negative numbers and other value types do not affect the algorithm.

  • A common follow-up asks how to preserve the original list: copy it first, giving O(n) time and O(n) additional space.

25

How do you solve Rain Water Trapping using arrays?

The two-pointer algorithm solves Rain Water Trapping in linear time by processing the shorter current boundary from both ends of the array. At each position, it computes the water depth using the smaller of the tallest boundaries on the left and right.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

For an index i, let left_max[i] and right_max[i] be the maximum heights from the start through i and from i through the end, respectively. The trapped depth is:

max(0, min(left_max[i], right_max[i]) - height[i])

Including the current index and clamping at zero prevents a local peak or negative elevation from being described as negative water depth.

The two-pointer version maintains:

  • left and right: the boundaries of the unprocessed region.

  • left_max and right_max: the greatest heights encountered from each side.

  • water: the total trapped water.

If height[left] <= height[right], the left position can be finalized using left_max; otherwise, the right position can be finalized using right_max. Each iteration processes one position.

An array context distinction is relevant:

  • A static array has a fixed capacity, while a dynamic array can grow or shrink while preserving indexed access.

  • Python’s list is a dynamic array: indexing is O(1), appending is amortized O(1), and inserting or deleting in the middle is O(n) because elements may need to shift.

  • This solution only reads the input. It does not modify the input in place, so mutation permission is not required.

Approach Comparison

Approach Time Extra space When to use
Brute force: scan both sides for every index O(n²) O(1) Small arrays or conceptual explanation
Two pointers O(n) O(1) Production and interview solutions
Prefix and suffix maximum arrays O(n) O(n) When all boundary maxima are needed directly

Example Walkthrough

For [2, 0, 2]:

  1. Initialize left = 0, right = 2, left_max = 2, and right_max = 2.

  2. The boundary heights are equal, so process the left side. Its contribution is 2 - 2 = 0.

  3. Move left to index 1. The height is 0, and left_max remains 2.

  4. The water at index 1 is 2 - 0 = 2.

  5. The total trapped water is 2.

Complexity and Edge Cases

  • Time: O(n) in the best, average, and worst cases because each index is processed at most once.

  • Auxiliary space: O(1), including an O(1) recursion stack; the algorithm is iterative and uses no recursion.

  • The input array is excluded from auxiliary space but occupies O(n) storage, making total space O(n) when it is counted.

  • Empty, one-element, or two-element input: Returns 0.

  • Duplicate heights: Handled naturally.

  • Already sorted or monotonic input: Returns 0.

  • Negative heights: Supported as elevations relative to a common baseline, with water depth kept nonnegative.

  • Disconnected graphs and cycles: Not applicable to a one-dimensional height array.

Code Example

def trap_rain_water(height: list[int]) -> int:
    """Return the total rainwater trapped by the given height array."""
    if len(height) < 3:
        return 0

    left = 0
    right = len(height) - 1
    left_max = height[left]
    right_max = height[right]
    water = 0

    while left <= right:
        if height[left] <= height[right]:
            left_max = max(left_max, height[left])
            water += left_max - height[left]
            left += 1
        else:
            right_max = max(right_max, height[right])
            water += right_max - height[right]
            right -= 1

    return water


print(trap_rain_water([2, 0, 2]))  # Expected output: 2

Common Pitfalls

  • Initializing both maxima to zero can produce incorrect results for arrays containing only negative heights; initialize them from the actual boundary heights.

  • Forgetting that the water level uses the minimum of the two boundary maxima.

  • Moving both pointers simultaneously can skip positions.

  • Accidentally mutating the input when a read-only solution is sufficient.

  • Confusing auxiliary space with total space or overlooking the recursion stack when stating complexity.

Interviewers may follow up by asking for the brute-force solution, the prefix/suffix-array variant, or how to compute trapped water at each position rather than only the total.

26

How does the two-pointer technique solve array problems?

The two-pointer technique uses two positions moving through an array or linked structure to reduce the number of comparisons needed to solve a problem. It is especially effective on sorted data, where pointer movement can safely eliminate an entire candidate range.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

Two pointers often start at opposite ends of a collection:

  • left begins at the first element.

  • right begins at the last element.

  • Compare the values at the two pointers.

  • Move left forward or right backward based on the comparison.

  • Stop when the pointers meet or cross.

The technique works when the current comparison proves that moving a pointer in one direction cannot produce a better answer. For example, when searching a sorted array for a pair with a given sum:

  • If the sum is too small, move left rightward because the current left value cannot make a sufficiently large sum with any remaining value.

  • If the sum is too large, move right leftward because the current right value cannot make a sufficiently small sum with any remaining value.

  • If the sum matches, return the result.

Arrays and Complexity

A static array has a fixed capacity, while a dynamic array can grow as elements are added. Python’s list is a dynamic array:

  • Index access: O(1), because the element’s address is calculated directly.

  • Append: amortized O(1), because occasional resizing copies elements, but each copy is amortized across many appends.

  • Insert or delete in the middle: O(n), because existing elements must be shifted.

  • Access by position in a two-pointer scan: O(1), so scanning the entire array takes O(n).

For a two-pointer algorithm that scans at most n elements:

  • Best time: O(1) when an early match is found.

  • Average time: O(n).

  • Worst time: O(n).

  • Auxiliary space: O(1), because only two indices and a few variables are stored. This excludes the input collection.

Common Applications

Problem pattern Movement Best, average and worst time Auxiliary space
Find a pair with a target sum in sorted data Opposite directions O(1), O(n), O(n) O(1)
Check whether a sequence is a palindrome Opposite directions O(n), O(n), O(n) O(1)
Reverse an array Opposite directions O(n), O(n), O(n) O(1)
Remove sorted duplicates in place Same direction O(n), O(n), O(n) O(1)
Maintain a sliding window Same direction O(n), O(n), O(n) O(1)

The reason these approaches take O(n) is that each iteration performs constant work and advances at least one pointer. Two-pointer algorithms are not limited to arrays; they also work with linked lists and, in some problems, with two separate sorted collections.

Code Example

The following function finds two indices whose values sum to a target in a sorted list. It does not modify the input.

def find_pair_with_sum(values: list[int], target: int) -> tuple[int, int] | None:
    """Return matching indices for the target sum, or None if no pair exists."""
    left = 0
    right = len(values) - 1

    while left < right:
        pair_sum = values[left] + values[right]

        if pair_sum == target:
            return left, right
        if pair_sum < target:
            left += 1
        else:
            right -= 1

    return None


# Expected output: (0, 1)
print(find_pair_with_sum([2, 7, 11, 15], 9))

For [2, 7, 11, 15] and target 9, the steps are:

Step left right Sum Action
1 0 3 17 Move right left
2 0 2 13 Move right left
3 0 1 9 Return (0, 1)

Common Pitfalls

  • Using the technique on unsorted data: Opposite-end elimination may discard valid pairs. Sort first when sorting does not conflict with the requirements.

  • Crossing pointers: Continue while left < right, not while left <= right, unless the same element may be used twice.

  • Ignoring duplicates: Decide whether multiple valid index pairs are required. The implementation above returns the first valid pair.

  • Forgetting empty and single-element inputs: No pair exists in either case, so the function returns None.

  • Incorrect mutation assumptions: State whether the input may be modified. The example is read-only; in-place duplicate removal requires a separate implementation.

  • Interview follow-ups: Common questions ask about handling duplicates, reversing the pointer directions, applying the pattern to a linked list, and using a same-direction sliding window.

27

What are common sliding-window array use cases?

A sliding window is a contiguous range of array elements whose boundaries move to solve problems involving sums, extrema, frequencies, distinctness, or constraints. Common uses include fixed-size windows, variable-size windows, monotonic maxima or minima, distinct-element tracking, and sliding frequency comparisons.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

A sliding-window algorithm usually maintains two boundaries:

  • left marks the beginning of the current window.

  • right marks the end of the current window.

  • The window contains elements from left through right, inclusive.

  • Auxiliary state may maintain a sum, element frequencies, a set of unique values, or candidate indices.

Both boundaries move only forward, so each element is added and removed at most once. A fixed-size window advances both boundaries together. A variable-size window expands right until a constraint is violated, then advances left until the window becomes valid again.

Arrays may be statically sized or dynamically resized. In Python, a list is a dynamic array: indexing is O(1), append is amortized O(1), and inserting or deleting near the beginning is O(n).

Common Use Cases

Let n be the array length, k the window size, and σ the number of possible symbols.

Use case Typical problem Time complexity Auxiliary space
Fixed-size rolling calculation Maximum sum of every subarray of length k O(n) in the best, average, and worst case; each element enters and leaves once O(1)
Variable-size constrained window Longest subarray with sum at most target when values are non-negative O(n) in the best, average, and worst case; each pointer advances at most n times O(1)
Distinct-element window Longest subarray containing only unique values O(n) best and average; O(n²) worst case with pathological hash collisions O(n) for frequencies or a set
Monotonic candidate window Maximum or minimum of every window of length k O(n) in the best, average, and worst case; each index enters and leaves a monotonic deque at most once O(k)
Frequency or pattern comparison Find all anagram starts in another string O(n) in the best, average, and worst case O(σ)

These space bounds exclude the input and returned output and include an O(1) recursion stack because iterative implementations use no recursion. If the input itself is counted, total space is O(n).

For target-sum problems containing negative numbers, expanding and shrinking based only on the current sum is not generally safe. Prefix sums, hash maps, or a different monotonicity argument may be required.

Example Walkthrough

For the fixed-size maximum [2, 1, 3, 4, 6] with k = 3, a monotonic deque stores candidate indices whose corresponding values are decreasing:

Processed value Candidate indices afterward Result
2 [0] No complete window
1 [0, 1] No complete window
3 [2] 3
4 [3] 4
6 [4] 6

When a newer value is at least as large as an older candidate, the older candidate can be removed because the newer value is no worse and expires later.

Best Practices and Edge Cases

  • Empty input: There are no complete windows, so return an empty result.

  • One element: A window of size 1 returns that element.

  • Duplicates: A newer equal candidate can replace an older one because it remains in future windows longer.

  • Negative numbers: Monotonic maxima and minima still work; target-sum window logic requires additional care.

  • Already sorted input: A monotonic deque may contain only one candidate, but correctness is unchanged.

  • Window larger than the input: There are no complete windows.

  • Disconnected graphs and cycles: These do not apply to ordinary one-dimensional array windows. Equivalent graph-traversal problems require separate reachability and cycle handling.

  • Mutation: Sliding-window solutions usually do not require modifying the input. State explicitly whether mutation is permitted if an in-place variant is used.

Common Pitfalls

  • Off-by-one errors: A full fixed-size window begins when right >= k - 1.

  • Incorrect expiry: An index is outside the current window when index <= right - k.

  • Invalid monotonicity assumptions: Do not assume target sums decrease predictably when negative values are present.

  • Underestimating hash-table costs: Membership and frequency operations are O(1) on average but can degrade under pathological collisions.

  • Using pop(0): Removing the front of a Python list is O(n); use an appropriate deque or advance indices.

  • Unexpected mutation: Make clear whether the algorithm changes the caller’s array.

28

How do you find all array pairs with a given sum?

A hash map can find every pair of distinct array positions whose values add to a target in expected O(n + k) time, where k is the number of matching pairs. The implementation below returns index pairs, which preserves every valid combination when duplicate values exist.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

Maintain a dictionary mapping each previously encountered value to all of its indices.

  1. For the current value, calculate its complement: target - value.

  2. If the complement has appeared, every stored index for that value forms a pair with the current index.

  3. Store the current index under its value.

  4. Look up the complement before inserting the current index, ensuring that one element cannot pair with itself.

Static arrays have a fixed capacity, whereas dynamic arrays grow by reallocating. In the Python example, a list is a dynamic array: indexing is O(1), append is amortized O(1), and insert/delete in the middle is O(n). This solution only indexes the input and appends to per-value lists, so it does not modify the input; leaving the input unchanged is allowed and usually preferred.

Complexity

  • Best time: O(n + k) — each lookup is constant time and k pairs are returned.

  • Average time: O(n + k) — hash-table lookups and insertions take expected O(1) time.

  • Worst time: O(n² + k) — pathological hash collisions can make each dictionary operation O(n).

  • Auxiliary space: O(n) for the dictionary of value-to-index lists.

  • Output space: O(k) for the returned pairs.

  • Total space: O(n + k), excluding the input array. There is no recursion stack.

The output itself can be quadratic: for an array containing only zeros with a target of zero, there are n(n - 1) / 2 valid index pairs.

Approach Comparison

Approach Time Auxiliary Space When to Use
Nested loops O(n²) O(1) Small arrays or a simple brute-force solution
Hash map O(n + k) expected O(n) General-purpose solution that finds all pairs
Sorted input + two pointers O(n + k) if already sorted; O(n log n + k) if sorting a copy O(1) if already sorted; O(n) if sorting a copy Value pairs on sorted data, or when extra space is tight; carry indices if original index pairs are required

The hash map is the general approach; use two pointers when the array is already sorted and you want less auxiliary space.

Example Walkthrough

For values = [3, 1, 3, 4, 2] and target = 6:

Index Value Complement Previous Match New Pair
0 3 3 None —
1 1 5 None —
2 3 3 Index 0 (0, 2)
3 4 2 None —
4 2 4 Index 3 (3, 4)

The resulting value pairs, in index order, are (3, 3) and (4, 2).

Code Example

def find_pairs_with_sum(
    values: list[int], target: int
) -> list[tuple[int, int]]:
    """Return every pair of distinct indices whose values sum to target."""
    indices_by_value: dict[int, list[int]] = {}
    pairs: list[tuple[int, int]] = []

    for index, value in enumerate(values):
        complement = target - value

        matching_indices = indices_by_value.get(complement)
        if matching_indices is not None:
            for previous_index in matching_indices:
                pairs.append((previous_index, index))

        # Insert only after matching so an index cannot pair with itself.
        indices_by_value.setdefault(value, []).append(index)

    return pairs


result = find_pairs_with_sum([3, 1, 3, 4, 2], 6)
print(result)  # [(0, 2), (3, 4)]

Common Pitfalls

  • Pairing an element with itself: Perform the lookup before inserting the current index.

  • Losing duplicate combinations: Store a list of indices for each value rather than only one index.

  • Returning unwanted duplicates: If only unique value pairs are required, convert each index pair to values, canonicalize the pair by sorting the two values or using a frozenset, then deduplicate; otherwise (2, 4) and (4, 2) would be counted separately.

  • Ignoring negative values: The complement calculation works for negative numbers and zero without special handling.

  • Assuming sorted input: Sorting is unnecessary because the hash-map solution processes the array directly.

  • Edge cases: Empty and single-element arrays correctly return an empty list because two distinct indices are required.

29

What is the difference between row-major and column-major order in multidimensional arrays?

Row-major order stores a multidimensional array so that elements in the same row are contiguous in memory, while column-major order stores elements in the same column contiguously. Both give O(1) random access using an index formula; the difference is memory layout and therefore cache behavior during traversal.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Memory Layout

For a matrix with m rows and n columns, using 0-based indexing and matrix[row][col]:

  • Row-major: stores row 0 left to right, then row 1, and so on. The address offset is row * n + col. The last dimension varies fastest.

  • Column-major: stores column 0 top to bottom, then column 1, and so on. The address offset is col * m + row. The first dimension varies fastest.

  • Higher dimensions: row-major makes the last index contiguous; column-major makes the first index contiguous.

Typical defaults:

Language or library Default layout
C and C++ built-in arrays Row-major
Python nested lists Not a contiguous 2D block; list of row references
NumPy ndarray Row-major (order='C'); supports column-major with order='F'
Fortran, MATLAB, R, Julia Column-major

Indexing and Complexity

  • Random access: O(1) time in both layouts, because the offset is computed with a few arithmetic operations.

  • Full traversal: O(m * n) time in both layouts. Best, average and worst cases do not differ asymptotically.

  • Cache effect: a row-major scan of a row-major matrix visits contiguous memory and is usually fast. A column-by-column scan of a row-major matrix jumps by n elements each step, causing more cache misses. The Big-O is still O(m * n), but the constant factor can be much larger.

  • Space: O(m * n) to store the input matrix; O(1) auxiliary space for address arithmetic. No recursion stack is involved.

Practical Impact

  • Nested loops: match loop order to storage order. For a row-major matrix, prefer for row in range(m): for col in range(n):. For a column-major matrix, swap the loops.

  • Libraries: NumPy’s default is row-major. If a library expects Fortran order, converting may cost O(m * n) time and O(m * n) extra space.

  • Transpose: transposing a matrix improves locality for the other traversal order, but it is not free: it normally costs O(m * n) time and O(m * n) space unless done in place on a square matrix.

Comparison

Aspect Row-major Column-major
Contiguous elements Same row Same column
Offset formula row * n + col col * m + row
Fastest dimension Last index First index
Random access O(1) O(1)
Full scan O(m * n) O(m * n)
Friendly scan Row by row Column by column
Common users C, C++, NumPy default Fortran, MATLAB, R, Julia

Common Pitfalls

  • Wrong formula: mixing row * n + col with col * m + row produces wrong addresses or transposed results.

  • Assuming Python nested lists are contiguous: they are lists of references to row lists, not a flat matrix buffer. Use NumPy when layout matters.

  • Shared rows: never create a 2D list with [[0] * n] * m; every row is the same object. Use [[0] * n for _ in range(m)].

  • Ignoring empty matrices: guard before indexing when there are 0 rows or 0 columns, since conventions for empty shapes vary.

  • Confusing Big-O with performance: both layouts are O(m * n) to scan, but cache locality can make one order much faster in practice. Interviewers often ask why a column-wise loop over a row-major matrix is slow.

30

What is a circular array and how to implement it?

A circular array is a fixed-capacity array whose last index wraps around to the first, forming a logical ring. It is a classic implementation of a bounded queue or ring buffer: storage is reused instead of shifted, so enqueue and dequeue stay O(1).

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

  • Fixed buffer: allocate data = [None] * size; in Python the backing list is a dynamic array, but here we treat it as fixed-capacity storage.

  • Two pointers: head points to the next element to remove and tail to the next free slot. Advance each with (index + 1) % size.

  • Count: count tracks the number of stored elements. Empty is count == 0; full is count == size. With all slots usable, head == tail can occur both when empty and after exactly size writes, so use count to disambiguate.

  • Alternative without count: reserve one empty slot (capacity size - 1); then full is (tail + 1) % size == head and empty is head == tail.

Key Operations

  • Enqueue: O(1) best, average, and worst case — write at tail, advance tail, increment count; when full, reject or overwrite by policy.

  • Dequeue: O(1) all cases — read at head, advance head, decrement count.

  • Peek: O(1) — read data[head] without moving pointers.

  • Is Empty / Is Full: O(1) — compare count with 0 or size.

  • Space: O(size) total for the backing storage (stored elements count); each operation uses O(1) extra space, and there is no recursion.

Static vs Dynamic Arrays

Operation Python list (dynamic) Circular array (static)
Index O(1) O(1)
Append/enqueue at end amortized O(1), worst O(n) on resize O(1) worst case
Insert/delete in middle O(n) O(n) if shifting; circular enqueue/dequeue avoid shifts
  • A circular array is a static buffer unless you add explicit growth logic.

  • The code below mutates its own backing buffer in place; it does not modify a caller-owned input array, so no in-place permission is needed.

Use Cases

  • Bounded queues: when the maximum size is known.

  • Ring buffers: streaming audio, network packets, logs; oldest data is overwritten by policy.

  • Round-robin scheduling: cycling through a fixed set of resources.

  • Python’s collections.deque is the usual general-purpose queue; use a circular array when capacity is fixed and you want explicit storage control.

Code Example

from typing import Any


class CircularArray:
    """A fixed-capacity circular array (ring buffer) with head/tail pointers."""

    def __init__(self, size: int) -> None:
        if size <= 0:
            raise ValueError("size must be positive")
        self.size: int = size
        self.data: list[Any] = [None] * size
        self.head: int = 0
        self.tail: int = 0
        self.count: int = 0

    def enqueue(self, value: Any) -> bool:
        """Add value at tail; return False if full."""
        if self.is_full():
            return False
        self.data[self.tail] = value
        self.tail = (self.tail + 1) % self.size  # wrap to 0 at the end
        self.count += 1
        return True

    def dequeue(self) -> Any:
        """Remove and return value at head; return None if empty."""
        if self.is_empty():
            return None
        value = self.data[self.head]
        self.head = (self.head + 1) % self.size  # wrap to 0 at the end
        self.count -= 1
        return value

    def peek(self) -> Any:
        """Return value at head without removing it; return None if empty."""
        if self.is_empty():
            return None
        return self.data[self.head]

    def is_empty(self) -> bool:
        return self.count == 0

    def is_full(self) -> bool:
        return self.count == self.size


if __name__ == "__main__":
    arr = CircularArray(3)
    print(arr.enqueue(1), arr.enqueue(2), arr.enqueue(3), arr.enqueue(4),
          arr.dequeue(), arr.peek())
    # Expected output: True True True False 1 2

Trace with capacity 3: 1. enqueue(1): data[0] = 1, tail = 1, count = 1. 2. enqueue(2): data[1] = 2, tail = 2, count = 2. 3. enqueue(3): data[2] = 3, tail = (2 + 1) % 3 = 0, count = 3. 4. enqueue(4): full, returns False. 5. dequeue(): returns data[0] = 1, head = 1, count = 2. 6. peek(): returns data[1] = 2.

Common Pitfalls

  • Full vs empty ambiguity: if you allow all slots and keep only head/tail, head == tail can mean empty or full; use count or reserve one empty slot.

  • Off-by-one and modulo errors: advance with (index + 1) % size; a bare tail + 1 raises IndexError at the end. Validate that size > 0.

  • Empty sentinel: dequeue/peek return None when empty; if None can be a stored value, raise IndexError or use a unique sentinel instead.

  • Edge cases: size == 1 fills the only slot immediately; duplicates and negative values are stored unchanged; count == 0 is the empty state.

  • Interviewers often follow up by asking what to do when full (reject, overwrite oldest, or grow) and how to implement the one-empty-slot variant or a circular buffer with a single pointer.

31

How can operations on a very large sparse array be optimized?

A sparse array should store only its nonzero elements, typically in a dictionary keyed by their original indices. This reduces memory from proportional to the full array length to proportional to the number of nonzero entries while preserving logical indexed access.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Representation Choices

Choose a representation based on the expected operations and sparsity ratio.

Representation Space Indexed access Updates Best suited for
Static fixed-length array O(n) O(1) O(1) replacement; O(n) if shifting Fixed capacity and direct access
Dynamic Python list O(n) O(1) O(1) replacement; append amortized O(1); middle insert/delete O(n) General-purpose dynamic data
Dictionary of nonzero entries O(k) O(1) average O(1) average Random access and sparse data
Sorted indices and values O(k) O(log k) O(k) because lists shift Range scans and binary search
Packed bit vector O(n) bits O(1) word lookup O(1) word update Large index range with very low density

Here, n is the logical array length and k is the number of nonzero elements. A static array cannot grow without copying it into a larger allocation, whereas a Python list is dynamic and grows through occasional reallocations.

Core Strategy

  • Store only nonzero values: Map each occupied index to its value. An absent key represents zero.

  • Preserve original indices: Do not compress positions unless coordinate mappings are acceptable.

  • Overwrite duplicate indices: Assigning a value to an existing index replaces the previous value.

  • Remove zeros explicitly: When an entry becomes zero, delete its dictionary key rather than storing index: 0.

  • Avoid full scans: Iterate over occupied entries or compressed blocks instead of examining all n positions.

  • Use an ordered index for range operations: For frequent scans, successor, predecessor, or k-th nonzero queries, maintain sorted indices, a balanced ordered tree, or a segment tree over compressed coordinates.

  • Handle edge cases: Empty storage represents all zeros; a zero-length array has no valid indices; one-element arrays work normally; duplicate-index writes overwrite; negative values remain nonzero; deleting an absent index is a no-op; and ordered output is correct regardless of assignment order.

Code Example

class SparseArray:
    """Store only nonzero values while preserving logical array indices."""

    __slots__ = ("length", "_values")

    def __init__(self, length: int) -> None:
        if length < 0:
            raise ValueError("length must be non-negative")
        self.length = length
        self._values: dict[int, int] = {}

    def _validate_index(self, index: int) -> None:
        if not 0 <= index < self.length:
            raise IndexError("array index out of range")

    def __getitem__(self, index: int) -> int:
        self._validate_index(index)
        return self._values.get(index, 0)

    def __setitem__(self, index: int, value: int) -> None:
        self._validate_index(index)
        if value == 0:
            self._values.pop(index, None)
        else:
            self._values[index] = value

    def __delitem__(self, index: int) -> None:
        self._validate_index(index)
        self._values.pop(index, None)

    @property
    def nonzero_count(self) -> int:
        return len(self._values)

    def nonzero_items(self) -> list[tuple[int, int]]:
        """Return nonzero entries ordered by their original indices."""
        return sorted(self._values.items())


array = SparseArray(10)
array[2] = 5  # Store a nonzero value.
array[4] = -7
array[4] = 8  # Replace the existing entry.

print(array[2], array[3], array[4], array.nonzero_count)
# 5 0 8 2

del array[2]
print(array.nonzero_items())
# [(4, 8)]

Complexity

For the dictionary implementation:

  • Best-case indexed access: O(1), when lookup requires only one probe.

  • Average-case indexed access: O(1) under ordinary hashing. Reads do not require amortization.

  • Worst-case indexed access: O(k), when many keys occupy the same initial hash-table slot and require probing.

  • Updating or deleting an entry: O(1) best and average case, O(k) worst case. Insertion is amortized O(1) over a sequence because occasional resizing costs are distributed across insertions.

  • Producing ordered nonzero entries: O(k) best case when the items are already sorted, and O(k log k) average and worst cases for Python’s adaptive sort.

  • Persistent space: O(k) plus O(1) metadata, excluding input because the class receives no dense array. If a dense source array exists separately, it still occupies O(n) input space.

  • Auxiliary space during sorting: O(k), including the returned list and sorting workspace; the sort’s O(log k) control stack is dominated by O(k).

For a dynamic Python list, indexing and replacement are O(1), append is amortized O(1) although one append can take O(n) during reallocation, and insertion or deletion in the middle is O(n).

Example Walkthrough

For a logical array of length 10:

  1. Initially, storage is empty {}, representing ten zeros.

  2. Assigning array[2] = 5 stores {2: 5}.

  3. Assigning array[4] = -7 stores {2: 5, 4: -7}.

  4. Assigning array[4] = 8 overwrites the same key.

  5. Reading array[3] returns 0 without creating an entry.

  6. Deleting index 2 removes it, leaving {4: 8}.

Common Pitfalls

  • Creating list(range(n)) immediately allocates O(n) memory, defeating sparse storage.

  • Repeatedly calling nonzero_items() sorts the same keys each time; maintain an ordered index when reads are frequent and updates are rare.

  • Use the logical range [0, length) consistently to avoid off-by-one errors.

  • The implementation mutates only its own dictionary and allocates no dense backing array.

  • Python integers do not overflow, but fixed-width languages require careful index and value sizing.

  • No visited set is required because this structure does not perform graph traversal.

  • Interviewers commonly follow up about the operation mix, dynamic updates, range scans, and selecting the k-th nonzero element.

32

How to create and access a multi-dimensional array in Python

In Python, a multi-dimensional array is implemented as a list of lists, where each element of the outer list is itself a list representing a row. Unlike languages with native multi-dimensional types, Python lists are dynamic arrays that nest naturally, allowing you to build 2D, 3D, or higher-dimensional structures.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

A 2D array is conceptually a grid with rows and columns. In Python, you access an element using the notation matrix[row][col], where row selects the inner list and col selects the value within that list. Python lists are dynamic arrays, meaning they resize automatically when you append or insert elements, but fixed-size initialization requires explicit construction.

Creating Multi-Dimensional Arrays

There are two primary ways to initialize a 2D array, but one is dangerous due to reference sharing.

  • List Comprehension: Creates independent rows. This is the correct and standard approach.

  • Multiplication ([[0]*n]*m): Creates m references to the same inner list. Modifying one row modifies all of them.

Approach Syntax Row Independence Risk
Comprehension [[0] * cols for _ in range(rows)] Independent None
Multiplication [[0] * cols] * rows Shared Data corruption

Traversal and Complexity

Traversing a multi-dimensional array requires nested loops. You iterate over each row, then over each element within that row.

  • Time Complexity: O(m * n) for traversal or initialization, where m is rows and n is columns. Accessing a specific element is O(1).

  • Space Complexity: O(m * n) to store the data. Auxiliary space for traversal is O(1).

Code Example

This function creates a 2D array using a list comprehension and returns the value at a specific index, demonstrating safe creation and access.

def create_and_access_matrix(rows: int, cols: int, target_row: int, target_col: int) -> int:
    """
    Creates a rows x cols 2D array filled with zeros and returns the value at [target_row][target_col].
    """
    if rows <= 0 or cols <= 0:
        raise ValueError("Dimensions must be positive")
    if not (0 <= target_row < rows and 0 <= target_col < cols):
        raise IndexError("Index out of bounds")

    # List comprehension creates independent rows; avoid [[0] * cols] * rows
    matrix = [[0] * cols for _ in range(rows)]

    # Simulate work: update a value at the target position
    matrix[target_row][target_col] = 1

    return matrix[target_row][target_col]

# Example call: create_and_access_matrix(3, 3, 1, 2) -> 1

Common Pitfalls

  • Shared References: Using [[0] * n] * m creates a single row object repeated m times. If you change matrix[0][0], matrix[1][0] changes too. Always use a comprehension.

  • Index Errors: Multi-dimensional access is prone to IndexError if you assume dimensions without checking bounds. Always validate indices.

  • Mutating Input: If a function modifies the matrix in place, the caller sees the change. Be clear about whether the input is allowed to be modified.

  • 1D vs 2D: Remember that a flat list of length m*n is not the same as a 2D list. You must explicitly nest the lists to get row/column semantics.

33

What is the methodology and time complexity of dynamic array resizing?

Dynamic array resizing allocates a larger backing buffer, copies the existing elements into it, and continues appending. With geometric growth, each append is amortized O(1) even though an individual resize costs O(n).

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How Resizing Works

A dynamic array stores elements in a backing array plus a size (the number of elements used) and a capacity (the number of allocated slots).

  1. On append, if size < capacity, write the value at data[size] and increment size. This is O(1).

  2. If size == capacity, allocate a new backing array, usually with approximately twice the previous capacity.

  3. Copy all size existing elements into the new array.

  4. Release the old buffer, install the new one, and then append the new value.

The append mutates the dynamic array in place. If the original must be preserved, copy it first, which costs O(n) time and space.

In CPython 3.12, list is a dynamic array of object references. CPython over-allocates rather than always doubling by an exact factor; its capacities and resize thresholds are implementation details rather than Python language guarantees. CPython list indexing is O(1), while inserting or deleting in the middle is O(n) because elements shift.

Time and Space Complexity

  • Best-case append: O(1), when spare capacity already exists.

  • Amortized append: O(1) across a sequence of appends because geometric growth spreads copying over many operations.

  • Average append over a sequence: O(1) per append; for example, n appends perform O(n) total copying with geometric growth.

  • Worst-case single append: O(n), when the append triggers a resize and copies all existing elements.

  • Resize operation: O(n) time to copy n existing elements.

  • Index access: O(1) in the best, average, and worst cases because it uses direct offset access.

  • Middle insertion or deletion: O(n) because a contiguous range of elements must shift.

  • Space: O(n) to store n elements, counting the stored data itself. No recursion stack is used. A resize temporarily requires an additional O(n) buffer, so peak extra space is O(n).

Growth Strategies Compared

Strategy Cost of one resize Total copying for n appends Amortized append
Fixed capacity, no growth Not applicable 0 while the capacity is sufficient O(1) until overflow
Grow by one slot Copy k elements at size k 1 + 2 + ... + (n-1) = O(n²) O(n)
Grow by doubling Copy k elements 1 + 2 + 4 + ... < n = O(n) O(1)
CPython list over-allocation Copy current elements O(n) O(1)

Doubling works because resizes occur at geometrically increasing sizes. The total number of copied elements is less than 2n, so the average cost per append is constant.

Step-by-Step Trace

Starting with capacity 1 and appending 0 through 4 under a doubling strategy:

Append Capacity after Size after Elements copied
0 1 1 0
1 2 2 1
2 4 3 2
3 4 4 0
4 8 5 4

Five appends copy 0 + 1 + 2 + 0 + 4 = 7 elements. As n grows, total copying remains O(n).

Common Pitfalls

  • Assuming every append is worst-case O(1): a resize-triggering append is O(n); O(1) is the amortized bound.

  • Growing by a fixed amount: adding one slot per resize leads to O(n²) total copying.

  • Shrinking too aggressively: halve capacity only when the size is sufficiently below capacity, such as one quarter, to avoid repeated resize thrashing.

  • Confusing implementation details with language guarantees: Python’s exact list capacity and growth policy are CPython implementation details.

  • Interview follow-up: expect questions on amortized analysis, choosing a growth factor, peak memory usage, and why inserting in the middle is O(n).

34

How do you implement binary search in a circularly sorted array?

Binary search can locate a value in a circularly sorted array by identifying which half remains sorted after the rotation, then discarding the half that cannot contain the target. Duplicate values require extra care because several elements may make the rotation boundary ambiguous, and the function may return any matching index.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

A circularly sorted array is a nondecreasing sorted array rotated by an unknown amount. For example, [0, 1, 2, 3, 4, 5] rotated becomes [3, 4, 5, 0, 1, 2].

The algorithm maintains inclusive boundaries left and right:

  1. Compare the middle element with the target.

  2. If values[left] <= values[middle], the left half is sorted.

  3. If the target lies between values[left] and values[middle], search the left half.

  4. Otherwise, search the right half.

  5. Otherwise, the right half is sorted and the same range check determines the next search region.

  6. If all three boundary-related values are equal, their ordering is ambiguous, so move both boundaries inward.

The function returns one matching index in the supplied rotated array or -1 if the target is absent.

Complexity

Approach Best Average Worst Extra space
Linear search O(1) O(n) O(n) O(1)
Binary search, distinct values O(1) O(log n) O(log n) O(1)
Binary search, duplicates possible O(1) Data-dependent: O(log n) for benign distributions; O(n) is possible O(n) O(1)
  • Time: Without duplicates, every iteration discards approximately half the remaining candidates. With duplicate values, ambiguous boundaries may force linear shrinking.

  • Space: O(1) auxiliary space because the implementation is iterative and uses no recursion stack. The input array occupies O(n) space if counted, and it is not modified.

Example Walkthrough

Search for 0 in [4, 5, 6, 7, 0, 1, 2]:

  1. left = 0, right = 6, middle = 3; values[middle] = 7.

  2. The left half [4, 5, 6, 7] is sorted. Since 0 is outside its range, set left = 4.

  3. left = 4, right = 6, middle = 5; values[middle] = 1.

  4. The left half [0, 1, 2] is sorted. Since 0 is within its range, set right = 4.

  5. middle = 4, where values[middle] = 0; return index 4.

Code Example

from collections.abc import Sequence


def binary_search_rotated(values: Sequence[int], target: int) -> int:
    """Return the target's index in a rotated sorted sequence, or -1."""
    left, right = 0, len(values) - 1

    while left <= right:
        middle = left + (right - left) // 2

        if values[middle] == target:
            return middle

        # Equal boundaries make it impossible to identify the sorted half.
        if values[left] == values[middle] == values[right]:
            left += 1
            right -= 1
            continue

        if values[left] <= values[middle]:
            # The left half is sorted.
            if values[left] <= target < values[middle]:
                right = middle - 1
            else:
                left = middle + 1
        else:
            # The right half is sorted.
            if values[middle] < target <= values[right]:
                left = middle + 1
            else:
                right = middle - 1

    return -1


print(binary_search_rotated([4, 5, 6, 7, 0, 1, 2], 0))  # 4

Best Practices

  • Define “circularly sorted” as a rotation of a nondecreasing sorted array; otherwise the algorithm’s invariant does not hold.

  • Use left + (right - left) // 2 to avoid integer overflow in fixed-width languages.

  • The implementation is read-only and does not modify the input in place. In-place modification is allowed for this problem but is unnecessary, so preserve the input.

  • For an empty array, the loop never runs and the function returns -1.

  • Negative values, one-element arrays, an unrotated sorted array, and duplicates are supported.

Common Pitfalls

  • Assuming the rotation point is unique; duplicates can make it impossible to identify.

  • Using incorrect inclusive inequalities can discard the target’s half.

  • Confusing the sorted half with the half containing the target.

  • Forgetting that worst-case time becomes O(n) when duplicate-heavy input causes repeated boundary shrinking.

  • Common follow-up questions ask how to find the minimum element, count target occurrences, or return the first matching index.

35

How does the Dutch National Flag algorithm sort arrays?

The Dutch National Flag algorithm is an in-place sorting method designed specifically for arrays containing exactly three distinct values, typically 0, 1, and 2. It uses three pointers to partition the array into three sections in a single pass, ensuring O(n) time complexity without requiring extra memory.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

The algorithm maintains an invariant using three pointers: low, mid, and high. The array is conceptually divided into four regions: - arr[0..low-1]: Contains only 0s. - arr[low..mid-1]: Contains only 1s. - arr[mid..high]: Contains unexamined elements. - arr[high+1..n-1]: Contains only 2s.

The mid pointer traverses the array from left to right while low and high adjust boundaries. For each element at arr[mid], the algorithm performs one of three actions: 1. If arr[mid] == 0: Swap arr[low] and arr[mid], then increment both low and mid. This places the 0 in the correct region and moves the unexamined region forward. 2. If arr[mid] == 1: The element is already in the correct region (the 1s section), so simply increment mid. 3. If arr[mid] == 2: Swap arr[mid] and arr[high], then decrement high. The element swapped from high into mid is unexamined, so mid stays in place to process it in the next iteration.

The loop terminates when mid exceeds high, meaning all elements are sorted.

Complexity Analysis

  • Time Complexity: O(n) for best, average, and worst cases. The algorithm performs a single pass through the array, and each swap places an element in its final position.

  • Space Complexity: O(1). The sorting is done in-place using only a constant amount of extra space for the three pointers.

Code Example

def sort_colors(arr: list[int]) -> list[int]:
    """Sorts an array of 0s, 1s, and 2s in place using the Dutch National Flag algorithm."""
    if not arr:
        return arr

    low, mid, high = 0, 0, len(arr) - 1

    while mid <= high:
        if arr[mid] == 0:
            arr[low], arr[mid] = arr[mid], arr[low]
            low += 1
            mid += 1
        elif arr[mid] == 1:
            mid += 1
        else:
            arr[mid], arr[high] = arr[high], arr[mid]
            high -= 1
    return arr

# Example call:
# print(sort_colors([2, 0, 2, 1, 1, 0]))  # Output: [0, 0, 1, 1, 2, 2]

Common Pitfalls

  • Off-by-one errors: Ensure the loop condition is mid <= high, not mid < high. Stopping early leaves the last element unexamined.

  • Not re-examining swapped elements: When swapping with high, the new element at mid must be processed in the next iteration, so mid must not be incremented.

  • Invalid input: This algorithm assumes the input contains only 0, 1, and 2. Values outside this set will not be sorted correctly and may cause logical errors.

  • Edge cases: The code handles empty lists and single-element lists correctly, but always validate input constraints before running the algorithm.

36

How do you multiply two large numbers stored as digit arrays?

Multiply two large numbers represented by digit arrays using schoolbook (long) multiplication: multiply each digit pair, accumulate the partial products at the appropriate positions, and propagate carries. This takes O(m·n) time and O(m+n) space without converting the complete operands to fixed-width integers.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

  • Array representation: Digit arrays have a fixed length for the operation, but Python’s list is dynamic: indexing is O(1), append is amortized O(1), and insertion or deletion in the middle is O(n). This algorithm only reads the inputs and writes into a preallocated result.

  • Assumptions: Each array contains digits 0–9, most significant digit first. For lengths m and n, allocate a result containing m + n positions.

  • Position mapping: With i and j running from right to left, the raw digit product belongs at i + j + 1; its carry belongs at i + j.

  • Carry propagation: Compute product = num1[i] * num2[j] + result[i + j + 1], store product % 10 in the digit position, and add product // 10 to the carry position. A position may temporarily exceed 9 and is normalized when later consumed.

  • Input mutation: Neither input is modified; the function returns a fresh result array.

Trace of [9, 9] × [9, 9]:

Step (i, j) Product calculation Result after step
(1, 1) 81 + 0 = 81 [0, 0, 8, 1]
(1, 0) 81 + 8 = 89 [0, 8, 9, 1]
(0, 1) 81 + 9 = 90 [0, 17, 0, 1]
(0, 0) 81 + 17 = 98 [9, 8, 0, 1]

The final result is [9, 8, 0, 1], representing 9801; the leading-zero scan leaves it unchanged.

Complexity

  • Time: Best case is O(m+n) when validation dominates a zero-operand call; average and worst case are O(m·n) for general nonzero operands. Every digit pair is processed once.

  • Space: O(m+n) auxiliary space for the result, excluding the inputs; including the inputs, the total remains O(m+n). There is no recursion stack.

For the advanced algorithms below, let N = max(m, n).

Approach Time Space When to use
Schoolbook multiplication O(m·n) O(m+n) Default interview answer and modest sizes
Karatsuba O(N^1.585) O(N) Very large equal-length inputs
Schönhage–Strassen, using FFT-based techniques O(N log N log log N) O(N) Extremely large integers in specialized implementations

Edge Cases

  • Empty input: The function raises ValueError, because an empty digit array does not represent a number.

  • Zero: [0] returns immediately; an all-zero array such as [0, 0] is normalized to [0].

  • Leading zeros: The final scan produces canonical output without leading zeros, although normalizing inputs first avoids unnecessary computation.

  • One element and repeated digits: Both are handled by the same digit-pair loop; repeated values require no special case.

  • Negative or invalid digits: These raise ValueError. For signed numbers, keep the sign separately and multiply the magnitudes.

  • Digit order: Little-endian arrays must be reversed or handled with different index arithmetic.

  • Short result: The product has at most m + n digits, so leading zero positions are removed.

Code Example

def multiply_digits(num1: list[int], num2: list[int]) -> list[int]:
    """Multiply two non-negative digit arrays in most-significant-first order."""
    if not num1 or not num2:
        raise ValueError("Digit arrays must not be empty")

    if any(
        not isinstance(digit, int) or not 0 <= digit <= 9
        for digits in (num1, num2)
        for digit in digits
    ):
        raise ValueError("Each digit must be an integer from 0 through 9")

    if num1 == [0] or num2 == [0]:
        return [0]

    m, n = len(num1), len(num2)
    result = [0] * (m + n)

    for i in range(m - 1, -1, -1):
        for j in range(n - 1, -1, -1):
            product = num1[i] * num2[j] + result[i + j + 1]
            result[i + j + 1] = product % 10
            result[i + j] += product // 10

    start = 0
    while start < len(result) - 1 and result[start] == 0:
        start += 1

    return result[start:]


print(multiply_digits([1, 2, 3], [4, 5]))  # [5, 5, 3, 5]

Common Pitfalls

  • Off-by-one errors: The digit goes at i + j + 1; the carry goes at i + j.

  • Leaving leading zeros: Remove them from the returned result, but never remove its final remaining digit.

  • Assuming exactly m + n output digits: Smaller products leave leading zero positions.

  • Fixed-width overflow: Converting the complete arrays to int or long in fixed-width languages can overflow or throw an out-of-range error.

  • Mutating inputs: This solution does not modify either argument; do not mutate them unless the prompt explicitly permits it.

  • Likely follow-ups: Karatsuba, FFT-based multiplication, handling signs, and least-significant-digit-first layouts.

37

How to implement efficient range sum queries with arrays

The standard solution for answering range sum queries efficiently is the Prefix Sum array. This technique precomputes cumulative totals during a single pass, allowing any range sum to be calculated in constant time using simple subtraction.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

  • Build a new array where index i stores the sum of all elements from the start of the input up to index i - 1.

  • To find the sum from index left to right, subtract the prefix sum at left from the prefix sum at right + 1.

  • This works because prefix[right + 1] includes everything up to right, and subtracting prefix[left] removes everything before left.

  • The input array is not modified; a separate auxiliary array is created to store the cumulative sums.

Complexity Analysis

Operation Time Complexity Space Complexity Reason
Preprocessing O(n) O(n) One pass to compute cumulative sums (auxiliary array only; the input itself is not counted)
Query O(1) O(1) Single subtraction of two stored values
Approach Preprocess Per Query Space When to Use
Brute force (loop) O(1) O(n) O(1) Very few queries, or the array changes constantly
Prefix sum O(n) O(1) O(n) Many queries on a static array

Walkthrough and Edge Cases

For nums = [1, 2, 3, 4, 5]: 1. Build prefix = [0, 1, 3, 6, 10, 15]; each entry adds the next element of nums. 2. sum_range(1, 3) = prefix[4] - prefix[1] = 10 - 1 = 9, which equals 2 + 3 + 4.

Edge cases handled by the code: - Empty input: prefix = [0]; any query raises ValueError because no valid right index exists. - Single element: sum_range(0, 0) returns that element. - Negative numbers: handled naturally; prefix sums may decrease. - left == right: returns the single element at left. - Out-of-bounds indices: rejected by the validation check.

Code Example

class RangeSumQuery:
    """Implements efficient range sum queries using a prefix sum array."""

    def __init__(self, nums: list[int]) -> None:
        # prefix[i] holds the sum of nums[0...i-1]
        self.prefix = [0] * (len(nums) + 1)
        for i, num in enumerate(nums):
            self.prefix[i + 1] = self.prefix[i] + num

    def sum_range(self, left: int, right: int) -> int:
        # Validate range indices
        if not (0 <= left <= right < len(self.prefix) - 1):
            raise ValueError("Range indices out of bounds")
        # Sum from left to right is prefix[right+1] - prefix[left]
        return self.prefix[right + 1] - self.prefix[left]


query = RangeSumQuery([1, 2, 3, 4, 5])
print(query.sum_range(1, 3))  # Output: 9 (2 + 3 + 4)

Common Pitfalls

  • Off-by-one errors when calculating right + 1 or left.

  • Forgetting to handle left == 0 if using a 0-indexed prefix array without a sentinel; the sentinel approach above handles this naturally.

  • Assuming this works for frequent updates; use a Segment Tree or Binary Indexed Tree if the array changes often.

  • Integer overflow in languages with fixed-size integers; Python handles large integers automatically.

  • Mutating the input array instead of creating a copy, which may be disallowed by the interviewer.

38

What data structure efficiently represents sparse arrays?

A hash map can represent a sparse array by storing only nonzero values, mapping each occupied index to its value. For an array of logical size (n) containing (k) nonzero elements, this reduces persistent storage from (O(n)) to (O(k)), excluding the original input.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Representation

A sparse array needs two pieces of information:

  • Logical size: The number of positions the array conceptually contains.

  • Value map: A mapping from occupied indices to nonzero values.

For example, an array of size 10 with values at indices 1 and 7 can be represented as:

{1: 5, 7: -2}

Unstored positions implicitly contain the default value, usually 0.

Compared with conventional arrays:

Representation Index Access Storage Important Behavior
Static array (O(1)) (O(n)) Fixed size; allocated contiguously
Python list (O(1)) (O(n)) Dynamic array; append is amortized (O(1))
Sparse hash map (O(1)) average (O(k)) Stores only occupied positions
Compressed sparse row (O(1)) per retrieved row (O(k+r)) Efficient for sparse 2D matrices

A hash map is appropriate when (k) is much smaller than (n). If most positions are populated, a dense Python list has lower per-element overhead.

Complexity

Let (n) be the logical array size and (k) the number of stored nonzero entries.

Operation Best Average Worst Space
Get an index (O(1)) (O(1)) expected (O(k)), hence (O(n)) (O(1)) auxiliary
Set an index (O(1)) (O(1)) expected and amortized (O(k)) (O(1)) auxiliary or (O(k)) when inserted
Remove an index (O(1)) (O(1)) expected (O(k)) (O(1)) auxiliary
Build from a dense array (O(n)) (O(n)) expected (O(nk)) under pathological collisions (O(k)) additional
Materialize a dense array (O(n)) (O(n)) (O(n)) (O(n)) for the output
Visit stored entries (O(k)) (O(k)) (O(k)) (O(1)) auxiliary if streamed

The worst cases assume a hash table with severe collisions. Normal insertion cost is amortized (O(1)) because occasional table resizing is distributed across many insertions.

Persistent storage is (O(k)) and excludes the original dense input. There is no recursion stack, so recursion-stack space is (O(1)). When materializing a dense result, the (O(n)) output array is counted as additional space.

Small Walkthrough

Starting with logical size 10:

  1. The value map is initially {}.

  2. Setting index 2 to 4 produces {2: 4}.

  3. Setting index 7 to -1 produces {2: 4, 7: -1}.

  4. Setting index 2 to 0 removes key 2, restoring {7: -1}.

  5. Reading any missing index returns the default value, usually 0.

Negative and duplicate values are valid: negative values are stored, while duplicate values at different indices occupy separate map entries.

Code Example

from __future__ import annotations


class SparseArray:
    """Represent a fixed-size array using only its nonzero entries."""

    def __init__(
        self,
        size: int,
        initial_values: dict[int, int] | None = None,
    ) -> None:
        if size < 0:
            raise ValueError("size must be non-negative")

        self._size = size
        self._values: dict[int, int] = {}

        if initial_values is not None:
            for index, value in initial_values.items():
                self.set(index, value)

    @classmethod
    def from_dense(cls, values: list[int]) -> SparseArray:
        """Create a sparse array by scanning a dense list."""
        sparse = cls(len(values))

        for index, value in enumerate(values):
            sparse.set(index, value)

        return sparse

    def _validate_index(self, index: int) -> None:
        if index < 0 or index >= self._size:
            raise IndexError(f"index {index} is outside the array bounds")

    def get(self, index: int) -> int:
        """Return the value at an index, or 0 when it is not stored."""
        self._validate_index(index)
        return self._values.get(index, 0)

    def set(self, index: int, value: int) -> None:
        """Store a nonzero value, or remove the entry when value is 0."""
        self._validate_index(index)

        if value == 0:
            self._values.pop(index, None)
        else:
            self._values[index] = value

    def remove(self, index: int) -> int:
        """Remove and return the value at an index."""
        self._validate_index(index)
        return self._values.pop(index, 0)

    def stored_items(self) -> tuple[tuple[int, int], ...]:
        """Return the occupied index-value pairs in insertion order."""
        return tuple(self._values.items())

    def to_dense(self) -> list[int]:
        """Materialize the sparse array as a dense Python list."""
        dense = [0] * self._size

        for index, value in self._values.items():
            dense[index] = value

        return dense


sparse = SparseArray.from_dense([0, 5, 0, 0, -2, 0])
sparse.set(2, 9)
sparse.set(5, 0)

print((sparse.stored_items(), sparse.get(4)))
# (((1, 5), (4, -2), (2, 9)), -2)

Common Pitfalls

  • Treating zero as absent: This design cannot distinguish an unstored zero from an explicitly stored zero. If zero is meaningful, store an additional presence set or store every value, accepting (O(n)) storage.

  • Ignoring overhead: A hash map uses more memory per element than a dense list, so it is beneficial only when the array is sufficiently sparse.

  • Confusing logical and physical size: The logical size remains (n), but only (k) positions are physically represented.

  • Missing bounds checks: Negative indices and indices greater than or equal to the logical size must be rejected.

  • Choosing the wrong 2D representation: For matrix workloads needing fast row scans, the compressed sparse row format is often more compact than a nested dictionary.

  • Adding unnecessary ordering work: If ordered traversal is required, maintain sorted keys or use a balanced search tree, remembering that sorting (k) keys costs (O(klog k)).

39

How does Quickselect find the kth smallest element in an array?

Quickselect is a selection algorithm that returns the k-th smallest element of an array without fully sorting it. It reuses quicksort’s partition step but continues into only the side containing the target index, giving expected O(n) time. It fits arrays because it needs O(1) random access and in-place swaps.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How Quickselect Works

  1. Choose a pivot value from the current subarray.

  2. Partition the subarray into values less than, equal to, and greater than the pivot.

  3. If the target index k lies inside the equal range, return that value.

  4. If k is left of the equal range, continue on the left part; otherwise continue on the right part.

Unlike quicksort, which recurses into both sides, Quickselect discards the side that cannot contain the k-th smallest value.

Relation to Arrays

  • Random access: Quickselect reads and swaps elements by index, so a dynamic array such as a Python list is ideal: indexing is O(1), while append is amortized O(1) and middle insert/delete are O(n).

  • In-place operation: The standard version rearranges the input array. If the caller needs the original order, copy first with values.copy(), which costs O(n) extra space.

  • Not linked lists: A linked list lacks O(1) indexing, making partition and pivot access impractical.

Complexity

  • Best case: O(n), when the first pivot’s equal range contains k, so only one partition pass is needed.

  • Average case: O(n) with random pivots; expected work is roughly n + n/2 + n/4 + … = O(n).

  • Worst case: O(n^2), when pivots repeatedly land at an extreme and the target is at the other end.

  • Space: O(1) auxiliary for the iterative version; the input array is modified in place and is not counted as extra space. A recursive version uses O(log n) average stack space and O(n) worst-case stack space.

Approach Time Extra space When to use
Sort O(n log n) O(n) for Python sorted Need all elements ordered
Quickselect O(n) average, O(n^2) worst O(1) iterative Need only the k-th element and may modify input
Heap of size k O(n log k) O(k) Streaming data or input must stay unchanged

Step-by-Step Example

Target k = 2, meaning the third smallest value in [7, 10, 4, 3, 20, 15]. One possible run with random pivots:

Step Pivot Array after partition Equal range Next
1 10 [7, 4, 3, 10, 15, 20] indexes 3..3 k=2, search left
2 4 [3, 4, 7, 10, 15, 20] indexes 1..1 k=2, search right
3 7 [3, 4, 7, 10, 15, 20] indexes 2..2 k=2, return 7

Code Example

import random


def quickselect(values: list[int], k: int) -> int:
    """Return the 0-indexed k-th smallest value; rearranges values in place."""
    if not values or not 0 <= k < len(values):
        raise ValueError("values must be non-empty and k must be in range")

    def partition(left: int, right: int, pivot_value: int) -> tuple[int, int]:
        less, scan, greater = left, left, right
        while scan <= greater:
            if values[scan] < pivot_value:
                values[less], values[scan] = values[scan], values[less]
                less += 1
                scan += 1
            elif values[scan] > pivot_value:
                values[scan], values[greater] = values[greater], values[scan]
                greater -= 1
            else:
                scan += 1
        return less, greater

    left, right = 0, len(values) - 1
    while left <= right:
        pivot_value = values[random.randint(left, right)]
        equal_left, equal_right = partition(left, right, pivot_value)
        if k < equal_left:
            right = equal_left - 1
        elif k > equal_right:
            left = equal_right + 1
        else:
            return values[k]
    raise RuntimeError("unreachable")


numbers = [7, 10, 4, 3, 20, 15]
print(quickselect(numbers, 2))  # 7

Common Pitfalls

  • Off-by-one: Decide whether k is 0-indexed or 1-indexed; subtract 1 if the problem says “k-th” starting from 1.

  • Mutating input: Quickselect changes the array. Copy it if the original order matters.

  • Duplicate-heavy arrays: A two-way partition can degrade badly; the 3-way partition above groups equals in one pass.

  • Bad pivots: Random pivots avoid common adversarial cases, but worst-case O(n^2) remains possible. Median-of-medians gives O(n) worst-case time with higher constants.

  • Empty or one-element input: Validate k; a single-element array returns that element for k = 0.

  • Not a sort: Only the k-th element is guaranteed; other elements are merely partitioned.

40

How can Quicksort be optimized for arrays with many duplicates?

Three-way partitioning is the main optimization: it separates elements into values less than, equal to, and greater than the pivot, so duplicate values are processed only once. A randomized pivot and recursing into the smaller partition improve performance and keep recursion depth low.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

A conventional two-way partition usually places elements into “less than or equal to the pivot” and “greater than the pivot” groups. When many values equal the pivot, repeated partitioning can cause excessive work.

Three-way partitioning creates three regions:

  • Less-than region: values smaller than the pivot.

  • Equal region: values exactly equal to the pivot.

  • Greater-than region: values larger than the pivot.

Only the less-than and greater-than regions need further sorting. The implementation below also:

  • Chooses a random pivot to reduce predictable worst-case behavior.

  • Recursively sorts the smaller partition and processes the larger partition iteratively.

  • Sorts the list in place.

Why It Helps with Duplicates

For an array containing only one repeated value, a three-way partition completes in one scan:

[3, 3, 3, 3, 3] → less: [], equal: [3, 3, 3, 3, 3], greater: []

The equal region is excluded from further recursion. This avoids repeatedly partitioning equal elements, which can otherwise degrade a two-way implementation toward O(n²) time.

For example, with the pivot 3:

Step Array state
Initial [3, 1, 3, 2, 3]
Partition around 3 [1, 2, 3, 3, 3]
Sort less-than region [1, 2, 3, 3, 3]
Equal region No further work
Final [1, 2, 3, 3, 3]

Complexity

Case Time Reason
Best O(n log n) Balanced partitions produce logarithmic recursion depth
Average O(n log n) Randomized pivots give expected balanced partitions
Worst O(n²) A sequence of highly unbalanced pivots can be chosen
All equal values O(n) One three-way partition handles every element
  • Auxiliary space: O(log n), including the recursion stack, because the algorithm recursively sorts only the smaller partition.

  • Input storage: O(n) if the input array itself is counted; the list is modified in place and no additional O(n) array is allocated.

Array Context

A Python list is a dynamic array. It supports O(1) index access and amortized O(1) append, although inserting or deleting near the beginning costs O(n). Quicksort operates on the list’s existing contiguous storage and uses constant-time swaps, so it does not require extra array capacity.

The same algorithm applies to static arrays in languages with fixed-size contiguous storage, provided the array is mutable. The implementation returns the same list object rather than creating a copy.

Code Example

from random import randrange


def quicksort_three_way(values: list[int]) -> list[int]:
    """Sort values in place using randomized three-way quicksort."""

    def sort(left: int, right: int) -> None:
        while left < right:
            pivot = values[randrange(left, right + 1)]

            less = left
            current = left
            greater = right

            # Partition into values < pivot, == pivot, and > pivot.
            while current <= greater:
                if values[current] < pivot:
                    values[less], values[current] = values[current], values[less]
                    less += 1
                    current += 1
                elif values[current] > pivot:
                    values[current], values[greater] = values[greater], values[current]
                    greater -= 1
                else:
                    current += 1

            # Recurse into the smaller partition to limit stack depth.
            if less - left < right - greater:
                if left < less:
                    sort(left, less - 1)
                left = greater + 1
            else:
                if greater < right:
                    sort(greater + 1, right)
                right = less - 1

    sort(0, len(values) - 1)
    return values


example = [3, 1, 3, 2, 3, -1, 3]
print(quicksort_three_way(example))
# [-1, 1, 2, 3, 3, 3, 3]

Common Pitfalls

  • Forgetting the equal region: Ensure the equal elements are not recursively sorted again.

  • Unbalanced recursion: Recursing into the larger partition can cause O(n) recursion depth. Recursing into the smaller partition keeps the stack at O(log n).

  • Mutating the input: This implementation sorts the supplied list in place. Copy it first if callers require the original order.

  • Edge cases: Empty and one-element lists are handled automatically; negative values, duplicates, and already sorted inputs are supported.

  • Guaranteed worst-case performance: If worst-case O(n²) behavior is unacceptable, use introsort, which switches to heapsort after excessive partitioning, or use Python’s built-in list.sort(), which uses Timsort with O(n log n) worst-case time.

41

How to count inversions in an array efficiently

Inversion Count is the number of pairs (i, j) where i < j and arr[i] > arr[j]. The efficient comparison-based solution modifies merge sort to count split inversions during merging, achieving O(n log n) time instead of the brute-force O(n²).

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Approaches

A static array has a fixed capacity, while a dynamic array can grow as needed. Python’s list is a dynamic array: indexing is O(1), append is amortized O(1), and insertion or deletion in the middle is O(n). The merge-sort algorithm works with either representation, although the example uses Python lists.

Approach Time Space When to use
Brute force O(n²) O(1) Small arrays only
Merge sort O(n log n) O(n) General-purpose, comparison-optimal solution

How It Works

The merge sort approach exploits the divide-and-conquer structure of sorting. During a merge, if an element from the right subarray is placed before elements remaining in the left subarray, all those remaining left elements form inversions with it.

  • Divide: Split the array into two halves recursively until each subarray has one element.

  • Conquer: Count inversions within the left half and within the right half.

  • Combine: Merge the two sorted halves while counting split inversions — when right[j] < left[i], every element from left[i] to the end of the left half is greater than right[j].

The total inversions equal the left inversions plus the right inversions plus the split inversions.

Complexity

Case Time Space Reason
Best O(n log n) O(n) Merge sort always divides and merges
Average O(n log n) O(n) Same as best
Worst O(n log n) O(n) No degenerate case for merge sort

The recursion tree has O(log n) levels, and each level performs O(n) merging work. Space is O(n) for temporary arrays and lists, including O(log n) for the recursion stack. The input array itself is not counted.

Walkthrough

Consider [3, 1, 2]:

  1. Split into [3] and [1, 2].

  2. [1, 2] splits into [1] and [2], which merge with 0 inversions.

  3. Merge [3] with [1, 2]: 3 > 1, so add 1. Then 3 > 2, so add 1. The split inversions total 2.

  4. The overall count is 0 + 0 + 2 = 2. The inversions are (3, 1) and (3, 2).

Code Example

def count_inversions(arr: list[int]) -> int:
    """Count inversions in an array using a modified merge sort."""
    if len(arr) <= 1:
        return 0

    def merge_sort(items: list[int]) -> tuple[int, list[int]]:
        if len(items) <= 1:
            return 0, items

        middle = len(items) // 2
        left_inversions, left_sorted = merge_sort(items[:middle])
        right_inversions, right_sorted = merge_sort(items[middle:])
        merge_inversions, merged = merge(left_sorted, right_sorted)
        return (
            left_inversions + right_inversions + merge_inversions,
            merged,
        )

    def merge(left: list[int], right: list[int]) -> tuple[int, list[int]]:
        inversions = 0
        merged: list[int] = []
        i = j = 0

        while i < len(left) and j < len(right):
            if left[i] <= right[j]:
                merged.append(left[i])
                i += 1
            else:
                merged.append(right[j])
                j += 1
                inversions += len(left) - i

        merged.extend(left[i:])
        merged.extend(right[j:])
        return inversions, merged

    return merge_sort(arr)[0]


print(count_inversions([3, 1, 2]))  # Output: 2

Common Pitfalls

  • Off-by-one in the merge count: When right[j] < left[i], the count is len(left) - i, not len(left) - i + 1.

  • Empty or one-element input: Both produce 0 inversions; the code returns immediately.

  • Duplicates: The comparison left[i] <= right[j] ensures equal elements are not counted as inversions.

  • Negative values: They require no special handling because inversion counting uses relative comparisons.

  • Already sorted input: A nondecreasing array produces 0 inversions.

  • Mutating the input: This implementation does not modify the caller’s array, so permission to mutate the input is unnecessary. A variant that writes the sorted result back into the original still requires O(n) auxiliary space; merge sort is not an O(1)-extra-space in-place algorithm.

  • Integer overflow: The count can reach n * (n - 1) // 2. Python integers grow automatically, but fixed-width languages may require a 64-bit or wider integer.

  • Follow-up: Interviewers often ask for the actual inversion pairs, a permutation-specific solution, or an extension to other data structures.

42

How are Fenwick trees applied to array sum queries?

A Fenwick tree, also called a Binary Indexed Tree (BIT), efficiently maintains prefix sums of an array while allowing individual elements to be updated. It combines an array-like structure with O(log n) point updates, prefix queries, and range-sum queries.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

A Fenwick tree uses one-based indexing internally. For each internal position i, it stores a sum over a range whose length is determined by i & -i, commonly called the lowest set bit.

For example, in a tree of length 8:

  • tree[4] stores the sum of elements 1 through 4.

  • tree[6] stores the sum of elements 5 through 6.

  • tree[8] stores the sum of elements 1 through 8.

A prefix query for position p repeatedly adds tree[p], then replaces p with p - (p & -p). These ranges partition the requested prefix without overlap.

A point update starts at the updated position and repeatedly moves upward using p + (p & -p), updating every Fenwick node that contains that element.

Array Applications

  • Prefix sums: Query the sum of values[0:index + 1].

  • Range sums: Calculate prefix_sum(right) - prefix_sum(left - 1).

  • Frequency counts: Store counts or weighted counts at compressed value positions.

  • Inversion counting: Scan an array and use prefix counts to determine how many earlier elements exceed the current value.

  • Range updates and point queries: Store differences between adjacent elements in a Fenwick tree.

  • Order statistics: Find the smallest value whose cumulative count reaches a target, provided the underlying weights are non-negative.

Fenwick trees do not make arbitrary middle insertions efficient. Inserting into a Python list at index i remains O(n) because later elements must shift. A Fenwick tree should usually be rebuilt after structural changes.

Complexity

Operation Best case Average case Worst case Reason
Build O(n) O(n) O(n) Each node is propagated once
Point update O(1) O(log n) O(log n) Visits ancestors selected by lowbit
Prefix sum O(1) O(log n) O(log n) Visits disjoint lowbit ranges
Range sum O(1) O(log n) O(log n) Combines two prefix queries
  • Space: O(n) additional storage, excluding the original input array; O(n) total when the input is included.

  • There is no recursion stack.

  • Python integers do not overflow.

  • A Python list is a dynamic array: indexing is O(1), appending is amortized O(1), and insertion or deletion in the middle is O(n).

Approach Query time Extra space When to use
Direct prefix calculation O(n) O(1) A few one-off queries
Fenwick tree O(log n) O(n) Repeated queries with frequent updates

Code Example

def build_fenwick_tree(values: list[int]) -> list[int]:
    """Build a Fenwick tree from zero-based array values."""
    tree = [0] + values.copy()

    for position in range(1, len(tree)):
        parent = position + (position & -position)
        if parent < len(tree):
            tree[parent] += tree[position]

    return tree


def fenwick_add(tree: list[int], index: int, delta: int) -> None:
    """Add delta to a zero-based array index, modifying tree in place."""
    size = len(tree) - 1
    if size == 0:
        raise ValueError("Cannot update an empty Fenwick tree")
    if not 0 <= index < size:
        raise IndexError("Fenwick tree index out of range")

    position = index + 1
    while position <= size:
        tree[position] += delta
        position += position & -position


def fenwick_prefix_sum(tree: list[int], index: int) -> int:
    """Return the sum from index 0 through the inclusive zero-based index."""
    size = len(tree) - 1
    if index < -1 or index >= size:
        raise IndexError("Fenwick tree index out of range")

    position = index + 1
    total = 0
    while position > 0:
        total += tree[position]
        position -= position & -position

    return total


def fenwick_range_sum(tree: list[int], left: int, right: int) -> int:
    """Return the inclusive range sum from left through right."""
    size = len(tree) - 1
    if size == 0 or not 0 <= left <= right < size:
        raise IndexError("Invalid Fenwick tree range")

    return (
        fenwick_prefix_sum(tree, right)
        - fenwick_prefix_sum(tree, left - 1)
    )


def example() -> None:
    values = [3, -2, 5, 1]
    tree = build_fenwick_tree(values)

    fenwick_add(tree, 1, 4)
    prefix_total = fenwick_prefix_sum(tree, 2)
    range_total = fenwick_range_sum(tree, 1, 2)

    print(prefix_total, range_total)


example()  # Output: 10 7

Walkthrough

Starting values are [3, -2, 5, 1].

Step Operation Relevant result
1 Build the tree Internal values become [0, 3, 1, 5, 7]
2 Add 4 at array index 1 Internal positions 2 and 4 become 5 and 11
3 Query prefix through index 2 tree[3] + tree[2] = 5 + 5 = 10
4 Query range 1 through 2 10 - prefix_sum(0) = 10 - 3 = 7

Negative values and duplicates are valid for sum and frequency operations. An empty tree supports an empty prefix sum of 0, but it has no valid element to update.

Common Pitfalls

  • Off-by-one errors: Public APIs above use zero-based array indexes, while the tree internally uses one-based positions.

  • Input mutation: fenwick_add modifies the separate tree, not the original values list. Update the source list separately if it must remain synchronized.

  • Wrong tree size: Every update must stay within len(tree) - 1 elements.

  • Invalid order-statistics use: Finding the k-th element requires non-negative cumulative weights; arbitrary negative sums do not support that search.

  • Confusing features: Standard Fenwick trees directly support point updates and prefix sums. Other patterns, such as range updates with point queries, use a difference-array representation.

  • Typical follow-up: Interviewers may ask about building the tree in O(n), handling duplicate values during inversion counting, or choosing coordinate compression for large and negative values.

43

How do you solve the Skyline Problem with arrays?

The Skyline Problem asks for the outer contour of rectangular buildings supplied as an array of [left, right, height] triples. The standard array-based solution is a sweep line over sorted events, using a max-heap to track the tallest active building.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Idea

  1. Convert each building into two events in a dynamic array: (left, start, height, right) and (right, end, 0, 0).

  2. Sort events by x. For equal x, process starts before ends so a building starting at x is active, while one ending at x is not.

  3. Sweep left to right. Push each start’s (-height, right) onto a min-heap; the negative height simulates a max-heap.

  4. At each x, lazily remove heap tops whose right <= x. The heap top is the current maximum height, or 0 if the heap is empty.

  5. Append [x, height] only when the height changes; this merges flat segments and avoids duplicate key points.

Arrays and Complexity

  • Static array: fixed size, O(1) indexing, cannot grow without copying.

  • Dynamic array: Python list; append is amortized O(1), indexing is O(1), and inserting/deleting in the middle is O(n). This algorithm only appends and sorts.

  • 2D input: the input is an n x 3 array, so reading it is O(n). For a general m x n matrix, scanning is O(m*n). Never create a grid as [[0] * n] * m; use a comprehension.

  • In-place? The input is not modified. Events and the output are separate arrays.

  • Time: best case O(n) when the event array is already sorted and the heap stays small, such as non-overlapping buildings; average and worst case O(n log n) from sorting 2n events and pushing/popping each building at most once.

  • Space: O(n) excluding input for the event array, heap and skyline. Including input, still O(n) because there are n constant-size triples. There is no recursion stack.

Algorithm Choices

Approach Time Space When to use
Brute force: test every coordinate against all buildings O(n^2) O(n) Tiny inputs or as a baseline
Divide and conquer O(n log n) O(n) Avoids a heap; recursion depth is O(log n)
Sweep line + heap O(n log n) O(n) Standard array-based solution

Example

For [[1,3,2],[2,4,3]]:

x Action Heap top height Skyline
1 Start height 2 2 [1,2]
2 Start height 3 3 [2,3]
3 First building ends; height 3 remains active 3 unchanged
4 Second building ends; pop expired entries 0 [4,0]

Result: [[1,2],[2,3],[4,0]].

Code Example

import heapq


def get_skyline(buildings: list[list[int]]) -> list[list[int]]:
    """Return skyline key points for buildings [left, right, height]."""
    if not buildings:
        return []

    events: list[tuple[int, int, int, int]] = []
    for left, right, height in buildings:
        # type 0 = start, type 1 = end; starts sort before ends at the same x
        events.append((left, 0, -height, right))
        events.append((right, 1, 0, 0))

    events.sort()  # sort by x, then event type

    skyline: list[list[int]] = []
    heap: list[tuple[int, int]] = []  # (-height, right)
    previous_height = 0
    index = 0

    while index < len(events):
        x = events[index][0]

        # Add all buildings starting at this x.
        while index < len(events) and events[index][0] == x:
            _, event_type, neg_height, right = events[index]
            if event_type == 0:
                heapq.heappush(heap, (neg_height, right))
            index += 1

        # Remove buildings whose right edge is at or before x.
        while heap and heap[0][1] <= x:
            heapq.heappop(heap)

        current_height = -heap[0][0] if heap else 0
        if current_height != previous_height:
            skyline.append([x, current_height])
            previous_height = current_height

    return skyline


print(get_skyline([[2, 9, 10], [3, 7, 15], [5, 12, 12],
                  [15, 20, 10], [19, 24, 8]]))
# [[2, 10], [3, 15], [7, 12], [12, 0], [15, 10], [20, 8], [24, 0]]

Common Pitfalls

  • Right edge is exclusive: remove a building when right <= x, not only when right < x.

  • Same x ordering: process all starts at x before recording a height, otherwise you may emit intermediate key points.

  • Lazy deletion: only pop while the heap top is expired; expired entries buried below the top do not affect the maximum.

  • Duplicates and flat segments: append only when the height changes, so adjacent equal heights merge.

  • Edge cases: empty input returns []; one building works; zero-width buildings add no segment; negative coordinates work, but negative heights are invalid.

  • Follow-ups: output format, duplicate key points, streaming buildings, and the divide-and-conquer alternative are common interviewer extensions.

44

How do you efficiently transpose a matrix in Python?

Matrix transposition converts an m × n matrix into an n × m matrix by moving each element from position [row][col] to position [col][row]. The implementation below creates a new matrix, uses preallocated rows, and avoids modifying the input.

Read full answer

Applies toPython 3.12

How It Works

  1. Read the number of rows and columns.

  2. Create the result with n rows and m columns.

  3. Copy each input element using:

result[col][row] = matrix[row][col]

The result must be allocated independently for each row. Python lists are dynamic arrays, so preallocating the result avoids repeated resizing and ensures that rows are not accidentally shared.

Complexity

For an input matrix with m rows and n columns:

  • Time: O(m × n) because every element is visited and assigned exactly once.

  • Auxiliary space: O(1) beyond the returned matrix.

  • Space including the returned matrix: O(m × n).

  • Input storage: The input matrix is not counted as additional space and is not modified.

  • Recursion stack: O(1) because the implementation is iterative.

For a square n × n matrix, an in-place transpose can also use O(n²) time and O(1) auxiliary space, but it mutates the input and cannot handle rectangular matrices using the same approach.

Approach Time Extra space, excluding input When to use
New result matrix O(m × n) O(m × n) for the result Rectangular matrices or when the input must remain unchanged
In-place transpose O(n²) O(1) Square matrices when mutation is allowed
zip(*matrix) O(m × n) O(m × n) for the result Concise code for validated rectangular matrices

Example Walkthrough

For:

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

The result has three rows and two columns:

  1. matrix[0][0] = 1 moves to result[0][0].

  2. matrix[0][1] = 2 moves to result[1][0].

  3. matrix[0][2] = 3 moves to result[2][0].

  4. matrix[1][0] = 4 moves to result[0][1].

  5. matrix[1][1] = 5 moves to result[1][1].

  6. matrix[1][2] = 6 moves to result[2][1].

The final matrix is:

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

Code Example

def transpose(matrix: list[list[int]]) -> list[list[int]]:
    """Return a new matrix containing the transpose of a rectangular matrix."""
    if not matrix:
        return []

    row_count = len(matrix)
    col_count = len(matrix[0])

    if any(len(row) != col_count for row in matrix):
        raise ValueError("All rows must have the same length")

    # Result has col_count rows and row_count columns
    result = [[0] * row_count for _ in range(col_count)]

    for row in range(row_count):
        for col in range(col_count):
            result[col][row] = matrix[row][col]

    return result


# Expected output: [[1, 4], [2, 5], [3, 6]]
print(transpose([[1, 2, 3], [4, 5, 6]]))

Best Practices and Common Pitfalls

  • Validate rectangular matrices. zip(*matrix) is concise, but it can silently discard values when rows have different lengths.

  • Handle an empty matrix explicitly by returning [].

  • Preserve duplicates, negative numbers, zeros, and the original ordering of rows and columns.

  • Avoid [[0] * col_count] * row_count; the repeated inner list would share rows. Use a list comprehension as shown.

  • Clearly state whether the operation modifies its input. This version does not; an in-place implementation is more memory-efficient but restricted to square matrices.

  • Common follow-up questions ask about in-place transposition, sparse matrices, and the time and space trade-offs between creating a result and modifying the original.

45

Which array-based techniques make matrix multiplication efficient?

Matrix multiplication can be optimized through cache-friendly loop ordering, divide-and-conquer algorithms such as Strassen’s method, and optimized native matrix libraries. For general rectangular matrices in Python, a carefully ordered classical implementation is usually the most practical choice.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Method Comparison

For matrices left with dimensions m × k and right with dimensions k × n:

Method Time complexity Space complexity When to use
Naive i-j-k loops O(mkn) in all cases; each output element calculates a dot product of length k O(mn) for the output and O(1) auxiliary space; inputs are not counted Small matrices and simple implementations
Reordered i-k-j loops O(mkn) in all cases; the same arithmetic is arranged for better cache locality O(mn) for the output and O(1) auxiliary space; inputs are not counted General dense matrices and the usual practical choice
Strassen’s method O(n^log₂7) ≈ O(n².807) for square matrices; seven half-size products replace one full-size product O(n²) for the output and temporary matrices in a standard recursive implementation, including an O(log n) recursion stack; inputs are not counted Very large square matrices
Native blocked GEMM/BLAS Typically O(mkn) for dense multiplication; optimized native code improves locality and constants Implementation-dependent auxiliary space, plus O(mn) if the complete output is retained; inputs are not counted High-performance production workloads

Strassen’s method has a better asymptotic time bound but usually loses to optimized classical multiplication for small or medium matrices because of allocation and recursion overhead.

How the Cache-Friendly Algorithm Works

The result is defined by:

C[i][j] = sum(A[i][k] * B[k][j])

Instead of calculating each dot product with i-j-k ordering, the reordered algorithm uses i-k-j:

  1. Select one row from the left matrix.

  2. Visit each shared dimension k.

  3. Multiply the scalar left[i][k] by the corresponding row of the right matrix.

  4. Add the contribution to the result row.

In a contiguous row-major layout, this order accesses consecutive elements in both the right row and result row, improving cache utilization. Python nested lists have more pointer indirection than contiguous native arrays, so the benefit can be smaller.

Array Storage and Complexity

Python’s list is a dynamic array: indexing is O(1), append is amortized O(1), and inserting or deleting in the middle is O(n) because elements must be shifted. Fixed-size arrays provide O(1) indexing without resize overhead, but their dimensions cannot change.

A non-mutating classical implementation needs O(mn) space for the output and O(1) auxiliary space, excluding the input matrices. Its recursion stack is O(1) because no recursion is required. If the left matrix is overwritten instead, that must be explicitly permitted and the output dimensions must be compatible with the available storage.

For a nested-list representation, each output row must be allocated independently; multiplying every row of a list by the same inner list aliases those rows and causes incorrect updates.

Example Walkthrough

For [[1, 2], [3, 4]] × [[5, 6], [7, 8]]:

  1. C[0][0] = 1×5 + 2×7, producing 19.

  2. C[0][1] = 1×6 + 2×8, producing 22.

  3. C[1][0] = 3×5 + 4×7, producing 43.

  4. C[1][1] = 3×6 + 4×8, producing 50.

Common Pitfalls

  • Dimension mismatch: Multiplication is valid only when left has k columns and right has k rows.

  • Ragged rows: Reject matrices whose rows have inconsistent lengths.

  • Shared rows: Multiplying a list by an inner list creates aliased rows and produces incorrect updates.

  • Input mutation: A non-mutating approach leaves both inputs unchanged; overwriting an input requires explicit permission and compatible dimensions.

  • Integer overflow: Fixed-width arrays in other languages can overflow during multiplication or accumulation; use sufficiently wide integer types.

  • Edge cases: An empty outer list represents an empty matrix, while zero-row or zero-column matrices require an explicit representation and defined behavior. One-element matrices, duplicate values, and negative values are valid. Sortedness, graph connectivity, and cycles are not applicable.

46

How can arrays be used to solve a Sudoku puzzle?

Backtracking with row, column, and box occupancy arrays solves a Sudoku puzzle by trying valid digits, recursively filling the next empty cell, and undoing choices that lead to a contradiction. In Python, the board and occupancy tables are represented with dynamic list objects.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Approach

A Sudoku board is a 2D array of 81 cells. Maintain three additional 2D Boolean arrays:

  • row_values[row][digit]: whether a digit already exists in that row.

  • column_values[column][digit]: whether a digit already exists in that column.

  • box_values[box][digit]: whether a digit already exists in that 3×3 box.

For each empty cell, try digits 1 through 9. A digit is valid only if it is absent from all three corresponding occupancy arrays.

Python lists are dynamic arrays:

  • Indexing is O(1).

  • Appending is amortized O(1).

  • Inserting or deleting in the middle is O(n).

Algorithm

  1. Validate that the board is 9×9 and that prefilled digits are legal and non-duplicated.

  2. Build the row, column, and box occupancy arrays.

  3. Store the coordinates of empty cells in empty_cells.

  4. Recursively process the empty cells in order.

  5. Try every unused digit in the current cell.

  6. If a later cell cannot be solved, remove the digit and backtrack.

  7. Return True when every empty cell has been filled.

The box index is calculated as:

box = (row // 3) * 3 + (column // 3)

This maps each 3×3 box to a unique index from 0 through 8.

Example Walkthrough

Consider a nearly solved board whose only empty cell is the top-right cell:

1 2 3 | 4 5 6 | 7 8 .
4 5 6 | 7 8 9 | 1 2 3
7 8 9 | 1 2 3 | 4 5 6
  • The row already contains 1 through 8, so the only candidate is 9.

  • The column also permits only 9.

  • The top-right box is missing only 9.

  • The algorithm places 9, updates all three occupancy arrays, and reaches the end successfully.

In a harder puzzle, a chosen digit may cause a later contradiction. The algorithm then resets that cell to "." and tries the next candidate.

Code Example

def solve_sudoku(board: list[list[str]]) -> bool:
    """Solve a 9x9 Sudoku board in place using '.' for empty cells."""
    if len(board) != 9 or any(len(row) != 9 for row in board):
        return False

    row_values: list[list[bool]] = [[False] * 10 for _ in range(9)]
    column_values: list[list[bool]] = [[False] * 10 for _ in range(9)]
    box_values: list[list[bool]] = [[False] * 10 for _ in range(9)]
    empty_cells: list[tuple[int, int]] = []

    # Build occupancy arrays and validate prefilled cells.
    for row in range(9):
        for column in range(9):
            value = board[row][column]

            if value == ".":
                empty_cells.append((row, column))
                continue

            if value not in {"1", "2", "3", "4", "5", "6", "7", "8", "9"}:
                return False

            digit = int(value)
            box = (row // 3) * 3 + (column // 3)

            if (
                row_values[row][digit]
                or column_values[column][digit]
                or box_values[box][digit]
            ):
                return False

            row_values[row][digit] = True
            column_values[column][digit] = True
            box_values[box][digit] = True

    def search(index: int) -> bool:
        if index == len(empty_cells):
            return True

        row, column = empty_cells[index]
        box = (row // 3) * 3 + (column // 3)

        for digit in range(1, 10):
            if (
                row_values[row][digit]
                or column_values[column][digit]
                or box_values[box][digit]
            ):
                continue

            # Place the candidate and mark it in every constraint table.
            board[row][column] = str(digit)
            row_values[row][digit] = True
            column_values[column][digit] = True
            box_values[box][digit] = True

            if search(index + 1):
                return True

            # Undo the candidate before trying the next one.
            board[row][column] = "."
            row_values[row][digit] = False
            column_values[column][digit] = False
            box_values[box][digit] = False

        return False

    return search(0)


if __name__ == "__main__":
    board = [
        ["1", "2", "3", "4", "5", "6", "7", "8", "."],
        ["4", "5", "6", "7", "8", "9", "1", "2", "3"],
        ["7", "8", "9", "1", "2", "3", "4", "5", "6"],
        ["2", "3", "4", "5", "6", "7", "8", "9", "1"],
        ["5", "6", "7", "8", "9", "1", "2", "3", "4"],
        ["8", "9", "1", "2", "3", "4", "5", "6", "7"],
        ["3", "4", "5", "6", "7", "8", "9", "1", "2"],
        ["6", "7", "8", "9", "1", "2", "3", "4", "5"],
        ["9", "1", "2", "3", "4", "5", "6", "7", "8"],
    ]

    result = solve_sudoku(board)  # Expected: True

    print(result)
    # Expected output:
    # True

    for row in board:
        print(" ".join(row))
    # Expected output:
    # 1 2 3 4 5 6 7 8 9
    # 4 5 6 7 8 9 1 2 3
    # 7 8 9 1 2 3 4 5 6
    # 2 3 4 5 6 7 8 9 1
    # 5 6 7 8 9 1 2 3 4
    # 8 9 1 2 3 4 5 6 7
    # 3 4 5 6 7 8 9 1 2
    # 6 7 8 9 1 2 3 4 5
    # 9 1 2 3 4 5 6 7 8

Complexity

Let E be the number of empty cells.

Approach Time Space When to use
Exhaustive assignment enumeration O(9^E · 81) worst case O(E) auxiliary Simple correctness demonstration
Constraint-guided backtracking O(9^E) worst case O(E + 81) auxiliary Practical Sudoku solver, implemented above
  • Best case: O(81 + E) because validation and initialization occur once, and the first candidate path succeeds without backtracking.

  • Average case: Data-dependent and usually much faster than the worst case because invalid choices are rejected immediately; there is no guaranteed tighter bound.

  • Worst case: O(9^E) because the solver may explore up to nine choices for each empty cell.

  • Space: O(E + 81), including the recursion stack, empty_cells, and the occupancy arrays. The input board itself is not counted separately because it is modified in place. For a fixed 9×9 board, the board and occupancy sizes are constants.

Common Pitfalls and Interview Tips

  • Use matrix[row][column], not matrix[column][row].

  • Compute the 3×3 box index correctly; an off-by-one error produces incorrect candidate checks.

  • Remove both the board value and all occupancy flags when backtracking.

  • Validate prefilled duplicates before searching; otherwise the initial state may already be invalid.

  • The function modifies board in place. Copy the board first if the original must be preserved.

  • Empty, one-element, negative, or otherwise malformed boards return False. An already solved board returns True. “Sorted input,” disconnected graphs, and cycles are not applicable to the Sudoku grid model.

  • The recursion depth is at most 81 for a standard puzzle, safely below Python’s default recursion limit of approximately 1,000.

  • Common follow-up questions ask about uniqueness, constraint propagation, iterative backtracking, and why the occupancy arrays make candidate checks constant time.

47

Flatten a 2D matrix into a 1D array in place

In-place flattening converts the rows of a rectangular matrix into one row-major 1D array while reusing the matrix’s existing storage and avoiding a separate output buffer. The output itself necessarily requires space proportional to the number of elements, so “without extra space” conventionally means O(1) auxiliary space, excluding the output.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

For an m × n matrix, visit elements in row-major order:

  1. Use the first row as the output list.

  2. Append each subsequent row’s elements to that list.

  3. Remove the original row lists from the matrix.

  4. Return the flattened first row.

For example:

Before: [[1, 2], [3, 4]]
After:  [1, 2, 3, 4]

This approach modifies the input matrix and is appropriate when the caller does not need to preserve the original row structure.

Complexity

For a matrix with m rows and n columns:

  • Time: O(m × n) in the best, average, and worst cases, because every element must be copied into the flattened result.

  • Auxiliary space: O(1), excluding the input and output. No recursion stack is used.

  • Output space: O(m × n), since the result contains every matrix element.

  • Empty matrix: O(1) time and space.

In Python, a list may reallocate its backing storage when it grows, so the interpreter may temporarily use additional memory during extend. The algorithm does not create a separate flattened array.

Code Example

from typing import TypeVar

T = TypeVar("T")


def flatten_matrix_in_place(matrix: list[list[T]]) -> list[T]:
    """Flatten a rectangular matrix row-major using its first row as output."""
    if not matrix:
        return []

    column_count = len(matrix[0])

    if any(len(row) != column_count for row in matrix):
        raise ValueError("The matrix must be rectangular")

    result = matrix[0]

    for row_index in range(1, len(matrix)):
        result.extend(matrix[row_index])

    # Keep only the flattened row in the original matrix.
    del matrix[1:]

    return result


values = [[1, 2], [3, 4], [5, 6]]
flattened = flatten_matrix_in_place(values)

print(flattened)  # [1, 2, 3, 4, 5, 6]
print(values)     # [[1, 2, 3, 4, 5, 6]]

The function handles an empty matrix, an empty rectangular matrix such as [[], []], and matrices containing duplicates or negative numbers. It rejects ragged matrices because their row lengths differ.

Common Pitfalls

  • Confusing auxiliary space with output space: The flattened result still needs O(m × n) storage. A separate O(m × n) buffer is what the in-place approach avoids.

  • Using list.pop(0) or list.insert(0, value): Both are O(n) operations and defeat the purpose of an efficient in-place algorithm.

  • Overwriting unread values: If compacting directly into matrix cells, use a write pointer that never passes the read position.

  • Forgetting row-major order: The expected result for [[1, 2], [3, 4]] is [1, 2, 3, 4], not [1, 3, 2, 4].

  • Mutating input unexpectedly: Clearly state that the original matrix is changed. If the matrix must remain intact, allocate a separate flattened result.

48

How do you search a row-wise and column-wise sorted 2D array?

A row-wise and column-wise sorted matrix can be searched in O(m+n) time with the staircase search: start at the top-right corner, compare the current value with the target, and eliminate either the current column or the current row. This assumes a rectangular matrix whose rows and columns are sorted in ascending order.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How the Staircase Search Works

  • Let the matrix have m rows and n columns. Start at row = 0, col = n - 1.

  • If matrix[row][col] == target, return (row, col).

  • If target < matrix[row][col], the remaining cells below it in the current column are at least as large, so the target cannot be in that column. Decrement col.

  • If target > matrix[row][col], the remaining cells to its left in the current row are at most this value, so the target cannot be in that row. Increment row.

  • Stop when row == m or col < 0; the target is absent.

  • Starting at the bottom-left corner and moving up/right is the symmetric alternative.

Complexity

Approach Time Space When to use
Brute-force scan O(m*n) O(1) Small or unsorted matrices
Binary search each row O(m log n) O(1) Rows are sorted; columns may not be
Staircase search O(m+n) O(1) Both rows and columns are sorted
  • Best case: O(1) if the target is the starting cell.

  • Average and worst case: O(m+n), because each step removes one row or one column.

  • Space: O(1) auxiliary space, with no recursion stack. The input matrix itself is not counted.

  • The algorithm does not modify the input matrix.

  • Array representation: In Python, a list is a dynamic array: indexing is O(1), append is amortized O(1), and insertion or deletion in the middle is O(n). A statically allocated rectangular array also provides O(1) indexing but requires fixed dimensions. This search performs only O(1) reads per step and does not resize either structure.

Step-by-Step Example

Search for 29 in this matrix:

[[10, 20, 30, 40],
 [15, 25, 35, 45],
 [27, 29, 37, 48],
 [32, 33, 39, 50]]
Step Row Col Value Action
1 0 3 40 29 < 40, move left
2 0 2 30 29 < 30, move left
3 0 1 20 29 > 20, move down
4 1 1 25 29 > 25, move down
5 2 1 29 Found at (2, 1)

Code Example

def search_sorted_matrix(
    matrix: list[list[int]], target: int
) -> tuple[int, int] | None:
    """Return (row, col) of target in a rectangular row/column-sorted matrix."""
    if not matrix or not matrix[0]:
        return None

    rows = len(matrix)
    cols = len(matrix[0])
    row, col = 0, cols - 1

    while row < rows and col >= 0:
        value = matrix[row][col]
        if value == target:
            return (row, col)
        if target < value:
            col -= 1  # Eliminate the current column.
        else:
            row += 1  # Eliminate the current row.

    return None


matrix = [
    [10, 20, 30, 40],
    [15, 25, 35, 45],
    [27, 29, 37, 48],
    [32, 33, 39, 50],
]
print(search_sorted_matrix(matrix, 29))  # (2, 1)

Common Pitfalls and Interview Tips

  • Handle an empty matrix and an empty first row before indexing matrix[0].

  • Use col = len(matrix[0]) - 1; an off-by-one error breaks the search immediately.

  • A 1×1 matrix works without a special case.

  • With duplicates, this returns any matching cell, not necessarily the first in row-major order.

  • Negative numbers work because the algorithm relies on ordering rather than numeric magnitude.

  • An already-sorted matrix is the defining precondition, not merely an optimization.

  • The method requires both row-wise and column-wise sorting. If only rows are sorted, binary-search each row instead.

  • Common follow-ups include counting negative numbers, finding the k-th smallest element, and adapting the search when rows and columns are sorted in descending order.

49

How can you implement a priority queue with an array?

A binary heap implements a priority queue efficiently by storing elements in an array-like structure. Each node is no smaller than its parent in a min-heap, so the array’s first element is always the item with the highest priority.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How the Array Representation Works

A binary heap is a complete binary tree stored implicitly in a zero-indexed array:

  • Parent of index i: (i - 1) // 2

  • Left child of index i: 2 * i + 1

  • Right child of index i: 2 * i + 2

The core operations are:

  1. Push: Append the new element, then move it toward the root until the heap property is restored. This is called sift-up.

  2. Pop: Remove the root, replace it with the last element, then move that element downward. This is called sift-down.

  3. Peek: Return the root without modifying the heap.

The implementation below is a min-priority queue. Equal-priority elements are removed in insertion order using a sequence number.

Complexity

Operation Best Average Worst Reason
push O(1) O(log n) O(log n) At most one root-to-leaf path is traversed
pop O(1) O(log n) O(log n) At most one leaf-to-root path is traversed
peek O(1) O(1) O(1) The minimum is always at index 0
Build a heap from an existing array O(n) O(n) O(n) Nodes are processed bottom-up
  • Total space: O(n) for the stored heap elements.

  • Auxiliary space per operation: O(1).

  • Recursion stack: O(1), because both operations are iterative.

  • The heap itself is the data structure’s state; no separate input array is copied or counted.

An unsorted-array implementation is simpler: push is O(1), but pop and peek are O(n) because the entire array must be searched. The heap trades a little insertion cost for much faster removal.

Code Example

from typing import Generic, TypeVar

T = TypeVar("T")


class PriorityQueue(Generic[T]):
    """A min-priority queue backed by an array-based binary heap."""

    def __init__(self) -> None:
        self._heap: list[tuple[int, int, T]] = []
        self._next_sequence = 0

    def _key(self, index: int) -> tuple[int, int]:
        priority, sequence, _ = self._heap[index]
        return priority, sequence

    def push(self, priority: int, value: T) -> None:
        """Insert a value with the given priority."""
        self._heap.append((priority, self._next_sequence, value))
        self._next_sequence += 1

        child = len(self._heap) - 1

        while child > 0:
            parent = (child - 1) // 2

            if self._key(parent) <= self._key(child):
                break

            self._heap[parent], self._heap[child] = (
                self._heap[child],
                self._heap[parent],
            )
            child = parent

    def pop(self) -> T:
        """Remove and return the highest-priority value."""
        if not self._heap:
            raise IndexError("pop from an empty priority queue")

        priority, sequence, value = self._heap[0]
        last_item = self._heap.pop()

        if self._heap:
            self._heap[0] = last_item
            self._sift_down(0)

        return value

    def peek(self) -> T:
        """Return the highest-priority value without removing it."""
        if not self._heap:
            raise IndexError("peek from an empty priority queue")

        return self._heap[0][2]

    def _sift_down(self, root: int) -> None:
        while True:
            left = 2 * root + 1
            right = left + 1
            smallest = root

            if left < len(self._heap) and self._key(left) < self._key(smallest):
                smallest = left

            if right < len(self._heap) and self._key(right) < self._key(smallest):
                smallest = right

            if smallest == root:
                return

            self._heap[root], self._heap[smallest] = (
                self._heap[smallest],
                self._heap[root],
            )
            root = smallest

    def __len__(self) -> int:
        return len(self._heap)


queue: PriorityQueue[str] = PriorityQueue()
queue.push(2, "deploy")
queue.push(1, "page")
queue.push(1, "restart")

print(queue.pop())  # page
print(queue.pop())  # restart
print(queue.pop())  # deploy

Example Walkthrough

Using smaller numbers as higher priorities:

  1. Insert (2, "deploy"): the heap is [deploy].

  2. Insert (1, "page"): it sifts above deploy, producing [page, deploy].

  3. Insert (1, "restart"): it has the same priority as page but was inserted later, so page remains first.

  4. Popping returns page, then restart, and finally deploy.

Common Pitfalls and Interview Tips

  • A heap is not fully sorted; only the minimum or maximum is guaranteed to be at the root.

  • Define whether the queue is a min-heap or max-heap. Reverse the comparisons for a max-heap.

  • Handle an empty queue explicitly; this implementation raises IndexError.

  • Check child indexes before accessing them to avoid index errors.

  • Use a consistent tie-breaker if equal priorities must have predictable ordering.

  • This implementation modifies only its internal array; it does not mutate an external input array.

  • Common follow-up questions ask about heap construction in O(n), stable ordering, and how to implement a max-priority queue.

50

How do you implement a suffix array and why is it useful?

A suffix array is an integer array sa where sa[i] is the starting index of the i-th lexicographically smallest suffix of a string. It represents all suffixes with O(n) indices instead of O(n²) suffix strings, and it is the array-based alternative to a suffix tree.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Array Structure and Construction

  • For text of length n, the suffixes are text[i:] for i = 0..n-1; sa is a permutation of those start indices.

  • Store sa in a Python list, which is a dynamic array: indexing is O(1), append is amortized O(1), and inserting or deleting in the middle is O(n). Construction sorts the list rather than inserting into the middle.

  • Prefix doubling avoids storing suffix strings. Keep rank[i], the rank of suffix i by its first k characters. Sort indices by (rank[i], rank[i + k] if i + k < n else -1), assign new compact ranks, then double k. Stop when every rank is unique.

  • The sentinel -1 must be smaller than every real rank; it represents “past the end of the string.” Unicode code points are non-negative, so using ord() is safe.

  • Only integer arrays are needed: sa, rank, and new_rank.

  • For banana, the construction moves through these states; the final sorted suffixes are a, ana, anana, banana, na, nana:

After round sa rank
k = 1 [5, 1, 3, 0, 2, 4] [2, 1, 3, 1, 3, 0]
k = 2 [5, 3, 1, 0, 4, 2] [3, 2, 5, 1, 4, 0]
  • The function does not modify the input string; it returns a new index array. In-place mutation of caller data is generally not allowed unless documented.

  • The implementation below uses comparison sorting. Replacing each round with radix or counting sort reduces construction from O(n log² n) to O(n log n).

Why It Is Useful

  • Pattern search: binary-search the suffix array, comparing the pattern with a suffix character by character without slicing it. One search takes O(m log n) when m <= n; all occurrences form a contiguous range.

  • Longest repeated substring: build the LCP array, where lcp[i] for 1 <= i < n is the longest common prefix of suffixes sa[i-1] and sa[i]. The maximum LCP gives the repeated substring length.

  • Longest common substring: concatenate two strings with a separator absent from both strings and use the suffix array plus LCP.

  • Compression and indexing: suffix arrays underlie the Burrows-Wheeler transform, FM-index, full-text search, and genomic indexes.

  • Suffix-tree alternative: suffix arrays use less memory and have smaller constants, while LCP arrays recover much of the information a suffix tree provides.

Complexity

Space below is auxiliary: the input string occupies O(n) and is not counted. There is no recursion.

Operation Time Space
Build with prefix doubling and comparison sort O(n log n) best if ranks become unique after the first sort; O(n log² n) average and worst O(n)
Build with radix/counting-sort doubling O(n log n) best, average, and worst O(n)
SA-IS construction O(n) best, average, and worst O(n)
Locate one occurrence by binary search, with m <= n O(m) best; O(m log n) average and worst O(1)
Kasai LCP construction O(n) best, average, and worst O(n)

Code Example

def build_suffix_array(text: str) -> list[int]:
    """Return start indices of all suffixes in lexicographic order."""
    n = len(text)
    if n == 0:
        return []

    sa = list(range(n))                 # suffix start indices
    rank = [ord(ch) for ch in text]     # rank by first character
    k = 1

    while True:
        # Sort by first k chars represented by rank, then next k chars.
        sa.sort(key=lambda i: (rank[i], rank[i + k] if i + k < n else -1))

        new_rank = [0] * n
        for idx in range(1, n):
            prev, cur = sa[idx - 1], sa[idx]
            prev_key = (rank[prev], rank[prev + k] if prev + k < n else -1)
            cur_key = (rank[cur], rank[cur + k] if cur + k < n else -1)
            new_rank[cur] = new_rank[prev] + (cur_key != prev_key)

        rank = new_rank
        if rank[sa[-1]] == n - 1:       # all suffixes have unique ranks
            break
        k *= 2

    return sa


print(build_suffix_array("banana"))  # [5, 3, 1, 0, 4, 2]

Common Pitfalls and Interview Tips

  • Do not sort text[i:] directly; slicing every suffix can use O(n²) memory.

  • Handle the empty string by returning []; a one-character string must return [0].

  • Duplicate characters are handled by equal ranks; the next doubling round breaks ties.

  • For integer arrays, normalize ranks or choose a sentinel guaranteed smaller than every rank; -1 is safe only when ranks are non-negative.

  • In pattern search, avoid suffix slices in the comparison loop. Handle an empty pattern and reject a pattern longer than the text.

  • Interviewers often follow up with “build the LCP array,” “find all occurrences,” or “compare with a suffix tree or suffix automaton.”

51

How is a deque implemented with an array?

An array-backed deque stores elements in a circular buffer and tracks the front index and current size. Both ends map to array positions using modular arithmetic, so additions and removals avoid shifting the remaining elements.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

A fixed-capacity circular array uses a head index for the first element and a size counter. The right end is at (head + size - 1) % capacity.

  1. append_left moves head one position backward modulo the capacity.

  2. append_right writes at (head + size) % capacity.

  3. pop_left returns the value at head, clears that slot, and advances head.

  4. pop_right returns the value at the current tail.

  5. When a dynamic buffer is full, it allocates a larger array and copies elements into logical order, resetting head to 0.

For example, inserting 2 at the right, 1 at the left, and 3 at the right produces logical order [1, 2, 3]. Removing from each end then returns 1, followed by 3.

Complexity

Operation Best Average Worst Reason
append_left / append_right O(1) O(1) amortized O(n) A full dynamic buffer may require copying all n elements
pop_left / pop_right O(1) O(1) O(1) Only an endpoint index changes
peek_left / peek_right O(1) O(1) O(1) One slot is accessed directly

Space is O©, where C is the allocated capacity and n <= C; the input is not counted. A resize temporarily uses another O© slots. Because this implementation does not shrink, capacity can remain larger than the number of stored elements after many removals.

Static vs Dynamic Arrays

Array type Advantage Limitation
Static circular array Every endpoint operation is O(1) with no copying Insertion fails when fixed capacity is exhausted
Dynamic circular array Grows to fit the deque Endpoint additions become O(n) in the resize case, but O(1) amortized

A Python list is itself a dynamic array: indexing and append are O(1), with append amortized, but insert(0, value) and pop(0) take O(n) because they shift elements. A circular array avoids those shifts. The implementation modifies only its own internal array, not any caller-owned input.

Code Example

from typing import Generic, TypeVar, cast

T = TypeVar("T")


class ArrayDeque(Generic[T]):
    """A growable circular-array deque."""

    def __init__(self, initial_capacity: int = 8) -> None:
        if initial_capacity < 1:
            raise ValueError("initial_capacity must be positive")
        self._data: list[T | None] = [None] * initial_capacity
        self._head = 0
        self._size = 0

    def __len__(self) -> int:
        return self._size

    def is_empty(self) -> bool:
        return self._size == 0

    def _resize(self) -> None:
        old_data = self._data
        old_capacity = len(old_data)
        self._data = [None] * (old_capacity * 2)

        for logical_index in range(self._size):
            self._data[logical_index] = old_data[
                (self._head + logical_index) % old_capacity
            ]
        self._head = 0

    def append_left(self, value: T) -> None:
        if self._size == len(self._data):
            self._resize()
        self._head = (self._head - 1) % len(self._data)
        self._data[self._head] = value
        self._size += 1

    def append_right(self, value: T) -> None:
        if self._size == len(self._data):
            self._resize()
        tail = (self._head + self._size) % len(self._data)
        self._data[tail] = value
        self._size += 1

    def pop_left(self) -> T:
        if self.is_empty():
            raise IndexError("pop from an empty deque")

        value = cast(T, self._data[self._head])
        self._data[self._head] = None
        self._head = (self._head + 1) % len(self._data)
        self._size -= 1
        return value

    def pop_right(self) -> T:
        if self.is_empty():
            raise IndexError("pop from an empty deque")

        tail = (self._head + self._size - 1) % len(self._data)
        value = cast(T, self._data[tail])
        self._data[tail] = None
        self._size -= 1
        return value

    def peek_left(self) -> T:
        if self.is_empty():
            raise IndexError("peek from an empty deque")
        return cast(T, self._data[self._head])

    def peek_right(self) -> T:
        if self.is_empty():
            raise IndexError("peek from an empty deque")
        tail = (self._head + self._size - 1) % len(self._data)
        return cast(T, self._data[tail])


dq = ArrayDeque[int]()
dq.append_right(2)
dq.append_left(1)
dq.append_right(3)
print(dq.pop_left(), dq.pop_right(), dq.peek_left())  # 1 3 2

Common Pitfalls

  • Using list.insert(0, value) or list.pop(0) repeatedly introduces O(n) shifts.

  • Confusing the physical array order with the deque’s logical order after wraparound.

  • Forgetting to clear removed slots, which can retain references longer than necessary.

  • Miscounting the tail as head + size; the last stored index is head + size - 1.

  • Failing to test empty, one-element, full-buffer, wraparound, and resize cases.

  • Interviewers often follow up by asking for a fixed-capacity circular version, indexed access, or the minimum stack/queue variant.

52

How do I implement an array-based Trie in Python?

An array-based Trie represents each node with a fixed-size array of child indexes. In a lowercase-English alphabet, each node has 26 slots; -1 means that no child exists, while a non-negative value identifies another node.

Read full answer

Applies toPython 3.12

How It Works

The implementation maintains two parallel arrays:

  • _children[node][index]: the index of the child reached by a letter, or -1 if absent.

  • _terminal[node]: whether a word ends at that node.

For example, the slot at index 0 represents "a", index 1 represents "b", and index 25 represents "z".

Searching follows one child per character. Exact search additionally checks _terminal; prefix search only verifies that every character has a corresponding child.

Complexity

Let L be the word length, T the total number of inserted characters, N the number of stored words, and A = 26.

Operation Best Average Worst Auxiliary space
insert O(L + 1) O(L + 1) O(L + 1) O(1)
search O(L + 1) O(L + 1) O(L + 1) O(1)
starts_with O(L + 1) O(L + 1) O(L + 1) O(1)

Each character requires one array lookup. Auxiliary space excludes both the caller’s input string and the Trie’s stored nodes; no input copy or recursion stack is used.

The complete Trie requires O(A × T) space, which is O(T) for a fixed 26-letter alphabet.

Approach Lookup time Storage When to use
Scan every stored word O(NL) Existing corpus Small corpus or one-time lookup
Array-based Trie O(L) O(AT) Repeated lookup, insertion, or prefix queries

Example Walkthrough

Inserting "cat" creates these states:

Step Character Node state
1 "c" Root gains child c
2 "a" Node c gains child a
3 "t" Node ca gains child t
4 End Node cat is marked terminal

Code Example

class ArrayTrie:
    """A Trie for lowercase English letters using fixed-size child arrays."""

    _ALPHABET_SIZE = 26

    def __init__(self) -> None:
        # Each node stores indexes into the shared node arrays.
        self._children: list[list[int]] = [[-1] * self._ALPHABET_SIZE]
        self._terminal: list[bool] = [False]

    @staticmethod
    def _letter_index(character: str) -> int:
        """Return the array index for a lowercase English letter."""
        if len(character) != 1 or not ("a" <= character <= "z"):
            raise ValueError(
                f"Unsupported character {character!r}; expected 'a' through 'z'"
            )
        return ord(character) - ord("a")

    def insert(self, word: str) -> None:
        """Insert a word; inserting the same word again has no effect."""
        node = 0

        for character in word:
            letter_index = self._letter_index(character)
            child = self._children[node][letter_index]

            if child == -1:
                child = len(self._children)
                self._children[node][letter_index] = child
                self._children.append([-1] * self._ALPHABET_SIZE)
                self._terminal.append(False)

            node = child

        self._terminal[node] = True

    def search(self, word: str) -> bool:
        """Return True only when the complete word exists."""
        node = 0

        for character in word:
            letter_index = self._letter_index(character)
            node = self._children[node][letter_index]

            if node == -1:
                return False

        return self._terminal[node]

    def starts_with(self, prefix: str) -> bool:
        """Return True when any inserted word starts with the prefix."""
        node = 0

        for character in prefix:
            letter_index = self._letter_index(character)
            node = self._children[node][letter_index]

            if node == -1:
                return False

        return True


trie = ArrayTrie()
trie.insert("cat")
trie.insert("car")
trie.insert("cat")  # Duplicate insertion is idempotent.

result = (
    trie.search("cat"),
    trie.search("ca"),
    trie.starts_with("ca"),
    trie.search("dog"),
)

print(result)  # (True, False, True, False)

Edge Cases

  • Empty string: insert("") marks the root as terminal. search("") then returns True; otherwise it returns False. starts_with("") always returns True, because the empty string is a prefix of every string.

  • One character: A one-letter word creates one child node and works normally.

  • Duplicates: Inserting an existing word only resets its terminal flag, so duplicates do not create additional nodes.

  • Digits and negative numbers: Characters outside "a" through "z" raise ValueError. A larger alphabet can be supported with a different index calculation.

  • Input order: Sorted or unsorted insertion order does not affect lookup.

  • Cycles and disconnected graphs: These graph concepts do not apply to a Trie.

Common Pitfalls

  • Confusing prefix matching with exact matching: starts_with("ca") must not imply that "ca" is a word.

  • Forgetting the terminal flag: reaching the end of a path alone does not prove a complete word exists.

  • Assuming arbitrary characters are supported: the fixed alphabet must match the indexing logic.

  • Counting the Trie itself as per-operation auxiliary space; storage belongs to the data structure, while each operation uses O(1) additional space.

  • A common interview follow-up asks how to add deletion, word counts, or support characters beyond the fixed alphabet.

53

How does Kadane's algorithm solve the maximum subarray problem?

Kadane’s algorithm finds the maximum sum of a contiguous subarray in one left-to-right pass by tracking the best sum ending at the current position and the best sum seen so far. At each element it decides whether to extend the previous subarray or start a new one at the current element.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

Let current_sum be the maximum sum of a contiguous subarray that ends at the current index, and best_sum be the maximum sum found anywhere so far. The recurrence is:

current_sum = max(value, current_sum + value)

best_sum = max(best_sum, current_sum)

The local choice is to keep extending while the running sum helps, and to restart at value when the running sum would only reduce it. This is safe because if current_sum is negative, adding it to any future subarray can only make that future sum smaller; dropping it and starting fresh is at least as good.

Approaches Compared

Approach Time Extra space When to use
Brute force: check every contiguous subarray with a running sum O(n^2) O(1) Small inputs, or to explain the baseline
Kadane’s algorithm O(n) O(1) Standard optimal solution for one-dimensional arrays

Complexity

  • Time: O(n) in the best, average, and worst cases, because every element is visited once and each step performs constant work.

  • Space: O(1) extra space, excluding the input; there is no recursion stack. The input array itself is not counted.

  • Input mutation: The algorithm does not modify the input; it only reads elements.

  • Array model: Kadane’s algorithm works with both static and dynamic arrays. A Python list is a dynamic array: indexing is O(1), append is amortized O(1), and insertion or deletion in the middle is O(n). This solution only indexes existing elements.

Step-by-Step Example

For [-2, 1, -3, 4, -1, 2, 1, -5, 4]:

Value current_sum best_sum
-2 -2 -2
1 1 1
-3 -2 1
4 4 4
-1 3 4
2 5 5
1 6 6
-5 1 6
4 5 6

The maximum subarray is [4, -1, 2, 1], with sum 6.

Code Example

def max_subarray_sum(numbers: list[int]) -> int:
    """Return the maximum sum of a non-empty contiguous subarray.

    Raises ValueError if numbers is empty.
    """
    if not numbers:
        raise ValueError("numbers must contain at least one element")

    # Initialize with the first element so all-negative inputs work correctly.
    current_sum = numbers[0]
    best_sum = numbers[0]

    for index in range(1, len(numbers)):
        value = numbers[index]
        # Extend the previous subarray or start a new one at value.
        current_sum = max(value, current_sum + value)
        best_sum = max(best_sum, current_sum)

    return best_sum


example = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(max_subarray_sum(example))  # 6

Common Pitfalls and Edge Cases

  • Empty input: This version raises ValueError, because the maximum sum of a non-empty subarray is undefined for an empty array. If the contract allows an empty subarray, initialize current_sum and best_sum to 0 instead.

  • All-negative input: Do not initialize best_sum to 0 for the non-empty version; [-3, -2, -5] should return -2.

  • One element: The loop body is skipped, and the single value is returned correctly.

  • Duplicates, zeros, and already sorted input: These require no special handling; the recurrence still processes every element once.

  • Slicing the input: Avoid iterating over numbers[1:] because the slice allocates O(n) additional memory. Indexing preserves O(1) extra space.

  • Returning indices: If asked for the subarray itself, record a candidate start when restarting at value, and update the best start and end when current_sum beats best_sum.

  • Indexing and numeric limits: Keep the returned end index inclusive and check off-by-one errors. Python integers do not overflow, but fixed-width languages need a type large enough to hold the sum.

  • Graph-specific cases: Disconnected graphs, cycles, and visited sets are not applicable to this one-dimensional problem.

  • Large inputs: The iterative form avoids recursion-depth limits. Interviewers often follow up by asking for indices, a divide-and-conquer version, or the variant that allows an empty subarray.

54

How do you solve Minimum Jumps to Reach the End with arrays?

The Minimum Jumps to Reach the End problem finds the fewest jumps needed to move from index 0 to the last index of an array, where max_jumps[i] is the maximum distance allowed from index i. A greedy level-expansion algorithm solves it in O(n) time and O(1) auxiliary space.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Problem Model and Greedy Idea

The input can be a fixed-size static array or a dynamic array; the algorithm only requires indexed reads. Python list is a dynamic array: indexing is O(1), appending is amortized O(1), and inserting or deleting in the middle is O(n).

Treat reachable indices as levels in an implicit graph:

  • current_end is the farthest index reachable with the current number of jumps.

  • farthest is the farthest index reachable with one additional jump.

  • Whenever the scan reaches current_end, advance to the next level and increment the jump count.

The greedy choice is safe because every route to a farther position must make one more jump from the current reachable level. Taking the farthest possible endpoint therefore skips no shorter useful route.

Approach Comparison

Approach Time Space When to use
Enumerating all jump sequences O(2^n) upper bound O(n) recursion stack Primarily for conceptual comparison
Bottom-up dynamic programming O(n²) O(n) When constructing minimum-jump counts for every index
Greedy level expansion O(n) O(1) When only the minimum jump count is required

Example Walkthrough

For max_jumps = [2, 3, 1, 1, 4]:

  1. From index 0, the farthest candidate is 0 + 2 = 2. One jump reaches the level ending at index 2.

  2. Scan indices 1 and 2. Their candidates are 1 + 3 = 4 and 2 + 1 = 3, so the farthest candidate is 4.

  3. A second jump reaches index 4, the final index.

The answer is 2.

Code Example

def minimum_jumps_to_end(max_jumps: list[int]) -> int:
    """Return the minimum jumps to the last index, or -1 if unreachable."""
    if any(jump < 0 for jump in max_jumps):
        raise ValueError("Jump distances cannot be negative")

    if not max_jumps:
        return -1
    if len(max_jumps) == 1:
        return 0

    current_end = 0
    farthest = 0
    jumps = 0
    last_index = len(max_jumps) - 1

    for index in range(last_index):
        farthest = max(farthest, index + max_jumps[index])

        # The current reachable level has been fully scanned.
        if index == current_end:
            if farthest == current_end:
                return -1  # No further progress is possible.

            jumps += 1
            current_end = farthest

            if current_end >= last_index:
                return jumps

    return -1


print(minimum_jumps_to_end([2, 3, 1, 1, 4]))  # 2

Complexity and Edge Cases

  • Best-case time: O(1) when the target is reached immediately or the input has at most one element.

  • Average-case time: O(n), because the array may be scanned completely.

  • Worst-case time: O(n), since each index is processed at most once.

  • Auxiliary space: O(1), with no recursion stack. The input list occupies O(n) storage but is not counted as auxiliary space.

  • Empty input: Returns -1.

  • One element: Returns 0, because the target is already reached.

  • Zero-valued jump: Does not allow movement beyond that position; the algorithm returns -1 if progress stops.

  • Negative values: Rejected with ValueError, because a negative jump distance is invalid.

  • Duplicates or already sorted input: No special handling is required.

  • The implementation does not mutate the input.

Common Pitfalls

  • Incrementing jumps for every array element instead of only when reaching a level boundary.

  • Updating current_end without checking whether farthest made progress.

  • Allowing a jump of zero to count as movement.

  • Forgetting that an empty array has no target.

  • Mutating the input when a read-only algorithm is sufficient.

  • Python integers do not overflow; implementations using fixed-width integers in other languages should check bounds.

  • A common follow-up asks how to reconstruct the actual path. Greedy level expansion does not directly provide it, so a dynamic-programming solution with parent pointers is preferable.

55

How does a randomized set support O(1) insert, delete, and getRandom?

A randomized set supports average O(1) insertion, deletion, and random selection by combining a dynamic array with a hash map from each value to its index in that array. The array gives O(1) random access, while the map makes membership checks and index lookups average O(1); deletion avoids shifting by swapping the removed value with the last element.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Idea

  • Dynamic array: Python’s list is a dynamic array. Indexing is O(1), append is amortized O(1), but inserting or deleting in the middle is O(n) because elements shift.

  • Index map: index_of[value] stores where value lives in the array, so a linear search is unnecessary.

  • Insert: If the value already exists, return False. Otherwise, append it and record its new index.

  • Delete: Look up the value’s index, move the last array element into that slot, pop the last slot, and update the moved element’s index in the map.

  • getRandom: Pick a random index with random.randrange(len(values)) and return values[index]. Every element is equally likely.

  • Mutation: The structure mutates its own internal array and map by design. It does not mutate a caller’s input array; values from an input iterable are copied into the structure.

Complexity

Operation Best Average/expected Amortized Worst Why
insert O(1) O(1) O(1) O(n) Hash-map operations are expected O(1), while list growth is amortized O(1); collisions or resizing can make an operation O(n).
remove O(1) O(1) O(1) O(n) Lookup and swap are constant-time in the normal case; list shrinking is amortized O(1), but collisions or resizing can make an operation O(n).
getRandom O(1) O(1) O(1) O(1) Generating an index and indexing the array take constant time under the usual word-RAM model.

Space is O(n) for n stored elements, excluding the input. The map and list each hold n entries.

Why Not Just One Structure?

Approach Insert Delete getRandom Use when
List only O(1) append O(n) O(1) Random access matters and deletions are rare
Hash set only Average O(1) Average O(1) O(n) You need membership, not efficient random selection
List + index map Average O(1) Average O(1) O(1) You need all three operations
Balanced BST O(log n) O(log n) O(log n) or O(n) You also need ordered operations

Walkthrough

  1. insert(10): array [10], map {10: 0}.

  2. insert(20): array [10, 20], map {10: 0, 20: 1}.

  3. remove(10): index 0; the last value is 20; put 20 at index 0; pop the last slot; update map[20] = 0; delete map[10]. The array is [20].

  4. get_random(): random index 0, so return 20.

Code Example

import random


class RandomizedSet:
    """Set with average O(1) insert, remove, and uniform random selection."""

    def __init__(self) -> None:
        self.values: list[int] = []
        self.index_of: dict[int, int] = {}

    def insert(self, value: int) -> bool:
        """Add value; return False if it was already present."""
        if value in self.index_of:
            return False
        self.index_of[value] = len(self.values)
        self.values.append(value)
        return True

    def remove(self, value: int) -> bool:
        """Remove value; return False if it was absent."""
        if value not in self.index_of:
            return False

        index = self.index_of[value]
        last_index = len(self.values) - 1

        # Move the last element into the removed element's slot.
        if index != last_index:
            last_value = self.values[last_index]
            self.values[index] = last_value
            self.index_of[last_value] = index

        self.values.pop()
        del self.index_of[value]
        return True

    def get_random(self) -> int:
        """Return a uniformly random element; require a non-empty set."""
        if not self.values:
            raise IndexError("get_random from empty RandomizedSet")
        return self.values[random.randrange(len(self.values))]


random_set = RandomizedSet()
print(random_set.insert(10))      # True
print(random_set.insert(20))      # True
print(random_set.insert(10))      # False
print(random_set.remove(10))      # True
print(random_set.remove(99))      # False
print(random_set.get_random())    # 20 (only remaining element)

Common Pitfalls

  • Forgetting to update the moved element’s index after deletion.

  • Removing an element that is already last; the conditional index != last_index handles that case.

  • Using list.remove(value) or list.pop(0), both O(n), instead of swap-with-last and pop().

  • Calling get_random() on an empty set; the implementation raises IndexError.

  • Treating hash-map operations as worst-case O(1); they are expected O(1), with O(n) worst case under collisions.

  • Negative and zero values need no special handling, and duplicate insertions are rejected by the index map.

  • If duplicates must be supported, map each value to a collection of indices and update those indices after swaps.

56

How do you solve 0/1 Knapsack with dynamic programming arrays?

The 0/1 Knapsack Problem selects a subset of items whose total weight does not exceed a capacity while maximizing their total value. Dynamic programming stores the best achievable value for every capacity, updating the array backward so each item is selected at most once.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

Let matrix[item][capacity] represent the maximum value obtainable using the first item items with a capacity of at most capacity.

For each item with weight weight and value value, there are two choices:

  • Skip the item: keep matrix[item - 1][capacity].

  • Take the item: use matrix[item - 1][capacity - weight] + value, provided the item fits.

The recurrence is:

matrix[item][capacity] = max(matrix[item - 1][capacity], matrix[item - 1][capacity - weight] + value)

Only the previous row is needed, so the implementation compresses the table into one array named dp:

  • dp[capacity] stores the best value for that capacity.

  • Capacities are processed from largest to smallest.

  • Backward iteration prevents the current item from being reused, preserving the 0/1 constraint.

Approach Time Auxiliary space When to use
Brute-force subset enumeration O(n · 2ⁿ) O(n) recursion stack Very small inputs or teaching purposes
Array-based dynamic programming O(nW) O(W) General solution when capacity is manageable

Here, n is the number of items and W is the capacity.

Complexity and Array Choices

  • Time: O(nW) best, average, and worst case. Each of the n items may update W + 1 capacities.

  • Auxiliary space: O(W), excluding the input arrays. The DP array contains one value per capacity.

  • Total space including input: O(n + W).

  • Recursion stack: O(1), because the solution is iterative.

A conceptual two-dimensional DP table has (n + 1) rows x (W + 1) columns and requires O(nW) space. Compressing it to one row reduces that to O(W).

In Python, list is a dynamic array: indexing is O(1), append is amortized O(1), and insertion or deletion in the middle is O(n). The implementation preallocates a fixed-length list and assigns elements directly by index.

Code Example

def solve_01_knapsack(
    weights: list[int],
    values: list[int],
    capacity: int,
) -> int:
    """Return the maximum value achievable within the given capacity."""
    if capacity < 0:
        raise ValueError("capacity must be non-negative")
    if len(weights) != len(values):
        raise ValueError("weights and values must have the same length")
    if any(weight < 0 for weight in weights):
        raise ValueError("item weights must be non-negative")

    dp = [0] * (capacity + 1)

    for weight, value in zip(weights, values):
        # Descending order ensures each item is selected at most once.
        for current_capacity in range(capacity, weight - 1, -1):
            dp[current_capacity] = max(
                dp[current_capacity],
                dp[current_capacity - weight] + value,
            )

    return dp[capacity]


print(solve_01_knapsack([1, 3, 4], [15, 20, 30], 4))  # 35

Example Walkthrough

For weights [1, 3, 4], values [15, 20, 30], and capacity 4:

Items processed dp for capacities 0 through 4
None [0, 0, 0, 0, 0]
Weight 1, value 15 [0, 15, 15, 15, 15]
Weight 3, value 20 [0, 15, 15, 20, 35]
Weight 4, value 30 [0, 15, 15, 20, 35]

The best selection contains the items with weights 1 and 3, giving total weight 4 and total value 35.

Common Pitfalls

  • Ascending iteration: Updating capacities from small to large can reuse the current item and incorrectly solve the unbounded variant.

  • Wrong initialization: Initialize dp with zero when capacity is an upper bound; use -inf only for an exact-weight formulation.

  • Edge cases: Empty input returns 0; one item is handled naturally; duplicate items remain distinct; negative values are safely skipped; negative weights are invalid. Zero-weight items may be taken once but do not consume capacity.

  • Input ordering: The algorithm works with sorted or unsorted input and does not modify either input array.

  • Large capacities: O(nW) may be expensive when W is very large. An alternative DP indexed by total value can be considered when the sum of values is smaller.

  • Follow-up questions: Interviewers often ask about reconstructing the selected items, changing 0/1 to unbounded knapsack, or handling fractional items.

57

How do you find the median of two sorted arrays efficiently?

The median of two sorted arrays can be found in logarithmic time by binary-searching for a partition where every element on the left is no greater than every element on the right. This avoids merging or sorting the arrays and uses constant auxiliary space.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Idea

For arrays A and B, let the total number of elements be m + n.

  • If the total is odd, the median is the largest element in the left partition.

  • If the total is even, the median is the average of the largest element in the left partition and the smallest element in the right partition.

The combined left partition must contain:

left_size = (m + n + 1) // 2

For a candidate split, let i elements come from A and j from B, where i + j = left_size. The partition is valid when:

A[i - 1] <= B[j]
B[j - 1] <= A[i]

Missing boundary elements are treated as negative or positive infinity.

This algorithm works with both static arrays, whose capacity is fixed, and dynamic arrays, which can resize. It only requires indexed access and the array length. In Python 3.12, a list is a dynamic array: indexing is O(1), appending is amortized O(1), and inserting or deleting in the middle is O(n). This algorithm neither modifies the lists nor performs resizing operations.

Algorithm

  1. Put the shorter array in A so the binary-search range is minimized.

  2. Calculate left_size.

  3. Binary-search the possible split point i in A.

  4. Calculate the corresponding split point j in B.

  5. If the left boundary of A is greater than the right boundary of B, move the search left.

  6. If the left boundary of B is greater than the right boundary of A, move the search right.

  7. Once the partition is valid, return the middle value or the average of the two middle values.

Example Walkthrough

For A = [1, 3, 5] and B = [2, 4]:

  1. Total elements: 5, so left_size = 3.

  2. The binary search finds i = 2 and j = 1.

  3. Left partition: A[:2] + B[:1] = [1, 3] + [2].

  4. Right partition: A[2:] + B[1:] = [5] + [4].

  5. The largest left value is 3; the smallest right value is 4.

  6. Since the total is odd, the median is 3.

Complexity and Alternatives

Approach Time Auxiliary Space When to Use
Concatenate and sort O((m + n) log(m + n)) O(m + n) Simple baseline or unsorted input
Linear merge, median only O(m + n) O(1) When a single linear traversal is acceptable
Binary-search partition O(1 + log(min(m, n) + 1)) O(1) Median-only query on sorted arrays

For the binary-search approach:

  • Best case: O(1) when the first candidate partition is valid.

  • Average case: O(1 + log(min(m, n) + 1)).

  • Worst case: O(1 + log(min(m, n) + 1)).

  • Space: O(1) auxiliary space. The input lists are not counted, and there is no recursion stack.

Code Example

from math import inf


def median_of_two_sorted_arrays(nums1: list[int], nums2: list[int]) -> float:
    """Return the median of two nondecreasing integer arrays."""
    if not nums1 and not nums2:
        raise ValueError("At least one array must contain an element.")

    # Binary-search the shorter array.
    if len(nums1) > len(nums2):
        nums1, nums2 = nums2, nums1

    m = len(nums1)
    n = len(nums2)
    total = m + n
    left_size = (total + 1) // 2

    low = max(0, left_size - n)
    high = min(m, left_size)

    while low <= high:
        i = (low + high) // 2
        j = left_size - i

        a_left = nums1[i - 1] if i > 0 else -inf
        a_right = nums1[i] if i < m else inf
        b_left = nums2[j - 1] if j > 0 else -inf
        b_right = nums2[j] if j < n else inf

        if a_left > b_right:
            high = i - 1
        elif b_left > a_right:
            low = i + 1
        else:
            if total % 2 == 1:
                return float(max(a_left, b_left))

            return (max(a_left, b_left) + min(a_right, b_right)) / 2.0

    raise ValueError("No valid partition found.")


print(median_of_two_sorted_arrays([1, 3, 5], [2, 4]))  # 3.0

Common Pitfalls

  • Input precondition: Both arrays must be nondecreasing. The function does not validate this and may return an incorrect result for unsorted inputs.

  • Empty arrays: One empty array is supported; two empty arrays have no defined median, so the function raises ValueError.

  • Off-by-one errors: Carefully distinguish the left boundary (i - 1, j - 1) from the right boundary (i, j).

  • Incorrect partition size: For an odd total, use (total + 1) // 2; for an even total, this naturally equals total // 2.

  • Mutating input: This implementation does not modify either array.

  • Edge cases: Duplicates, negative values, already sorted input, and arrays with one element are handled normally.

  • Using only the shorter array incorrectly: The split in the longer array must always be recalculated as j = left_size - i.

58

What strategies prevent integer overflow in numeric arrays?

Integer overflow occurs when an arithmetic result exceeds the range supported by its data type. Effective prevention combines suitable array element types, boundary checks, widened or arbitrary-precision arithmetic, and an explicit policy for checked, wrapping, or saturating behavior.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Overflow Models and Array Choices

  • Fixed-width integers: Operations may wrap, saturate, raise an exception, or trigger undefined behavior, depending on the language.

  • Arbitrary-precision integers: Python int and Java BigInteger grow as needed, avoiding fixed-width overflow but increasing memory and processing costs for very large values.

  • Static arrays: Have a fixed length and usually fixed-width elements. Their size and element range must be selected before processing.

  • Dynamic arrays: Can grow at runtime. A Python list is dynamically sized; indexing is O(1), append is amortized O(1), and insertion or deletion in the middle is O(n).

Overflow is separate from array capacity. A dynamic array can have sufficient capacity while its elements still overflow during an operation.

Safe Strategies

Strategy Behavior Typical cost When to use it
Check before operating Compare against known minimum and maximum bounds O(1) per element When overflow should raise an error
Widen before operating Promote operands before addition or multiplication O(1) for fixed-width types When the result fits a larger type
Use arbitrary precision Allow the result to grow O(b) bit work for b-bit values When exact results of arbitrary size are required
Modular arithmetic Deliberately retain results modulo a fixed width O(1) for fixed-width values Cryptography, hashes, and intentional wraparound
Saturating arithmetic Clamp results to the representable range O(1) for fixed-width values Graphics, audio, and percentage calculations
Scale or split values Process smaller units or chunks Usually O(n) When the final result cannot fit directly

For addition of values a and b, bounds can be checked without performing the risky operation:

  • minimum - b <= a <= maximum - b

Use language-provided checked operations when available, such as Java’s Math.addExact and Math.multiplyExact. Widening must happen before the operation; converting the result afterward cannot recover an already-overflowed value.

Edge Cases

  • Empty input: Returns 0 (or the identity element for the operation).

  • One element: Checks that element against the allowed range.

  • Duplicates: Have no special effect.

  • Negative numbers: Are supported, including values that move the total downward.

  • Already sorted input: Does not affect correctness or complexity.

  • Extreme limits: Python handles the boundary comparisons safely because its integers are arbitrary precision.

  • Graph edge cases: Disconnected graphs and cycles are not applicable to this array operation.

Common Pitfalls and Interview Tips

  • Off-by-one errors: Clearly define whether bounds such as [0, 255] are inclusive.

  • Post-operation checks: Converting a wrapped result to a wider type does not restore lost information.

  • Unsigned arithmetic: Unsigned types usually prevent negative storage but can wrap during subtraction.

  • Mutating input: State whether an in-place update is allowed; otherwise return a new result.

  • Unstated behavior: Specify whether overflow should raise, wrap, saturate, or produce an arbitrary-precision result.

  • Unnecessary visited sets: A visited set is required for graph traversal, not for this array calculation.

59

What are the performance implications of caching and locality in arrays?

Data locality of reference determines how frequently array operations access nearby or recently used memory. Contiguous, sequential access generally benefits from CPU caching and hardware prefetching, improving runtime constants and memory bandwidth without changing the standard Big-O complexity of array operations.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How Caching and Locality Work

CPU caches retain small blocks of recently accessed memory rather than individual values. Arrays can exploit two forms of locality:

  • Spatial locality: Accessing array[i + 1] after array[i] uses adjacent memory, allowing nearby elements to share a cache line.

  • Temporal locality: Reaccessing the same element shortly afterward can retrieve it from a cache instead of main memory.

This produces several practical effects:

  • Sequential scans are usually faster per element than random access because the CPU can prefetch upcoming memory.

  • Cache-friendly algorithms consume less memory bandwidth and often execute faster, even when both versions have identical Big-O complexity.

  • Pointer-heavy structures, such as linked lists, can cause cache misses because each node may reside in a different memory region.

  • Caching improves constants, not asymptotic complexity. It does not make an O(n) middle insertion into an O(1) operation.

Complexity and Array Types

For a Python list, which is implemented as a dynamic array of object references:

Operation Best Average Worst Reason
values[index] O(1) O(1) O(1) The reference is found at a calculated position.
values.append(value) O(1) O(1) amortized O(n) Capacity grows occasionally, requiring one linear copy.
Insert or delete away from the end O(n) O(n) O(n) Existing elements must be shifted.
Sequential traversal O(n) O(n) O(n) Every element is visited once.

A sequence of n appends takes O(n) total time because the expensive resizes occur only occasionally.

  • Static array: Has fixed capacity and contiguous storage. It avoids resize costs, but overflow or insertion may require shifting elements.

  • Dynamic array: Grows as needed. Appending is amortized O(1), although an individual resize can take O(n).

  • Python list: Stores references to Python objects. The references are contiguous, but integer and other object values may live elsewhere.

  • array.array: Stores compact, fixed-width values contiguously, which can improve memory efficiency and locality for numeric workloads.

The array itself occupies O(n) space. A resize may temporarily allocate another O(n) backing store. These space figures exclude the caller’s input reference but include temporary storage; there is no recursion stack.

Cache-Friendly Access Patterns

Prefer traversal order that follows memory layout:

  • Use row-major order for a matrix: matrix[row][col].

  • For a matrix with rows rows and cols columns, any full traversal takes O(rows * cols) time and O(1) auxiliary space, excluding the input.

  • Two pointers and sliding windows are cache-friendly when both pointers move through adjacent positions.

  • Prefix sums are sequential and usually locality-friendly.

  • In-place partitioning and in-place swaps reduce memory traffic, although they modify the input.

  • Random-index algorithms may still be asymptotically optimal but can run substantially slower when the working set exceeds the CPU cache.

For the matrix:

1 2 3
4 5 6

Row-major traversal visits 1, 2, 3, 4, 5, 6. Column-major traversal visits 1, 4, 2, 5, 3, 6. Both take O(rows * cols) time, but row-major access follows each row’s storage order and generally has better locality.

Code Example

from collections.abc import Sequence


def sum_matrix_both_orders(
    matrix: Sequence[Sequence[int]],
) -> tuple[int, int]:
    """Return row-major and column-major sums for a rectangular matrix."""
    row_major = 0
    for row in matrix:
        for value in row:
            row_major += value

    column_count = len(matrix[0]) if matrix else 0
    column_major = 0
    for column in range(column_count):
        for row in range(len(matrix)):
            column_major += matrix[row][column]

    return row_major, column_major


print(sum_matrix_both_orders([[1, 2, 3], [4, 5, 6]]))  # (21, 21)

Both traversals use O(rows * cols) time and O(1) auxiliary space, excluding the input. The function supports empty and one-element matrices and handles negative values. It assumes the matrix is rectangular.

Best Practices

  • Store related data in a layout that matches its traversal order.

  • Prefer sequential loops when the order does not affect correctness.

  • Use compact numeric storage when the working set is large or memory locality matters.

  • Avoid assuming that a theoretical operation count captures actual performance; include cache misses and memory traffic in benchmarks.

  • When using an in-place algorithm, explicitly state that the input is modified and whether that is permitted.

Common Pitfalls

  • Mistaking cache benefits for a change in asymptotic complexity.

  • Assuming a Python list stores primitive values contiguously; it stores object references.

  • Assuming every append is individually O(1); only amortized O(1) is guaranteed.

  • Creating matrix rows with [[0] * cols] * rows, which shares the same row list. Use a list comprehension instead.

  • Introducing off-by-one errors when calculating row and column boundaries.

  • Mutating an input during an in-place algorithm without stating that behavior.

  • Python integers do not overflow, but fixed-width arrays and languages such as C++ may require overflow checks.

Interviewers commonly follow up by asking about cache lines, prefetching, working-set size, contiguous versus pointer-based layouts, and why an O(n) algorithm can outperform a theoretically similar O(n) implementation.

60

How can large-array access minimize page faults in memory-constrained systems?

Page-fault locality is the main lever: traverse large arrays in physical order, process bounded chunks when process memory is strictly constrained, and use file-backed mapping with readahead advice when appropriate. These techniques reduce unnecessary faults, although already-resident data requires no new fault until the OS evicts it.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How Page Faults Occur

  • Demand fault: The first access to a nonresident page causes the OS to resolve and map it.

  • Minor fault: The page can be serviced without storage I/O, such as a file page already in the page cache, a fresh allocation, or a copy-on-write page.

  • Major fault: The page is not in memory, so the OS must read it from storage (the file or swap).

  • Sequential access lets adjacent elements reuse the same resident pages. Random access may touch a different page for every lookup.

Access Strategies

Approach Time Space When to use
Read fixed-size chunks O(n) CPU plus O(n) bytes of I/O O(k) process memory for chunk size k Strict process-memory limit
Sequential memory-mapped scan O(n) CPU plus page-in I/O O(n) virtual mapping; resident set is OS-controlled Large file-backed array
Load the entire array O(n) copy plus O(n) processing O(n) resident memory The array fits comfortably in RAM
Random lookup O(1) CPU per lookup plus fault I/O Up to O(n/P) resident pages for n bytes and page size P A small, frequently reused subset

Additional techniques include:

  • Traverse multidimensional arrays in tiles so nearby accesses share pages. For row-major storage, avoid repeatedly jumping between distant columns.

  • Use mmap with MADV_SEQUENTIAL where supported to encourage readahead and earlier release of pages behind the scan.

  • Limit prefetch distance; reading too far ahead increases memory pressure and I/O contention.

  • Consider huge pages for large working sets. They reduce page-table overhead, but each allocation covers more memory.

  • Use a read-only scan unless mutation is explicitly required. The strategy should match whether modifying the source array is allowed.

Static and Dynamic Arrays

  • Static array: Fixed capacity and contiguous storage; growth requires reallocating or creating a larger array.

  • Python list: A dynamic array of object references. Indexing is O(1) because the address is calculated directly. Appending is O(1) amortized, although one resize can cost O(n). Middle insertion or deletion is O(n) because elements must shift.

  • array.array: A resizable, contiguous, typed array. Indexing is O(1), appending is O(1) amortized, and middle insertion or deletion is O(n). Its compact representation usually improves cache locality and reduces pages touched.

  • Memory-mapped view: A fixed-size file-backed mapping. It reserves virtual address space, but physical pages need not all become resident immediately.

Code Example

The following function scans native-endian signed 64-bit values sequentially. The chunk size limits each Python memoryview slice, but it does not cap the mapping’s resident set; use fixed-size file reads when that bound must be enforced by the process.

from array import array
import mmap
from pathlib import Path
from tempfile import TemporaryDirectory


def sum_i64_file(path: Path, chunk_values: int = 4096) -> int:
    """Sum native-endian signed 64-bit values using sequential mapped access."""
    if chunk_values <= 0:
        raise ValueError("chunk_values must be positive")

    size = path.stat().st_size
    if size == 0:
        return 0

    item_size = array("q").itemsize
    if size % item_size != 0:
        raise ValueError("file size must contain complete q values")

    with path.open("rb") as file:
        with mmap.mmap(file.fileno(), 0, access=mmap.ACCESS_READ) as mapped:
            # Advisory and available only on some platforms.
            if hasattr(mapped, "madvise") and hasattr(mmap, "MADV_SEQUENTIAL"):
                try:
                    mapped.madvise(mmap.MADV_SEQUENTIAL)
                except OSError:
                    pass

            values = memoryview(mapped).cast("q")
            try:
                total = 0
                for start in range(0, len(values), chunk_values):
                    end = min(start + chunk_values, len(values))
                    for value in values[start:end]:
                        total += value
                return total
            finally:
                values.release()


with TemporaryDirectory() as directory:
    path = Path(directory) / "values.bin"
    path.write_bytes(array("q", [5, -2, 7]).tobytes())
    result = sum_i64_file(path)  # 10
    print(result)  # 10

For [5, -2, 7]:

  1. The file is mapped without copying its entire contents into Python objects.

  2. Reading 5 may trigger a demand fault for the containing page.

  3. Reading -2 and 7 normally reuses that same resident page.

  4. The accumulated result is 5 - 2 + 7 = 10.

Complexity and Edge Cases

  • Traversal time: O(n) CPU because every value is visited once.

  • Page faults: The best case is zero when all required pages are already resident. The worst case is O(n/P) faults for n bytes and page size P. A universal average cannot be stated because it depends on cache residency, readahead, eviction, and access order.

  • Random access: CPU work is O(1) per lookup. Faults range from zero when pages are resident to O(n/P) for n uncached lookups that touch distinct pages; the average is workload-dependent.

  • Space: Python auxiliary space is O(1), including an O(1) recursion stack. A mapping reserves O(n) virtual address space and may resident O(n) bytes in the worst case, although its resident set is OS-controlled. The input file separately occupies O(n) bytes of storage. A chunked-read implementation instead uses O(k) process memory.

  • The code handles empty files, one-element files, duplicates, and negative values. Sortedness is irrelevant, and malformed file lengths are rejected. It does not modify the file.

Common Pitfalls

  • Calling unbounded read() or converting the whole dataset to a list defeats a strict memory limit.

  • Assuming madvise guarantees readahead or prevents faults; it is advisory and platform-dependent.

  • Assuming every fault requires physical-disk I/O.

  • Overestimating the memory bound of sliced mmap views.

  • Ignoring chunk-boundary errors or integer overflow when summing fixed-width values in languages with bounded integers.

  • Measuring resident memory and page-fault counts rather than relying only on theoretical access complexity; interviewers commonly ask how the solution behaves when the file is larger than RAM.

Sign in to keep reading

You've opened 2 full answers. Sign in to read all 60 Arrays answers, mark what you know and pick up where you left off.

Report a mistake

What's wrong?

All Data Structures & Algorithms subjects