Arrays

An array is a row of values stored side by side, where you can read or write any position by its index (its position number, counting from 0) in constant time, which means the cost does not grow with the length of the list. Interviewers love array questions because they are quick to state and show at once whether you can avoid a slow loop inside a loop: move the zeros, find the best day to sell a stock, rotate a list, find the leaders. Underneath, most of them use one of a few patterns. Once you spot the pattern, the code is short. A "brute-force" idea means trying every possibility; the costs written O(n) and O(n²) are explained in Basics and maths.

Arrays in Java and lists in Python

A Java array has a fixed length that you choose when you create it, and reading past the end throws an exception. A Python list can grow and shrink, and it also reads and writes by index in constant time. On this site both arrive as "a list of integers" and your function returns the result. You may change the input in place and return it, or build a new list; both are accepted.

Pattern 1: one pass with a running value

Many problems need only one walk from left to right while you keep a small summary of what you have passed. Ask yourself: "what do I need to remember about the values behind me?" For the stock problem it is the lowest price so far. With prices 7, 1, 5, 3, 6, 4 the lowest price becomes 1 on day 2, and selling on day 5 at 6 earns 5, the best profit. For the largest sum of a run (Kadane's algorithm) the summary is the best sum of a run that ends at the current position. When the summary is one or two numbers, the solution is O(n) time and O(1) extra space.

Pattern 2: a write position

To filter or compact a list in place (inside the same list, without building a new one), keep a second index that marks where the next kept value goes. Walk the list with the first index; each value you keep is copied to the write position, which then moves one step. For 0, 1, 0, 3, 12 the values 1, 3 and 12 are written to positions 0, 1 and 2, and the rest is filled with zeros. The program below shows this "move zeros to the end" answer together with the stock problem.

import java.util.Arrays;

public class Main {
    static int[] moveZeroes(int[] nums) {
        int write = 0;
        for (int value : nums) {
            if (value != 0) {
                nums[write++] = value;
            }
        }
        while (write < nums.length) {
            nums[write++] = 0;
        }
        return nums;
    }

    static int maxProfit(int[] prices) {
        int lowest = Integer.MAX_VALUE;
        int best = 0;
        for (int price : prices) {
            lowest = Math.min(lowest, price);
            best = Math.max(best, price - lowest);
        }
        return best;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(moveZeroes(new int[] {0, 1, 0, 3, 12})));
        System.out.println(maxProfit(new int[] {7, 1, 5, 3, 6, 4}));
    }
}

[1, 3, 12, 0, 0]
5

def move_zeroes(nums):
    write = 0
    for value in nums:
        if value != 0:
            nums[write] = value
            write += 1
    for i in range(write, len(nums)):
        nums[i] = 0
    return nums


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


print(move_zeroes([0, 1, 0, 3, 12]))
print(max_profit([7, 1, 5, 3, 6, 4]))

[1, 3, 12, 0, 0]
5

Pattern 3: two ends and reversal

Two indexes that start at both ends and move toward each other reverse a list in place in n / 2 swaps. Reversal is also the trick behind rotation. Rotating right by k steps means moving the last k values to the front. To rotate 1, 2, 3, 4, 5, 6, 7 right by 3: reverse it all (7, 6, 5, 4, 3, 2, 1), reverse the first 3 values (5, 6, 7, 4, 3, 2, 1), then reverse the rest (5, 6, 7, 1, 2, 3, 4). Reduce k first with k mod n (the remainder of k divided by n, where n is the length of the list), because rotating n steps gives the same list back, and handle the empty list before you divide by its length.

Pattern 4: scan from the right

Some questions talk about "everything to the right" of a position, such as the leaders problem (values greater than everything to their right). Walk from the right end and keep the maximum seen so far; each value then needs a single comparison. Reverse the collected answers at the end if the output must be in left-to-right order.

Pattern 5: use what you know about the values

When the values are limited, use that. A list holding 1 to n with one number missing can be solved with the sum formula n(n + 1) / 2. A list of only 0, 1 and 2 can be sorted in one pass with three positions (the Dutch national flag method). A value that fills more than half the list survives a vote where different values cancel each other out (Boyer-Moore voting).

How to answer in an interview

Ask about the edges first: can the list be empty, can values be negative, how large can it get? Then say the brute-force idea (simply try every possibility) in one sentence with its cost ("try every pair of days, O(n²)"), and improve it by naming the pattern ("keep the lowest price so far, one pass, O(n)"). Write the code, trace the first example by hand, and finish with time and extra space. Interviewers care about that reasoning as much as the final code.

Common mistakes

• Not handling empty lists and lists with one value.
• Starting a "best so far" at 0 when every value can be negative. Start from the first value instead.
• Sums that overflow 32 bits. The sum of 100,000 values near a billion needs a 64-bit integer in Java.
• Off-by-one errors at the last index, especially with two positions.
• Nested loops over 100,000 values, billions of steps, which is far too slow in both languages.

Recap

Look for the pattern before you write loops: a running value, a write position, two ends, a scan from the right, or a fact about the values. Each one turns an O(n²) idea into a single O(n) pass.