Test results - Codility

Tasks Details

hard

1. MaxPathFromTheLeftTopCorner

Find a maximal value path in a matrix, starting in the top-left corner and ending in the bottom-right corner.

100%

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]

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]

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].

Solution

Programming language used Java 8

Total time used 1 minutes

Effective time used 1 minutes

Notes

not defined yet

Task timeline

Code: 09:31:09 UTC, java, verify, result: Passed

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69

import java.util.*;

class Solution {
	class Position {
		int n;
		int m;

		Position(int n, int m) {
			this.n = n;
			this.m = m;
		}
	}

	public String solution(int[][] A) {
		int N = A.length;
		int M = A[0].length;
		int Max = Math.max(N, M);

		ArrayList<Position> P0 = new ArrayList<Position>(Max);
		ArrayList<Position> P1 = new ArrayList<Position>(Max);
		P0.add(new Position(0, 0));

		String R = "" + A[0][0];
		while (!(P0.size() == 1 && (P0.get(0).m == M - 1 || P0.get(0).n == N - 1))) {

			int biggestNumber = 0;
			for (Position p : P0) {
				if (p.n < N - 1) {
					int p1 = A[p.n + 1][p.m];
					if (p1 > biggestNumber) {
						biggestNumber = p1;
						P1.clear();
						P1.add(new Position(p.n + 1, p.m));
						A[p.n + 1][p.m] = 0;
					} else if (p1 == biggestNumber) {
						P1.add(new Position(p.n + 1, p.m));
						A[p.n + 1][p.m] = 0;
					}
				}
				if (p.m < M - 1) {
					int p1 = A[p.n][p.m + 1];
					if (p1 > biggestNumber) {
						biggestNumber = p1;
						P1.clear();
						P1.add(new Position(p.n, p.m + 1));
						A[p.n][p.m + 1] = 0;
					} else if (p1 == biggestNumber) {
						P1.add(new Position(p.n, p.m + 1));
						A[p.n][p.m + 1] = 0;
					}
				}
			}
			R += biggestNumber;

			ArrayList<Position> t = P0;
			P0 = P1;
			P1 = t;
			P1.clear();
		}
		Position p = P0.get(0);
		if (p.m == M - 1)
			for (int i = p.n + 1; i < N; i++)
				R += A[i][p.m];
		else if (p.n == N - 1)
			for (int i = p.m + 1; i < M; i++)
				R += A[p.n][i];
		return R;
	}
}

Analysis

▶

example
example test

✔

Code: 09:31:15 UTC, java, verify, result: Passed

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69

import java.util.*;

class Solution {
	class Position {
		int n;
		int m;

		Position(int n, int m) {
			this.n = n;
			this.m = m;
		}
	}

	public String solution(int[][] A) {
		int N = A.length;
		int M = A[0].length;
		int Max = Math.max(N, M);

		ArrayList<Position> P0 = new ArrayList<Position>(Max);
		ArrayList<Position> P1 = new ArrayList<Position>(Max);
		P0.add(new Position(0, 0));

		String R = "" + A[0][0];
		while (!(P0.size() == 1 && (P0.get(0).m == M - 1 || P0.get(0).n == N - 1))) {

			int biggestNumber = 0;
			for (Position p : P0) {
				if (p.n < N - 1) {
					int p1 = A[p.n + 1][p.m];
					if (p1 > biggestNumber) {
						biggestNumber = p1;
						P1.clear();
						P1.add(new Position(p.n + 1, p.m));
						A[p.n + 1][p.m] = 0;
					} else if (p1 == biggestNumber) {
						P1.add(new Position(p.n + 1, p.m));
						A[p.n + 1][p.m] = 0;
					}
				}
				if (p.m < M - 1) {
					int p1 = A[p.n][p.m + 1];
					if (p1 > biggestNumber) {
						biggestNumber = p1;
						P1.clear();
						P1.add(new Position(p.n, p.m + 1));
						A[p.n][p.m + 1] = 0;
					} else if (p1 == biggestNumber) {
						P1.add(new Position(p.n, p.m + 1));
						A[p.n][p.m + 1] = 0;
					}
				}
			}
			R += biggestNumber;

			ArrayList<Position> t = P0;
			P0 = P1;
			P1 = t;
			P1.clear();
		}
		Position p = P0.get(0);
		if (p.m == M - 1)
			for (int i = p.n + 1; i < N; i++)
				R += A[i][p.m];
		else if (p.n == N - 1)
			for (int i = p.m + 1; i < M; i++)
				R += A[p.n][i];
		return R;
	}
}

Analysis

▶

example
example test

✔

Code: 09:31:21 UTC, java, final, score: 100

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69

import java.util.*;

class Solution {
	class Position {
		int n;
		int m;

		Position(int n, int m) {
			this.n = n;
			this.m = m;
		}
	}

	public String solution(int[][] A) {
		int N = A.length;
		int M = A[0].length;
		int Max = Math.max(N, M);

		ArrayList<Position> P0 = new ArrayList<Position>(Max);
		ArrayList<Position> P1 = new ArrayList<Position>(Max);
		P0.add(new Position(0, 0));

		String R = "" + A[0][0];
		while (!(P0.size() == 1 && (P0.get(0).m == M - 1 || P0.get(0).n == N - 1))) {

			int biggestNumber = 0;
			for (Position p : P0) {
				if (p.n < N - 1) {
					int p1 = A[p.n + 1][p.m];
					if (p1 > biggestNumber) {
						biggestNumber = p1;
						P1.clear();
						P1.add(new Position(p.n + 1, p.m));
						A[p.n + 1][p.m] = 0;
					} else if (p1 == biggestNumber) {
						P1.add(new Position(p.n + 1, p.m));
						A[p.n + 1][p.m] = 0;
					}
				}
				if (p.m < M - 1) {
					int p1 = A[p.n][p.m + 1];
					if (p1 > biggestNumber) {
						biggestNumber = p1;
						P1.clear();
						P1.add(new Position(p.n, p.m + 1));
						A[p.n][p.m + 1] = 0;
					} else if (p1 == biggestNumber) {
						P1.add(new Position(p.n, p.m + 1));
						A[p.n][p.m + 1] = 0;
					}
				}
			}
			R += biggestNumber;

			ArrayList<Position> t = P0;
			P0 = P1;
			P1 = t;
			P1.clear();
		}
		Position p = P0.get(0);
		if (p.m == M - 1)
			for (int i = p.n + 1; i < N; i++)
				R += A[i][p.m];
		else if (p.n == N - 1)
			for (int i = p.m + 1; i < M; i++)
				R += A[p.n][i];
		return R;
	}
}

Analysis summary

The solution obtained perfect score.

Analysis

Detected time complexity:

O(N*M) or O(N*M*log(N+M))

▶

example
example test

✔

▶

simple
simple tests with N <= 3 and M <= 3

✔

▶

small_array
tests with N = 1 and M = 1

✔

▶

one_row
tests with N = 1

✔

▶

one_column
tests with M = 1

✔

▶

same_values
all elements from the matrix have the same value

✔

▶

same_values_except_one
all elements except one are the same

✔

▶

random_small_tests
small random tests

✔

▶

big_values
all elements are either 8 or 9

✔

▶

big_matrix_size

✔