Arrays

In simple words

An array is a row of boxes of the same type, each with an index starting at 0. Getting any box is instant because the computer calculates its address: start + index × size.

The cost: inserting or deleting in the middle means shifting everything after it. 2D arrays (matrix[row][col]) are just arrays of arrays.

Key ideas

• Kadane's algorithm: maximum subarray sum in O(n). Keep a running sum; if it goes negative, start fresh.
• Reverse trick: rotate an array by k = reverse all, reverse first k, reverse the rest. O(n) time, O(1) space.
• Dutch National Flag: sort 0s, 1s, 2s in one pass with three pointers.
• In-place marking: use the array itself (e.g. negate values, or place value v at index v−1) to save space.
• Prefix / suffix products: 'product except self' without division.
• Matrix tricks: rotate 90° = transpose + reverse each row; spiral traversal with four boundaries.
• Always check empty array, single element, all negatives, and index out of bounds.

Operations & cost

Java code

// Kadane: largest sum of a contiguous subarray
int maxSubArray(int[] nums) {
    int best = nums[0], cur = 0;
    for (int x : nums) {
        cur = Math.max(x, cur + x);   // extend or restart
        best = Math.max(best, cur);
    }
    return best;
}

// Rotate right by k using three reverses
void rotate(int[] a, int k) {
    k %= a.length;
    reverse(a, 0, a.length - 1);
    reverse(a, 0, k - 1);
    reverse(a, k, a.length - 1);
}
void reverse(int[] a, int i, int j) {
    while (i < j) { int t = a[i]; a[i++] = a[j]; a[j--] = t; }
}

// Best time to buy and sell stock (one transaction)
int maxProfit(int[] prices) {
    int minPrice = Integer.MAX_VALUE, profit = 0;
    for (int p : prices) {
        minPrice = Math.min(minPrice, p);
        profit = Math.max(profit, p - minPrice);
    }
    return profit;
}

Interview traps to remember

• Comparing arrays: a == b and even a.equals(b) are false for two arrays with the same values. Use Arrays.equals(a, b).
• Printing: System.out.println(arr) prints something like [I@4517d9a3. Use Arrays.toString(arr).
• Sizes: arrays use arr.length, strings use s.length(), lists use list.size().
• Kadane: start best at nums[0], not 0, so an all-negative array like [-3, -1, -2] returns -1.
• Rotate Array: always do k %= n first. Rotating [1, 2, 3, 4, 5] by 7 is the same as by 2 → [4, 5, 1, 2, 3].
• Sort Colors: after swapping with high, don't move mid: the number that came back hasn't been checked yet.

Spot it when

• Almost every problem starts with an array — decide next which technique (hashing, two pointers, window, prefix sum) fits.

Practice problems

Interview tip

★ Before coding, ask: Is it sorted? Can there be duplicates or negatives? Can I modify the input? The answers often decide the technique.