Largest Magic Square | LeetCode 1895 | Medium | Prefix Sum + Brute Force | Daily LeetCode

Описание: In this video, we solve LeetCode 1895: Largest Magic Square.

Code:
https://leetcode.com/problems/largest...

Upsolve Leetcode Contest:
   • Leetcode Contests  

Greedy & Heaps:
   • Greedy & Heaps  

Two pointers:
   • Two pointers  

Sliding Window:
   • Sliding Window  

Maths & Geometry:
   • Maths & Geometry  

Stack:
   • Stack  

Set & Map:
   • Set & Map  

Bit manipulation:
   • Bit Manipulation  

Backtracking:
   • Backtracking  

Linked List:
   • Linked List  

Binary Search:
   • Плейлист  

Graph:
   • Graph  

Dynamic Progamming:
   • Dynamic Programming  

A k × k magic square is a square grid where:
Every row sum is equal
Every column sum is equal
Both diagonal sums are equal
(Note: elements do NOT need to be distinct)

We are given an integer grid and need to find the largest possible size (side length k)
of a magic square that exists inside the grid.

Approach:
Precompute prefix sums for rows and columns to query sums in O(1).
Try all possible square sizes from largest to smallest.
For each k × k subgrid:
Check if all row sums are equal.
Check if all column sums are equal.
Check both diagonal sums.
The first valid square found gives the maximum size.

Prefix sums help reduce repeated sum calculations and keep the solution efficient.

Time Complexity:
O(min(n, m)³)

Space Complexity:
O(n × m)

LeetCode Problem Link:
https://leetcode.com/problems/largest...


#leetcode #leetcode1895 #dailyleetcode #largestmagicsquare
#prefixsum #matrixproblems #2darray
#mediumleetcode #geometry #math
#dsa #datastructures #algorithms
#competitiveprogramming #codinginterview
#faang #google #amazon #microsoft #meta
#javacoding #java #problem_solving
#placementprep #studyplacement #csfundamentals