Direction Array: reducing complexity

Question

I have an m*n matrix where every element is unique. From a given starting point I have to move to the smallest point in a relative direction (e.g. up, down, left, right) and then have to repeat the process again. When all other surrounding points have a value that is greater than the existing one I have to stop and print the position from start. Suppose I have a 5x5 matrix:

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

and starting point is (2,2) then the output will be 13,8,3,2,1. I have solved this problem my way, but the problem is its complexity. I do not think my solution is efficient. Can anyone suggest to me a better solution?

N.B: Except scanner pkg, I am not allowed to import any other pkg. Here is my code:

import java.util.Arrays;
import java.util.Scanner;
public class DirectionArray {
public static void main(String [] args) {
 Scanner in = new Scanner(System.in);
 int row = in.nextInt();
 int col = in.nextInt();
 int[][] ara = new int[row][col];
 int[] ara2 = new int[4];
 for (int i = 0; i < row; i++) {
 for (int j = 0; j < col; j++) {
 ara[i][j] = in.nextInt();
 }
 }
 System.out.println("Give starting point(x) ");
 int x= in.nextInt();
 System.out.println("Give starting point(y) ");
 int y= in.nextInt();
 int sx=x;
 int sy =y;
 int [] fx={+1,-1,0,0};
 int [] fy={0,0,+1,-1};
 int p=0;
 int l=0;
 int v=0;
 int r=0;
 int [] result=new int[row*col] ;
 int min=ara[x][y];
 boolean swap=true;
 for(int i=0;i<(row*col)-1;i++) {
 for (int k = 0; k < 4; k++) {
 int nx = x + fx[k];
 int ny = y + fy[k];
 if (nx >= 0 && nx < row && ny >= 0 && ny < col) {
 if (min > ara[nx][ny]) {
 ara2[p] = ara[nx][ny];
 p++;
 // x = nx;
 //y = ny;
 }
 }
 }
 p=0;
 while(swap) {
 swap=false;
 r++;
 for (int q = 0; q < ara2.length-r; q++) {
 if(ara2[q]>ara2[q+1]){
 int temp = ara2[q];
 ara2[q]=ara2[q+1];
 ara2[q+1]=temp;
 swap=true;
 }
 }
 }
 // Arrays.sort(ara2);
 for(int j=0;j<ara2.length;j++) {
 if(ara2[j]!=0)
 {
 v=ara2[j];
 result[l]=v;
 l++;
 break;
 }
 }
 // System.out.println(v);
 min=v;
 for(int o=0;o<ara2.length;o++) {
 ara2[o]=0;
 }
 for(int m=0;m<row;m++){
 for(int n=0;n<col;n++){
 if(ara[m][n]==v) {
 x = m;
 y = n;
 }
 }
 }
 }
 System.out.print(ara[sx][sy]+" ");
 for(int i=0;i<result.length;i++) {
 if(result[i]!=0) {
 System.out.print(result[i] + " ");
 }
 if(result[i]==0) {
 break;
 }
 }
 }
}

• Timothy Truckle: Welcome to CodeReview.SE! What is your definition of "efficient"?

Answer 1

Thanks for sharing your code!

Naming

Finding good names is the hardest part in programming, so always take your time to think about the names of your identifiers.

avoid single character names

Since the number of characters is quite limited in most languages you will soon run out of names. This means that you either have to choose another character which is not so obviously connected to the purpose of the variable. And/or you have to "reuse" variable names in different contexts. Both makes your code hard to read and understand for other persons. (keep in mind that you are that other person yourself if you look at your code in a few month!)

On the other hand in Java the length of identifier names is virtually unlimited. There is no penalty in any way for long identifier names. So don't be stingy with letters when choosing names.

avoid abbreviations

In your code you use some abbreviations such as the variable ara. Although this abbreviation makes sense to you (now) anyone reading your code being not familiar with the problem (like me) has a hard time finding out what this means.

If you do this to save typing work: remember that you way more often read your code than actually typing something. Also for Java you have good IDE support with code completion so that you most likely type a long identifier only once and later on select it from the IDEs code completion proposals.

OOP

Your code is a procedural approach to the problem.

There is nothing wrong with procedural approaches in general, but Java is an object oriented (OO) programming language and if you want to become a good Java programmer then you should start solving problems in an OO way.

But OOP doesn't mean to "split up" code into random classes.

The ultimate goal of OOP is to reduce code duplication, improve readability and support reuse as well as extending the code.

Doing OOP means that you follow certain principles which are (among others):

