CareerCup

In fact, as a node, I am a leaf i.i.f. the node following me in the preorder traversal array is greater than the first of my ancestors which is greater than me. So while traversing the BST, we need to maintain the stack of the ancestors that are greater than the current node.

In java, something like:

public static List<Integer> getLeaves(List<Integer> bst) {
        List<Integer> leaves = new ArrayList<>();
        
        Stack<Integer> greaterAncestors = new Stack<>();

        int previous = 0;

        for (int i: bst) {
            int ancestor = 0;
            // Find the first ancestor which is greater than the current node.
            while (!greaterAncestors.isEmpty() && greaterAncesters.peek() < i) {
                ancestor = greaterAncestors.pop();
            }
            greaterAncestors.push(i);
            if (ancestor > previous) {
                leaves.add(previous);
            }
            previous = i;
        }

        if (!bst.isEmpty()) {
            // The last node is always a leaf.
            leaves.add(previous);
        }

        return leaves;
    }

I wonder:
Is this a plus?

0 0 0 0 1 0 0 0 0
0 1 1 0 1 0 1 1 0
0 0 0 0 1 0 1 1 0
0 0 0 0 1 0 0 0 0
1 1 1 1 1 1 1 1 1
0 0 0 0 1 0 0 0 0
0 0 0 0 1 0 0 0 0
0 0 0 0 1 0 0 1 0
1 0 0 0 1 0 0 0 0

that is to say a "plus" would be defined as one horizontal segment of only 1s of size 2*i+1 and one vertical segment of only 1s of size 2*i+1 intersecting at their center.

Or only that kind of stuff is a plus?

0 0 0 0 1 0 0 0 0
0 0 0 0 1 0 0 0 0
0 0 0 0 1 0 0 0 0
0 0 0 0 1 0 0 0 0
1 1 1 1 1 1 1 1 1
0 0 0 0 1 0 0 0 0
0 0 0 0 1 0 0 0 0
0 0 0 0 1 0 0 0 0
0 0 0 0 1 0 0 0 0

If that's the second, it is a bit more complicated with a sparse matrix... So I'll assume it is the first.

I represent the sparse matrix simply as the set of positions where the 1s are.

package exercices;

import java.util.*;

public class LargestPlusFinder {

    public static Plus findLargestPlus(Set<Position> board) throws NoPlusFoundException {
        AdjacencyGraph adjacencyGraph = new AdjacencyGraph(board);
        return adjacencyGraph.findLargestPlus();
    }

    private static class AdjacencyGraph {
        Map<Position, Vertex> vertices;
        Set<Vertex> potentialPlusCenters;

        public AdjacencyGraph(Set<Position> board) {
            vertices = new HashMap<>();
            potentialPlusCenters = new HashSet<>();
            for (Position position: board) {
                addPosition(position);
            }
        }

        private void addPosition(Position position) {
            if (vertices.containsKey(position)) {
                return;
            }
            Vertex newVertex = new Vertex(position);
            makeEdgesForNewVertex(newVertex);
            if (newVertex.isPotentialPlusCenter()) {
                potentialPlusCenters.add(newVertex);
            }
            vertices.put(position, newVertex);
        }

        private void makeEdgesForNewVertex(Vertex newVertex) {
            Position position = newVertex.getPosition();
            for (Direction direction: Direction.values()) {
                if (vertices.containsKey(position.getAdjacentPosition(direction))) {
                    Vertex adjacentVertex = vertices.get(position.getAdjacentPosition(direction));
                    makeBidirectionalEdge(newVertex, direction, adjacentVertex);
                    if (adjacentVertex.isPotentialPlusCenter()) {
                        potentialPlusCenters.add(adjacentVertex);
                    }
                }
            }
        }

        private void makeBidirectionalEdge(Vertex v1, Direction direction, Vertex v2) {
            v1.add(direction, v2);
            v2.add(opposite(direction), v1);
        }

        public Plus findLargestPlus() throws NoPlusFoundException {
            if (vertices.isEmpty()) {
                throw new NoPlusFoundException();
            }
            int maxEdgeLength = 0;
            Position maxPlusCenter = vertices.keySet().iterator().next();
            for (Vertex v: potentialPlusCenters) {
                Plus plus = getPlusAt(v); // there is at least a plus of edge size 0 at v
                if (plus.getEdgeLength() > maxEdgeLength) {
                    maxEdgeLength = plus.getEdgeLength();
                    maxPlusCenter = plus.getCenter();
                }
            }
            return new Plus(maxPlusCenter, maxEdgeLength);
        }

