Array and Matrix Problem Set

Problem Story

A stock analytics tool tracks the day-over-day change in a portfolio's value, which naturally produces both positive and negative numbers, and a user wants to know: what's the best possible contiguous run of days that produced the biggest cumulative gain? Given [-2, 1, -3, 4, -1, 2, 1, -5, 4], the answer is the subarray [4, -1, 2, 1], summing to 6 — even though it contains a negative number in the middle, that dip is worth absorbing because the days surrounding it more than make up for it.

Approach & Solution

The brute-force approach tries every possible contiguous subarray and sums each one, which is O(n^2) if you sum each subarray freshly (or O(n^3) if you're really being wasteful about it). It's correct, and it's a fine place to start reasoning about the problem, but it recomputes sums that overlap heavily with sums you've already computed.

Kadane's algorithm collapses this into a single pass by tracking two running values: currentSum, the best sum of a subarray ending exactly at the current position, and bestSum, the best currentSum seen anywhere so far. The insight that makes this work is a local decision rule: at each position, the best subarray ending here either extends the best subarray ending at the previous position (if that's helpful) or starts fresh at the current element (if everything before it was a net negative drag). Formally, currentSum = Math.max(nums[i], currentSum + nums[i]) — if adding the current element to the running sum would make it worse than starting over at the current element alone, start over; otherwise, keep extending. After updating currentSum at each step, update bestSum = Math.max(bestSum, currentSum), because the best overall answer might end at any position, not necessarily the last one.

Trace [-2, 1, -3, 4, -1, 2, 1, -5, 4]: start currentSum = -2, bestSum = -2. At 1: currentSum = max(1, -2+1=-1) = 1, bestSum = max(-2, 1) = 1. At -3: currentSum = max(-3, 1-3=-2) = -2, bestSum stays 1. At 4: currentSum = max(4, -2+4=2) = 4, bestSum = max(1, 4) = 4. At -1: currentSum = max(-1, 4-1=3) = 3, bestSum stays 4. At 2: currentSum = max(2, 3+2=5) = 5, bestSum = 5. At 1: currentSum = 6, bestSum = 6. At -5: currentSum = max(-5, 6-5=1) = 1, bestSum stays 6. At 4: currentSum = max(4, 1+4=5) = 5, bestSum stays 6. Final answer: 6, matching the expected subarray [4, -1, 2, 1].

This is O(n) time and O(1) space, and the underlying idea — that the best answer 'ending here' can be computed from the best answer 'ending at the previous position' plus one new piece of information — is the exact same idea that dynamic programming formalizes in the next topic in this set. Kadane's algorithm is, in effect, a one-variable DP: currentSum IS the DP state, and the recurrence currentSum[i] = max(nums[i], currentSum[i-1] + nums[i]) is a textbook DP transition that just happens not to need an array because each step only depends on the immediately preceding one. Seeing Kadane's this way makes the jump into formal DP thinking much less abstract later on.

One edge case worth naming out loud in an interview: if the array is allowed to be entirely negative, the algorithm still works correctly as written, because bestSum is initialized from nums[0] rather than from zero — if you mistakenly initialize bestSum to 0, an all-negative array would wrongly report 0 as the best subarray sum, when really the correct answer is the least-negative single element.

public class MaximumSubarray {

    // Kadane's algorithm. Time: O(n), Space: O(1).
    public static int maxSubArray(int[] nums) {
        int currentSum = nums[0];
        int bestSum = nums[0];

        for (int i = 1; i < nums.length; i++) {
            // Either extend the previous run, or start fresh here.
            currentSum = Math.max(nums[i], currentSum + nums[i]);
            bestSum = Math.max(bestSum, currentSum);
        }

        return bestSum;
    }

    public static void main(String[] args) {
        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println(maxSubArray(nums)); // 6
    }
}

Problem Story

