Top Array Interview Questions (with Answers)

Keep a write pointer w marking where the next non-zero value belongs. Scan with a read pointer; whenever you find a non-zero value, swap it into position w and advance w. Non-zero values keep their relative order, and the zeros end up at the back in a single pass.

def move_zeroes(nums):
    w = 0
    for r in range(len(nums)):
        if nums[r] != 0:
            nums[w], nums[r] = nums[r], nums[w]
            w += 1

Time: O(n). Space: O(1).

Start l at the first element and r at the last. If the pair sums to less than the target, the only way to increase it is to move l right; if it is too large, move r left. Because the array is sorted, each move discards an element that cannot pair with anything still in range. The problem expects 1-based indices.

def two_sum_sorted(numbers, target):
    l, r = 0, len(numbers) - 1
    while l < r:
        s = numbers[l] + numbers[r]
        if s == target:
            return [l + 1, r + 1]  # 1-based indices
        if s < target:
            l += 1
        else:
            r -= 1
    return []

Time: O(n). Space: O(1).

This is the Dutch national flag problem. Keep three pointers: everything before low is 0, everything after high is 2, and mid scans the unknown middle. A 0 is swapped to low, a 2 is swapped to high, and a 1 stays. After swapping with high, do not advance mid, because the value that just arrived has not been examined yet.

def sort_colors(nums):
    low, mid, high = 0, 0, len(nums) - 1
    while mid <= high:
        if nums[mid] == 0:
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1
            mid += 1
        elif nums[mid] == 1:
            mid += 1
        else:
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1

Time: O(n), one pass. Space: O(1).

Sort the array. Fix each element nums[i] in turn and run the Two Sum II technique on the rest of the array, looking for a pair that sums to -nums[i]. Skip repeated values of nums[i], and after recording a triplet skip repeated values of nums[l], so no triplet is reported twice. Once nums[i] is positive, no later triplet can sum to zero.

def three_sum(nums):
    nums.sort()
    res = []
    for i in range(len(nums) - 2):
        if nums[i] > 0:
            break
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        l, r = i + 1, len(nums) - 1
        while l < r:
            s = nums[i] + nums[l] + nums[r]
            if s < 0:
                l += 1
            elif s > 0:
                r -= 1
            else:
                res.append([nums[i], nums[l], nums[r]])
                l += 1
                r -= 1
                while l < r and nums[l] == nums[l - 1]:
                    l += 1
    return res

Time: O(n²): the sort is O(n log n) and each of the n fixed elements runs a linear scan. Space: O(1) extra apart from the output and the memory the sort uses.

Start with the widest container, l = 0 and r = n - 1. Its area is min(height[l], height[r]) * (r - l). Then move the shorter line inwards. Moving the taller line can never help: the width shrinks, and the height is still capped by the shorter line, so every container using the shorter line has already been beaten.

def max_area(height):
    l, r = 0, len(height) - 1
    best = 0
    while l < r:
        best = max(best, min(height[l], height[r]) * (r - l))
        if height[l] < height[r]:
            l += 1
        else:
            r -= 1
    return best

Time: O(n). Space: O(1).

The water above bar i is min(highest bar on its left, highest bar on its right) - height[i]. Walk two pointers inwards while tracking left_max and right_max. Whenever height[l] < height[r], the right side always has a wall at least as tall as left_max, so the water at l depends only on left_max: add it and move l. Otherwise do the same from the right.

def trap(height):
    l, r = 0, len(height) - 1
    left_max = right_max = 0
    water = 0
    while l < r:
        if height[l] < height[r]:
            left_max = max(left_max, height[l])
            water += left_max - height[l]
            l += 1
        else:
            right_max = max(right_max, height[r])
            water += right_max - height[r]
            r -= 1
    return water

Time: O(n). Space: O(1). A prefix-maximum and suffix-maximum array version is easier to explain first and uses O(n) space.

A fixed window of size k. Sum the first k elements, then slide one step at a time: add the element entering on the right and subtract the one leaving on the left. Track the best sum and divide by k once at the end.

def find_max_average(nums, k):
    window = sum(nums[i] for i in range(k))
    best = window
    for i in range(k, len(nums)):
        window += nums[i] - nums[i - k]
        best = max(best, window)
    return best / k

Time: O(n). Space: O(1).