        private Plus getPlusAt(Vertex v) {
            Queue<Exploration> q = new LinkedList<>();
            for (Direction d: Direction.values()) {
                q.add(new Exploration(d, v.getAdjacent(d), 1));
            }
            Exploration e = q.poll();
            while (e != null) {
                Direction direction = e.getDirection();
                Vertex exploredVertex = e.getVertex();
                int currentEdgeLength = e.getReachedEdgeLength();
                if (exploredVertex.getAdjacent(direction) != null) {
                    q.add(new Exploration(direction, exploredVertex.getAdjacent(direction), currentEdgeLength + 1));
                } else {
                    // Exploration stops here
                    return (new Plus(v.getPosition(), currentEdgeLength));
                }
                e = q.poll();
            }
            throw new ProgrammingErrorException();
        }

        private static class Vertex {
            final Position position;
            Map<Direction, Vertex> adjacentVertices;

            public Vertex(Position position) {
                this.position = position;
                adjacentVertices = new HashMap<>();
            }

            public void add(Direction d, Vertex v) {
                adjacentVertices.put(d, v);
            }

            public boolean isPotentialPlusCenter() {
                return adjacentVertices.size() == Direction.values().length;
            }

            public Position getPosition() {
                return position;
            }

            public Vertex getAdjacent(Direction d) {
                return adjacentVertices.get(d);
            }
        }

        private static class Exploration {
            Direction direction;
            Vertex vertex;
            int reachedEdgeLength;

            public Exploration(Direction direction, Vertex vertex, int reachedEdgeLength) {
                this.direction = direction;
                this.vertex = vertex;
                this.reachedEdgeLength = reachedEdgeLength;
            }

            public Direction getDirection() {
                return direction;
            }

            public Vertex getVertex() {
                return vertex;
            }

            public int getReachedEdgeLength() {
                return reachedEdgeLength;
            }
        }
    }

    private static class Position {
        int i;
        int j;

        public Position(int i, int j) {
            this.i = i;
            this.j = j;
        }

        public Position getAdjacentPosition(Direction d) {
            switch (d) {
                case UP:
                    return new Position(i-1, j);
                case DOWN:
                    return new Position(i+1, j);
                case LEFT:
                    return new Position(i, j-1);
                case RIGHT:
                    return new Position(i, j+1);
                default:
                    throw new ProgrammingErrorException();
            }
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Position position = (Position) o;
            return i == position.i &&
                    j == position.j;
        }

        @Override
        public int hashCode() {
            return Objects.hash(i, j);
        }

        @Override
        public String toString() {
            return "Position{" +
                    "i=" + i +
                    ", j=" + j +
                    '}';
        }
    }

    private static class Plus {
        private Position center;
        private int edgeLength;

        public Plus(Position center, int edgeLength) {
            this.center = center;
            this.edgeLength = edgeLength;
        }

        public Position getCenter() {
            return center;
        }

        public int getEdgeLength() {
            return edgeLength;
        }

        @Override
        public String toString() {
            return "(" + i + ", " + j + ")";
        }
    }

    private enum Direction {UP, DOWN, RIGHT, LEFT}

    private static Direction opposite(Direction d) {
        switch (d) {
            case UP:
                return Direction.DOWN;
            case DOWN:
                return Direction.UP;
            case LEFT:
                return Direction.RIGHT;
            case RIGHT:
                return Direction.LEFT;
            default:
                throw new ProgrammingErrorException();
        }
    }

    private static class NoPlusFoundException extends Exception {}

    private static class ProgrammingErrorException extends RuntimeException {}

    public static void main(String[] args) {
        Set<Position> board = new HashSet<>();
        board.add(new Position(100, 100));
        board.add(new Position(101, 100));
        board.add(new Position(102, 100));
        board.add(new Position(99, 100));
        board.add(new Position(98, 100));
        board.add(new Position(100, 101));
        board.add(new Position(100, 102));
        board.add(new Position(100, 99));
        board.add(new Position(100, 98));
        board.add(new Position(99, 98));

        try {
            Plus maxPlus = findLargestPlus(board);
            System.out.println(maxPlus);
        } catch (NoPlusFoundException e) {
            System.out.println("No plus in board.");
        }
    }
}