נגדיר: מטריצה ממוינת (Sorted Matrix) היא מטריצה (מערך דו-ממדי) מלאה במספרים שלמים, שבה במעבר על המטריצה החל בשורה העליונה ועד לשורה התחתונה, ובכל שורה במעבר משמאל לימין, הערכים במטריצה יהיו ממוינים בסדר עולה ממש מהקטן לגדול. שימו לב שבכל שורה, האיבר האחרון בה קטן ממש מהאיבר הראשון בשורה הבאה. כמו כן, כל המספרים במטריצה שונים זה מזה.
נגדיר: מטריצה כמעט ממוינת (almost sorted) כמטריצה ממוינת, אלא שתא אחד בלבד במטריצה לא נמצא במקומו הנכון.
לדוגמא, אם היינו משנים את התא שבשורה 1 עמודה 3 כך שיהיה בו הערך 68, המטריצה הייתה כמעט ממוינת.
בהינתן מטריצה כמעט ממוינת כמתואר לעיל. יש לתקן את המטריצה כך שתהיה מטריצה ממוינת. התיקון המבוקש הוא לתקן את מיקומי האיברים במטריצה מבלי לשנות את הערכים השמורים בה.
דוגמאות: מצד ימין המטריצה לפני הקריאה לשיטה, ומצד שמאל שמאל לאחריה.
| 0 | 1 | 2 | 3 | 4 | |
| 0 | 3 | 5 | 7 | 12 | 18 |
| 1 | 23 | 31 | 44 | 68 | 56 |
| 2 | 61 | 68 | 72 | 89 | 90 |
השיטה שתכתבו צריכה להיות רקורסיבית ללא שימוש בלולאות כלל. כך גם כל שיטות העזר שתכתבו (אם תכתבו) לא יכולות להכיל לולאות.
null.mat = [[3, 5, 7, 12, 18], [23, 31, 44, 68, 56], [61, 67, 72, 89, 90]]
[3, 5, 7, 12, 18] [23, 31, 44, 56, 61] [67, 68, 72, 89, 90]
הסבר: הערך 68 בשורה 1 עמודה 3 היה במקום הלא נכון (במקום להיות בשורה 2 עמודה 1). לאחר התיקון, כל האיברים שביניהם (56, 61, 67) הוזזו במקום אחד, ו-68 עבר למקומו הנכון.
mat = [[3, 5, 7, 12, 18], [23, 31, 44, 4, 56], [61, 67, 72, 89, 90]]
[3, 4, 5, 7, 12] [18, 23, 31, 44, 56] [61, 67, 72, 89, 90]
הסבר: הערך 4 בשורה 1 עמודה 3 היה במקום הלא נכון (במקום להיות בשורה 0 עמודה 1). לאחר התיקון, כל האיברים שביניהם (5, 7, 12, 18, 23, 31, 44) הוזזו במקום אחד, ו-4 עבר למקומו הנכון.
mat = [[1, 2, 4, 3]]
[1, 2, 3, 4]
הסבר: מקרה פשוט: הערכים 4 ו-3 החליפו מקום, ודי בהחלפה בודדת אחת כדי לתקן.
mat = [[10, 50, 20, 30, 40]]
[10, 20, 30, 40, 50]
הסבר: הערך 50 הוזז למקום השני (אינדקס 1), וכל שאר האיברים זזו ימינה. לאחר התיקון המערך חוזר להיות ממוין.
mat = [[4, 1], [2, 3]]
[1, 2] [3, 4]
הסבר: הערך הגדול ביותר (4) הונח בתחילת המטריצה. לאחר התיקון, הוא עובר לסוף וכל השאר נדחפים צעד אחד אחורה.
mat = [[2, 3, 4], [5, 6, 7], [8, 9, 1]]
[1, 2, 3] [4, 5, 6] [7, 8, 9]
הסבר: הערך הקטן ביותר (1) הושם בסוף המטריצה. תיקונו דורש להעבירו לתחילת המטריצה ולהזיז את שאר האיברים.
mat = [[10], [40], [20], [30]]
[10] [20] [30] [40]
הסבר: מטריצת עמודה שבה הערך 40 ממוקם שלא במקומו (בשורה 1 במקום בשורה 3).
mat = [[10, 20, 40], [50, 30, 60]]
[10, 20, 30] [40, 50, 60]
הסבר: הערך 30 'ברח' לשורה השנייה. לאחר תיקון הוא חוזר לשורה הראשונה ודוחף את 40 ו-50 למקומם החדש.
קלט:
mat = [[3, 5, 7, 12, 18], [23, 31, 44, 68, 56], [61, 67, 72, 89, 90]]
הפלט המבוקש:
[3, 5, 7, 12, 18] [23, 31, 44, 56, 61] [67, 68, 72, 89, 90]