Largest cross in a sparse matrix – Andrey Khayrutdinov – Medium

Problem

Given a binary matrix of size N × M (0/1 entries), find the largest plus-shaped cross composed entirely of 1s. A cross has a center cell (r,c) and four arms (up/down/left/right) of equal length k where each arm consists of k contiguous 1s extending outward (not counting the center). Use zero-based indexing. If there is no 1, return (-1, -1, 0).

When the matrix is sparse (only P ones, with P << N*M), sparse-friendly methods can reduce space/time versus full-grid DP.

Examples

Example 1

Input:
matrix = [
        [0,0,1,0,0,1,0],
        [1,0,1,0,1,0,1],
        [1,1,1,1,1,1,1],
        [0,0,1,0,0,0,0],
        [0,0,0,0,0,0,0]
]
Output: (2, 2, 1)
Explanation: Center (2,2); one continuous 1 in each direction ⇒ arm length 1.

Example 2

Input:
matrix = [
        [0,0,1,0,0],
        [0,0,1,0,0],
        [1,1,1,1,1],
        [0,0,1,0,0],
        [0,0,1,0,0]
]
Output: (2, 2, 2)
Explanation: From (2,2) we can extend 2 cells each direction (arm length 2).

Example 3

Input: matrix = [[0,0],[0,0]]
Output: (-1, -1, 0)
Explanation: No 1s.

Example 4

Input: matrix = [[1]]
Output: (0, 0, 0)
Explanation: Single 1 ⇒ arms length 0.

Solution

We present two common approaches:

• Method 1 — DP over the full grid (O(NM) time and O(NM) space): compute, for every cell, the number of consecutive ones in the four directions and take the maximum of the minima.
• Method 2 — Sparse-optimized graph approach (O(P) time and memory): store only the coordinates of ones, link neighbors, and compute line lengths by traversing adjacency lists with memoization.

Method 1 — Dynamic Programming (full-grid)

Intuition

For each cell (i,j) compute up[i][j], down[i][j], left[i][j], right[i][j] — the lengths of consecutive ones including the cell itself in each direction. The largest arm length centered at (i,j) is min(up, down, left, right) - 1 (subtract 1 to exclude the center if you want arm length). The answer is the maximum over all cells.

Approach

1. Initialize four N×M arrays up/down/left/right with zeros.
2. Fill up and left in a top-left to bottom-right pass: if mat[i][j] == 1 then up[i][j] = 1 + up[i-1][j] and left[i][j] = 1 + left[i][j-1] else 0.
3. Fill down and right in a bottom-right to top-left pass similarly.
4. For every cell with value 1, compute arm = min(up, down, left, right) - 1; track the maximum arm and the center.

Edge cases: empty matrix, all zeros.

Code

C++

class Solution {
 public:
    struct Cross { int r,c,k; };
    Cross largestCross(const vector<vector<int>>& mat) {
        int N = mat.size(); if (!N) return {-1,-1,0};
        int M = mat[0].size();
        vector<vector<int>> up(N, vector<int>(M)), down(up), left(up), right(up);
        for (int i = 0; i < N; ++i) for (int j = 0; j < M; ++j) if (mat[i][j]) {
            up[i][j] = 1 + (i? up[i-1][j]:0);
            left[i][j] = 1 + (j? left[i][j-1]:0);
        }
        for (int i = N-1; i >= 0; --i) for (int j = M-1; j >= 0; --j) if (mat[i][j]) {
            down[i][j] = 1 + (i+1<N? down[i+1][j]:0);
            right[i][j] = 1 + (j+1<M? right[i][j+1]:0);
        }
        int bestK = 0, br=-1, bc=-1;
        for (int i = 0; i < N; ++i) for (int j = 0; j < M; ++j) if (mat[i][j]) {
            int arm = min(min(up[i][j], down[i][j]), min(left[i][j], right[i][j])) - 1;
            if (arm > bestK) { bestK = arm; br = i; bc = j; }
        }
        return {br, bc, bestK};
    }
};

Go

package main

type Cross struct{ r, c, k int }

