Tasks Details
hard
Find a maximal value path in a matrix, starting in the top-left corner and ending in the bottom-right corner.
Task Score
77%
Correctness
100%
Performance
33%
You are given a matrix A consisting of N rows and M columns, where each cell contains a digit. Your task is to find a continuous sequence of neighbouring cells, starting in the top-left corner and ending in the bottom-right corner (going only down and right), that creates the biggest possible integer by concatenation of digits on the path. By neighbouring cells we mean cells that have exactly one common side.
Write a function:
class Solution { public String solution(int[][] A); }
that, given matrix A consisting of N rows and M columns, returns a string which represents the sequence of cells that we should pick to obtain the biggest possible integer.
For example, given the following matrix A:
![[9 9 7]
[9 7 2]
[6 9 5]
[9 1 2]](https://codility-frontend-prod.s3.amazonaws.com/media/task_static/max_path_from_the_left_top_corner/static/images/auto/e4106284e1483f9fce9c30d5310fecd4.png)
the function should return "997952", because you can obtain such a sequence by choosing a path as shown below:
![[9 9 *]
[* 7 *]
[* 9 5]
[* * 2]](https://codility-frontend-prod.s3.amazonaws.com/media/task_static/max_path_from_the_left_top_corner/static/images/auto/a924dca3559786b2be62f6bf86341f4d.png)
Write an efficient algorithm for the following assumptions:
- N and M are integers within the range [1..1,000];
- each element of matrix A is an integer within the range [1..9].
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used Java 21
Time spent on task 1 minutes
Notes
not defined yet
Code: 20:50:47 UTC,
java,
autosave
Code: 20:50:59 UTC,
java,
verify,
result: Passed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
import java.util.*;
class Solution {
public static String solution(int[][] A) {
String re = Integer.toString(A[0][0]);
int temp=0;
ArrayList<Integer> xxx = new ArrayList<Integer>();
ArrayList<Integer> yyy = new ArrayList<Integer>();
xxx.add(0); yyy.add(0);
for(int i=1;i<A.length+A[0].length-1;i++) {
// Tao 2 mang phu de luu toa do
ArrayList<Integer> mmm = new ArrayList<Integer>();
ArrayList<Integer> nnn = new ArrayList<Integer>();
temp=0;
//int temp=Math.min(i,A.length-1);
for(int j=0; j<xxx.size(); j++) {
if(yyy.get(j)+1< A[0].length) {
if(A[xxx.get(j)][yyy.get(j)+1] > temp) {
mmm.clear();
nnn.clear();
temp=A[xxx.get(j)][yyy.get(j)+1];
mmm.add(xxx.get(j));
nnn.add(yyy.get(j)+1);
}
else if(A[xxx.get(j)][yyy.get(j)+1] == temp) {
mmm.add(xxx.get(j));
nnn.add(yyy.get(j)+1);
}
}
if(xxx.get(j)+1< A.length) {
int leng = mmm.size();
if(leng>0) if(xxx.get(j)+1 == mmm.get(leng-1) && yyy.get(j) == nnn.get(leng-1)) continue;
if(A[xxx.get(j)+1][yyy.get(j)] > temp) {
mmm.clear();
nnn.clear();
temp=A[xxx.get(j)+1][yyy.get(j)];
mmm.add(xxx.get(j)+1);
nnn.add(yyy.get(j));
}
else if(A[xxx.get(j)+1][yyy.get(j)] == temp) {
mmm.add(xxx.get(j)+1);
nnn.add(yyy.get(j));
}
}
}
/*while(temp>=0 && i-temp<A[0].length) {
if(A[temp][i-temp] > max[i] && (xxx.contains(temp) || yyy.contains(i-temp))) {
mmm.clear();
nnn.clear();
max[i]=A[temp][i-temp];
mmm.add(temp);
nnn.add(i-temp);
}
else if(A[temp][i-temp] == max[i] && (xxx.contains(temp) || yyy.contains(i-temp))) {
mmm.add(temp);
nnn.add(i-temp);
}
temp--;
} */
copyList(xxx, mmm);
copyList(yyy, nnn);
re+=Integer.toString(temp);
}
return re;
}
public static int Lonnhat(int a, int[][] A) {
int temp=Math.min(a,A.length-1);
int re = A[temp][a-temp];
System.out.println(temp + " " + (a-temp));
while(temp>=0 && a-temp<A[0].length) {
if(A[temp][a-temp] > re) re=A[temp][a-temp];
temp--;
}
return re;
}
public static void copyList(java.util.List dest , java.util.List source) {
dest.clear();
for( int i = 0 ; i < source.size() ; i++ ) {
dest.add( source.get( i ));
}
}
}
Analysis
Code: 20:51:07 UTC,
java,
verify,
result: Passed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
import java.util.*;
class Solution {
public static String solution(int[][] A) {
String re = Integer.toString(A[0][0]);
int temp=0;
ArrayList<Integer> xxx = new ArrayList<Integer>();
ArrayList<Integer> yyy = new ArrayList<Integer>();
xxx.add(0); yyy.add(0);
for(int i=1;i<A.length+A[0].length-1;i++) {
// Tao 2 mang phu de luu toa do
ArrayList<Integer> mmm = new ArrayList<Integer>();
ArrayList<Integer> nnn = new ArrayList<Integer>();
temp=0;
//int temp=Math.min(i,A.length-1);
for(int j=0; j<xxx.size(); j++) {
if(yyy.get(j)+1< A[0].length) {
if(A[xxx.get(j)][yyy.get(j)+1] > temp) {
mmm.clear();
nnn.clear();
temp=A[xxx.get(j)][yyy.get(j)+1];
mmm.add(xxx.get(j));
nnn.add(yyy.get(j)+1);
}
else if(A[xxx.get(j)][yyy.get(j)+1] == temp) {
mmm.add(xxx.get(j));
nnn.add(yyy.get(j)+1);
}
}
if(xxx.get(j)+1< A.length) {
int leng = mmm.size();
if(leng>0) if(xxx.get(j)+1 == mmm.get(leng-1) && yyy.get(j) == nnn.get(leng-1)) continue;
if(A[xxx.get(j)+1][yyy.get(j)] > temp) {
mmm.clear();
nnn.clear();
temp=A[xxx.get(j)+1][yyy.get(j)];
mmm.add(xxx.get(j)+1);
nnn.add(yyy.get(j));
}
else if(A[xxx.get(j)+1][yyy.get(j)] == temp) {
mmm.add(xxx.get(j)+1);
nnn.add(yyy.get(j));
}
}
}
/*while(temp>=0 && i-temp<A[0].length) {
if(A[temp][i-temp] > max[i] && (xxx.contains(temp) || yyy.contains(i-temp))) {
mmm.clear();
nnn.clear();
max[i]=A[temp][i-temp];
mmm.add(temp);
nnn.add(i-temp);
}
else if(A[temp][i-temp] == max[i] && (xxx.contains(temp) || yyy.contains(i-temp))) {
mmm.add(temp);
nnn.add(i-temp);
}
temp--;
} */
copyList(xxx, mmm);
copyList(yyy, nnn);
re+=Integer.toString(temp);
}
return re;
}
public static int Lonnhat(int a, int[][] A) {
int temp=Math.min(a,A.length-1);
int re = A[temp][a-temp];
System.out.println(temp + " " + (a-temp));
while(temp>=0 && a-temp<A[0].length) {
if(A[temp][a-temp] > re) re=A[temp][a-temp];
temp--;
}
return re;
}
public static void copyList(java.util.List dest , java.util.List source) {
dest.clear();
for( int i = 0 ; i < source.size() ; i++ ) {
dest.add( source.get( i ));
}
}
}
Analysis
Code: 20:51:11 UTC,
java,
final,
score:
77
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
import java.util.*;
class Solution {
public static String solution(int[][] A) {
String re = Integer.toString(A[0][0]);
int temp=0;
ArrayList<Integer> xxx = new ArrayList<Integer>();
ArrayList<Integer> yyy = new ArrayList<Integer>();
xxx.add(0); yyy.add(0);
for(int i=1;i<A.length+A[0].length-1;i++) {
// Tao 2 mang phu de luu toa do
ArrayList<Integer> mmm = new ArrayList<Integer>();
ArrayList<Integer> nnn = new ArrayList<Integer>();
temp=0;
//int temp=Math.min(i,A.length-1);
for(int j=0; j<xxx.size(); j++) {
if(yyy.get(j)+1< A[0].length) {
if(A[xxx.get(j)][yyy.get(j)+1] > temp) {
mmm.clear();
nnn.clear();
temp=A[xxx.get(j)][yyy.get(j)+1];
mmm.add(xxx.get(j));
nnn.add(yyy.get(j)+1);
}
else if(A[xxx.get(j)][yyy.get(j)+1] == temp) {
mmm.add(xxx.get(j));
nnn.add(yyy.get(j)+1);
}
}
if(xxx.get(j)+1< A.length) {
int leng = mmm.size();
if(leng>0) if(xxx.get(j)+1 == mmm.get(leng-1) && yyy.get(j) == nnn.get(leng-1)) continue;
if(A[xxx.get(j)+1][yyy.get(j)] > temp) {
mmm.clear();
nnn.clear();
temp=A[xxx.get(j)+1][yyy.get(j)];
mmm.add(xxx.get(j)+1);
nnn.add(yyy.get(j));
}
else if(A[xxx.get(j)+1][yyy.get(j)] == temp) {
mmm.add(xxx.get(j)+1);
nnn.add(yyy.get(j));
}
}
}
/*while(temp>=0 && i-temp<A[0].length) {
if(A[temp][i-temp] > max[i] && (xxx.contains(temp) || yyy.contains(i-temp))) {
mmm.clear();
nnn.clear();
max[i]=A[temp][i-temp];
mmm.add(temp);
nnn.add(i-temp);
}
else if(A[temp][i-temp] == max[i] && (xxx.contains(temp) || yyy.contains(i-temp))) {
mmm.add(temp);
nnn.add(i-temp);
}
temp--;
} */
copyList(xxx, mmm);
copyList(yyy, nnn);
re+=Integer.toString(temp);
}
return re;
}
public static int Lonnhat(int a, int[][] A) {
int temp=Math.min(a,A.length-1);
int re = A[temp][a-temp];
System.out.println(temp + " " + (a-temp));
while(temp>=0 && a-temp<A[0].length) {
if(A[temp][a-temp] > re) re=A[temp][a-temp];
temp--;
}
return re;
}
public static void copyList(java.util.List dest , java.util.List source) {
dest.clear();
for( int i = 0 ; i < source.size() ; i++ ) {
dest.add( source.get( i ));
}
}
}Analysis summary
The following issues have been detected: timeout errors.
Analysis
Detected time complexity:
O(2**(N+M)) or O(N*M*(N+M))
expand all
Correctness tests
1.
0.004 s
OK
2.
0.004 s
OK
3.
0.008 s
OK
1.
0.004 s
OK
2.
0.008 s
OK
3.
0.008 s
OK
1.
0.008 s
OK
2.
0.008 s
OK
3.
0.004 s
OK
1.
0.008 s
OK
2.
0.008 s
OK
3.
0.004 s
OK
1.
0.016 s
OK
2.
0.008 s
OK
3.
0.684 s
OK
1.
0.008 s
OK
2.
0.016 s
OK
expand all
Performance tests
1.
0.008 s
OK
2.
0.008 s
OK
3.
0.008 s
OK
1.
15.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 15.000 sec.
2.
0.024 s
OK
3.
0.180 s
OK
1.
6.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 6.000 sec.
2.
15.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 15.000 sec.
3.
12.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 12.000 sec.