A scheduling tool stores the next 7 days of on-call engineers as an array, and once a week it needs to 'rotate' that schedule by k days — whoever was on day 3 is now on day 0, and the engineers who just finished their rotation wrap around to the end. Given [1,2,3,4,5,6,7] rotated right by k=3, the result should be [5,6,7,1,2,3,4]. The obvious approach, copying elements into a new array at their shifted positions, works, but it costs O(n) extra space, and the in-place trick that avoids that extra array is one of the cleanest applications of the reversal technique from the string-reversal lesson earlier in this set.

Approach & Solution

First, normalize k: since rotating an array of length n by n positions returns it to its original order, only k % n rotations are ever meaningful — if a caller passes k larger than n (or even negative k, depending on the problem's conventions), reduce it with k = k % n first, otherwise you'll do redundant full loops of work for no visible effect.

The copy-based approach allocates a new array of the same length and places nums[i] at position (i + k) % n in the new array, then copies the new array back over the old one. This is O(n) time and correct, but it's worth naming explicitly as 'the version that uses extra space' before showing the better one, because interviewers specifically want to see whether you can avoid that extra array.

The in-place reversal trick does it with O(1) extra space using three calls to the same reverse-a-range routine from the string lesson. The insight: rotating the whole array right by k is equivalent to (1) reversing the entire array, then (2) reversing the first k elements, then (3) reversing the remaining n-k elements. Trace [1,2,3,4,5,6,7] with k=3: reverse the whole thing to get [7,6,5,4,3,2,1]. Reverse the first 3 elements (indices 0..2): [5,6,7,4,3,2,1]. Reverse the remaining elements (indices 3..6): [5,6,7,1,2,3,4]. That's exactly the target output. The intuition for why this works is that a full reversal puts every element in reverse order, which coincidentally also puts each 'block' (the last k elements, and the first n-k elements) in the right relative region, just internally backwards — so reversing each of those two blocks again un-reverses them internally while leaving them in their new, correctly rotated regions.

Each of the three reversals is O(length of that segment), and the three segments sum to roughly 2n total work (the full array once, plus its two halves once combined), so the whole operation is still O(n) time, just with no second array — only the same O(1)-extra-space two-pointer swap helper reused three times with different bounds.

The broader lesson worth carrying forward: a surprising number of 'in-place array rearrangement' problems decompose into 'reverse this, then reverse these two pieces separately' once you look for the right decomposition, because reversal is one of the few operations that's simultaneously in-place, O(1) extra space, and easy to compose. It's worth having the two-pointer reversal helper memorized cold, because it's the building block for this problem, the string-reversal problem, and several others in the same family.

public class RotateArray {

    // In-place rotation via the reversal trick.
    // Time: O(n), Space: O(1) extra.
    public static void rotate(int[] nums, int k) {
        int n = nums.length;
        k = k % n;

        reverse(nums, 0, n - 1);      // reverse the whole array
        reverse(nums, 0, k - 1);       // reverse the first k elements
        reverse(nums, k, n - 1);       // reverse the remaining elements
    }

    private static void reverse(int[] nums, int left, int right) {
        while (left < right) {
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            left++;
            right--;
        }
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 5, 6, 7};
        rotate(nums, 3);
        for (int n : nums) System.out.print(n + " "); // 5 6 7 1 2 3 4
    }
}

Problem Story

An event-registration system assigns every attendee a sequential badge number from 0 to n, but one badge printer jammed and skipped exactly one number. Given the array of n badge numbers that WERE printed, find the one number from the full 0-to-n range that's missing. For [3, 0, 1], where the full range should be 0, 1, 2, 3, the missing number is 2. This looks like it wants a sort, or a seen-array, but there's a neat arithmetic shortcut that needs neither.

Approach & Solution

The sorting approach sorts the array, then walks it checking that each element equals its expected value (index), and the first place that breaks is where the missing number lives. This is O(n log n) because of the sort, and it's a reasonable first pass at a solution, but the sort is unnecessary overhead for a problem that doesn't actually care about order.