func largestCross(mat [][]int) Cross {
        N := len(mat); if N == 0 { return Cross{-1,-1,0} }
        M := len(mat[0])
        up := make([][]int, N); down := make([][]int, N); left := make([][]int, N); right := make([][]int, N)
        for i := 0; i < N; i++ { up[i] = make([]int, M); down[i] = make([]int, M); left[i] = make([]int, M); right[i] = make([]int, M) }
        for i := 0; i < N; i++ {
                for j := 0; j < M; j++ {
                        if mat[i][j] == 1 {
                                if i > 0 { up[i][j] = up[i-1][j] + 1 } else { up[i][j] = 1 }
                                if j > 0 { left[i][j] = left[i][j-1] + 1 } else { left[i][j] = 1 }
                        }
                }
        }
        for i := N-1; i >= 0; i-- {
                for j := M-1; j >= 0; j-- {
                        if mat[i][j] == 1 {
                                if i+1 < N { down[i][j] = down[i+1][j] + 1 } else { down[i][j] = 1 }
                                if j+1 < M { right[i][j] = right[i][j+1] + 1 } else { right[i][j] = 1 }
                        }
                }
        }
        bestK, br, bc := 0, -1, -1
        for i := 0; i < N; i++ {
                for j := 0; j < M; j++ {
                        if mat[i][j] == 1 {
                                arm := min4(up[i][j], down[i][j], left[i][j], right[i][j]) - 1
                                if arm > bestK { bestK, br, bc = arm, i, j }
                        }
                }
        }
        return Cross{br, bc, bestK}
}

func min4(a,b,c,d int) int { m := a; if b < m { m = b }; if c < m { m = c }; if d < m { m = d }; return m }

Java

class Solution {
    static class Cross { int r,c,k; Cross(int r,int c,int k){this.r=r;this.c=c;this.k=k;} }
    public Cross largestCross(int[][] mat) {
        int N = mat.length; if (N==0) return new Cross(-1,-1,0);
        int M = mat[0].length;
        int[][] up = new int[N][M], down = new int[N][M], left = new int[N][M], right = new int[N][M];
        for (int i=0;i<N;i++) for (int j=0;j<M;j++) if (mat[i][j]==1) {
            up[i][j] = (i>0? up[i-1][j]:0) + 1;
            left[i][j] = (j>0? left[i][j-1]:0) + 1;
        }
        for (int i=N-1;i>=0;i--) for (int j=M-1;j>=0;j--) if (mat[i][j]==1) {
            down[i][j] = (i+1<N? down[i+1][j]:0) + 1;
            right[i][j] = (j+1<M? right[i][j+1]:0) + 1;
        }
        int bestK=0, br=-1, bc=-1;
        for (int i=0;i<N;i++) for (int j=0;j<M;j++) if (mat[i][j]==1) {
            int arm = Math.min(Math.min(up[i][j], down[i][j]), Math.min(left[i][j], right[i][j])) - 1;
            if (arm > bestK) { bestK = arm; br = i; bc = j; }
        }
        return new Cross(br, bc, bestK);
    }
}

Python

from typing import List, Tuple

class Solution:
        def largest_cross(self, mat: List[List[int]]) -> Tuple[int,int,int]:
                if not mat: return (-1,-1,0)
                N, M = len(mat), len(mat[0])
                up = [[0]*M for _ in range(N)]; down = [[0]*M for _ in range(N)]
                left = [[0]*M for _ in range(N)]; right = [[0]*M for _ in range(N)]
                for i in range(N):
                        for j in range(M):
                                if mat[i][j]:
                                        up[i][j] = 1 + (up[i-1][j] if i>0 else 0)
                                        left[i][j] = 1 + (left[i][j-1] if j>0 else 0)
                for i in range(N-1, -1, -1):
                        for j in range(M-1, -1, -1):
                                if mat[i][j]:
                                        down[i][j] = 1 + (down[i+1][j] if i+1<N else 0)
                                        right[i][j] = 1 + (right[i][j+1] if j+1<M else 0)
                bestK = 0; br = -1; bc = -1
                for i in range(N):
                        for j in range(M):
                                if mat[i][j]:
                                        arm = min(up[i][j], down[i][j], left[i][j], right[i][j]) - 1
                                        if arm > bestK:
                                                bestK, br, bc = arm, i, j
                return (br, bc, bestK)

Complexity

• ⏰ Time complexity: O(N*M) — we perform a constant amount of work per cell in the two passes and a final scan.
• 🧺 Space complexity: O(N*M) for four direction arrays (can be reduced to O(M) by streaming rows if needed).

Method 2 — Sparse-optimized graph approach

Intuition

When only P cells contain 1, building full N×M arrays is wasteful. Store the coordinates of 1s in a hash set and build an adjacency-like structure that links each cell to its immediate neighbor in four directions (if present). Then compute line lengths along each direction using memoization and iterative stack to avoid recursion. The algorithm visits each occupied cell a constant number of times; overall time and memory are O(P).

Approach

1. Represent each occupied cell (r,c) as a packed key (e.g., (r<<32) | c) and insert into a map from key to Vertex structure.
2. For every Vertex, set pointers to its up/down/left/right neighbours by looking up keys toKey(r-1,c) etc.
3. For each Vertex and each direction, compute the contiguous line length by walking along the neighbor chain until a cached length or end is reached; use a stack to fill memoized lengths iteratively (avoid recursion).
4. For each Vertex that has all four neighbours (a potential center) compute arm = min(topLen, bottomLen, leftLen, rightLen) - 1 and track the best.

