Interview Guide: Arrays Problems and Solutions

Introduction to Arrays in Technical Interviews

Arrays are the most fundamental data structure in computer science and, by extension, the most frequently tested topic in coding interviews. An array is a contiguous block of memory that stores elements of the same type, accessible by index in constant O(1) time. Mastering array problems is not optional — it's the foundation upon which your interview performance is built.

From FAANG companies to startups, interviewers gravitate toward array questions because they test a candidate's ability to reason about memory, indices, iteration patterns, and edge cases under pressure. This guide covers everything you need to know: core concepts, problem-solving patterns, complete code solutions, and the best practices that separate strong candidates from exceptional ones.

Why Arrays Dominate Coding Interviews

Interviewers love arrays for several compelling reasons. Arrays require no custom class definitions, allowing candidates to dive straight into algorithmic reasoning. They expose a candidate's comfort with zero-based indexing, off-by-one errors, and boundary conditions — mistakes that reveal inexperience quickly. Furthermore, array problems scale naturally from trivial warm-ups to complex optimization challenges, letting interviewers probe the full depth of your skills in a single session.

Common array-based categories include:

• Searching and sorting — binary search, merge sort, quick sort foundations
• Two-pointer techniques — converging pointers, fast/slow pointers, partition schemes
• Sliding window — fixed and variable-size windows for subarray calculations
• Prefix sums — precomputed cumulative sums for range queries
• In-place manipulation — rotating, reversing, or rearranging without extra memory
• Duplicate and missing element detection — hash-based, index-marker, or XOR tricks
• Stock trading and profit maximization — classic dynamic programming on arrays

Problem Category 1: Two-Pointer Technique

The Classic: Two Sum in a Sorted Array

Given a sorted array of integers, find two numbers that add up to a target value. The brute-force O(n²) nested loop is unacceptable. Instead, place one pointer at the start and one at the end. If the sum exceeds the target, move the right pointer left; if the sum is too low, move the left pointer right. This converges in O(n) time.

def two_sum_sorted(arr, target):
    """
    Returns indices (1-indexed) of two elements summing to target.
    Assumes array is sorted in ascending order and exactly one solution exists.
    """
    left, right = 0, len(arr) - 1

    while left < right:
        current_sum = arr[left] + arr[right]

        if current_sum == target:
            return [left + 1, right + 1]  # 1-indexed as often required
        elif current_sum < target:
            left += 1  # Need a larger sum, move left pointer forward
        else:
            right -= 1  # Need a smaller sum, move right pointer backward

    return [-1, -1]  # No solution found (should not happen per problem constraints)

# Example usage:
numbers = [2, 7, 11, 15]
target_value = 9
result = two_sum_sorted(numbers, target_value)
print(f"Indices: {result}")  # Output: Indices: [1, 2]

Three Sum: Extending the Pattern

The three-sum problem asks for all unique triplets that sum to zero. The optimal approach sorts the array first (O(n log n)), then for each element, runs a two-pointer scan on the remaining suffix. This yields O(n²) overall complexity, a significant improvement over O(n³) brute force.

def three_sum(nums):
    """
    Returns all unique triplets [nums[i], nums[j], nums[k]] such that
    nums[i] + nums[j] + nums[k] == 0. No duplicate triplets in output.
    """
    nums.sort()
    result = []
    n = len(nums)

    for i in range(n - 2):
        # Skip duplicate values for the first element to avoid duplicate triplets
        if i > 0 and nums[i] == nums[i - 1]:
            continue

        left, right = i + 1, n - 1
        target_two_sum = -nums[i]

        while left < right:
            current = nums[left] + nums[right]

            if current == target_two_sum:
                result.append([nums[i], nums[left], nums[right]])
                left += 1
                right -= 1

                # Skip duplicates for the second element
                while left < right and nums[left] == nums[left - 1]:
                    left += 1
                # Skip duplicates for the third element
                while left < right and nums[right] == nums[right + 1]:
                    right -= 1

            elif current < target_two_sum:
                left += 1
            else:
                right -= 1

    return result

