Swift Coding Test Course, Find the Largest Square

Algorithm problems play an important role in developing problem-solving skills for programmers. In this article, we will address the problem of finding the largest square using Swift. The goal is to find the area of the largest square in a given 2D array.

Problem Description

Given a binary matrix, write a function to find the largest square containing only 1s and return its area. 0 represents an empty cell, and 1 represents a filled cell.

Example

Input:
[
    [1, 0, 1, 0, 0],
    [1, 0, 1, 1, 1],
    [1, 1, 1, 1, 1],
    [1, 0, 0, 1, 0]
]

Output: 4

Problem Solving Process

Approach to the Problem

To solve this problem, we will use a dynamic programming approach. Below are the steps to tackle the problem.

1. Create a DP table based on the given binary matrix.
2. Calculate the size of the largest square at each cell.
3. More specifically, while traversing each element of the matrix, if that element is 1, update it to be the minimum value of the element to the right, below, and diagonally below plus one.
4. Calculate and return the area of the largest square found.

Dynamic Programming Table Construction

The size of the DP table will be the same as the input matrix, and the values at each element will be set according to the following rules.

• If it is 0: Set to 0 since no square can be formed at that position.
• If it is 1: Calculate the size of the square by referencing the adjacent values as described above.

Swift Code Implementation

Now let’s implement the approach described above in Swift code.

func maximalSquare(_ matrix: [[Character]]) -> Int {
    guard !matrix.isEmpty else { return 0 }
    let rows = matrix.count
    let cols = matrix[0].count
    var dp = Array(repeating: Array(repeating: 0, count: cols), count: rows)
    var maxSide = 0

    for i in 0..

let testMatrix1: [[Character]] = [
    ["1", "0", "1", "0", "0"],
    ["1", "0", "1", "1", "1"],
    ["1", "1", "1", "1", "1"],
    ["1", "0", "0", "1", "0"]
]

let result1 = maximalSquare(testMatrix1)
print(result1) // 4

let testMatrix2: [[Character]] = [
    ["0", "1"],
    ["1", "0"]
]

let result2 = maximalSquare(testMatrix2)
print(result2) // 1