A seen-set/boolean-array approach marks which numbers from 0 to n appeared, then scans for the one that didn't. This is O(n) time and O(n) space, better than sorting on time, but it's still spending memory it doesn't need to spend.

The sum-formula trick gets to O(n) time and O(1) extra space by using a basic fact of arithmetic: the sum of all integers from 0 to n is n*(n+1)/2 (the classic Gauss formula). If you compute that expected sum, then subtract the ACTUAL sum of the given array (which contains every number from 0 to n except exactly one), what's left over is exactly the missing number. For [3, 0, 1]: n = 3 (the array has 3 elements, representing the range 0..3 with one missing), expected sum = 3*4/2 = 6, actual sum = 3+0+1 = 4, missing = 6 - 4 = 2. Matches.

This is elegant, but it's worth flagging its one real weakness honestly: for very large n, n*(n+1) can overflow a 32-bit int before the division by 2 happens, so in a language or context where that matters, you'd compute using a wider type (long in Java) or restructure the subtraction to avoid building the full sum first — for instance, by walking the array once and accumulating expected-minus-actual incrementally: missing = sum over i of (i - nums[i]) plus n, or equivalent reorderings, specifically to keep intermediate values small. For interview-sized inputs this is rarely the deciding factor, but naming the overflow risk and how you'd mitigate it is exactly the kind of detail that separates a good answer from a complete one.

An alternative, equally O(n)/O(1) approach that avoids the overflow question entirely is bitwise XOR: XOR every index from 0 to n together, then XOR every array element in as well; because XOR-ing a number with itself cancels to zero, every number present in both the full range and the array cancels out, and what survives is the missing number. This works because XOR is commutative and associative and has no large intermediate 'sum' to overflow — each partial result stays bounded by the bit-width of the numbers themselves. Mentioning this as an alternative, and explaining why it sidesteps the overflow concern the sum-formula approach has, is a strong signal of genuinely understanding the tradeoffs rather than having memorized one trick.

public class MissingNumber {

    // Gauss sum-formula trick. Time: O(n), Space: O(1).
    public static int findMissingBySum(int[] nums) {
        int n = nums.length; // range is 0..n inclusive, one value missing
        long expectedSum = (long) n * (n + 1) / 2; // use long to avoid overflow

        long actualSum = 0;
        for (int num : nums) {
            actualSum += num;
        }

        return (int) (expectedSum - actualSum);
    }

    // XOR trick: avoids any overflow concern entirely. Time: O(n), Space: O(1).
    public static int findMissingByXor(int[] nums) {
        int n = nums.length;
        int result = n; // start by XOR-ing in the top of the range

        for (int i = 0; i < n; i++) {
            result ^= i;
            result ^= nums[i];
        }

        return result;
    }

    public static void main(String[] args) {
        int[] nums = {3, 0, 1};
        System.out.println(findMissingBySum(nums)); // 2
        System.out.println(findMissingByXor(nums));  // 2
    }
}

Problem Story

A photo-editing tool stores an image's pixel grid as a 2D array and needs to support a 90-degree 'rotate right' button — the kind every photo app has — without allocating a second full-size grid, because for a large image that's a meaningful amount of memory to duplicate just to rotate it. Given a 3x3 grid [[1,2,3],[4,5,6],[7,8,9]], rotating 90 degrees clockwise should produce [[7,4,1],[8,5,2],[9,6,3]]. This problem is a direct extension of the in-place-reversal mindset from the array-rotation problem, just applied across two dimensions instead of one.

Approach & Solution

The naive approach builds a brand-new matrix and, for each cell (row, col) in the original, places its value at the correctly rotated position in the new matrix (for a 90-degree clockwise rotation, original (row, col) maps to new (col, n-1-row)). This is correct and O(n^2) time, but it costs O(n^2) extra space for the second grid, which is exactly what the in-place version avoids.

