समस्या
एक run सीधी रेखा में लगातार k खाने (cells) होते हैं: किसी पंक्ति में बाएँ से दाएँ, किसी स्तंभ में ऊपर से नीचे, या दोनों में से किसी भी विकर्ण पर। हर run की संख्याओं को आपस में गुणा कीजिए और वह run खोजिए जिसका गुणनफल सबसे बड़ा हो।
largest_product_in_grid(grid, k) लिखिए।
इनपुट
grid: संख्याओं का आयताकार ग्रिड; हर पंक्ति की लंबाई बराबर है।
k: run की लंबाई।
आउटपुट
लंबाई k वाले सभी runs में सबसे बड़ा गुणनफल लौटाइए। अगर किसी भी दिशा में लंबाई k का कोई run ग्रिड में न समाए तो 0 लौटाइए।
सीमाएँ
1 ≤ पंक्तियाँ, स्तंभ ≤ 20; 0 ≤ grid[r][c] ≤ 99; 1 ≤ k ≤ 5
उदाहरण
इनपुट:
grid = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]
k = 2
अपेक्षित आउटपुट:
expected = 72
इनपुट:
std::vector<std::vector<long long>> grid = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
long long k = 2;
अपेक्षित आउटपुट:
long long expected = 72;
इनपुट:
long[][] grid = new long[][] {
new long[] {1, 2, 3},
new long[] {4, 5, 6},
new long[] {7, 8, 9}
};
long k = 2;
अपेक्षित आउटपुट:
long expected = 72;
व्याख्या
सबसे अच्छा run नीचे की पंक्ति में 8 और 9 है: 8 × 9 = 72। विकर्ण 5, 9 से सिर्फ़ 45 मिलता है।
इनपुट:
grid = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]
k = 3
अपेक्षित आउटपुट:
expected = 504
इनपुट:
std::vector<std::vector<long long>> grid = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
long long k = 3;
अपेक्षित आउटपुट:
long long expected = 504;
इनपुट:
long[][] grid = new long[][] {
new long[] {1, 2, 3},
new long[] {4, 5, 6},
new long[] {7, 8, 9}
};
long k = 3;
अपेक्षित आउटपुट:
long expected = 504;
व्याख्या
नीचे की पंक्ति से 7 × 8 × 9 = 504 मिलता है, जो दाएँ स्तंभ के 3 × 6 × 9 = 162 या किसी भी विकर्ण से बड़ा है।
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
चार दिशाएँ काफ़ी हैं: दाएँ, नीचे, नीचे-दाएँ और नीचे-बाएँ। बाकी दिशाएँ यही runs उलटे क्रम में दोहराती हैं।
संकेत 2
हर शुरुआती खाने से जाँचिए कि run का आख़िरी खाना अब भी ग्रिड के अंदर है।
संकेत 3
0 सिर्फ़ तब लौटाइए जब लंबाई k का कोई भी run न समाए।
अपेक्षित जटिलता
समय O(rows × cols × k), अतिरिक्त स्थान O(1)
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।