সমস্যা বিবরণ
একটি ২D গ্রিড দেওয়া আছে যেখানে grid[i][j] হলো (i, j) অবস্থানের বিল্ডিংয়ের উচ্চতা। আমরা যেকোনো বিল্ডিংয়ের উচ্চতা বাড়াতে পারি। কিন্তু চার দিক থেকে (উত্তর, দক্ষিণ, পূর্ব, পশ্চিম) দেখায় স্কায়লাইন (সর্বোচ্চ উচ্চতার আউটলাইন) অপরিবর্তিত থাকতে হবে। বিল্ডিং হাইট বাড়ানোর সর্বোচ্চ মোট যোগফল বের করতে হবে।
উদাহরণ
ইনপুট গ্রিড:
| 3 | 0 | 8 | 4 |
| 2 | 4 | 5 | 7 |
| 9 | 2 | 3 | 6 |
| 0 | 3 | 1 | 0 |
টপ/বটম স্কায়লাইন: [9, 4, 8, 7] (কলাম ভিত্তিক ম্যাক্স)
লেফট/রাইট স্কায়লাইন: [8, 7, 9, 3] (সারি ভিত্তিক ম্যাক্স)
আউটপুট: 35
ফাইনাল গ্রিড (স্কায়লাইন রক্ষা করে):
| 8 | 4 | 8 | 7 |
| 7 | 4 | 7 | 7 |
| 9 | 4 | 8 | 7 |
| 3 | 3 | 3 | 3 |
সমাধানের কৌশল
প্রতিটি সেল (i, j) এর সর্বোচ্চ সম্ভাব্য উচ্চতা হলো min(row_max[i], col_max[j])। কারণ এই সেলটি তার সারি ও কলামের স্কায়লাইন অতিক্রম করতে পারবে না।
অ্যালগরিদম
- প্রতিটি সারির ম্যাক্সimum বের করে
row_maxঅ্যারে বানান - প্রতিটি কলামের ম্যাক্সimum বের করে
col_maxঅ্যারে বানান - প্রতিটি সেল (i, j) এর জন্য:
- নতুন উচ্চতা =
min(row_max[i], col_max[j]) - বৃদ্ধি = নতুন উচ্চতা - পুরনো উচ্চতা
- সর্বমোট বৃদ্ধিতে যোগ করুন
- নতুন উচ্চতা =
পাইথন কোড
class Solution:
def maxIncreaseKeepingSkyline(self, grid):
# সারি ও কলাম ভিত্তিক ম্যাক্সimum বের করুন
row_max = [max(row) for row in grid]
col_max = [max(grid[i][j] for i in range(len(grid)))
for j in range(len(grid[0]))]
total_increase = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
max_allowed = min(row_max[i], col_max[j])
total_increase += max_allowed - grid[i][j]
return total_increase
ob = Solution()
grid = [[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]]
print(ob.maxIncreaseKeepingSkyline(grid)) # আউটপুট: 35
জটিলতা বিশ্লেষণ
- সময় জটিলতা: O(R × C) — R = সারি, C = কলাম
- স্থান জটিলতা: O(R + C) — row_max ও col_max অ্যারে জন্য
মূল বিষয়বস্তু
- স্কায়লাইন = প্রতিটি সারি/কলামের ম্যাক্সimum
- সেলের সর্বোচ্চ উচ্চতা তার সারি ও কলামের ম্যাক্সimum এর মিনিমাম
- গ্রিডি পদ্ধতিতে প্রতিটি সেল স্বতন্ত্রভাবে অপ্টিমাইজ করা যায়