The in-place technique decomposes the rotation into two simpler, well-understood steps, the same way array rotation decomposed into three reversals. Step one: transpose the matrix, meaning swap element (row, col) with element (col, row) for every pair where row < col — this flips the matrix across its main diagonal, turning rows into columns. Step two: reverse each row of the transposed matrix left-to-right. The combination of 'transpose, then reverse each row' produces exactly a 90-degree clockwise rotation; if you wanted counter-clockwise instead, you'd transpose and then reverse each column (equivalently, reverse the order of the rows before transposing) — worth stating explicitly in an interview so it's clear you understand why the two tiny variants differ, rather than just pattern-matching the code.

Trace [[1,2,3],[4,5,6],[7,8,9]]: transpose swaps (0,1)<->(1,0) giving 4 and 2 swapped, (0,2)<->(2,0) giving 7 and 3 swapped, (1,2)<->(2,1) giving 8 and 6 swapped. Diagonal elements (0,0), (1,1), (2,2) stay put because row == col for them, so there's nothing to swap. Result: [[1,4,7],[2,5,8],[3,6,9]]. Now reverse each row left-to-right: [7,4,1], [8,5,2], [9,6,3]. That matches the target 90-degree clockwise rotation exactly.

Both steps are O(n^2) (every cell is touched a constant number of times across the transpose and the row reversal), and crucially, both are done by mutating the existing 2D array directly — no second matrix is ever allocated, so the extra space is O(1) beyond the loop variables. The transpose loop only needs to iterate the upper triangle (row from 0 to n-1, col from row+1 to n-1) rather than the whole matrix, since iterating the full square would swap every pair twice and undo itself.

The pattern worth internalizing here is the same one from array rotation: a 2D geometric transformation that feels like it needs a fresh buffer to 'hold' intermediate state can often be decomposed into two or three simpler, well-known in-place operations (transpose, row-reverse, column-reverse) applied in the right sequence — and once you recognize the decomposition, the implementation is just gluing together helpers you've already written for other problems.

public class RotateMatrix {

    // Rotates an n x n matrix 90 degrees clockwise, in place.
    // Time: O(n^2), Space: O(1) extra.
    public static void rotate(int[][] matrix) {
        int n = matrix.length;

        // Step 1: transpose (swap across the main diagonal).
        for (int row = 0; row < n; row++) {
            for (int col = row + 1; col < n; col++) {
                int temp = matrix[row][col];
                matrix[row][col] = matrix[col][row];
                matrix[col][row] = temp;
            }
        }

        // Step 2: reverse each row left-to-right.
        for (int row = 0; row < n; row++) {
            int left = 0;
            int right = n - 1;
            while (left < right) {
                int temp = matrix[row][left];
                matrix[row][left] = matrix[row][right];
                matrix[row][right] = temp;
                left++;
                right--;
            }
        }
    }

    public static void main(String[] args) {
        int[][] matrix = {{1,2,3}, {4,5,6}, {7,8,9}};
        rotate(matrix);
        for (int[] row : matrix) {
            for (int val : row) System.out.print(val + " ");
            System.out.println();
        }
        // 7 4 1
        // 8 5 2
        // 9 6 3
    }
}

Problem Story

A printer-friendly report layout needs to lay out a grid of data cells in the order a reader's eye would naturally trace if you handed them the page and said 'read it like a spiral, starting from the top-left corner' — across the top row, down the right column, back across the bottom row, up the left column, then inward to do the same thing on the smaller grid that remains. For [[1,2,3],[4,5,6],[7,8,9]], the spiral order is 1,2,3,6,9,8,7,4,5. The challenge isn't any single step of this walk — it's keeping track of which part of the grid has already been visited without a separate visited-matrix to track it.

Approach & Solution

The most reliable way to do this without a separate boolean 'visited' grid is to shrink four boundary variables as you consume each side of the current rectangle: top, bottom, left, right, initialized to the matrix's outer edges (top=0, bottom=rows-1, left=0, right=cols-1). On each lap around the current rectangle, do four walks in order, and tighten the corresponding boundary immediately after each one, since that boundary's row or column is now fully consumed and must never be revisited.