This is the method implemented in the original article; below are compact implementations in Java and Python, adapted from the article. The Java version follows the Vertex/Sibling pattern; the Python version uses dictionaries and iterative memoization.

Code (Java)

// Compact/annotated variant of the sparse approach (adapted)
class SparseSolution {
    static class Vertex { long key; Vertex up, down, left, right; int upLen=-1, downLen=-1, leftLen=-1, rightLen=-1; Vertex(long k){key=k;} }
    static long toKey(long r,int c){ return (r<<32)|c; }
    static int rowFrom(long k){ return (int)(k>>>32); }
    static int colFrom(long k){ return (int)k; }
    public static int[] largestCross(List<long[]> ones){
        Map<Long, Vertex> map = new HashMap<>();
        for (long[] p: ones) map.put(toKey(p[0], (int)p[1]), new Vertex(toKey(p[0], (int)p[1])));
        for (Vertex v: map.values()){
            int r=rowFrom(v.key), c=colFrom(v.key);
            v.up = map.get(toKey(r-1,c)); v.down = map.get(toKey(r+1,c)); v.left = map.get(toKey(r,c-1)); v.right = map.get(toKey(r,c+1));
        }
        int bestK=0, br=-1, bc=-1;
        for (Vertex v: map.values()){
            int up = computeLen(v, "up"); int down = computeLen(v, "down");
            int left = computeLen(v, "left"); int right = computeLen(v, "right");
            if (up>0 && down>0 && left>0 && right>0){ int arm = Math.min(Math.min(up,down), Math.min(left,right)) - 1; if (arm>bestK){ bestK=arm; br=rowFrom(v.key); bc=colFrom(v.key); } }
        }
        return new int[]{br,bc,bestK};
    }
    static int computeLen(Vertex v, String dir){
        // iterative memoized walk; for brevity treat string directions
        Deque<Vertex> st = new ArrayDeque<>(); Vertex cur=v; int len=0; while (cur!=null){ int cached = getCached(cur, dir); if (cached!=-1){ len = cached; break; } st.push(cur); cur = getNeighbor(cur, dir); }
        while (!st.isEmpty()){ Vertex t=st.pop(); len = len + 1; setCached(t, dir, len); }
        return len;
    }
    static Vertex getNeighbor(Vertex v, String dir){ switch(dir){ case "up": return v.up; case "down": return v.down; case "left": return v.left; default: return v.right; } }
    static int getCached(Vertex v, String dir){ switch(dir){ case "up": return v.upLen; case "down": return v.downLen; case "left": return v.leftLen; default: return v.rightLen; } }
    static void setCached(Vertex v, String dir, int val){ switch(dir){ case "up": v.upLen=val; break; case "down": v.downLen=val; break; case "left": v.leftLen=val; break; default: v.rightLen=val; break; } }
}

Code (Python)

from typing import List, Tuple

def to_key(r:int,c:int)->int:
        return (r<<32) | c

def largest_cross_sparse(ones: List[Tuple[int,int]]) -> Tuple[int,int,int]:
        s = set(to_key(r,c) for r,c in ones)
        neigh = {}
        for r,c in ones:
                k = to_key(r,c)
                neigh[k] = (to_key(r-1,c) if to_key(r-1,c) in s else None,
                                        to_key(r+1,c) if to_key(r+1,c) in s else None,
                                        to_key(r,c-1) if to_key(r,c-1) in s else None,
                                        to_key(r,c+1) if to_key(r,c+1) in s else None)
        cache = {}
        def walk(k, idx):
                # idx: 0=up,1=down,2=left,3=right
                if (k,idx) in cache: return cache[(k,idx)]
                path = []
                cur = k
                while cur is not None and (cur,idx) not in cache:
                        path.append(cur)
                        cur = neigh[cur][idx]
                base = cache.get((cur,idx), 0)
                cur_len = base
                for node in reversed(path):
                        cur_len += 1
                        cache[(node,idx)] = cur_len
                return cache[(k,idx)]
        best = ( -1, -1, 0 )
        for r,c in ones:
                k = to_key(r,c)
                up = walk(k,0); down = walk(k,1); left = walk(k,2); right = walk(k,3)
                if up and down and left and right:
                        arm = min(up,down,left,right) - 1
                        if arm > best[2]: best = (r,c,arm)
        return best

Complexity

• ⏰ Time complexity: O(P) — each occupied cell and each direction is visited a constant number of times thanks to memoization.
• 🧺 Space complexity: O(P) for maps and memo caches.

Notes

• This problem is equivalent to the LeetCode problem "Largest Plus Sign" (see related_problems). The DP method is simpler to implement when N*M is small; the sparse-optimized method is preferable for large grids with few ones.
• I preserved the original reference and gist links in source_links above. Created at: 2018-09-08T08:58:51+02:00 Updated at: 2018-09-08T08:58:51+02:00