DROPS

Document

DOI: 10.4230/LIPIcs.FUN.2026.1

Finding Maximum and Minimum Size Matrices: The Algorithmic Complexity of Coding Challenges

Authors: Abdelrahman Abdelmonsef, Xingyu Dong, Daniel Průša, Michael Wehar, and Chen Xu

Published in: LIPIcs, Volume 366, 13th International Conference on Fun with Algorithms (FUN 2026)

Abstract

We investigate coding challenge problems related to finding a maximum (or minimum) size match for a predetermined two-dimensional pattern. We improve upon known runtime results by introducing new algorithms and refining existing algorithmic techniques. First, we present our main result which introduces a nearly quadratic time algorithm for the problem of finding a rectangular block within a matrix of maximum (or minimum) size containing only positive border entries which improves the prior cubic time solution. Then, we introduce a quadratic time and linear space algorithm for the problem of finding all rectangular blocks containing only positive border and empty interior entries. Finally, we present a log(n) factor improvement for detecting the largest length such that all square blocks in a matrix have their sums bounded by a given number.

Cite as

Abdelrahman Abdelmonsef, Xingyu Dong, Daniel Průša, Michael Wehar, and Chen Xu. Finding Maximum and Minimum Size Matrices: The Algorithmic Complexity of Coding Challenges. In 13th International Conference on Fun with Algorithms (FUN 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 366, pp. 1:1-1:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{abdelmonsef_et_al:LIPIcs.FUN.2026.1,
  author =	{Abdelmonsef, Abdelrahman and Dong, Xingyu and Pr\r{u}\v{s}a, Daniel and Wehar, Michael and Xu, Chen},
  title =	{{Finding Maximum and Minimum Size Matrices: The Algorithmic Complexity of Coding Challenges}},
  booktitle =	{13th International Conference on Fun with Algorithms (FUN 2026)},
  pages =	{1:1--1:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-417-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{366},
  editor =	{Iacono, John},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2026.1},
  URN =		{urn:nbn:de:0030-drops-257203},
  doi =		{10.4230/LIPIcs.FUN.2026.1},
  annote =	{Keywords: Pattern Matching, Matrices, Discrete Algorithms}
}

Search Results

Documents authored by Xu, Chen

Finding Maximum and Minimum Size Matrices: The Algorithmic Complexity of Coding Challenges

Abstract

Cite as

Thanks for your feedback!

Could not send message