Walk 1: traverse the top row from left to right (column left to right at fixed row top), then increment top, because that row is done. Walk 2: traverse the right column from top to bottom (row top to bottom at fixed column right), then decrement right, because that column is done. Walk 3, but only if top <= bottom still holds (meaning there are still unvisited rows left): traverse the bottom row from right to left, then decrement bottom. Walk 4, but only if left <= right still holds (meaning there are still unvisited columns left): traverse the left column from bottom to top, then increment left. Repeat this whole four-step lap while top <= bottom and left <= right.

The two guard conditions on walks 3 and 4 are the detail everyone gets wrong on a first attempt, and they matter specifically for rectangles that are a single row or a single column wide at some point in the spiral. Picture a 1-row-tall remaining rectangle after several laps: walk 1 (top row left-to-right) consumes that entire remaining row and increments top past bottom. Without the guard on walk 3, you'd then try to traverse 'the bottom row' again — but it's the same row you just consumed, now walked right-to-left, producing duplicate output. The guard top <= bottom catches exactly this and skips walk 3 (and similarly walk 4) once there's nothing left to walk in that direction.

Trace the 3x3 example: top=0,bottom=2,left=0,right=2. Walk 1: row 0, cols 0->2: visit 1,2,3. top becomes 1. Walk 2: col 2, rows 1->2: visit 6,9. right becomes 1. Walk 3 (top=1<=bottom=2, proceed): row 2, cols 1->0: visit 8,7. bottom becomes 1. Walk 4 (left=0<=right=1, proceed): col 0, rows 1->1: visit 4. left becomes 1. Now top=1<=bottom=1 and left=1<=right=1, so one more lap: walk 1: row 1, cols 1->1: visit 5. top becomes 2, now top > bottom, loop ends. Full output: 1,2,3,6,9,8,7,4,5 — matching exactly.

This is O(rows*cols) time, since every cell is visited exactly once, and O(1) extra space beyond the output list itself, since the four boundary integers are all the bookkeeping the algorithm needs. The boundary-shrinking idea generalizes to any 'process the outer ring, then recurse/iterate inward' matrix problem, including setting a matrix's border to a given value or peeling a matrix layer by layer — the four-boundary pattern is worth having as a reusable mental template rather than re-deriving the guard conditions from scratch each time.

import java.util.ArrayList;
import java.util.List;

public class SpiralMatrix {

    // Boundary-shrinking spiral traversal.
    // Time: O(rows * cols), Space: O(1) extra (beyond the result list).
    public static List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> result = new ArrayList<>();
        if (matrix.length == 0) return result;

        int top = 0, bottom = matrix.length - 1;
        int left = 0, right = matrix[0].length - 1;

        while (top <= bottom && left <= right) {
            // Walk 1: top row, left to right.
            for (int col = left; col <= right; col++) {
                result.add(matrix[top][col]);
            }
            top++;

            // Walk 2: right column, top to bottom.
            for (int row = top; row <= bottom; row++) {
                result.add(matrix[row][right]);
            }
            right--;

            // Walk 3: bottom row, right to left (only if rows remain).
            if (top <= bottom) {
                for (int col = right; col >= left; col--) {
                    result.add(matrix[bottom][col]);
                }
                bottom--;
            }

            // Walk 4: left column, bottom to top (only if columns remain).
            if (left <= right) {
                for (int row = bottom; row >= top; row--) {
                    result.add(matrix[row][left]);
                }
                left++;
            }
        }

        return result;
    }

    public static void main(String[] args) {
        int[][] matrix = {{1,2,3}, {4,5,6}, {7,8,9}};
        System.out.println(spiralOrder(matrix)); // [1, 2, 3, 6, 9, 8, 7, 4, 5]
    }
}