# Example usage:
nums_array = [-1, 0, 1, 2, -1, -4]
unique_triplets = three_sum(nums_array)
print(unique_triplets)  # Output: [[-1, -1, 2], [-1, 0, 1]]

Container With Most Water

This problem asks for the maximum area between two vertical lines on an elevation array. Two pointers start at the extremes. The area is limited by the shorter line; move the pointer at the shorter line inward, because moving the taller line can only decrease the maximum possible width without gaining height. This is a beautiful example of greedy choice within two-pointer traversal.

def max_area(height):
    """
    Given an array 'height' where height[i] represents the height of a vertical line
    at position i, return the maximum water area between any two lines.
    """
    left, right = 0, len(height) - 1
    max_water = 0

    while left < right:
        # Area = width * min(height[left], height[right])
        current_area = (right - left) * min(height[left], height[right])
        max_water = max(max_water, current_area)

        # Move the pointer at the shorter line inward
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1

    return max_water

# Example usage:
elevation = [1, 8, 6, 2, 5, 4, 8, 3, 7]
print(max_area(elevation))  # Output: 49

Problem Category 2: Sliding Window

Maximum Sum Subarray of Fixed Size K

The sliding window technique eliminates redundant recomputation by maintaining a running sum as the window slides across the array. For a fixed window size k, compute the sum of the first k elements, then for each subsequent step, subtract the element leaving the window and add the element entering. This runs in O(n) time regardless of k.

def max_sum_fixed_window(arr, k):
    """
    Returns the maximum sum of any contiguous subarray of length k.
    Assumes k <= len(arr) and all elements are integers.
    """
    n = len(arr)
    if n < k or k <= 0:
        return 0

    # Compute initial window sum
    window_sum = sum(arr[:k])
    max_sum = window_sum

    # Slide the window: remove leftmost element, add new rightmost element
    for i in range(k, n):
        window_sum = window_sum - arr[i - k] + arr[i]
        max_sum = max(max_sum, window_sum)

    return max_sum

# Example usage:
data = [2, 1, 5, 1, 3, 2]
k_size = 3
print(max_sum_fixed_window(data, k_size))  # Output: 9 (subarray [5, 1, 3])

Longest Substring Without Repeating Characters (Variable-Length Window)

Variable-length sliding windows expand when conditions hold and contract when they fail. For finding the longest substring without repeating characters, maintain a set of characters currently in the window. Expand the right boundary, and if a duplicate appears, contract the left boundary until uniqueness is restored. Track the maximum window size encountered.

def length_of_longest_substring(s):
    """
    Returns the length of the longest substring without repeating characters.
    Uses a sliding window with a character set for O(n) time complexity.
    """
    char_set = set()
    left = 0
    max_length = 0

    for right in range(len(s)):
        # If s[right] is already in the set, contract from the left
        while s[right] in char_set:
            char_set.remove(s[left])
            left += 1

        char_set.add(s[right])
        max_length = max(max_length, right - left + 1)

    return max_length

# Example usage:
test_string = "abcabcbb"
print(length_of_longest_substring(test_string))  # Output: 3 ("abc")

Minimum Window Substring (Advanced Variable Window)

This problem asks for the smallest contiguous substring containing all characters of a target string. The solution uses two hash maps — one for required character counts, one for current window counts — and two pointers. The right pointer expands until all required characters are satisfied, then the left pointer contracts to find the minimal valid window. This pattern is crucial for interview mastery.

def min_window(s, t):
    """
    Returns the minimum window substring of s that contains all characters
    in t (including duplicates). Returns empty string if no such window exists.
    """
    if not s or not t:
        return ""

    # Dictionary to store required character frequencies from t
    required = {}
    for char in t:
        required[char] = required.get(char, 0) + 1

    # Variables for sliding window
    window_counts = {}
    have = 0          # Number of unique characters satisfied
    need = len(required)  # Total unique characters needed

    left = 0
    min_len = float('inf')
    min_start = 0

    for right in range(len(s)):
        char = s[right]
        window_counts[char] = window_counts.get(char, 0) + 1

        # If this character is needed and count matches exactly, increment 'have'
        if char in required and window_counts[char] == required[char]:
            have += 1

        # Contract window while all required characters are satisfied
        while have == need:
            # Update minimum window if current is smaller
            current_len = right - left + 1
            if current_len < min_len:
                min_len = current_len
                min_start = left

            # Remove leftmost character from window
            left_char = s[left]
            window_counts[left_char] -= 1

            if left_char in required and window_counts[left_char] < required[left_char]:
                have -= 1

            left += 1

    return "" if min_len == float('inf') else s[min_start:min_start + min_len]

