An Efficient Frequency-Based Approach for Maximal Square Detection in Binary Matrices
Swastik Bhandari · 2025
Read An Efficient Frequency-Based Approach for Maximal Square Detection in Binary Matrices by Swastik Bhandari (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-18974.txt.
Introduction
Swastik Bhandari introduces, in a 2025 paper, a frequency-based algorithm that finds the largest all-ones square inside a binary matrix faster than the classic method. The textbook dynamic programming solution is optimal on paper but wastes time on repeated minimum hunts and hops around memory. His alternative watches columns instead.
A greedy pass tracks how long each column's run of ones has lasted, using a frequency array that adapts and a moving threshold to spot candidate squares. Across matrices up to 5,000 by 5,000 and densities from sparse to dense, the new method won every race, averaging 3.32 times faster and peaking at 4.6. Dense matrices gained most. Square hunting sits inside image analysis and pattern tools, so the speedup travels widely.
Catalog record
| CREATOR | Swastik Bhandari |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 27 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-18974
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
An Efficient Frequency-Based Approach for Maximal Square Detection in Binary Matrices Swastik Bhandari Abstract Detecting maximal square submatrices of ones in binary matrices is a fundamental problem with applications in computer vision and pattern recognition. While the standard dynamic programming (DP) solution achieves optimal asymptotic complexity, its practical performance suffers from repeated minimum operations and inefficient memory access patterns that degrade cache utilization. To address these limitations, we introduce a novel frequency-based algorithm that employs a greedy approach to track the columnar continuity of ones through an adaptive frequency array and a dynamic thresholding mechanism. Extensive benchmarking demonstrates that the frequency-based algorithm achieves faster performance than the standard DP in 100% of test cases with an average speedup of 3.32 × \times , a maximum speedup of 4.60 × \times , and a minimum speedup of 2.31 × \times across matrices up to 5000 × \times 5000 with densities from 0.1 to 0.9. The algorithm’s average speedup exceeds 2.5 × \times for all densities and rises to over 3.5 × \times for densities of 0.7 and higher across all matrix sizes. These results demonstrate that the frequency-based approach is a superior alternative to standard DP and opens new possibilities for efficient matrix analysis in performance-critical applications. 1 Introduction The maximal square detection problem involves finding the largest contiguous square submatrix composed entirely of 1s in a binary matrix. It is a classical problem with applications in various areas, such as computer vision and pattern recognition. The standard dynamic programming (DP) solution addresses this problem by constructing a two-dimensional table where each cell is computed as: dp[i][j]=\min\{dp[i-1][j],\,dp[i][j-1],\,dp[i-1][j-1]\}+1, which represents the side length of the largest square ending at that cell [ 1 ] . While the classic dynamic programming (DP) approach is theoretically optimal, its practical speed is often limited by repeated minimum operations and poor cache performance on modern hardware. To understand the performance bottlenecks, it is important to consider how matrices are stored in computer memory. Matrices are mapped to the one-dimensional contiguous memory of a computer. In programming languages like C++, Python, and Java, the elements are stored in row-major order, meaning each row is placed next to each other, whereas in programming languages like Fortran, MATLAB, and R, elements are placed in column-major order, in which elements within a column are adjacent in memory. In the DP approach, it reads from the top ( dp[i-1][j] ), left ( dp[i][j-1] ), and top-left ( dp[i-1][j-1] ) neighbours. In row-major order, the vertical ( dp[i-1][j] ) and diagonal ( dp[i-1][j-1] ) accesses jump across rows, increasing the likelihood of cache misses. Similarly, in column-major order, the horizontal ( dp[i][j-1] ) and diagonal ( dp[i-1][j-1] ) accesses cause similar issues. As a result, the DP algorithm does not access memory efficiently in either layout, especially for large binary matrices. This paper presents a frequency-based algorithm that mitigates these issues and finds the maximal squares faster than the existing DP solution. The algorithm tracks the vertical continuity of the ones using a frequency array and employs a dual threshold mechanism to dynamically adjust search parameters. This approach avoids repeated minimum computations over vertical, horizontal, and diagonal neighbors, reducing computational overhead and performs much faster than the standard DP approach with average speedup of 3.32 \times . The main objective of this paper is to introduce a frequency-based algorithm for maximal square detection in binary matrices that overcomes performance limitations of the standard dynamic programming (DP) approach and achieves significantly faster execution in practice. 2 Related Work 2.1 Traditional Dynamic Programming for Maximal Squares Traditional dynamic programming techniques for the maximal square problem use a 2D table with entries computed as: dp[i][j]=\min\{dp[i-1][j],\,dp[i][j-1],\,dp[i-1][j-1]\}+1, (1) yielding O(mn) time and space complexity [ 1 ] . A well-known space optimization processes the matrix row by row, maintaining only the values of the previous row to achieve O(n) space complexity while maintaining O(mn) time complexity. 2.2 Statistical Foundations and Maximal Squares The statistical behavior of maximal square submatrices of ones in binary matrices has been rigorously explored by Sun and Nobel [ 2 ] . They analyze the size of the largest k\times k square of ones in a random binary matrix with independent Bernoulli entries and establish a sharp concentration around s(n)=2\log_{b}n-2\log_{b}\log_{b}n+C+o(1) , where b=1/p and p is the success probability. Their work establishes precise probabilistic bounds for the largest square under randomness and analyzes submatrix recovery under additive noise, providing a crucial theoretical baseline for distinguishing statistically significant squares from those likely to arise from noise. While their analysis establishes a valuable theoretical foundation for understanding randomness and noise, it does not consider efficient detection in arbitrary binary matrices, which is the primary focus of our approach. 2.3 Histogram-Based Maximal Rectangle Detection The histogram-based approach is a widely used method for detecting maximal rectangles in binary matrices. It converts each row into a histogram of vertical one-counts and applies a stack-based linear algorithm to compute the largest rectangular area. While effective for rectangles, this method differs fundamentally from our approach in both structure and objective. Unlike the histogram method, which is designed for maximal rectangles and relies on building histograms and using stacks to validate areas after full row processing, our algorithm performs inline square validation in a single pass using a greedy strategy. It incrementally updates vertical frequency counts and confirms larger squares only if smaller ones have already been found. 2.4 Summary Standard DP suffers from min-operations and cache inefficiency. Statistical methods analyze random matrices but don’t accelerate detection, while histogram-based approaches target rectangles with stack overhead. Our frequency-based algorithm uses a fundamentally different approach: single-pass greedy validation via adaptive thresholds and vertical continuity tracking, eliminating min operations and achieving unprecedented speedups while maintaining optimality. 3 Algorithm Design and Analysis 3.1 Core Methodology The frequency-based algorithm uses a greedy approach. The algorithm maintains a frequency array freq that tracks consecutive ones in column j . A variable found_max_width tracks the current maximal square, while two dynamic thresholds ( check_max_width and check_max_height ) validate larger square formation. If a larger square is found, found_max_width is updated to reflect the new maximum, and both check_max_width and check_max_height are incremented accordingly. A counter variable maintains horizontal continuity, enabling validation of adjacent larger squares, as illustrated in Fig. 1 . 3.2 Greedy Square Validation Strategy Initially, the algorithm sets the square size threshold to 1 \times 1 and attempts to validate squares on each row. For each row: • Vertical continuity is tracked via freq[j] , whereas horizontal continuity is tracked using a scalar counter and if the counter equals the check_max_width, a square is validated. • Upon successful detection, found_max_width is updated to the current maximal square, and the square size thresholds (check_max_width and check_max_height) are increased by 1. Algorithm 1 Maximal Square in Binary Matrix 0: v is a 2D matrix of characters (’0’ or ’1’) 0: Returns the area of the largest square containing only ’1’s 1: function MaximalSquare ( v ) 2: if v is empty OR v[0] is empty then 3: return 0 4: end if 5: row\_size\leftarrow|v[0]| {Number of columns} 6: col\_size\leftarrow|v| {Number of rows} 7: found\_max\_width\leftarrow 0 {Side length of largest square found} 8: check\_max\_width\leftarrow 1 {Target square width