Four Array Interview Problems with Worked Examples

1. Introduction to Array Patterns

These four problems teach different ways to avoid repeating work on an array. Before choosing an algorithm, identify what must stay together: a contiguous subarray, every element except one position, overlapping ranges, or groups of equal values. Those requirements lead to different solutions even though every input is an array.

You should already be comfortable with array indexing and loops. Review the array fundamentals guide if you need a refresher. Each example below states its assumptions; changing an assumption can change the correct algorithm.

Essential Array Patterns:

1. Kadane's Algorithm (Dynamic Programming / Sliding State)
2. Prefix / Suffix Products without Division
3. Interval Merging & Sweep-Line
4. In-Place Partitioning (Dutch National Flag)

2. Core Array Interview Questions & Solutions

Q1. Maximum Subarray Sum (Kadane's Algorithm)

Problem Statement: Given a non-empty integer array nums, return the largest sum of a non-empty contiguous subarray. For this C++ implementation, assume every possible subarray sum fits in a signed int.

At each position, there are only two useful choices: extend the best subarray ending immediately before it, or start again at the current value. A negative previous sum only makes a new subarray worse. This is why currentSum = max(nums[i], currentSum + nums[i]) is enough; we do not need to remember every earlier starting index.

For [-4, 3, -1, 2, -7, 4], track the best sum ending here separately from the best sum seen anywhere:

The result is 4, achieved by [3, -1, 2] and also [4]. The function returns the sum, not the indices. Initializing the best sum to zero would incorrectly allow an empty subarray: [-8, -3, -5] must return -3.

cpp
#include <vector>
#include <algorithm>

int maxSubArray(const std::vector<int>& nums) {
    int currentSum = nums[0];
    int maxSub = nums[0];

    for (std::size_t i = 1; i < nums.size(); i++) {
        currentSum = std::max(nums[i], currentSum + nums[i]);
        maxSub = std::max(maxSub, currentSum);
    }
    return maxSub;
}

• Time Complexity: O(N) | Space Complexity: O(1)

Check [5] → 5, [-8, -3, -5] → -3, and the mixed-sign example above. An empty array is outside this function's contract. For larger values, use a wider accumulator and specify its numeric limits.

Q2. Product of Array Except Self

Problem Statement: Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i], without using the division operator in O(N) time.

For each position, multiply the product strictly to its left by the product strictly to its right. Store the left products directly in the output array, then walk backward with one running right product. The empty product is 1, which handles the ends without a separate case.

For [2, 3, 4, 5], the first pass writes [1, 2, 6, 24]. The backward pass multiplies these values by [60, 20, 5, 1], giving [60, 40, 30, 24]. Because the method never divides, it also handles zeros: [0, 3, 4] → [12, 0, 0], while [0, 3, 0] → [0, 0, 0].

python
def productExceptSelf(nums: list[int]) -> list[int]:
    n = len(nums)
    output = [1] * n
    
    # Left prefix pass
    left_prefix = 1
    for i in range(n):
        output[i] = left_prefix
        left_prefix *= nums[i]
        
    # Right suffix pass
    right_suffix = 1
    for i in range(n - 1, -1, -1):
        output[i] *= right_suffix
        right_suffix *= nums[i]
        
    return output

• Time Complexity: O(N) | Space Complexity: O(1) auxiliary (excluding output array).

The total storage including the returned array is O(N). This implementation returns [] for an empty input and [1] for a single-element input. Complexity here counts arithmetic operations; Python's arbitrary-size integers take more time and memory as products grow.

Q3. Merge Intervals

Problem Statement: Given an array of intervals where intervals[i] = [start_i, end_i], merge all overlapping intervals.

Assume closed intervals with start_i <= end_i. Sort by the start coordinate. After sorting, the next interval can overlap only the last interval in the output; it cannot reach backward past a gap that was already established.

For [[6, 8], [1, 4], [3, 5], [9, 10]], sorting produces [[1, 4], [3, 5], [6, 8], [9, 10]]. Merge the first two into [1, 5]; the remaining intervals are separate. The result is [[1, 5], [6, 8], [9, 10]]. Under the closed-interval convention, [1, 4] and [4, 7] merge because they share endpoint 4.

java
import java.util.*;

class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals.length <= 1) return intervals;

        // Sort by interval start time
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

        List<int[]> merged = new ArrayList<>();
        int[] currentInterval = intervals[0];
        merged.add(currentInterval);

        for (int[] interval : intervals) {
            int currentEnd = currentInterval[1];
            int nextStart = interval[0];
            int nextEnd = interval[1];

            if (currentEnd >= nextStart) {
                // Overlap: expand end boundary
                currentInterval[1] = Math.max(currentEnd, nextEnd);
            } else {
                // No overlap: add new interval
                currentInterval = interval;
                merged.add(currentInterval);
            }
        }
        return merged.toArray(new int[merged.size()][]);
    }
}

• Time Complexity: O(N log N) (sorting) | Space Complexity: O(N)

This code sorts and modifies the input intervals. Copy the outer array and each inner pair first if the caller needs the original unchanged. Test an empty input, one interval, a contained interval such as [[1, 9], [2, 3]], touching endpoints, and disjoint ranges. Integer.compare avoids the overflow risk of sorting with a[0] - b[0].

Q4. Sort Colors (Dutch National Flag Algorithm)

Problem Statement: Given an array nums with n objects colored red, white, or blue (represented by 0, 1, 2), sort them in-place so that objects of the same color are adjacent.

Maintain four regions: zeros before low, ones from low to mid - 1, unclassified values from mid to high, and twos after high. Each loop iteration shrinks the unclassified region by one.

On [2, 0, 1], swap the first 2 with the last value to obtain [1, 0, 2] and reduce high. Keep mid at the same index: the value moved in from the right has not been classified. The next step advances over 1; the final step swaps 0 into the left region, producing [0, 1, 2].

javascript
function sortColors(nums) {
    let low = 0;
    let mid = 0;
    let high = nums.length - 1;

    while (mid <= high) {
        if (nums[mid] === 0) {
            [nums[low], nums[mid]] = [nums[mid], nums[low]];
            low++;
            mid++;
        } else if (nums[mid] === 1) {
            mid++;
        } else {
            [nums[mid], nums[high]] = [nums[high], nums[mid]];
            high--;
        }
    }
}

• Time Complexity: O(N) | Space Complexity: O(1) in-place.

The function returns nothing and mutates nums. Its contract permits only 0, 1, and 2; the else branch is not a validator for arbitrary integers. Test [], [2, 2], [2, 0, 1], and [2, 0, 2, 1, 1, 0]. Advancing mid after the swap with high is a common bug because it can skip an unclassified zero.

3. Summary of Array Problem Patterns

4. Choose the Pattern Before Writing Code

• Use Kadane's state when the answer concerns a contiguous sum. It does not solve arbitrary subsequence selection.
• Use prefix and suffix products when each answer excludes one position. Do not use division when zeros are allowed.
• Sort and merge when the inputs represent overlapping ranges. First clarify whether touching endpoints overlap.
• Use three-way partitioning when the domain contains exactly three categories. For general integers, choose a general sorting algorithm.

To check your understanding, explain one loop invariant aloud, trace a normal input on paper, and then choose an input that could break your implementation. Continue with the two-pointer guide, sorting guide, or available practice questions.