# Example usage:
s_source = "ADOBECODEBANC"
t_target = "ABC"
print(min_window(s_source, t_target))  # Output: "BANC"

Problem Category 3: Prefix Sums and Range Queries

Subarray Sum Equals K

The prefix sum pattern transforms "sum of subarray from i to j" into "prefix[j+1] - prefix[i]", converting a nested iteration problem into a hash-map lookup. For counting subarrays that sum to k, maintain a running prefix sum and a hash map of previously seen prefix sums and their frequencies. If prefix_sum - k exists in the map, a valid subarray has been found.

def subarray_sum_equals_k(nums, k):
    """
    Returns the total number of contiguous subarrays whose sum equals k.
    Uses prefix sums and a hash map for O(n) time complexity.
    """
    count = 0
    prefix_sum = 0
    # Map: prefix_sum -> frequency of occurrence
    prefix_freq = {0: 1}  # Base case: empty prefix with sum 0

    for num in nums:
        prefix_sum += num

        # If (prefix_sum - k) exists, we found subarrays ending at current index
        if (prefix_sum - k) in prefix_freq:
            count += prefix_freq[prefix_sum - k]

        # Record the current prefix sum for future iterations
        prefix_freq[prefix_sum] = prefix_freq.get(prefix_sum, 0) + 1

    return count

# Example usage:
arr_values = [1, 1, 1]
target_k = 2
print(subarray_sum_equals_k(arr_values, target_k))  # Output: 2

Product of Array Except Self

This problem asks for an output array where each element is the product of all other elements, without using division and in O(n) time. The elegant solution computes prefix products (left to right) and suffix products (right to left) in separate passes, then multiplies them. This is a classic illustration of how prefix/suffix decomposition solves constraint-heavy problems.

def product_except_self(nums):
    """
    Returns an array 'output' where output[i] equals the product of all
    elements in nums except nums[i]. O(n) time, O(1) extra space (excluding output).
    """
    n = len(nums)
    output = [1] * n

    # First pass: compute prefix products (left to right)
    prefix = 1
    for i in range(n):
        output[i] = prefix
        prefix *= nums[i]

    # Second pass: multiply by suffix products (right to left)
    suffix = 1
    for i in range(n - 1, -1, -1):
        output[i] *= suffix
        suffix *= nums[i]

    return output

# Example usage:
input_nums = [1, 2, 3, 4]
print(product_except_self(input_nums))  # Output: [24, 12, 8, 6]

Problem Category 4: In-Place Array Manipulation

Rotate Array by K Positions

Rotating an array in-place with O(1) extra space is a favorite interview challenge. The trick: reverse the entire array, then reverse the first k elements, then reverse the remaining n-k elements. This three-step reversal algorithm is both efficient and demonstrates mastery of in-place operations.

def rotate_array(nums, k):
    """
    Rotates the array nums to the right by k steps in-place.
    Uses the three-step reversal algorithm. k is normalized modulo n.
    """
    n = len(nums)
    k = k % n  # Handle cases where k >= n

    def reverse_slice(start, end):
        """Helper to reverse a portion of the array in-place."""
        while start < end:
            nums[start], nums[end] = nums[end], nums[start]
            start += 1
            end -= 1

    # Step 1: Reverse entire array
    reverse_slice(0, n - 1)
    # Step 2: Reverse first k elements
    reverse_slice(0, k - 1)
    # Step 3: Reverse remaining n-k elements
    reverse_slice(k, n - 1)

