Palantir Technology Interview Question
Front-end Software EngineersCountry: United States
Interview Type: Written Test
package com.nbethi.basins;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.StringTokenizer;
public class BasinUtil {
public static void main(String args[]) throws Exception {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
System.out.print("Please enter square size : ");
String line = reader.readLine();
int size = Integer.parseInt(line);
int area[][] = new int[size][size];
for (int x = 0; x < size; x++) {
for (int y = 0; y < size; y++) {
System.out.print("("+x+","+y+")"+" : ");
line = reader.readLine();
area[x][y] = Integer.parseInt(line.trim());
}
}
for (int x = 0; x < size; x++) {
for (int y = 0; y < size; y++) {
System.out.print(area[x][y]+" ");
}
System.out.println("");
}
calculateBasins(area);
System.out.println("DONE");
}
public static void calculateBasins(int area[][]) {
int size = area.length;
String basins[][] = new String [size][size];
HashMap map = new HashMap();
char uniqueChar = 'A';
for (int x = 0; x < size; x++) {
for (int y = 0; y < size; y++) {
basins[x][y] = lowestPlot(area,x,y,'A');
if(map.containsKey(basins[x][y])) {
String valueString = (String)map.get(basins[x][y]);
StringTokenizer tokens = new StringTokenizer(valueString,":");
char basinUniqueueChar = tokens.nextToken().charAt(0);
int basinSize = Integer.parseInt(tokens.nextToken());
basinSize = basinSize + 1;
map.put(basins[x][y], basinUniqueueChar+":"+basinSize);
} else {
map.put(basins[x][y], uniqueChar+":"+1);
uniqueChar++;
}
}
}
for (int x = 0; x < size; x++) {
for (int y = 0; y < size; y++) {
System.out.print(map.get(basins[x][y])+" ");
}
System.out.println("");
}
}
public static String lowestPlot(int area[][],int x, int y, char ch) {
String lowestPoint = x+","+y;
int size = area.length;
int leftX, leftY, rightX, rightY, topX, topY, bottomX, bottomY;
int minX, minY,minValue;
leftX = x;
leftY = y - 1;
rightX = x;
rightY= y + 1;
topX = x - 1;
topY = y;
bottomX = x + 1;
bottomY = y;
minX = x;
minY = y;
minValue = area[x][y];
if (!isOutOfBounds(leftX, leftY, size)) {
if (area[leftX][leftY] < minValue) {
minX = leftX;
minY = leftY;
minValue = area[leftX][leftY];
}
}
if (!isOutOfBounds(rightX, rightY, size)) {
if (area[rightX][rightY] < minValue) {
minX = rightX;
minY = rightY;
minValue = area[rightX][rightY];
}
}
if (!isOutOfBounds(topX, topY, size)) {
if (area[topX][topY] < minValue) {
minX = topX;
minY = topY;
minValue = area[topX][topY];
}
}
if (!isOutOfBounds(bottomX, bottomY, size)) {
if (area[bottomX][bottomY] < minValue) {
minX = bottomX;
minY = bottomY;
minValue = area[bottomX][bottomY];
}
}
if(minX == x && minY == y) {
//self is the lowest;
} else {
lowestPoint = lowestPlot(area, minX, minY, ch);
}
return lowestPoint;
}
public static boolean isOutOfBounds(int x, int y, int size) {
boolean flag = false;
if (x < 0 || x >= size) {
flag = true;
}
if (y < 0 || y >= size) {
flag = true;
}
return flag;
}
}
sample input ant output
Please enter square size : 5
(0,0) : 1
(0,1) : 0
(0,2) : 2
(0,3) : 5
(0,4) : 8
(1,0) : 2
(1,1) : 3
(1,2) : 4
(1,3) : 7
(1,4) : 9
(2,0) : 3
(2,1) : 5
(2,2) : 7
(2,3) : 8
(2,4) : 9
(3,0) : 1
(3,1) : 2
(3,2) : 5
(3,3) : 4
(3,4) : 2
(4,0) : 3
(4,1) : 3
(4,2) : 5
(4,3) : 2
(4,4) : 1
1 0 2 5 8
2 3 4 7 9
3 5 7 8 9
1 2 5 4 2
3 3 5 2 1
A:11 A:11 A:11 A:11 A:11
A:11 A:11 A:11 A:11 A:11
B:7 B:7 A:11 C:7 C:7
B:7 B:7 B:7 C:7 C:7
B:7 B:7 C:7 C:7 C:7
DONE
took less time but below not implemented
sorting of basins size:
what if if two lowest basins are adjacent.
approach:
matrix1: all plots with altitudes.
for each given plot find the lowest plot which we can find through recursion (recursion will end if the plot is lower than all of its neighbor plots).
store these lowest point in a separate matrix2
matrix2: all plot's corresponding lowest plot
now iterate through matrix2
--lowest plot does not exist in the HashMap--put an object with count as 1
--lowest plot exists in the HashMap--retrieve it and increase the count by 1.
at the end we will have all the LowestPlots and their corresponding count in the HashMap.
Guys instead of pasting code here, please discuss algorithms and techniques you used, because that will be more helpful to all of us. I know this can be done, its not that tough question.
Just that I was not able to do it in 100 min (time given by palantir).
I just wanted to know different approaches to solve this question.
package com.nbethi.basins;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.StringTokenizer;
public class BasinUtil {
public static void main(String args[]) throws Exception {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
System.out.print("Please enter square size : ");
String line = reader.readLine();
int size = Integer.parseInt(line);
int area[][] = new int[size][size];
for (int x = 0; x < size; x++) {
for (int y = 0; y < size; y++) {
System.out.print("("+x+","+y+")"+" : ");
line = reader.readLine();
area[x][y] = Integer.parseInt(line.trim());
}
}
for (int x = 0; x < size; x++) {
for (int y = 0; y < size; y++) {
System.out.print(area[x][y]+" ");
}
System.out.println("");
}
calculateBasins(area);
System.out.println("DONE");
}
public static void calculateBasins(int area[][]) {
int size = area.length;
String basins[][] = new String [size][size];
HashMap map = new HashMap();
char uniqueChar = 'A';
for (int x = 0; x < size; x++) {
for (int y = 0; y < size; y++) {
basins[x][y] = lowestPlot(area,x,y,'A');
if(map.containsKey(basins[x][y])) {
String valueString = (String)map.get(basins[x][y]);
StringTokenizer tokens = new StringTokenizer(valueString,":");
char basinUniqueueChar = tokens.nextToken().charAt(0);
int basinSize = Integer.parseInt(tokens.nextToken());
basinSize = basinSize + 1;
map.put(basins[x][y], basinUniqueueChar+":"+basinSize);
} else {
map.put(basins[x][y], uniqueChar+":"+1);
uniqueChar++;
}
}
}
for (int x = 0; x < size; x++) {
for (int y = 0; y < size; y++) {
System.out.print(map.get(basins[x][y])+" ");
}
System.out.println("");
}
}
public static String lowestPlot(int area[][],int x, int y, char ch) {
String lowestPoint = x+","+y;
int size = area.length;
int leftX, leftY, rightX, rightY, topX, topY, bottomX, bottomY;
int minX, minY,minValue;
leftX = x;
leftY = y - 1;
rightX = x;
rightY= y + 1;
topX = x - 1;
topY = y;
bottomX = x + 1;
bottomY = y;
minX = x;
minY = y;
minValue = area[x][y];
if (!isOutOfBounds(leftX, leftY, size)) {
if (area[leftX][leftY] < minValue) {
minX = leftX;
minY = leftY;
minValue = area[leftX][leftY];
}
}
if (!isOutOfBounds(rightX, rightY, size)) {
if (area[rightX][rightY] < minValue) {
minX = rightX;
minY = rightY;
minValue = area[rightX][rightY];
}
}
if (!isOutOfBounds(topX, topY, size)) {
if (area[topX][topY] < minValue) {
minX = topX;
minY = topY;
minValue = area[topX][topY];
}
}
if (!isOutOfBounds(bottomX, bottomY, size)) {
if (area[bottomX][bottomY] < minValue) {
minX = bottomX;
minY = bottomY;
minValue = area[bottomX][bottomY];
}
}
if(minX == x && minY == y) {
//self is the lowest;
} else {
lowestPoint = lowestPlot(area, minX, minY, ch);
}
return lowestPoint;
}
public static boolean isOutOfBounds(int x, int y, int size) {
boolean flag = false;
if (x < 0 || x >= size) {
flag = true;
}
if (y < 0 || y >= size) {
flag = true;
}
return flag;
}
}
sample input ant output
Please enter square size : 5
(0,0) : 1
(0,1) : 0
(0,2) : 2
(0,3) : 5
(0,4) : 8
(1,0) : 2
(1,1) : 3
(1,2) : 4
(1,3) : 7
(1,4) : 9
(2,0) : 3
(2,1) : 5
(2,2) : 7
(2,3) : 8
(2,4) : 9
(3,0) : 1
(3,1) : 2
(3,2) : 5
(3,3) : 4
(3,4) : 2
(4,0) : 3
(4,1) : 3
(4,2) : 5
(4,3) : 2
(4,4) : 1
1 0 2 5 8
2 3 4 7 9
3 5 7 8 9
1 2 5 4 2
3 3 5 2 1
A:11 A:11 A:11 A:11 A:11
A:11 A:11 A:11 A:11 A:11
B:7 B:7 A:11 C:7 C:7
B:7 B:7 B:7 C:7 C:7
B:7 B:7 C:7 C:7 C:7
DONE
took less time but below not implemented
sorting of basins size:
what if if two lowest basins are adjacent.
Javascript Implementation
/**
* our test cases
*/
function test(){
var results = [];
var alts = [[1,0]];
var res = findBasinSizes(alts);
results.push(res.A == 1);
var alts = [[1,5,2],
[2,4,7],
[3,6,9]];
res = findBasinSizes(alts);
results.push( res.A == '7' && res.B == '2');
var alts = [[1, 0, 2, 5, 8],
[2, 3, 4, 7, 9],
[3, 5, 7, 8, 9],
[1, 2, 5, 4, 2],
[3, 3, 5, 2, 1]]
var res = findBasinSizes(alts);
results.push( res.A == '11' && res.B == '7' && res.C == '7' );
return results;
}
// list of surrounding coords up, down, left, right, and current
var surroundingCoords = [[0, +1],
[0, -1],
[+1, 0],
[-1, 0],
[0, 0]];
/*
* finds the sizes for each basin
* @param NxN array of altitudes
* @return object - object with category as key and basin size as the value
*/
function findBasinSizes(alts){
var map = copyArray(alts);
freqList = {};
basinCount = 65; // char code for "A"
// set sinks
alts.forEach(function(row, i){
row.forEach(function(value, j){
if (isSink(i,j,alts)){
map[i][j] = String.fromCharCode(basinCount++);
}
});
});
// assign each element to a basin category
alts.forEach(function(row,i){
alts.forEach(function(value,j){
var cat = findBasinCategory(i,j,map,alts);
map[i][j] = cat;
freqList[cat] = freqList[cat] ? ++freqList[cat] : 1;
});
});
return freqList;
}
/**
* finds the category the current index belongs to
* @param i - x coord
* @param j - y coord
* @param map - 2d array with basin categories
* @param alts - 2d array of altitudes
* @return string - basin category
*/
function findBasinCategory(i,j,map,alts){
var val = 0;
// if we haven't found a sink or basin yet
while (typeof val !== 'string'){
var coords = findLowestAdjacent(i,j,alts);
val = map[coords[0]][coords[1]];
i = coords[0];
j = coords[1];
}
return val;
}
/**
* A sink is defined as an index surrounded by altitudes higher than itself
* @param i - x index
* @param j - y index
* @param alts - altitude map
* @return bool - whether the current index is a sink hole
*/
function isSink(i,j,alts){
var surrounding = getSurrounding(i,j,alts);
return Math.min.apply(this,surrounding) === alts[i][j];
}
/**
* @param i - x index
* @param j - y index
* @param alts - 2d array of altitudes
* @return coords - [i,j] index of the lowest adjacent altitude
*/
function findLowestAdjacent(i,j,alts){
var min = Infinity;
var coords = [];
surroundingCoords.forEach(function(v){
if (alts[i + v[0]] && alts[i + v[0]][j + v[1]] < min){
min = alts[i + v[0]][j + v[1]];
coords = [i + v[0], j + v[1]];
}
});
return coords;
}
/**
* @param i - x index
* @param j - y index
* @param alts - 2d array of altitudes
* @return array - array of surrounding altitude values
*/
function getSurrounding(i,j,alts){
var b = [];
surroundingCoords.forEach(function(v){
if (alts[i + v[0]] && alts[i + v[0]][j + v[1]] != undefined){
b.push(alts[i + v[0]][j + v[1]]);
}
});
return b;
}
/**
* copy helper for 2d array
*/
function copyArray(arr){
var a = arr.slice(0);
a.forEach(function(v,i){
a[i] = a[i].slice(0);
});
return a;
}
console.log(test());
Wrote this in C. Haven't implemented sorting of basin sizes.
#include <stdlib.h>
#include <stdio.h>
struct Cell {
int elevation;
int basinIndex;
};
struct Cell *elevationData[5000][5000];
int plotSize;
int currentBasinIndex;
int *basinSizes;
struct Cell* new_Cell() {
struct Cell* cell = (struct Cell*) malloc(sizeof(struct Cell));
cell->elevation = 0;
cell->basinIndex = -1;
return cell;
}
void processCell(int i, int j) {
int minElevation = 500;
struct Cell *cell = elevationData[i][j];
struct Cell *left = NULL, *top = NULL, *right = NULL, *bottom = NULL;
int minElevationCellI, minElevationCellJ;
if (cell->basinIndex != -1)
return;
if ((i - 1) >= 0) {
left = elevationData[i - 1][j];
if (left->elevation < minElevation) {
minElevation = left->elevation;
minElevationCellI = i - 1;
minElevationCellJ = j;
}
}
if ((i + 1) < plotSize) {
right = elevationData[i + 1][j];
if (right->elevation < minElevation) {
minElevation = right->elevation;
minElevationCellI = i + 1;
minElevationCellJ = j;
}
}
if ((j - 1) >= 0) {
top = elevationData[i][j - 1];
if (top->elevation < minElevation) {
minElevation = top->elevation;
minElevationCellI = i;
minElevationCellJ = j - 1;
}
}
if ((j + 1) < plotSize) {
bottom = elevationData[i][j + 1];
if (bottom->elevation < minElevation) {
minElevation = bottom->elevation;
minElevationCellI = i;
minElevationCellJ = j + 1;
}
}
if (minElevation > cell->elevation) {
//Current cell is the sink. Form a new basin
cell->basinIndex = ++currentBasinIndex;
} else {
processCell(minElevationCellI, minElevationCellJ);
cell->basinIndex = elevationData[minElevationCellI][minElevationCellJ]->basinIndex;
}
basinSizes[cell->basinIndex]++;
}
int main() {
int i, j, dummy;
currentBasinIndex = -1;
scanf("%d", &plotSize);
basinSizes = (int *) calloc(plotSize * plotSize, sizeof(int));
for (i = 0; i < plotSize; i++) {
for (j = 0; j < plotSize; j++) {
elevationData[i][j] = new_Cell();
scanf("%d", &(elevationData[i][j]->elevation));
}
}
for (i = 0; i < plotSize; i++) {
for (j = 0; j < plotSize; j++) {
processCell(i, j);
}
}
for (i = 0; i <= currentBasinIndex; i++) {
printf("%d ", basinSizes[i]);
}
scanf("%d", &dummy);
return 0;
}
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.TreeMap;
public class Solution {
private Cell[][] matrix;
private int size;
private Scanner scanner = new Scanner(System.in);;
public class Cell {
private int x;
private int y;
private int altitude;
private Integer basinsNo;
private boolean isVisited;
public int getX() {
return x;
}
public void setX(int x) {
this.x = x;
}
public int getY() {
return y;
}
public void setY(int y) {
this.y = y;
}
public int getAltitude() {
return altitude;
}
public void setAltitude(int altitude) {
this.altitude = altitude;
}
public Integer getBasinsNo() {
return basinsNo;
}
public void setBasinsNo(Integer basinsNo) {
this.basinsNo = basinsNo;
}
public boolean isVisited() {
return isVisited;
}
public void setVisited(boolean isVisited) {
this.isVisited = isVisited;
}
public Cell(int altitude, int x, int y) {
super();
this.altitude = altitude;
basinsNo = -1;
isVisited = false;
this.x = x;
this.y = y;
}
public Cell[] getNieghbors(int x, int y) {
Cell[] neighbors = new Cell[4];
if (x - 1 >= 0 && matrix[x - 1][y].isVisited == false) {
neighbors[0] = matrix[x - 1][y];
} else {
neighbors[0] = null;
}
if (x + 1 < size && matrix[x + 1][y].isVisited == false) {
neighbors[1] = matrix[x + 1][y];
} else {
neighbors[1] = null;
}
if (y - 1 >= 0 && matrix[x][y - 1].isVisited == false) {
neighbors[2] = matrix[x][y - 1];
} else {
neighbors[2] = null;
}
if (y + 1 < size && matrix[x][y + 1].isVisited == false) {
neighbors[3] = matrix[x][y + 1];
} else {
neighbors[3] = null;
}
return neighbors;
}
private Cell getSmallestNeighbor(int x, int y) {
// if self is the smallest one, return self
Cell smallestneighbor = matrix[x][y];
if (x - 1 >= 0) {
if (matrix[x - 1][y].altitude <= smallestneighbor.altitude) {
smallestneighbor = matrix[x - 1][y];
}
}
if (x + 1 < size) {
if (matrix[x + 1][y].altitude <= smallestneighbor.altitude) {
smallestneighbor = matrix[x + 1][y];
}
}
if (y - 1 >= 0) {
if (matrix[x][y - 1].altitude <= smallestneighbor.altitude) {
smallestneighbor = matrix[x][y - 1];
}
}
if (y + 1 < size) {
if (matrix[x][y + 1].altitude <= smallestneighbor.altitude) {
smallestneighbor = matrix[x][y + 1];
}
}
return smallestneighbor;
}
}
public Solution() {
super();
size = Integer.parseInt(scanner.nextLine());
if (!checkInput(size)) {
System.out.println("Size should be smaller than 5000.");
System.exit(0);
}
matrix = new Cell[size][size];
int y = 0;
int index = size;
while (index != 0) {
String line = scanner.nextLine();
String[] altitudes = line.split(" ");
if (altitudes.length != size) {
System.err.println("Input Error");
System.exit(-1);
}
for (int i = 0; i < altitudes.length; i++) {
matrix[i][y] = new Cell(Integer.parseInt(altitudes[i]), i, y);
}
y++;
index--;
}
}
private Cell findLowestCell(Cell c) {
Cell cell = c.getSmallestNeighbor(c.x, c.y);
if (cell == c) {
return c;
} else {
return findLowestCell(cell);
}
}
private boolean checkInput(int size) {
return size <= 5000;
}
public void findBasins() {
List<Cell> stack = new LinkedList<Cell>();
stack.add(matrix[0][0]);
int basinsNo = 0;
Cell cell;
while (!stack.isEmpty()) {
cell = stack.remove(stack.size() - 1);
Cell smallestCell = findLowestCell(cell);
if (smallestCell.getBasinsNo() == -1) {
basinsNo++;
smallestCell.setBasinsNo(basinsNo);
}
cell.setBasinsNo(smallestCell.getBasinsNo());
cell.setVisited(true);
Cell[] neighbors = cell.getNieghbors(cell.x, cell.y);
for (Cell neighbor : neighbors) {
if (neighbor != null && !neighbor.isVisited()) {
stack.add(neighbor);
}
}
}
}
public void print() {
for (int y = 0; y < size; y++) {
for (int x = 0; x < size; x++) {
System.out.print(matrix[x][y].getBasinsNo() + "\t");
}
System.out.println();
}
}
public Integer[] stat() {
Map<Integer, Integer> stat = new TreeMap<Integer, Integer>();
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
if (stat.get(matrix[i][j].getBasinsNo()) == null) {
stat.put(matrix[i][j].getBasinsNo(), 1);
} else {
stat.put(matrix[i][j].getBasinsNo(),
stat.get(matrix[i][j].getBasinsNo()) + 1);
}
}
}
List<Integer> list = new ArrayList<Integer>(stat.values());
Integer[] num = new Integer[stat.size()];
for (int i = 0; i < stat.size(); i++) {
num[i] = list.get(i);
}
Arrays.sort(num,Collections.reverseOrder());
return num;
}
/**
* @param args
*/
public static void main(String[] args) throws Exception {
Solution s = new Solution();
s.findBasins();
Integer[] num = s.stat();
for (int n : num) {
System.out.print(n + " ");
}
}
}
Algorithm:
For every element in 2D array find lowest neighboring element.
--if found, make it a child of this element. (note that this lowest neighbor element might already be in a tree, in which case you grow the tree further.)
--if not found make this root (its a sink).
you will end up with multiple trees (i.e number of basins)
number of elements in each tree is the size of basin.
The challenge is building the tree itself.
Every element will have a list of children and a parent.
Note: If no children element is a high altitude point, if no parent its a sink point.
My algorithm:
- search the 2D array for local minimums (the number of local mins will be the number of basins)
- grow each minimum out as far as possible:
- add all neighburs of each local min to a list of potential locations that are a part of that basin
- for each of these candidates check their neighbours to see if they are in fact a part of that basin (they have no neighbours less than the local min)
- move these points to the list of points in the basin if the candidate passes the test, otherwise move to a list of rejected candidates
- for each new point in the basin, repeat this process for all neighbouring points that are not already in the basin and are not already in the list of rejected candidates
Sorry, accidentally submitted.
The recursive algorithm to count the number of points that belong to a basin:
int basinSize(Node n) {
int size = 1;
for(Node neighbour : getSources(n)) {
size += basinSize(neighbour);
}
return size;
}
The method getSources(Node n) returns the set of nodes adjacent to Node n, such that n is the local sink for those nodes. For all non-basin nodes, this method will return at most 3 neighbour nodes.
Once we have the basin sizes for all basins, we simply sort the results.
An easy solution (works for all the cases, showing just the first one):
Input:
3
1 5 2
2 4 7
3 6 9
Solution:
Let us consider the input is stored in an array Basin[3][3] of type int.
At this point, make a new char array say Map[3][3] (same as the size of the Basin)
Map holds the direction in which the number at a particular position should flow.
Now go through every number in Basin[i][j] (i,j=1 to 3) using a nested for loop (one pass, so complexity O(n)):
for each number, a Maximum of 5 check is required as follows:
set 1st number=current number(number being checked say Basin [i][j])
set 2nd number=number East(E) of current number (that is Basin[i][j+1])
set 3rd Number=number West(W) of current number (that is Basin[i][j-1])
set 4th Number=number North(N) of current number (that is Basin[i-1][j])
set 5th Number=number South(S) of current number (that is Basin[i+1][j])
now find the min of 5 numbers (which is not too bad)
Now there are 2 cases:
1) if current number if min, it is the Sink,
Update Map[i][j] as 1 (means it is first sink, you can do it using a counter and for the next sink, counter++)
2) if any other number is min (say E,W,N,S) set Map[i][j] to that character (it means, the flow is in that direction for the current number.
The Map Array after one pass through Basin looks like this:
1 W 2
N W N
N W W
Make a new array farmLand[3][3]
Now Go through this Char array using a nested for loop and update farmLand[i][j] as follows:
if Map[i][j]=1 then 1st Basin and firmLand[i][j]=1
if Map[i][j]=W then go west of Map[i][j] which is Map[i][j-1] and check:
it is 1, set firmLand[i][j]=1
if Map[i][j]=N then go North of Map[i][j] which is Map[i-1][j] and check:
it is 1, set firmLand[i][j]=1
And so on,
The firmLand[3][3] array will look like this:
1 1 2
1 1 2
1 1 1
Counting the number of elements in each Basin is very easy, as one is making firmLand, one can keep and ArrayList that is initialized with zero for every Sink. In this case we have 2 sink so the ArrayList count=new ArrayList() will look like this
count=[0,0]
As one finds a basin each time, just increment the count(i) by 1.
Finally for this case: count=[7,2]
Note: in the second pass also the running time O(n) and hence the the total running time is O(n)+O(n)=O(n).
The input block for the second example has an incorrect number:
Input:
5
1 0 2 5 8
2 3 4 7 9
3 5 7 8 9
1 2 5 [4] 2
3 3 5 2 1
Output:
11 7 7
The number in brackets above does not have a *unique* lowest neighbor, according to the actual Palantir page the 2 in position [4, 3] should be a 3
5
1 0 2 5 8
2 3 4 7 9
3 5 7 8 9
1 2 5 4 [2] <-- should be a 3
3 3 5 2 1
import sys
import pdb
basins = {}
points = {}
map_size = int(sys.stdin.readline().strip())
for row, line in enumerate(sys.stdin):
line = line.strip()
data = line.split()
data = [int(num) for num in data]
for col in range(map_size):
points[(row, col)] = {}
points[(row, col)]['elevation'] = data[col]
def lowest_neighbor(row, col):
if 'lowest_neighbor' in points[(row, col)]:
return points[(row, col)]['lowest_neighbor']
lowest = min(neighbors(row, col) + [(row, col)], key=lambda x: points[x]['elevation'])
points[(row, col)]['lowest_neighbor'] = lowest
if lowest == (row, col):
points[(row, col)]['sink'] = lowest
basins[lowest] = 0
return lowest
def sink(row, col):
if 'sink' not in points[(row, col)]:
lowest = lowest_neighbor(row, col)
points[(row, col)]['sink'] = sink(lowest[0], lowest[1])
return points[(row, col)]['sink']
def neighbors(row, col):
adjacent = [(row - 1, col - 1), (row - 1, col), (row - 1, col + 1),
(row, col - 1), (row, col + 1),
(row + 1, col - 1), (row + 1, col), (row + 1, col + 1)]
return [neighbor for neighbor in adjacent if neighbor in points]
for row in range(map_size):
for col in range(map_size):
basins[sink(row, col)] += 1
basin_sizes = basins.values()
basin_sizes.sort()
basin_sizes.reverse()
output = ' '.join([str(num) for num in basin_sizes])
sys.stdout.write(output)
import sys
import pdb
basins = {}
points = {}
map_size = int(sys.stdin.readline().strip())
for row, line in enumerate(sys.stdin):
line = line.strip()
data = line.split()
data = [int(num) for num in data]
for col in range(map_size):
points[(row, col)] = {}
points[(row, col)]['elevation'] = data[col]
def lowest_neighbor(row, col):
if 'lowest_neighbor' in points[(row, col)]:
return points[(row, col)]['lowest_neighbor']
lowest = min(neighbors(row, col) + [(row, col)], key=lambda x: points[x]['elevation'])
points[(row, col)]['lowest_neighbor'] = lowest
if lowest == (row, col):
points[(row, col)]['sink'] = lowest
basins[lowest] = 0
return lowest
def sink(row, col):
if 'sink' not in points[(row, col)]:
lowest = lowest_neighbor(row, col)
points[(row, col)]['sink'] = sink(lowest[0], lowest[1])
return points[(row, col)]['sink']
def neighbors(row, col):
adjacent = [(row - 1, col - 1), (row - 1, col), (row - 1, col + 1),
(row, col - 1), (row, col + 1),
(row + 1, col - 1), (row + 1, col), (row + 1, col + 1)]
return [neighbor for neighbor in adjacent if neighbor in points]
for row in range(map_size):
for col in range(map_size):
basins[sink(row, col)] += 1
basin_sizes = basins.values()
basin_sizes.sort()
basin_sizes.reverse()
output = ' '.join([str(num) for num in basin_sizes])
sys.stdout.write(output)
import sys
basins = {}
points = {}
map_size = int(sys.stdin.readline().strip())
for row, line in enumerate(sys.stdin):
line = line.strip()
data = line.split()
data = [int(num) for num in data]
for col in range(map_size):
points[(row, col)] = {}
points[(row, col)]['elevation'] = data[col]
def lowest_neighbor(row, col):
if 'lowest_neighbor' in points[(row, col)]:
return points[(row, col)]['lowest_neighbor']
lowest = min(neighbors(row, col) + [(row, col)], key=lambda x: points[x]['elevation'])
points[(row, col)]['lowest_neighbor'] = lowest
if lowest == (row, col):
points[(row, col)]['sink'] = lowest
basins[lowest] = 0
return lowest
def sink(row, col):
if 'sink' not in points[(row, col)]:
lowest = lowest_neighbor(row, col)
points[(row, col)]['sink'] = sink(lowest[0], lowest[1])
return points[(row, col)]['sink']
def neighbors(row, col):
adjacent = [(row - 1, col - 1), (row - 1, col), (row - 1, col + 1),
(row, col - 1), (row, col + 1),
(row + 1, col - 1), (row + 1, col), (row + 1, col + 1)]
return [neighbor for neighbor in adjacent if neighbor in points]
for row in range(map_size):
for col in range(map_size):
basins[sink(row, col)] += 1
basin_sizes = basins.values()
basin_sizes.sort()
basin_sizes.reverse()
output = ' '.join([str(num) for num in basin_sizes])
sys.stdout.write(output)
I wrote the following code for the problem, the problem had a slight modification as each cell had 8 neighboring cells, but the code returned bad_alloc error and I am not able to figure out why its happening when the memory limit is 256 MB
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
// this function is used to assign a label to each cell in the farmer's land representing the connected component it belongs to
char assignLabel(vector< vector<int> >& elevationData , vector< vector<char> >& basinLabels , int i , int j , int S){
// these variables are used to find the index of the minimum elevation data cell
int minRow , minCol , minElevation;
minRow = i;
minCol = j;
minElevation = elevationData[i][j];
// check the cell above
if(i-1 > 0){
if(elevationData[i-1][j] < minElevation){
minRow = i-1;
minCol = j;
minElevation = elevationData[i-1][j];
}
}
// check the cell below
if(i+1 <= S){
if(elevationData[i+1][j] < minElevation){
minRow = i+1;
minCol = j;
minElevation = elevationData[i+1][j];
}
}
// check the cell to the left
if(j-1 > 0){
if(elevationData[i][j-1] < minElevation){
minRow = i;
minCol = j-1;
minElevation = elevationData[i][j-1];
}
}
// check the cell to the right
if(j+1 <= S){
if(elevationData[i][j+1] < minElevation){
minRow = i;
minCol = j+1;
minElevation = elevationData[i][j+1];
}
}
// compare with the cell diagonally to the left above
if(i-1 > 0 && j-1 >0){
if(elevationData[i-1][j-1] < minElevation){
minRow = i-1;
minCol = j-1;
minElevation = elevationData[i-1][j-1];
}
}
// compare with the cell diagonally below to right
if(i+1 <= S && j+1 <= S){
if(elevationData[i+1][j+1] < minElevation){
minRow = i+1;
minCol = j+1;
minElevation = elevationData[i+1][j+1];
}
}
// compare with the cell diagonally to the right above
if(i-1 > 0 && j+1 <= S){
if(elevationData[i-1][j+1] < minElevation){
minRow = i-1;
minCol = j+1;
minElevation = elevationData[i-1][j+1];
}
}
// compare with the cell diagonally to the left below
if(i+1 <= S && j-1 > 0){
if(elevationData[i+1][j-1] < minElevation){
minRow = i+1;
minCol = j-1;
minElevation = elevationData[i+1][j-1];
}
}
if(basinLabels[minRow][minCol] != 'A'-1){
basinLabels[i][j] = basinLabels[minRow][minCol];
return basinLabels[i][j];
}
else
basinLabels[i][j] = assignLabel(elevationData,basinLabels,minRow,minCol,S);
}
// this function is used to check if a particular cell is a sink or not
bool checkSink(vector< vector<int> >& elevationData , int i , int j, int S){
// compare with the cell above
if(i-1 > 0){
if(elevationData[i-1][j] < elevationData[i][j])
return false;
}
// compare with the cell below
if(i+1 <= S){
if(elevationData[i+1][j] < elevationData[i][j])
return false;
}
// compare with the cell to the left
if(j-1 > 0){
if(elevationData[i][j-1] < elevationData[i][j])
return false;
}
// compare with the cell to the right
if(j+1 <= S){
if(elevationData[i][j+1] < elevationData[i][j])
return false;
}
// compare with the cell diagonally to the left above
if(i-1 > 0 && j-1 >0){
if(elevationData[i-1][j-1] < elevationData[i][j])
return false;
}
// compare with the cell diagonally below to right
if(i+1 <= S && j+1 <= S){
if(elevationData[i+1][j+1] < elevationData[i][j])
return false;
}
// compare with the cell diagonally to the right above
if(i-1 > 0 && j+1 <= S){
if(elevationData[i-1][j+1] < elevationData[i][j])
return false;
}
// compare with the cell diagonally to the left below
if(i+1 <= S && j-1 > 0){
if(elevationData[i+1][j-1] < elevationData[i][j])
return false;
}
return true;
}
int main(){
// this integer represents the width and height of the farmer's land
int S;
cin >> S;
// this 2D vector represents the farmer's land
vector< vector< int > > elevationData(S+2 , vector<int>(S+2));
// scan the elevation data
for(int i = 1 ; i < S+1 ; ++i){
for(int j = 1 ; j < S+1 ; ++j)
cin >> elevationData[i][j];
}
// this set actually stores all the sinks present in the farmer's land
set< pair<int,int> > sinkSet;
for(int i = 1 ; i < S+1 ; ++i){
for(int j = 1 ; j < S+1 ; ++j){
if(checkSink(elevationData,i,j,S))
sinkSet.insert( make_pair(i,j) );
}
}
// this is used to assign a unique character to each sink
char sinkLabel = 'A';
// this vector stores the labels of the different basins in the farmer's land
vector< vector< char > > basinLabels(S+2 , vector< char >(S+2));
for(int i = 1 ; i < S+1 ; ++i){
for(int j = 1 ; j < S+1 ; ++j){
if(sinkSet.find( make_pair(i,j) ) != sinkSet.end()){
basinLabels[i][j] = sinkLabel;
++sinkLabel;
}else{
basinLabels[i][j] = 'A'-1;
}
}
}
for(int i = 1 ; i < S+1 ; ++i){
for(int j = 1 ; j < S+1 ; ++j){
if(basinLabels[i][j] == 'A'-1)
assignLabel(elevationData , basinLabels , i , j , S);
}
}
// this vector stores the sizes of the components
vector<int> basinSize;
sinkLabel = 'A';
// count the number of cells in a single connected component
for(int i = 0 ; i < (int)sinkSet.size() ; ++i){
int count = 0;
for(int j = 1 ; j < S+1 ; ++j){
for(int k = 1 ; k < S+1 ; ++k){
if(basinLabels[j][k] == sinkLabel)
++count;
}
}
basinSize.push_back(count);
++sinkLabel;
}
// sort the connected components by size
sort(basinSize.begin() , basinSize.end());
for(int i = (int)basinSize.size() - 1 ; i >= 0 ; --i)
cout << basinSize[i] << " ";
cout << endl;
elevationData.clear();
basinLabels.clear();
return 0;
}
Solution is O(n * m) (size of the matrix).
First let's build a graph: for each cell we define the cell where the water goes.
Now the answer is the number of connected components. We can do DFS for that. We start from some not labeled cell with DFS and mark all cells with some new_number (id). If we found vertex already marked with other id, connected to current component, we can then repaint everything with this color. BFS would be better probably, cause we can just save all the queue and repaint it.
Took me 80 minutes. My method:
I start from each point in the land to go down the stream and I number a second array with basin numbers. If I hit an basin number other than the current one I reassign the basin numbers (on my way out from recursion). I also increment an array with basin counters (hash) each time I assign a basin number in this double loop. Then I sort and output.
Code:
public class Main {
public static int MAX_ELEVATION = 1000000; // maximum elevation
public static int MAX_BASINS = 1000;
public static void main ( String [] arguments ) throws IOException
{
// get user input
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String line = reader.readLine();
int size = Integer.parseInt(line.trim());
int [][]land = new int[size][size];
int [][]basins = new int[size][size];
int []basinCounts = new int[MAX_BASINS];
for (int i = 0; i < size; i ++) {
String elevations = reader.readLine();
String[] splitted = elevations.split("\\s+");
for (int j = 0; j < size; j ++) {
land[i][j] = Integer.parseInt(splitted[j].trim());
basins[i][j] = -1;
}
}
// walk through land and count basins
for (int i = 0; i < size; i ++) {
for (int j = 0; j < size; j ++) {
basinCounts[walkThroughBasin(i, j, 0, land, basins, size)] ++;
}
}
// sort basins
Arrays.sort(basinCounts);
for( int i = 0; i < basinCounts.length/2; ++i ) {
int temp = basinCounts[i];
basinCounts[i] = basinCounts[basinCounts.length - i - 1];
basinCounts[basinCounts.length - i - 1] = temp;
}
// output
for (int i = 0; i < currentBasin; i ++) {
System.out.print(basinCounts[i] + " ");
}
}
public static int currentBasin = 0;
public static int walkThroughBasin(int i, int j, int basin, int [][]land, int [][]basins, int size) {
if (basins[i][j] != -1)
return basins[i][j];
int vl = i > 0 ? land[i-1][j] : MAX_ELEVATION;
int vr = i < size - 1 ? land[i + 1][j] : MAX_ELEVATION;
int vu = j > 0 ? land[i][j - 1] : MAX_ELEVATION;
int vd = j < size - 1 ? land[i][j + 1] : MAX_ELEVATION;
if (vl <= vr && vl <= vu && vl <= vd && vl < land[i][j]) {
basin = walkThroughBasin(i - 1, j, basin, land, basins, size);
} else
if (vr <= vl && vr <= vu && vr <= vd && vr < land[i][j]) {
basin = walkThroughBasin(i + 1, j, basin, land, basins, size);
} else
if (vu <= vr && vu <= vl && vu <= vd && vu < land[i][j]) {
basin = walkThroughBasin(i, j - 1, basin, land, basins, size);
} else
if (vd <= vr && vd <= vu && vd <= vl && vd < land[i][j]) {
basin = walkThroughBasin(i, j + 1, basin, land, basins, size);
} else {
basins[i][j] = currentBasin;
return currentBasin ++;
}
basins[i][j] = basin;
return basin;
}
}
Python implementation
import sys
#-------------------------------------------------------------------------------
def printFunc(x,y):
sys.stdout.write( "(" +str(x) + "," + str(y)+")" )
#-------------------------------------------------------------------------------
def printFunc1(x):
sys.stdout.write( str(x)+" " )
#-------------------------------------------------------------------------------
def isSink(x,y,n,grid):
curr = grid[y][x]
#North
if (y-1) >= 0 and grid[y-1][x] < curr:
return False
#South
if (y+1) < n and grid[y+1][x] < curr:
return False
#West
if (x-1) >= 0 and grid[y][x-1] < curr:
return False
#East
if (x+1) < n and grid[y][x+1] < curr:
return False
return True
#-------------------------------------------------------------------------------
def drainToSink(x,y,n,grid,visited,num):
curr = grid[y][x]
if visited[y][x] >= 0:
return num
minX = x
minY = y
currVisitList=[]
while not isSink(x,y,n,grid):
#North
if (y-1) >= 0 and grid[y-1][x] < curr:
minY = y-1
minX = x
curr = grid[minY][minX]
#South
if (y+1) < n and grid[y+1][x] < curr:
minY = y+1
minX = x
curr = grid[minY][minX]
#West
if (x-1) >= 0 and grid[y][x-1] < curr:
minX=x-1
minY = y
curr = grid[minY][minX]
#East
if (x+1) < n and grid[y][x+1] < curr:
minX=x+1
minY = y
curr = grid[minY][minX]
currVisitList.append([x,y])
if visited[minY][minX] >= 0:
#Trace back and assign the value of visited node
for pair in currVisitList:
xt = pair[0]
yt = pair[1]
visited[yt][xt] = visited[minY][minX]
return num
x = minX
y = minY
for pair in currVisitList:
xt = pair[0]
yt = pair[1]
visited[yt][xt] = num
visited[minY][minX] = num
return num+1
#-------------------------------------------------------------------------------
#Start by opening the file.
fIn = open(sys.argv[1],'r')
n = int( fIn.readline() )
landGrid=[]
#Create an array of integers representing elevation.
for line in fIn:
intList = map(int, line.split(' '))
landGrid.append( intList )
#print intList
#practice printing arrays
for y in range(0,n):
for x in range(0,n):
printFunc1(landGrid[y][x])
print
#Initialize and empty 2d array.
#-1 marks unvisited elements
visited =[]
for y in range(0,n):
tempList = []
for x in range(0,n):
tempList.append( -1 )
visited.append(tempList)
print "-----------------------------------"
numSinks = 0
for y in range(0,n):
for x in range(0,n):
numSinks = drainToSink(x,y,n,landGrid,visited,numSinks)
print numSinks
for y in range(0,n):
for x in range(0,n):
printFunc1(visited[y][x])
print
#initialize an array with basin counts.
basinCounts=[]
for i in range(0,numSinks):
basinCounts.append(0)
#now count them.
for lst in visited:
for x in lst:
basinCounts[x] = basinCounts[x]+1
basinCounts.sort(reverse=True)
print
for x in basinCounts:
sys.stdout.write( str(x)+" " )
print
My solution follows the O(m*n) scan and DFS algorithm. I'm pretty sure this is O(m*n) because each node is guaranteed to be visited once. In layman's terms this is what I do:
1. Scan each node marking the node as visited iff the node is considered a sink
2. For sink nodes, perform a DFS on the node to find the members of this basin.
3. For each member of the current basin, mark as visited and continue checking while incrementing the current count.
4. Add the basin count to the result list.
5. Once all nodes have been visited, print the basin size list in descending order.
EDIT: Fixed the output to be in-line with the required solution and removed debug printing.
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.*;
/**
* @author chris moran
*/
public class RainfallDFS {
public static void main(String[] args) {
int[][] rain = buildMatrix("rainfall.txt");
boolean[][] visited = new boolean[rain.length][rain[0].length];
for(boolean[] v : visited)
Arrays.fill(v, false);
List<Integer> basins = new ArrayList<Integer>();
for(int y = 0; y < rain.length; y++) {
for(int x = 0; x < rain[y].length; x++) {
processMatrix(rain, visited, y, x, basins);
}
}
Collections.sort(basins, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
});
for(int basin:basins)
System.out.print(basin + " ");
}
private static List<Integer> processMatrix(int[][] rain, boolean[][] visited, int y, int x, List<Integer> basins) {
if(visited[y][x])
return basins;
if(isSink(rain, y, x)) {
int count = processDFS(rain, visited, y, x);
basins.add(count);
visited[y][x] = true;
}
return basins;
}
private static int processDFS(int[][] rain, boolean[][] visited, int y, int x) {
int count = 0;
if(visited[y][x])
return count;
visited[y][x] = true;
count++;
if(x + 1 < rain[y].length && rain[y][x + 1] > rain[y][x] && rain[y][x] == findLowest(rain, y, x+1)) {//Are we the lowest of right's neighbors?
count += processDFS(rain, visited, y, x + 1);
}
if(x - 1 >= 0 && rain[y][x - 1] > rain[y][x] && rain[y][x] == findLowest(rain, y, x-1)) {//Are we the lowest of left's neighbors?
count += processDFS(rain, visited, y, x - 1);
}
if(y + 1 < rain.length && rain[y+1][x] > rain[y][x] && rain[y][x] == findLowest(rain, y+1, x)) {//Are we the lowest of down's neighbors?
count += processDFS(rain, visited, y+1, x);
}
if(y - 1 >= 0 && rain[y-1][x] > rain[y][x] && rain[y][x] == findLowest(rain, y-1, x)) {//Are we the lowest of up's neighbors?
count += processDFS(rain, visited, y-1, x);
}
return count;
}
private static int findLowest(int[][] rain, int y, int x) {
int clow = Integer.MAX_VALUE;
if(x + 1 < rain[y].length) {//r
clow = Math.min(clow, rain[y][x+1]);
}
if(x - 1 >= 0) {//l
clow = Math.min(clow, rain[y][x-1]);
}
if(y + 1 < rain.length) {//d
clow = Math.min(clow, rain[y+1][x]);
}
if(y - 1 >= 0) {//u
clow = Math.min(clow, rain[y-1][x]);
}
return clow;
}
private static boolean isSink(int[][] rain, int y, int x) {
boolean isSink = true;
if(x + 1 < rain[y].length) {//r
isSink = rain[y][x] < rain[y][x + 1];
}
if(x - 1 >= 0) {//l
isSink &= rain[y][x] < rain[y][x - 1];
}
if(y + 1 < rain.length) {//d
isSink &= rain[y][x] < rain[y + 1][x];
}
if(y - 1 >= 0) {//u
isSink &= rain[y][x] < rain[y - 1][x];
}
return isSink;
}
private static int[][] buildMatrix(String s) {
int[][] matrix = null;
try {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(new FileInputStream(s)));
String line = bufferedReader.readLine();
int size = Integer.parseInt(line.trim());
matrix = new int[size][size];
line = bufferedReader.readLine().trim();
for(int i = 0; i < size; i++) {
StringTokenizer st = new StringTokenizer(line);
for(int j = 0; j < size; j++) {
matrix[i][j] = Integer.parseInt(st.nextToken().trim());
}
line = bufferedReader.readLine();
}
} catch(Exception ignored) {
}
return matrix;
}
}
import sys
def find_root(i, set):
if set[i] < 0:
return i
else:
return find_root(set[i],set)
def method():
# taking stdin and making a matrix
size = sys.stdin.readline()
print(size)
size = int(size)
matrix = [None]*size
count = 0
for line in sys.stdin:
row = line.split(' ')
print(row)
for i in range(len(row)):
row[i] = int(row[i])
matrix[count] = row
count+=1
print(matrix)
# we also want to make a list of size = size*size
set_map = [None]*(size*size)
# iterate through the whole matrix
for i in range(size):
for j in range(size):
my_val = matrix[i][j]
my_idx = -1
east = matrix[i][j]
west = matrix[i][j]
north = matrix[i][j]
south = matrix[i][j]
if i+1 < size:
south = matrix[i+1][j]
if j+1 < size:
east = matrix[i][j+1]
if i-1 >= 0:
north = matrix[i-1][j]
if j-1 >= 0:
west = matrix[i][j-1]
if my_val > east:
my_val = east
my_idx = size*i + j + 1
if my_val > west:
my_val = west
my_idx = size*i + j - 1
if my_val > south:
my_val = south
my_idx = size*(i+1) + j
if my_val > north:
my_val = north
my_idx = size*(i-1)+j
#find the minimum value and set the index of the min value direction
# as the root of the current index
# basically you are making a disjoint set
set_map[size*i+j] = my_idx
# we have made a disjoint set with the set_map now
# it is time to find the number of roots
root_dict = {}
for i in range(size*size):
root = find_root(i, set_map)
if root in root_dict:
root_dict[root] += 1
else:
root_dict[root] = 1
print(root_dict) #this will print out the a dictionary of root and the number
# of elements in the set that have the root as their key
if __name__ == '__main__':
method()
Just another solution -
1) For every element in matrix(at pos1), find smallest(pos2) in its surroundings and record its position in format (row*ROWS+col);
2) union the original position to this position. union1(pos1,pos2);
3)store in map and sort by frequency
4)print it
#include <iostream>
#include <algorithm>
#include <climits>
#include <unordered_map>
#include <vector>
#define NEIGHBOURS 4
using namespace std;
typedef vector< vector<int> > matrix;
int neighbour[NEIGHBOURS][2] = { {0,-1}, {-1,0},{0,1},{1,0} };
int find(int id[],int p) {
while(p != id[p])
p = id[p];
return p;
}
void union1(int id[],int p,int q) {
int proot = find(id,p);
int qroot = find(id,q);
if(proot != qroot)
id[proot] = qroot;
}
bool issafe(int p,int S) {
return (p>=0 && p < S);
}
int small(matrix m,int i,int j,int S) {
int sm = m[i][j];
int pos = i*S+j;
for(int k=0;k<NEIGHBOURS;k++) {
if( issafe(neighbour[k][0]+i,S) && issafe(neighbour[k][1]+j,S) ) {
int tmp = min(sm, m[ neighbour[k][0]+i ] [ neighbour[k][1]+j ]);
if(sm != tmp)
pos = S*(neighbour[k][0]+i) + neighbour[k][1]+j;
sm = tmp;
}
}
return pos;
}
int main()
{
/*matrix mat = {
{1, 5, 2},
{2, 4, 7},
{3, 6, 9}
};*/
matrix mat = {
{1, 0, 2, 5, 8},
{2, 3, 4, 7, 9 },
{3, 5, 7, 8, 9},
{1, 2, 5, 4, 2},
{3, 3, 5, 2, 1}
};
int S = 5;
unordered_map<int,int> m;
vector<int> v;
int id[S*S];
for(int i=0;i<S*S;i++) {
id[i] = i;
}
for(int i=0;i<S;i++) {
for(int j=0;j<S;j++) {
int s = small(mat,i,j,S);
if( s != i*S +j)
union1(id,i*S+j,s);
}
}
for(int i=0;i<S*S;i++) {
m[ find(id,id[i]) ]++;
}
for(auto i:m) {
v.push_back(i.second);
}
sort(v.rbegin(),v.rend());
for(int i=0;i<v.size();i++){
cout<<v[i]<<" ";
}
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
struct Cell
{
int x, y;
char marker;
};
bool is_digit(char c)
{
return '0' <= c && c <= '9';
}
void clasterize(vector<vector<char>> &map)
{
char marker = 'A';
auto compare = [](pair<int, Cell> const &lhs, pair<int, Cell> const &rhs){ return lhs.first < rhs.first || (lhs.first == rhs.first && lhs.second.x < rhs.second.x) || (lhs.first == rhs.first && lhs.second.x == rhs.second.x && lhs.second.y < rhs.second.y); };
set<pair<int, Cell>, decltype(compare)> queue(compare);
for (auto i = 0; i < map.size(); ++i)
for (auto j = 0; j < map[i].size(); ++j)
{
bool top, bottom, right, left;
top = bottom = right = left = false;
if (0 == i || (i > 0 && map[i-1][j] > map[i][j]))
top = true;
if (map.size()-1 == i || (i < map.size()-1 && map[i+1][j] > map[i][j]))
bottom = true;
if (0 == j || (j > 0 && map[i][j-1] > map[i][j]))
left = true;
if (map[i].size()-1 == j || (j < map[i].size()-1 && map[i][j+1] > map[i][j]))
right = true;
if (top && bottom && left && right)
queue.insert(make_pair(map[i][j], Cell({.x = i, .y = j, .marker = marker++})));
}
while (!queue.empty())
{
auto cell = (*queue.begin()).second;
queue.erase(queue.begin());
if (is_digit(map[cell.x][cell.y]))
{
map[cell.x][cell.y] = cell.marker;
if (cell.x > 0 && is_digit(map[cell.x-1][cell.y]))
queue.insert(make_pair(map[cell.x-1][cell.y], Cell({.x = cell.x-1, .y = cell.y, .marker = cell.marker})));
if (cell.x < map.size()-1 && is_digit(map[cell.x+1][cell.y]))
queue.insert(make_pair(map[cell.x+1][cell.y], Cell({.x = cell.x+1, .y = cell.y, .marker = cell.marker})));
if (cell.y > 0 && is_digit(map[cell.x][cell.y-1]))
queue.insert(make_pair(map[cell.x][cell.y-1], Cell({.x = cell.x, .y = cell.y-1, .marker = cell.marker})));
if (cell.y < map[cell.x].size()-1 && is_digit(map[cell.x][cell.y+1]))
queue.insert(make_pair(map[cell.x][cell.y+1], Cell({.x = cell.x, .y = cell.y+1, .marker = cell.marker})));
}
}
}
int main()
{
vector<vector<char>> map =
{
{'1', '0', '2', '5', '8'},
{'2', '3', '4', '7', '9'},
{'3', '5', '7', '8', '9'},
{'1', '2', '5', '4', '2'},
{'3', '3', '5', '2', '1'}
};
clasterize(map);
for (auto v : map)
{
for (auto c : v)
cout << c << " ";
cout << endl;
}
return 0;
}
It's a kind of shortest path problem, so use BFS and a priority queue.
At the beginning traverse the map and find all sinks. Push them to the priority queue, where primary priority is land's height at that sink. You should also assign a marker to any cell you push to the queue. Initially just increment your marker starting with 'A' and assign it to each sink you find.
The loop until queue is empty. Pop a cell on the top of the queue and if the land corresponding to that cell has not being marked, mark it with the cell's marker and add to the queue any unmarked neighbors.
To count the number of As, Bs, etc. just count what marker you're assigning to an unmarked land once you've popped the next cell from the queue.
Union find algorithm is the right fit for this problem.
For each cell find another cell where it flows to and the group them in one group.
Finally return the number of basins.
class Solution:
def group_of_basins(self):
N, M = list(map(int, input().split()))
graph = self.get_graph(N, M)
parent = {(row, col):(row, col) for row in range(N) for col in range(M)}
self.size = {(row, col):1 for row in range(N) for col in range(M)}
for row in range(N):
for col in range(M):
sink_row, sink_col = row, col
value = graph[row][col]
DIR = [(1, 0), (0, 1), (-1, 0), (0, -1)]
for row_increase, col_increase in DIR:
new_row = row + row_increase
new_col = col + col_increase
if 0 <= new_row < N and 0 <= new_col < M:
if graph[new_row][new_col] < value:
sink_row = new_row
sink_col = new_col
value = graph[new_row][new_col]
self.union((row, col), (sink_row, sink_col), parent)
processed = set()
result = []
for row in range(N):
for col in range(M):
par = self.find((row, col), parent)
if par not in processed:
result.append(self.size[par])
processed.add(par)
return sorted(result, reverse = True)
def find(self, x, parent):
if parent[x] == x:
return x
parent[x] = self.find(parent[x], parent)
return parent[x]
def union(self, x, y, parent):
x_parent = self.find(x, parent)
y_parent = self.find(y, parent)
if x_parent != y_parent:
if self.size[x_parent] < self.size[y_parent]:
x_parent, y_parent = y_parent, x_parent
self.size[x_parent] += self.size[y_parent]
parent[y_parent] = x_parent
def get_graph(self, N, M):
graph = []
for _ in range(N):
graph.append(list(map(int, input().split())))
return graph
solution = Solution()
result = solution.group_of_basins()
print(result)
This could be done in liner time with having extra space.
start for first element and mark a unique flag (start with 1) for each element that has visited and its corresponding lowest neighbor.if lowest neighbor has been visited then mark that position with same flag, else assign different flag .
In case If a different flags lowest neighbor is already visited and its flag is differ then make both flag with same group.
In the last you may count nbr of basin on the basis of flag(flag group).
My Solution. Though I was not able to complete in 100 min. Wasted a golden opportunity.
-----------------------------
- Nitin Gupta February 02, 2013