Sorting Squared Elements of a Monotonic Array

Given an integer sequence arranged in non-decreasing order, the objective is to generate a new array containing the squares of each element, also sorted in non-decreasing order.

Because the original input may contain negative values, squaring them can invert their relative magnitude. The largest squared values will inevitably reside at either extremity of the original sequence. Rather than squaring all elements and applying a generic sorting algorithm, a two-pointer strategy yields linear time complexity.

Initialize pointers at the beginning and end of the input array. Compare the squared magnitude of the elements at these positions. Place the larger value at the highest available index of the output buffer and advance the corresponding pointer inward. Continue this process until the entire output buffer is populated.

public int[] computeSortedSquares(int[] inputSequence) {
    int n = inputSequence.length;
    int[] resultBuffer = new int[n];
    int startPtr = 0;
    int endPtr = n - 1;
    int fillIndex = n - 1;

    while (fillIndex >= 0) {
        int leftSquare = inputSequence[startPtr] * inputSequence[startPtr];
        int rightSquare = inputSequence[endPtr] * inputSequence[endPtr];
        
        if (rightSquare > leftSquare) {
            resultBuffer[fillIndex] = rightSquare;
            endPtr--;
        } else {
            resultBuffer[fillIndex] = leftSquare;
            startPtr++;
        }
        fillIndex--;
    }
    return resultBuffer;
}

Identifying the Shortest Subarray Meeting a Sum Threshold

For an array containing exclusively positive integers and a given positive threshold, locate the shortest contiguous subarray whose cumulative sum meets or exceeds that value. Return the length of this subarray, or zero if no valid sequence exists.

A brute-force approach checking every possible subarray results in quadratic time complexity. This can be optimized to linear time using a dynamic window technique. The window expands by moving a right boundary pointer forward, accumulating values. Once the running total satisfies the threshold condition, the window contracts from the left to isolate the minimal length that still meets the requirement. This contraction step continues until the sum drops below the threshold, at wich point expansion resumes.

public int findMinimalLengthSubarray(int threshold, int[] numbers) {
    int windowStart = 0;
    int currentSum = 0;
    int minimalLength = Integer.MAX_VALUE;

    for (int windowEnd = 0; windowEnd < numbers.length; windowEnd++) {
        currentSum += numbers[windowEnd];

        while (currentSum >= threshold) {
            int activeLength = windowEnd - windowStart + 1;
            if (activeLength < minimalLength) {
                minimalLength = activeLength;
            }
            currentSum -= numbers[windowStart];
            windowStart++;
        }
    }
    return minimalLength == Integer.MAX_VALUE ? 0 : minimalLength;
}

Generating a Clockwise Spiral Square Matrix

Construct an n x n matrix populated with integers from 1 to n^2, arranged in a clockwise spiral pattern starting from the top-left corner.

The generation process follows a strict layering mechanism defined by four directional boundaries. By adhering to a consistent loop invariant, the matrix can be filled ring by ring. For each iteration, values are assigned moving right across the top row, down the rightmost column, left across the bottom row, and up the leftmost column. After completing one full cycle, all four boundaries are tightened inward, and the sequence repeats until all cells are populated.

Careful boundary condition checks prevent overlapping assignments when the matrix dimension is odd or when the innermost layer collapses into a single row or column.

public int[][] createSpiralMatrix(int dimension) {
    int[][] grid = new int[dimension][dimension];
    int topRow = 0;
    int bottomRow = dimension - 1;
    int leftCol = 0;
    int rightCol = dimension - 1;
    int currentValue = 1;
    int totalCells = dimension * dimension;

    while (currentValue <= totalCells) {
        // Fill top boundary left to right
        for (int col = leftCol; col <= rightCol; col++) {
            grid[topRow][col] = currentValue++;
        }
        topRow++;

        // Fill right boundary top to bottom
        for (int row = topRow; row <= bottomRow; row++) {
            grid[row][rightCol] = currentValue++;
        }
        rightCol--;

        // Fill bottom boundary right to left
        if (topRow <= bottomRow) {
            for (int col = rightCol; col >= leftCol; col--) {
                grid[bottomRow][col] = currentValue++;
            }
            bottomRow--;
        }

        // Fill left boundary bottom to top
        if (leftCol <= rightCol) {
            for (int row = bottomRow; row >= topRow; row--) {
                grid[row][leftCol] = currentValue++;
            }
            leftCol++;
        }
    }
    return grid;
}