Solution.java

import java.util.Arrays;
import java.util.Scanner;

public class Solution {
    private static int discoverSink(int[][] farmland, int[][] basins, int nextbasin, int i, int j) {
        if (basins[i][j] != 0) {
            return basins[i][j];
        // perform a dfs starting at i,j searching for a sink
        } else {
            int minaltitude = farmland[i][j];
            int mini = i;
            int minj = j;
            // search for the lowest altitude neighbour
            for(int k=-1; k < 2; k++) {
                for (int l=-1; l < 2; l++) {
                    int tmpi = i+k;
                    int tmpj = j+l;
                    if (tmpi >= 0 && tmpi < farmland.length &&
                        tmpj >= 0 && tmpj < farmland.length) {
                        int altitude = farmland[tmpi][tmpj];
                        if (altitude < minaltitude) {
                            minaltitude = altitude;
                            mini = tmpi;
                            minj = tmpj;
                        }
                    }
                }
            }
            
            // i,j is a sink
            if (mini == i && minj == j) {
                basins[i][j] = nextbasin;
                return basins[i][j];
            // not a sink, recurse to the lowest altitude neighbour
            } else {
                basins[i][j] = discoverSink(farmland, basins, nextbasin, mini, minj);
                return basins[i][j];
            }
        }
    }
    
    public static void main(String... args)
    {
        try(Scanner sc = new Scanner(System.in)) {
            int length = sc.nextInt();
            int[][] farmland = new int[length][length];
            for (int i=0;i<length;i++)
                for(int j=0; j<length;j++)
                    farmland[i][j] = sc.nextInt();
            
            int[][] basins = new int[length][length];
            for(int i=0; i<length;i++)
                Arrays.fill(basins[i], 0);
            
            int nextbasin = 1;
            for (int i=0; i < length; i++) {
                for (int j=0; j < length; j++) {
                    // undiscovered spot
                    if (basins[i][j] == 0) {
                        int discovered_sink = discoverSink(farmland, basins, nextbasin, i, j);
                        if(discovered_sink == nextbasin)
                            nextbasin++;
                    }
                }
            }
            
            // for each sink, count the basin size
            int[] sinks = new int[nextbasin-1];
            Arrays.fill(sinks, 0);
            for (int i=0; i < length; i++)
                for(int j=0; j < length; j++)
                    sinks[basins[i][j]-1] += 1;
            
            // sorts in ascending, so output back to front
            Arrays.sort(sinks);
            for (int i=sinks.length-1; i >= 0; i--)
                System.out.print(sinks[i] + " ");
        }
    }
}