• information hiding / encapsulation
• single responsibility / separation of concerns
• same level of abstraction
• KISS (Keep it simple (and) stupid.)
• DRY (Don't repeat yourself.)
• "Tell! Don't ask."
• Law of Demeter ("Don't talk to strangers!")

---

Here is a OO-ish approach to the problem.

The idea is that a "cell" (a position in an the array) "knows" its neighbors. This the solution does not need to iterate over the whole array multiple times. My approach need to visit only 4 cells per iteration. This I have 90% less compares to do compared to your procedural approach. The ratio gets better the bigger the array gets...

I introduced two custom classes:

• a Cell class that does the actual search logic recursively.
• a StartPosition class as a Data Transfer Object (DTO) which is needed to enable a method to return both, x and y coordinate of the starting point.

I ignored your restriction to only use Scanner as the only allowed import because it is somewhat overstated.

import java.io.PrintStream; // implicit dependency from System.out.
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.Scanner;
public class DirectionArray {
 class Cell {
 private final int value;
 private final TreeSet<Cell> neighborsSortedByValue = new TreeSet<>((c1, c2) -> c1.value - c2.value);
 public Cell(int value) {
 this.value = value;
 }
 public void addNeighbor(Cell neighbor) {
 neighborsSortedByValue.add(neighbor);
 }
 public void findSink(Collection<Cell> pathToSink) {
 pathToSink.add(this);
 Cell minNeighbor = neighborsSortedByValue.first();
 if (minNeighbor.value < this.value)
 // recursive call if lesser value neighbor exists
 minNeighbor.findSink(pathToSink);
 }
 @Override
 public String toString() {
 return value + " ";
 }
 }
 class StartPosition {
 private int x;
 private int y;
 }
 public static void main(String[] args) {
 Scanner in = new Scanner(System.in);
 PrintStream out = System.out;
 new DirectionArray().runToSink(in, out);
 }
 void runToSink(Scanner in, PrintStream out) {
 Cell[][] cellArray = readArray(in);
 setNeighbors(cellArray);
 StartPosition startPosition = askForStartPosition(in, out);
 Collection<Cell> pathToSink = new ArrayList<>();
 cellArray[startPosition.x][startPosition.y].findSink(pathToSink);
 print(pathToSink, out);
 }
 private Cell[][] readArray(Scanner in) {
 int row = in.nextInt();
 int col = in.nextInt();
 Cell[][] cellArray = new Cell[row][col];
 for (int i = 0; i < row; i++) {
 for (int j = 0; j < col; j++) {
 cellArray[i][j] = new Cell(in.nextInt());
 }
 }
 return cellArray;
 }
 private void setNeighbors(Cell[][] cellArray) {
 for (int i = 0; i < cellArray.length; i++) {
 for (int j = 0; j < cellArray[i].length; j++) {
 setNeighborsToCell(i, j, cellArray);
 }
 }
 }
 private void setNeighborsToCell(int i, int j, Cell[][] cellArray) {
 for (int x : new int[] { -1, 1 }) { // one force, one back
 // neighbors in column
 cellArray[i][j].addNeighbor(cellArray[calculateNeighborIndex(i, x, cellArray.length)][j]);
 // neighbors in row
 cellArray[i][j].addNeighbor(cellArray[i][calculateNeighborIndex(j, cellArray[i].length, x)]);
 }
 }
 private int calculateNeighborIndex(int i, int x, int length) {
 return (length + i + x) % length;
 }
 private StartPosition askForStartPosition(Scanner in, PrintStream out) {
 StartPosition startPosition = new StartPosition();
 out.println("Give starting point(x) ");
 startPosition.x = in.nextInt();
 out.println("Give starting point(y) ");
 startPosition.y = in.nextInt();
 return startPosition;
 }
 private void print(Collection<Cell> pathToSink, PrintStream out) {
 for (Cell pathStep : pathToSink) {
 out.print(pathStep);
 }
 }
}

Finally I created a test driver a class that runs the solution with your test data. This test class is run by the JUnit framework:

import static org.hamcrest.CoreMatchers.endsWith;
import static org.junit.Assert.*;
import java.io.ByteArrayInputStream;
import java.io.ByteArrayOutputStream;
import java.io.PrintStream;
import java.util.Scanner;
import org.junit.Test;
public class DirectionArrayTest {
 @Test
 public void test() {
 Scanner scanner = new Scanner(new ByteArrayInputStream(
 ("5 5\n" + // array dimensions
 "1 2 3 4 5\n" + 
 "6 7 8 9 10\n" + 
 "11 12 13 14 15\n" + 
 "16 17 18 19 20\n" + 
 "21 22 23 24 25\n" +
 "2 2\n" // start position index
 ).getBytes()));
 
 ByteArrayOutputStream byteArrayOutputStream = new ByteArrayOutputStream();
 PrintStream out = new PrintStream(byteArrayOutputStream);
 
 new DirectionArray().runToSink(scanner, out);
 System.out.println(byteArrayOutputStream.toString());
 assertThat(byteArrayOutputStream.toString(), endsWith("13 8 3 1 "));
 }
}

• Yonex: Thanks for your nice suggestions. Next time I will keep it in mind.