₦airaland Forum

This challenge is based on working with 2-dimensional arrays (or matrix). I've met a number of professional Java developers who simply failed this task and I've met at least one student who successfully completed it.

It isn't an easy task but I think it is a real of test one's ability to think as a programmer should.


BACKGROUND CONTEXT

A zero-indexed matrix A consisting of N rows and M columns of integers is given. It can be decomposed into two sets, called upper spiral and lower spiral. The decomposition proceeds as follows:

· remove the top row of the matrix and assign its elements to the upper spiral;

· if a non-empty matrix is left, remove the bottom row of the matrix and assign its elements to the lower spiral;

· if a non-empty matrix is left, rotate it counter-clockwise (so that the rightmost column becomes the top row) and repeat.

For example, consider matrix A consisting of 7 rows and 8 columns:

5  3  8  9  4  1  3 -2
4  6  0  3  6  4  2  1
4 -5  3  1  9  5  6  6
3  7  5  3  2  8  9  4
5  3 -3  6  3  2  8  0
5  7  5  3  3 -9  2  2
0  4  3  2  5  7  5  4

It can be decomposed into the following upper spiral:

5  3  8  9  4  1  3 -2
                     1
  -5  3  1  9  5     6
   7     3  2  8     4
   3                 0
   7  5  3  3 -9  2  2

and the following lower spiral:

4  6  0  3  6  4  2
4                 6
3     5           9
5    -3  6  3  2  8
5
0  4  3  2  5  7  5  4

THE CHALLENGE

Write a function:

class Solution { 
        public int solution(int[][] A) {
           // your code in here!
        }

}

that, given a zero-indexed matrix A consisting of N rows and M columns of integers, returns the sum of the elements that belong to the upper spiral of matrix A. The function should return −1 if the sum does not lie within the range [−100,000,000..100,000,000].

Assume that:

· N and M are integers within the range [1..1,000,000];

· the number of elements in matrix A is within the range [1..99,999,999];

· each element of matrix A is an integer within the range [−2,147,483,648..2,147,483,647].

For example, given matrix A consisting of 7 rows and 8 columns corresponding to the example above (i.e. A[0][0] = 5, A[0][1] = 3, A[0][2] = 8, A[1][0] = 4, A[2][0] = 4 etc.), the function should return 91, because

5 + 3 + 8 + 9 + 4 + 1 + 3 + (−2)
+ 1 + 6 + 4 + 0 + 2
+ 2 + (−9) + 3 + 3 + 5 + 7
+ 3 + 7 + (−5)
+ 3 + 1 + 9 + 5
+ 8
+ 2 + 3
= 91.


I have competed this task myself and I'll be posting my own solution in a few days time.

No attempts yet.

Java heads where are you?

I haven't attempted the algorithm for this challenge but on close observation at the 3 matrices, I couldn't identify any counter clockwise rotation whatsoever. What I see is a systematic elimination of the matrix elements and a subsequent rebuilding of new matrices from the original matrix. Let's assume the first matrix is called A and the second and third matrices are called B and C respectively , if we also assume the vacant elements in B and C are given values of zero then its clear that. A = B + C. I cannot observe any real positional rotation of the elements. I am very open to correction or some eye opening pointers, I will take another hard look then post some code . Thanks. I typed this on a mobile phone and cannot understand why my formatting disappeared, wonder if someone can give me a clue.

@bluetrails

You're absolutely right. You will need to recreate the matrices to achieve the effect of a counter-clockwise rotation.

Just use hashmaps tree maps and u could solve this easily..

Mr. OP, what you posted here isn't really a Java problem but a programing algorithm challenge. It can be done in virtually any language or even a pseudocode or flowchart will do.

ikp4succes:
Just use hashmaps tree maps and u could solve this easily..

Please go ahead Sir and show how you would solve it by posting your solution.

Sibrah:
Mr. OP, what you posted here isn't really a Java problem but a programing algorithm challenge. It can be done in virtually any language or even a pseudocode or flowchart will do.

Ok. The solution I have done is in Java. But if you want to attempt it using a different language then by all means go ahead. I would be interested to see a solution posted in C# or in any other language.