For each day, the best trade that sells today buys at the lowest price seen so far. Keep that running minimum and the best profit. You can see it as a window whose left edge jumps forward to every new minimum price.

def max_profit(prices):
    min_price = float("inf")
    best = 0
    for p in prices:
        min_price = min(min_price, p)
        best = max(best, p - min_price)
    return best

Time: O(n). Space: O(1).

All numbers are positive, so a window's sum only grows as it widens. Extend r and add to the running total. While the total is at least the target, record the window length and shrink from the left, since a shorter window starting later might still qualify.

def min_sub_array_len(target, nums):
    l = 0
    total = 0
    best = float("inf")
    for r, x in enumerate(nums):
        total += x
        while total >= target:
            best = min(best, r - l + 1)
            total -= nums[l]
            l += 1
    return 0 if best == float("inf") else best

Time: O(n). Each element enters and leaves the window at most once, so the inner loop is O(n) across the whole run, not per step. Space: O(1).

Rephrase the question: find the longest window containing at most k zeros, because those are the zeros you would flip. Count zeros as the window grows, and shrink from the left whenever the count goes above k.

def longest_ones(nums, k):
    l = 0
    zeros = 0
    best = 0
    for r, x in enumerate(nums):
        if x == 0:
            zeros += 1
        while zeros > k:
            if nums[l] == 0:
                zeros -= 1
            l += 1
        best = max(best, r - l + 1)
    return best

Time: O(n). Space: O(1).

The numbers are positive, so the product grows as the window widens. For each r, multiply in nums[r] and shrink from the left until the product is below k. Every subarray that ends at r and starts anywhere in l..r is then valid, which adds r - l + 1 to the count. If k is 1 or less, no product of positive integers can be below it.

def num_subarray_product_less_than_k(nums, k):
    if k <= 1:
        return 0
    prod = 1
    l = 0
    count = 0
    for r, x in enumerate(nums):
        prod *= x
        while prod >= k:
            prod //= nums[l]
            l += 1
        count += r - l + 1
    return count

Time: O(n). Space: O(1).

Keep a deque of indices whose values are in decreasing order. Before adding index i, pop every index from the back whose value is not larger than nums[i]; those values can never be a window maximum again. Drop the front index once it falls out of the window. The front of the deque is always the current window's maximum.

from collections import deque
 
def max_sliding_window(nums, k):
    dq = deque()  # indices; their values decrease from front to back
    res = []
    for i, x in enumerate(nums):
        while dq and nums[dq[-1]] <= x:
            dq.pop()
        dq.append(i)
        if dq[0] <= i - k:
            dq.popleft()
        if i >= k - 1:
            res.append(nums[dq[0]])
    return res

Time: O(n), because each index is pushed and popped at most once. Space: O(k) for the deque.

Build the prefix array once in the constructor, with a leading 0 so that ranges starting at index 0 need no special case. Each query is then one subtraction.

class NumArray:
    def __init__(self, nums):
        self.prefix = [0]
        for x in nums:
            self.prefix.append(self.prefix[-1] + x)
 
    def sumRange(self, left, right):
        return self.prefix[right + 1] - self.prefix[left]

Time: O(n) to build, O(1) per query. Space: O(n).

Compute the total once. Walk left to right keeping the sum of everything before the current index; the sum to the right is then total - left - nums[i]. Return the first index where the two sides match, or -1.

def pivot_index(nums):
    total = sum(nums)
    left = 0
    for i, x in enumerate(nums):
        if left == total - left - x:
            return i
        left += x
    return -1

Time: O(n). Space: O(1).

The sum of a subarray ending at j is prefix[j + 1] minus some earlier prefix, so the best one subtracts the smallest earlier prefix. Kadane's algorithm is the same idea in running form: cur is the best sum of a subarray ending at the current index, and you restart from the current element whenever carrying the previous sum would only drag it down. Start from nums[0], not 0, so an all-negative array returns its largest element.

def max_sub_array(nums):
    best = cur = nums[0]
    for i in range(1, len(nums)):
        cur = max(nums[i], cur + nums[i])
        best = max(best, cur)
    return best

Time: O(n). Space: O(1).

The answer at i is the product of everything before i times the product of everything after it. Fill the output with prefix products in a left-to-right pass, then multiply in suffix products in a right-to-left pass. No division is needed, which also avoids the special cases that zeros would cause.

