{"id":34942,"date":"2024-11-01T09:33:51","date_gmt":"2024-11-01T09:33:51","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=34942"},"modified":"2024-11-01T12:56:03","modified_gmt":"2024-11-01T12:56:03","slug":"%d0%ba%d0%be%d1%82%d0%bb%d0%b8%d0%bd-%d0%ba%d0%be%d0%b4%d0%b8%d0%bd%d0%b3-%d1%82%d0%b5%d1%81%d1%82-%d0%ba%d1%83%d1%80%d1%81-%d0%bf%d0%be%d0%b8%d1%81%d0%ba-%d0%bd%d0%b0%d0%b8%d0%b1%d0%be%d0%bb%d1%8c","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/34942\/","title":{"rendered":"Kotlin coding test course, finding the largest square"},"content":{"rendered":"
\n

Hello, and welcome to the coding test problem-solving course using Kotlin. In this session, we will solve the problem called “Finding the Largest Square.” The task is to find the area of the largest square in a given 2D array. Through this problem, you will learn the basic concept of Dynamic Programming and understand the syntax and features of the Kotlin language.<\/p>\n

Problem Description<\/h2>\n

There is a given 2D binary array of size m x n. In this array, ‘1’ indicates that a square can be formed at that position, while ‘0’ indicates it cannot. The goal is to find the area of the largest square.<\/p>\n

For example, consider the following array:<\/p>\n

\n    1 0 1 0 0\n    1 0 1 1 1\n    1 1 1 1 1\n    1 0 0 1 0\n    <\/pre>\n
In this case, the area of the largest square is 4. (2×2 square)<\/p>\n
Approach to the Problem<\/h2>\n
To solve this problem, we will use Dynamic Programming. Here are the main steps to solve the problem:<\/p>\n
    \n
  1. Initialize DP Array:<\/strong> Create a DP array with the same size as the input 2D array. Each element in this DP array represents the length of the side of the square ending at position (i, j).<\/li>\n
  2. Set State Transition Relation:<\/strong> If grid[i][j] is ‘1’, then DP[i][j] will be the minimum of DP[i-1][j], DP[i][j-1], and DP[i-1][j-1] + 1. This determines the length of the largest square at (i,j).<\/li>\n
  3. Track Maximum Square Side Length:<\/strong> Through this process, track the side length of the largest square and finally calculate the area by squaring that value.<\/li>\n<\/ol>\n
    Code Implementation<\/h2>\n
    Now let’s implement the above algorithm in Kotlin. Below is the code for the algorithm:<\/p>\n
    \n    fun maximalSquare(matrix: Array): Int {\n        if (matrix.isEmpty()) return 0\n\n        val m = matrix.size\n        val n = matrix[0].size\n        val dp = Array(m) { IntArray(n) }\n        var maxSide = 0\n\n        for (i in 0 until m) {\n            for (j in 0 until n) {\n                if (matrix[i][j] == '1') {\n                    if (i == 0 || j == 0) {\n                        dp[i][j] = 1 \/\/ For the first row or first column\n                    } else {\n                        dp[i][j] = minOf(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1\n                    }\n                    maxSide = maxOf(maxSide, dp[i][j])\n                }\n            }\n        }\n        return maxSide * maxSide \/\/ Return the area of the square\n    }\n    <\/chararray><\/code><\/pre>\n
    Code Explanation<\/h2>\n
    The code takes a 2D array as input and calculates the length of the side of the square ending at each cell. Here is an explanation of the key parts of the code:<\/p>\n