Question

How to find the N smallest values in a 2D array in Java

Answer 1

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class NSmallestValues {

    /**
     * Finds the N smallest values in a 2D integer matrix using a Max-Heap (PriorityQueue).
     *
     * Algorithm Strategy:
     * Maintains a Max-Heap capped at size N. For every element in the matrix:
     *   1. If heap size < N, insert the element.
     *   2. If heap size == N and the element is smaller than the largest element in the heap,
     *      remove the max element and insert the new element.
     * This keeps the overall time complexity down to O(R * C * log N) and space complexity to O(N).
     *
     * @param matrix 2D input array of integers
     * @param n number of smallest values to retrieve
     * @return sorted array containing the n smallest elements in ascending order
     */
    public static int[] findNSmallest(int[][] matrix, int n) {
        // Guard against invalid inputs
        if (matrix == null || matrix.length == 0 || n <= 0) {
            return new int[0];
        }

        // Count total elements in case requested N exceeds available items
        int totalElements = 0;
        for (int[] row : matrix) {
            if (row != null) {
                totalElements += row.length;
            }
        }

        // Adjust N if it requests more items than available in the matrix
        int targetSize = Math.min(n, totalElements);
        if (targetSize == 0) {
            return new int[0];
        }

        // Max-Heap: The largest of our top-N candidates resides at the root (peek)
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(targetSize, Comparator.reverseOrder());

        // Process all elements in the 2D matrix
        for (int[] row : matrix) {
            if (row == null) {
                continue;
            }
            for (int val : row) {
                if (maxHeap.size() < targetSize) {
                    maxHeap.offer(val);
                } else if (val < maxHeap.peek()) {
                    maxHeap.poll(); // Evict current largest among our candidates
                    maxHeap.offer(val);
                }
            }
        }

        // Extract items from Max-Heap into an array in ascending order
        int[] result = new int[maxHeap.size()];
        for (int i = result.length - 1; i >= 0; i--) {
            result[i] = maxHeap.poll();
        }

        return result;
    }

    public static void main(String[] args) {
        int[][] matrix = {
            {42, 12, 85,  3},
            { 7, 99, 15, 23},
            {64,  1, 18, 30},
            { 3, 55, 11, 90}
        };

        int n = 5;

        System.out.println("Input Matrix:");
        for (int[] row : matrix) {
            System.out.println(Arrays.toString(row));
        }

        System.out.println("\nFinding the " + n + " smallest values:");
        int[] smallestValues = findNSmallest(matrix, n);
        System.out.println(Arrays.toString(smallestValues));
    }
}



/*
run:

Input Matrix:
[42, 12, 85, 3]
[7, 99, 15, 23]
[64, 1, 18, 30]
[3, 55, 11, 90]

Finding the 5 smallest values:
[1, 3, 3, 7, 11]

*/

 

70+ SQL courses for beginners and professionals

Answer 2

import java.util.Arrays;

public class NSmallestFlattenSort {

    /**
     * Finds the N smallest values in a 2D integer matrix by flattening, sorting, 
     * and limiting the stream results.
     *
     * Strategy:
     *   1. Arrays.stream(matrix) creates a Stream<int[]> of rows.
     *   2. flatMapToInt(Arrays::stream) flattens the 2D rows into a single IntStream.
     *   3. sorted() sorts all elements in ascending order.
     *   4. limit(n) caps the stream output to the first N elements.
     *
     * @param matrix 2D input array of integers
     * @param n number of smallest values to retrieve
     * @return array containing the N smallest elements in ascending order
     */
    public static int[] findNSmallest(int[][] matrix, int n) {
        if (matrix == null || matrix.length == 0 || n <= 0) {
            return new int[0];
        }

        return Arrays.stream(matrix)
                .filter(row -> row != null)
                .flatMapToInt(Arrays::stream)
                .sorted()
                .limit(n)
                .toArray();
    }

    public static void main(String[] args) {
        int[][] matrix = {
            {42, 12, 85,  3},
            { 7, 99, 15, 23},
            {64,  1, 18, 30},
            { 3, 55, 11, 90}
        };

        int n = 5;

        System.out.println("Input Matrix:");
        for (int[] row : matrix) {
            System.out.println(Arrays.toString(row));
        }

        System.out.println("\nFinding the " + n + " smallest values:");
        int[] smallestValues = findNSmallest(matrix, n);
        System.out.println(Arrays.toString(smallestValues));
    }
}


/*
run:

Input Matrix:
[42, 12, 85, 3]
[7, 99, 15, 23]
[64, 1, 18, 30]
[3, 55, 11, 90]

Finding the 5 smallest values:
[1, 3, 3, 7, 11]

*/

 

70+ SQL courses for beginners and professionals