def product_except_self(nums):
    n = len(nums)
    ans = [1] * n
    prefix = 1
    for i in range(n):
        ans[i] = prefix
        prefix *= nums[i]
    suffix = 1
    for i in range(n - 1, -1, -1):
        ans[i] *= suffix
        suffix *= nums[i]
    return ans

Time: O(n). Space: O(1) extra, since the problem does not count the output array.

Negative numbers are allowed, so a sliding window will not work. Keep a running prefix sum and a hash map counting how often each prefix sum has occurred. A subarray ending here sums to k exactly when an earlier prefix equals prefix - k, so add that count. Seed the map with a prefix sum of 0 seen once, for subarrays that start at index 0.

def subarray_sum(nums, k):
    seen = {0: 1}  # prefix sum -> number of times seen
    prefix = 0
    count = 0
    for x in nums:
        prefix += x
        count += seen.get(prefix - k, 0)
        seen[prefix] = seen.get(prefix, 0) + 1
    return count

Time: O(n) on average, because of the hash map. Space: O(n).

Treat every 0 as -1. A subarray with equal numbers of 0s and 1s now has a sum of 0, which means the running sum at its end equals the running sum just before its start. Store the first index where each running sum appears; the longest answer ending at i is i minus that first index. Seed the map with sum 0 at index -1.

def find_max_length(nums):
    first = {0: -1}  # running sum -> earliest index
    prefix = 0
    best = 0
    for i, x in enumerate(nums):
        prefix += 1 if x == 1 else -1
        if prefix in first:
            best = max(best, i - first[prefix])
        else:
            first[prefix] = i
    return best

Time: O(n). Space: O(n).

Store each value's index in a hash map as you scan. For each element x, check whether target - x is already in the map before inserting x; checking first stops an element from pairing with itself.

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

Time: O(n). Space: O(n). Sorting plus two pointers also finds the pair but loses the original indices unless you sort (value, index) pairs.

Add each value to a set and return as soon as you meet one that is already there. If memory is tight, sorting and comparing neighbours works too, at O(n log n) time.

def contains_duplicate(nums):
    seen = set()
    for x in nums:
        if x in seen:
            return True
        seen.add(x)
    return False

Time: O(n). Space: O(n).

Counting with a hash map and returning the most frequent value is the direct answer. The usual follow-up asks for O(1) space: Boyer-Moore voting keeps one candidate and a counter, adding 1 for a match and subtracting 1 otherwise, and takes a new candidate whenever the counter reaches 0. Because the majority value appears more than n/2 times, it survives all the cancelling.

from collections import Counter
 
def majority_element(nums):
    counts = Counter(nums)
    return max(counts, key=counts.get)
 
def majority_element_voting(nums):  # Boyer-Moore, O(1) space
    candidate, count = None, 0
    for x in nums:
        if count == 0:
            candidate = x
        count += 1 if x == candidate else -1
    return candidate

Time: O(n) for both. Space: O(n) with the counter, O(1) with voting.

Count frequencies with a hash map. No value can occur more than n times, so place each value in a bucket indexed by its frequency, then walk the buckets from highest to lowest until you have k values. A min-heap of size k is the other common answer, at O(n log k).

from collections import Counter
 
def top_k_frequent(nums, k):
    counts = Counter(nums)
    buckets = [[] for _ in range(len(nums) + 1)]  # buckets[f]: values seen f times
    for value, freq in counts.items():
        buckets[freq].append(value)
    res = []
    for freq in range(len(nums), 0, -1):
        for value in buckets[freq]:
            res.append(value)
            if len(res) == k:
                return res
    return res

Time: O(n). Space: O(n).

Put every value in a set. A value x starts a run only if x - 1 is not in the set; from each such start, count upwards while x + 1, x + 2 and so on are present. Every value is visited at most twice overall. Loop over the set rather than the original array, so duplicate starting values do not repeat the same run.

def longest_consecutive(nums):
    values = set(nums)
    best = 0
    for x in values:
        if x - 1 not in values:  # x starts a run
            length = 1
            while x + length in values:
                length += 1
            best = max(best, length)
    return best

Time: O(n) on average. Space: O(n). Sorting first gives a simpler O(n log n) solution, which is a fine starting point to mention.

