टीएल;डीआर
- समस्या: डेटा संरचनाओं और एल्गोरिदम के लिए समय और स्थान जटिलता (टाइम एंड स्पेस कॉम्प्लेक्सिटी) का अनुकूलन।
- दृष्टिकोण: बिना दूसरी मैट्रिक्स के NxN मैट्रिक्स को ९० डिग्री क्लॉकवाइज घुमाएँ। जावा में परत-दर-परत ४-वे स्वैप, टेक्स्ट डायग्राम और इंटरव्यू के एज केस।
- जटिलता: सीमांत मामलों (एज केसेस) के प्रबंधन के साथ इष्टतम समय और मेमोरी संतुलन।
कल्पना कीजिए: मेज पर एक चौकोर फोटो पड़ी है। आप उसे लैंडस्केप मोड में सीधा देखना चाहते हैं, इसलिए पूरी प्रिंट को ९० डिग्री क्लॉकवाइज घुमा देते हैं। हर कोना नए कोने पर जाता है। बीच का हिस्सा बीच में ही रहता है। आप दूसरी फोटो खरीदकर पिक्सेल कॉपी नहीं करते। वही शीट पलटते हैं।
यही समस्या है: एक N गुणा N मैट्रिक्स को ९० डिग्री in place घुमाना। पूरी दूसरी मैट्रिक्स नहीं।
यह सीटीसीआई-शैली सीरीज़ का अध्याय १, समस्या १.७ है। सीरीज़ का नक्शा: जावा में Cracking the Coding Interview। टैग: एल्गोरिदम।
समस्या सादे शब्दों में
इनपुट: आकार N x N की वर्गाकार मैट्रिक्स matrix। हर सेल में कोई मान (हर सेल को एक पिक्सेल समझें)।
आउटपुट: वही मैट्रिक्स ऑब्जेक्ट, मान ऐसे व्यवस्थित कि छवि ९० डिग्री क्लॉकवाइज घूम चुकी हो।
महत्वपूर्ण बाधा: in place करें। लक्ष्य अतिरिक्त O(१) मेमोरी (कुछ temp), कोई N x N कॉपी नहीं।
क्लॉकवाइज का मतलब:
- ऊपरी पंक्ति दाईं कॉलम बन जाती है।
- दाईं कॉलम निचली पंक्ति बन जाती है (पुराने top के क्रम के अनुसार)।
- और इसी तरह पूरे वर्ग के चारों ओर।
काउंटरक्लॉकवाइज वही विचार है, चक्र उल्टा। इंटरव्यू में लगभग हमेशा क्लॉकवाइज होता है जब तक न कहा जाए। संदेह हो तो एक बार पूछ लें।
छोटा उदाहरण जो हाथ से बना सकें
N = ४ से शुरू करें। अक्षरों से गति साफ दिखती है:
पहले: 90 deg क्लॉकवाइज बाद:
A B C D M I E A
E F G H N J F B
I J K L O K G C
M N O P P L H D
एक कोना जाँचें: A ऊपर-बाएँ था। घुमाने के बाद A ऊपर-दाएँ है। D नीचे-दाएँ गया। P नीचे-बाएँ। M ऊपर-बाएँ।
भीतरी सेल: F (१,१) पर था। घुमाने के बाद (१,२) पर है जहाँ G था। बीच का २x२ भी अपने वर्ग की तरह घूमता है।
कोड से पहले कैसे सोचें
ब्रूट फोर्स (आसान, पर in place नहीं)
नई मैट्रिक्स out बनाएँ, आकार N x N।
हर सेल (r, c) के लिए:
out[c][N - 1 - r] = matrix[r][c]
क्यों? पंक्ति कॉलम बन जाती है। पुराना पंक्ति इंडेक्स तय करता है कि आप दाएँ किनारे से कितनी दूर उतरते हैं।
(r, c) --> (c, N - 1 - r)
ऊपर के ४x४ पर उदाहरण:
| से | तक | अक्षर |
|---|---|---|
| (०,०) | (०,३) | A |
| (०,३) | (३,३) | D |
| (३,०) | (०,०) | M |
| (१,२) | (२,२) | G |
सही है, समय O(N²)। स्थान O(N²)। इंटरव्यू में पूछेंगे: क्या दूसरी मैट्रिक्स बचा सकते हैं?
बेहतर विचार: एक साथ चार सेल घुमाएँ
एक सेल को नए घर में बिना किसी को ओवरराइट किए नहीं ले जा सकते। इसलिए एक सेल temp में बचाएँ, फिर चार का चक्र चलाएँ:
top --> right --> bottom --> left --> top
परत के किनारे की हर स्थिति पर ऐसा करें, फिर अंदर जाएँ।
परतें (प्याज के छल्ले)
N x N मैट्रिक्स नेस्टेड रिंग होती है:
परत 0: बाहरी रिंग (पंक्ति/कॉलम 0 और N-1)
परत 1: अगली रिंग (पंक्ति/कॉलम 1 और N-2)
...
कितनी परतें? N / 2 (पूर्णांक भाग)। N = ४ पर २ परतें। N = ५ पर २ रिंग और एक केंद्र सेल जो नहीं हिलती।
N = 5, परतें = 2
* * * * * बाहरी परत
* + + + * भीतरी परत
* + o + * o केंद्र है, रहता है
* + + + *
* * * * *
एक परत, कदम दर कदम
N x N मैट्रिक्स की परत layer पर ध्यान दें।
first = layer
last = N - 1 - layer
उस रिंग पर offset i को 0 से last - first - 1 तक चलाएँ (उस कोने से पहले रुकें जिसे अगला offset पहले से कवर करता है; हर ४-चक्र साइड का एक "स्लॉट" संभालता है)।
हर offset i के लिए:
// चक्र में स्थितियाँ (क्लॉकवाइज गंतव्य मानचित्र)
top = matrix[first][first + i]
right = matrix[first + i][last]
bottom = matrix[last][last - i]
left = matrix[last - i][first]
क्लॉकवाइज घुमाव का मतलब: हर मान वहाँ जाता है जहाँ पिछली साइड का मान जाता था:
temp = top
top <- left // बाईं साइड ऊपर top पर
left <- bottom // bottom बाईं ओर
bottom <- right // right नीचे
right <- temp // पुराना top दाईं ओर
इंडेक्स रूप में (बोर्ड पर लिखें):
temp = matrix[first][first + i]
matrix[first][first + i] = matrix[last - i][first] // top <- left
matrix[last - i][first] = matrix[last][last - i] // left <- bottom
matrix[last][last - i] = matrix[first + i][last] // bottom <- right
matrix[first + i][last] = temp // right <- old top
बाहरी रिंग पर एक offset (N = ४, layer ०, i = ०)
पहले (केवल बाहरी कोने):
A B C D
E . . H
I . . L
M N O P
चक्र: A (top) , D (right) , P (bottom) , M (left)
इस चक्र के बाद:
M B C A
E . . H
I . . L
P N O D
फिर i = 1 साइड के अगले चार (B, H, O, I) घुमाता है, जब तक बाहरी रिंग खत्म न हो। फिर layer = 1 अंदर का २x२ घुमाता है।
वैकल्पिक दूसरा मॉडल: ट्रांसपोज़ फिर हर पंक्ति उलटें
दूसरा सही तरीका:
१. ट्रांसपोज़: c > r के लिए matrix[r][c] और matrix[c][r] बदलें।
२. हर पंक्ति उलटें।
A B C D ट्रांसपोज़ A E I M पंक्तियाँ उलटें M I E A
E F G H ----------> B F J N --------------> N J F B
I J K L C G K O O K G C
M N O P D H L P P L H D
वही परिणाम। परत-दर-परत क्लासिक "in place रिंग" कहानी है; ट्रांसपोज़ + रिवर्स दबाव में अक्सर टाइप करना आसान है। दोनों जानें। एक साफ कोड करें।
जावा समाधान (परत दर परत)
/**
* N x N मैट्रिक्स को 90 डिग्री क्लॉकवाइज in place घुमाता है।
* null या गैर-वर्ग पर false; सफलता पर true।
*/
public final class RotateMatrix {
private RotateMatrix() {}
public static boolean rotate(int[][] matrix) {
if (matrix == null || matrix.length == 0) {
return false;
}
int n = matrix.length;
for (int[] row : matrix) {
if (row == null || row.length != n) {
return false; // वर्ग नहीं
}
}
// बाहर से अंदर हर परत
for (int layer = 0; layer < n / 2; layer++) {
int first = layer;
int last = n - 1 - layer;
for (int i = first; i < last; i++) {
int offset = i - first;
// top बचाएँ
int top = matrix[first][first + offset];
// left -> top
matrix[first][first + offset] = matrix[last - offset][first];
// bottom -> left
matrix[last - offset][first] = matrix[last][last - offset];
// right -> bottom
matrix[last][last - offset] = matrix[first + offset][last];
// top -> right
matrix[first + offset][last] = top;
}
}
return true;
}
}
ट्रांसपोज़ + पंक्ति रिवर्स वाली वही लॉजिक
public static void rotateViaTranspose(int[][] matrix) {
int n = matrix.length;
// ट्रांसपोज़
for (int r = 0; r < n; r++) {
for (int c = r + 1; c < n; c++) {
int tmp = matrix[r][c];
matrix[r][c] = matrix[c][r];
matrix[c][r] = tmp;
}
}
// हर पंक्ति उलटें
for (int r = 0; r < n; r++) {
for (int c = 0; c < n / 2; c++) {
int tmp = matrix[r][c];
matrix[r][c] = matrix[r][n - 1 - c];
matrix[r][n - 1 - c] = tmp;
}
}
}
दोनों in place हैं। एक चुनें और दूसरा एक वाक्य में समझाने को तैयार रहें।
जटिलता
| तरीका | समय | अतिरिक्त स्थान |
|---|---|---|
| नई मैट्रिक्स में कॉपी | O(N²) | O(N²) |
| परत-दर-परत ४-चक्र | O(N²) | O(१) |
| ट्रांसपोज़ + पंक्ति रिवर्स | O(N²) | O(१) |
हर सेल को एक बार (या नियत बार) छूना पड़ता है, इसलिए घनी मैट्रिक्स के लिए O(N²) समय इष्टतम है।
एज केस जो इंटरव्यूअर छेड़ते हैं
| स्थिति | क्या होना चाहिए |
|---|---|
N = 0 या null |
No-op या अस्वीकार; क्रैश नहीं |
N = 1 |
एक सेल; पहले से "घुमी" |
N = 2 |
एक परत, प्रति साइड एक offset (चार कोने) |
विषम N |
केंद्र सेल नहीं हिलती; फिर भी N/2 परतें |
| वर्ग नहीं | व्यवहार तय करें; असली छवियाँ MxN हो सकती हैं, पर यह समस्या NxN है |
| ऑब्जेक्ट / बड़े struct मान | वही इंडेक्स गणित; केवल temp का प्रकार बदलता है |
दिशा भी स्पष्ट करें: क्लॉकवाइज बनाम काउंटरक्लॉकवाइज। काउंटरक्लॉकवाइज के लिए ४-चक्र के असाइनमेंट का क्रम उलटा करें (या ट्रांसपोज़ फिर कॉलम उलटें)।
त्वरित स्व-जाँच (N = ३)
1 2 3 CW घुमाएँ 7 4 1
4 5 6 ---------> 8 5 2
7 8 9 9 6 3
केवल परत ० (N/2 = 1)। बाहरी रिंग पर offset:
१. चक्र 1, 3, 9, 7 → 7 ऊपर-बाएँ, 1 ऊपर-दाएँ, 3 नीचे-दाएँ, 9 नीचे-बाएँ।
२. चक्र 2, 6, 8, 4 → साइड पूरे।
३. केंद्र 5 रहता है।
अगर कोड यही प्रिंट करे, इंडेक्स सही हैं।
दोस्त को समझाएँ
आपके पास पिक्सेल का चौकोर ग्रिड है। आप दूसरी पूरी ग्रिड बनाए बिना इसे ९० डिग्री क्लॉकवाइज घुमाना चाहते हैं।
इसे प्याज जैसा समझें। हर रिंग पर एक साइड पर चलें। हर स्थिति पर चार सेल जगह बदलते हैं: top, right, bottom, left। एक को temp में बचाएँ ताकि खो न जाए, बाकी तीन लिखें, temp को आखिरी खाली जगह में रखें। रिंग खत्म, अंदर आएँ, बीच तक दोहराएँ।
समय सेल की संख्या के समानुपाती है। अतिरिक्त मेमोरी लगभग एक अस्थायी सेल। यही पूरा ट्रिक है।
आगे अभ्यास
- दोनों संस्करण याद से लिखें (परत चक्र, फिर ट्रांसपोज़ + रिवर्स)।
- समस्या काउंटरक्लॉकवाइज करें और केवल चक्र बदलें।
- अतिरिक्त: M x N छवि घुमाना (नया बफ़र या अलग प्रतिनिधित्व चाहिए; गैर-वर्ग के लिए शुद्ध in place अलग पहेली है)।
सीरीज़ होम: जावा सीटीसीआई गाइड। प्लान में अगली ऐरे समस्या: Zero Matrix।