# Example usage:
rot_array = [1, 2, 3, 4, 5, 6, 7]
rotate_array(rot_array, 3)
print(rot_array)  # Output: [5, 6, 7, 1, 2, 3, 4]

Move Zeroes to the End

Moving all zeroes to the end while preserving the relative order of non-zero elements requires a write pointer tracking the next non-zero position. Scan the array: whenever a non-zero is found, swap it with the element at the write pointer and advance the pointer. This is in-place and runs in O(n) time.

def move_zeroes(nums):
    """
    Moves all 0's to the end of the array in-place while maintaining the
    relative order of non-zero elements.
    """
    write_ptr = 0  # Position where next non-zero should go

    for read_ptr in range(len(nums)):
        if nums[read_ptr] != 0:
            # Swap non-zero element to the write_ptr position
            nums[write_ptr], nums[read_ptr] = nums[read_ptr], nums[write_ptr]
            write_ptr += 1

    # All elements from write_ptr onward are now zeroes (implicitly)

# Example usage:
mixed_array = [0, 1, 0, 3, 12]
move_zeroes(mixed_array)
print(mixed_array)  # Output: [1, 3, 12, 0, 0]

Problem Category 5: Duplicate and Missing Element Detection

Find the Duplicate Number (Floyd's Tortoise and Hare)

Given an array of n+1 integers where each integer is between 1 and n inclusive, find the single duplicate. The array can be treated as a linked list where nums[i] points to the next index. Floyd's cycle detection algorithm — using fast and slow pointers — finds the duplicate without modifying the array or using extra memory.

def find_duplicate(nums):
    """
    Returns the duplicate number in an array of n+1 integers in range [1, n].
    Uses Floyd's Tortoise and Hare algorithm (cycle detection).
    Assumes exactly one duplicate exists and may appear multiple times.
    """
    # Phase 1: Find intersection point inside the cycle
    slow = nums[0]
    fast = nums[0]

    while True:
        slow = nums[slow]           # Move one step
        fast = nums[nums[fast]]     # Move two steps
        if slow == fast:
            break

    # Phase 2: Find the entrance to the cycle (the duplicate)
    slow = nums[0]
    while slow != fast:
        slow = nums[slow]
        fast = nums[fast]

    return slow

# Example usage:
dup_array = [1, 3, 4, 2, 2]
print(find_duplicate(dup_array))  # Output: 2

First Missing Positive (Index Marker Technique)

Finding the smallest missing positive integer in O(n) time and O(1) space is a hallmark interview problem. The approach: place each number in its correct index position (1 at index 0, 2 at index 1, etc.) through repeated swapping, then scan for the first index where the value doesn't match. This in-place reorganization is both elegant and efficient.

def first_missing_positive(nums):
    """
    Returns the smallest missing positive integer from an unsorted array.
    Runs in O(n) time with O(1) auxiliary space.
    """
    n = len(nums)

    # Place each number at its correct index: nums[i] should be i+1
    for i in range(n):
        # While nums[i] is a positive integer within range and not in correct position
        while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
            # Swap nums[i] to its correct position (nums[i] - 1)
            correct_idx = nums[i] - 1
            nums[i], nums[correct_idx] = nums[correct_idx], nums[i]

    # Scan for the first index where value != index + 1
    for i in range(n):
        if nums[i] != i + 1:
            return i + 1

    # If all positions 1..n are present, return n+1
    return n + 1

# Example usage:
test_nums = [3, 4, -1, 1]
print(first_missing_positive(test_nums))  # Output: 2

Problem Category 6: Stock Trading and Maximum Profit

Best Time to Buy and Sell Stock (Single Transaction)

The classic "max profit with one buy and one sell" problem teaches tracking the minimum seen so far and updating the maximum profit at each step. This O(n) greedy approach is the foundation for all stock-trading variants.

def max_profit_single(prices):
    """
    Returns the maximum profit achievable with a single buy followed by
    a single sell. Returns 0 if no profitable transaction is possible.
    """
    min_price = float('inf')
    max_profit = 0

    for price in prices:
        # Update minimum price seen so far (best day to buy)
        if price < min_price:
            min_price = price

        # Profit if sold at current price; update max profit
        current_profit = price - min_price
        if current_profit > max_profit:
            max_profit = current_profit

    return max_profit

# Example usage:
stock_prices = [7, 1, 5, 3, 6, 4]
print(max_profit_single(stock_prices))  # Output: 5 (buy at 1, sell at 6)

Best Time to Buy and Sell Stock II (Unlimited Transactions)

When unlimited transactions are allowed, the optimal strategy is to capture every upward price movement. Sum all positive differences between consecutive days — this greedy accumulation equals the maximum total profit.

def max_profit_unlimited(prices):
    """
    Returns maximum total profit with unlimited buy/sell transactions.
    You may only hold one share at a time.
    """
    total_profit = 0

    for i in range(1, len(prices)):
        # Capture every price increase as profit
        if prices[i] > prices[i - 1]:
            total_profit += prices[i] - prices[i - 1]

    return total_profit

# Example usage:
prices_series = [7, 1, 5, 3, 6, 4]
print(max_profit_unlimited(prices_series))  # Output: 7

Problem Category 7: Merge and Interval Operations

Merge Sorted Arrays

Merging two sorted arrays into one in sorted order is a fundamental operation that underpins merge sort. The approach uses three pointers — two for reading from each input array and one for writing to the merged output. This problem frequently appears as a warm-up or as part of a larger sorting question.

def merge_sorted_arrays(arr1, arr2):
    """
    Merges two sorted arrays into a single sorted array.
    Returns the merged sorted array.
    """
    merged = []
    i, j = 0, 0
    m, n = len(arr1), len(arr2)

    # Compare elements from both arrays and append the smaller one
    while i < m and j < n:
        if arr1[i] <= arr2[j]:
            merged.append(arr1[i])
            i += 1
        else:
            merged.append(arr2[j])
            j += 1

    # Append any remaining elements from arr1
    while i < m:
        merged.append(arr1[i])
        i += 1

    # Append any remaining elements from arr2
    while j < n:
        merged.append(arr2[j])
        j += 1

    return merged

# Example usage:
sorted_a = [1, 3, 5, 7]
sorted_b = [2, 4, 6, 8]
print(merge_sorted_arrays(sorted_a, sorted_b))
# Output: [1, 2, 3, 4, 5, 6, 7, 8]

Merge Intervals

Given a collection of intervals, merge all overlapping intervals. The key insight: sort intervals by start time, then iterate and merge whenever the current interval overlaps with the last merged interval. This pattern appears in calendar scheduling, meeting room allocation, and range query problems.

def merge_intervals(intervals):
    """
    Merges all overlapping intervals and returns the merged list.
    Each interval is represented as [start, end].
    """
    if not intervals:
        return []

    # Sort intervals by their start time
    intervals.sort(key=lambda x: x[0])

    merged = [intervals[0]]

    for current in intervals[1:]:
        last_merged = merged[-1]

        # If current interval overlaps with the last merged, extend the end
        if current[0] <= last_merged[1]:
            last_merged[1] = max(last_merged[1], current[1])
        else:
            # No overlap, add as a new merged interval
            merged.append(current)

    return merged

# Example usage:
interval_list = [[1, 3], [2, 6], [8, 10], [15, 18]]
print(merge_intervals(interval_list))
# Output: [[1, 6], [8, 10], [15, 18]]

Problem Category 8: Trapping Rain Water (The Crown Jewel)

Trapping Rain Water is widely considered one of the most important array problems in interviews. Given an elevation map, compute how much water can be trapped after rainfall. The two-pointer approach calculates water trapped at each position by tracking the maximum heights from both left and right sides simultaneously.

def trap_rain_water(height):
    """
    Returns the total amount of trapped rainwater.
    Uses two-pointer technique with left and right maximum tracking.
    O(n) time, O(1) space.
    """
    if not height:
        return 0

    left, right = 0, len(height) - 1
    left_max, right_max = 0, 0
    total_water = 0

    while left < right:
        # Work with the side that has the smaller boundary
        if height[left] < height[right]:
            if height[left] >= left_max:
                left_max = height[left]
            else:
                total_water += left_max - height[left]
            left += 1
        else:
            if height[right] >= right_max:
                right_max = height[right]
            else:
                total_water += right_max - height[right]
            right -= 1

    return total_water

# Example usage:
elevation_map = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
print(trap_rain_water(elevation_map))  # Output: 6

How to Approach Array Problems in Interviews

When you encounter an array problem during an interview, follow this structured approach to maximize your chances of success:

• Clarify constraints immediately — Ask about array size, element ranges, sorted vs. unsorted, duplicates, and whether in-place modification is allowed. These answers determine which techniques are viable.
• Start with a brute-force solution — Articulate the naive O(n²) or O(n³) approach first. This demonstrates you can solve the problem, buys you time to think, and provides a fallback if optimization stalls.
• Identify the pattern — Map the problem to one of the categories above: two-pointer, sliding window, prefix sum, in-place manipulation, or cycle detection. Naming the pattern aloud signals experience to the interviewer.
• Optimize step by step — Explain each optimization: "I'm using a hash map to reduce lookup from O(n) to O(1)" or "Sorting enables two-pointer scanning."
• Dry-run with a small example — Walk through your algorithm on a simple test case before coding. This catches logic errors early and impresses interviewers with your thoroughness.
• Handle edge cases explicitly — Empty arrays, single elements, all negative numbers, arrays with all identical values, and boundary conditions at index 0 and n-1.

Best Practices for Array Problem Success

• Master index arithmetic — Off-by-one errors are the most common interview mistake. Practice zero-based indexing until it's instinctive. When using 1-indexed output, document the conversion clearly.
• Prefer O(1) space solutions when possible — Interviewers reward in-place algorithms. Before allocating extra arrays or hash maps, ask yourself if the problem can be solved by modifying the input or using a few variables.
• Use meaningful variable names — left, right, slow, fast, write_ptr communicate your intent. Single-letter names like i, j are acceptable for loop indices but insufficient for pointer logic.
• Time your operations — Know that sorting is O(n log n), hash lookups are amortized O(1), and nested loops over the same array are O(n²). Verbalize complexity at each step.
• Test your code mentally before announcing completion — Run through a normal case, an edge case, and a boundary case. Correcting a bug silently before the interviewer notices it is far better than having it pointed out.
• Write clean, readable code — Use consistent spacing, avoid clever one-liners that obscure logic, and add brief comments explaining non-obvious steps. Interviewers read your code as a proxy for your professional work.
• Practice the most common problems until they're automatic — Two Sum, Three Sum, Maximum Subarray, Product Except Self, Trapping Rain Water, Merge Intervals, and Stock Trading variants appear with remarkable frequency across companies.

Common Pitfalls to Avoid

• Forgetting to handle the empty array case — Always check if not arr: return appropriate_value at the start of your function.
• Modifying the input array when not permitted — Some interviewers explicitly forbid input mutation. Ask first, and if disallowed, make a copy or use an alternative approach.
• Using division when the problem forbids it — Product Except Self is the classic example. Read constraints carefully.
• Incorrect loop termination conditions — Two-pointer loops typically use while left < right (not <=) to avoid processing the same element twice.
• Not handling integer overflow — In languages like Java or C++, prefix sums and products can overflow. In Python this is less of a concern, but mentioning it shows awareness.

Conclusion

Array problems form the backbone of coding interviews because they strip away complexity and expose raw algorithmic thinking. The patterns covered in this guide — two-pointer, sliding window, prefix sums, in-place manipulation, cycle detection, and greedy profit maximization — are not isolated tricks; they are reusable templates that apply across dozens of problems. Internalize these patterns through deliberate practice, and you'll approach any array problem with a structured, confident methodology. Remember: the goal is not merely to produce correct code, but to communicate your thought process clearly, handle edge cases gracefully, and optimize from brute force to an elegant solution. Master arrays, and you master the foundation of interview success.