The answer is always between 1 and n + 1, so only values in 1..n matter. Use the array as its own hash table: swap each such value v into index v - 1 until every position holds its own value or a value that does not belong anywhere. The first index i where nums[i] != i + 1 gives the answer i + 1; if every position matches, the answer is n + 1.

def first_missing_positive(nums):
    n = len(nums)
    for i in range(n):
        while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
            j = nums[i] - 1
            nums[i], nums[j] = nums[j], nums[i]
    for i in range(n):
        if nums[i] != i + 1:
            return i + 1
    return n + 1

Time: O(n). The while loop looks nested, but every swap puts one value in its final place, so there are at most n swaps in total. Space: O(1). Compute j before swapping; in Python, writing the swap with nums[nums[i] - 1] on both sides reads nums[i] after it has already changed.

nums1 has room for both arrays at its end. Fill it from the back: compare the largest remaining elements of each array and write the larger one into the last free slot. Filling from the back never overwrites a nums1 value you still need. When nums2 runs out, the rest of nums1 is already in place.

def merge(nums1, m, nums2, n):
    i, j, w = m - 1, n - 1, m + n - 1
    while j >= 0:
        if i >= 0 and nums1[i] > nums2[j]:
            nums1[w] = nums1[i]
            i -= 1
        else:
            nums1[w] = nums2[j]
            j -= 1
        w -= 1

Time: O(m + n). Space: O(1).

Sort by start. Walk through the intervals: if the current one starts at or before the end of the last merged interval, they overlap, so extend that end to the larger of the two; otherwise, start a new merged interval.

def merge_intervals(intervals):
    intervals.sort(key=lambda iv: iv[0])
    merged = []
    for start, end in intervals:
        if merged and start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    return merged

Time: O(n log n) for the sort; the merge pass is O(n). Space: O(n) for the output.

The input is already sorted and non-overlapping, so no sort is needed. Work in three phases: copy every interval that ends before the new one starts, merge every interval that starts before the new one ends into it, then copy the rest.

def insert(intervals, new_interval):
    res = []
    i, n = 0, len(intervals)
    start, end = new_interval
    while i < n and intervals[i][1] < start:
        res.append(intervals[i])
        i += 1
    while i < n and intervals[i][0] <= end:
        start = min(start, intervals[i][0])
        end = max(end, intervals[i][1])
        i += 1
    res.append([start, end])
    res.extend(intervals[i:])
    return res

Time: O(n). Space: O(n) for the output.

Minimising removals is the same as keeping as many non-overlapping intervals as possible. Sort by end time and greedily keep each interval that starts at or after the end of the last one kept: the interval that finishes earliest leaves the most room for the rest. In this problem, intervals that only touch, such as [1, 2] and [2, 3], do not overlap.

def erase_overlap_intervals(intervals):
    intervals.sort(key=lambda iv: iv[1])
    kept = 0
    last_end = float("-inf")
    for start, end in intervals:
        if start >= last_end:
            kept += 1
            last_end = end
    return len(intervals) - kept

Time: O(n log n). Space: O(1) extra apart from the sort.

Both lists are sorted and disjoint, so walk them with one pointer each. Two intervals intersect in [max(starts), min(ends)] whenever that range is not empty. Then advance whichever interval ends first, because it cannot intersect anything later in the other list.

def interval_intersection(first, second):
    i = j = 0
    res = []
    while i < len(first) and j < len(second):
        lo = max(first[i][0], second[j][0])
        hi = min(first[i][1], second[j][1])
        if lo <= hi:
            res.append([lo, hi])
        if first[i][1] < second[j][1]:
            i += 1
        else:
            j += 1
    return res

Time: O(m + n). Space: O(1) extra apart from the output.

Sorting and taking nums[n - k] works in O(n log n), and is worth saying first. The expected improvement keeps a min-heap of the k largest values seen so far: push each value, and pop the smallest whenever the heap grows past k. The top of the heap is the answer. Quickselect with a random pivot is the usual follow-up, at O(n) on average and O(n²) in the worst case.

import heapq
 
def find_kth_largest(nums, k):
    heap = []
    for x in nums:
        heapq.heappush(heap, x)
        if len(heap) > k:
            heapq.heappop(heap)
    return heap[0]

Time: O(n log k). Space: O(k).