Least counts to traverse all elements serial wise from given square grid

By Ann Roberts On Jan 19, 2023

Given a square matrix [][] of size N * N, containing elements from 1 to N * N. You have to traverse all the elements from 1 to N*N serial-wise, Formally starting from element 1 then 2, 3, and so on.. till N*N, the task is to return the minimum number of steps for traversing all the elements serial wise, If you can only go one step left, right, up, or down from the current position.

Examples:

Input: N = 1, matrix[][] = {{1}}
Output: 0
Explanation: The Matrix is of 1*1 dimension having only one element in it. We are at element 1 in starting then no further element is there for traversing. Therefore, the output is 0.

Input: N = 3, Matrix:{ {1, 7, 9}, {2, 4, 8}, {3, 6, 5}}
Output: 12
Explanation: Let us define the cells of Matrix as 1-based indexing then the steps are as follows:

First Element = 1 at cell (1, 1), current = (1, 1), Total Steps = 0

Second Element = 2, Traverse from current to (2, 1), Total Steps = 1, current = (2, 1)

Third Element = 3, Traverse from current to (3, 1), total steps = 2, current = (3, 1)

Fourth Element = 4, Traverse from current to (2, 1) then (2, 2), Total Steps = 4, current = (2, 2)

Fifth Element = 5, Traverse from current to (2, 3) then (3, 3), Total Steps = 6, current = (3, 3)

Sixth Element = 6, Traverse from current to (3, 2), Total Steps = 7, current = (3, 2)

Seventh Element = 7, Traverse from current to (2, 2) then (1, 2), Total Steps = 9, current = (1, 2)

Eighth Element = 8, Traverse from current to (2, 2) then (3, 2), Total Steps = 11, current = (2, 3)

Ninth Element = 9, Traverse from current to (1, 3), Total Steps = 12, current = (1, 3)

It can be verified that elements from 1 to 9 are traversed in 12 steps, Which are the minimum possible steps.

Approach: Implement the below idea to solve the problem:

The problem is observation based and can be solved by using some observation such that traversal can be done in the minimum number of operations. The problem can be used by making two temporary arrays.

Steps were taken to solve the problem:

Create two temp arrays X[] and Y[] of size N * N + 1.
Traverse on the Matrix using nested loops from i=0 to less than N and j=0 to less than N and follow the below-mentioned steps under the scope of the loop:
- Initialize temp variable equal to Matrix[i][j]
- initialize X[temp] = i
- initialize Y[temp] = j
Create two variables prevX and prevY and initialize them equal to X[1] and Y[1] respectively.
Create a variable Steps = 0.
Run a loop from i = 2 to less than X.length and follow the below-mentioned steps under the scope of loop:
- steps += Math.abs(prevX – x[i]) + Math.abs(prevY – y[i])
- prevX = x[i]
- prevY = y[i]
Print value of Steps.

Code to implement the approach:

Java

import java.io.*;

import java.util.*;

class Main {

public static void main(String args[])

{

int n = 3;

int[][] matrix

= { { 1, 7, 9 }, { 2, 4, 8 }, { 3, 6, 5 } };

Minimum_steps(n, matrix);

}

static void Minimum_steps(int n, int[][] matrix)

{

int[] x = new int[n * n + 1];

int[] y = new int[n * n + 1];

for (int i = 0; i < n; i++) {

for (int j = 0; j < n; j++) {

int temp = matrix[i][j];

x[temp] = i;

y[temp] = j;

}

int prevX = x[1];

int prevY = y[1];

int steps = 0;

for (int i = 2; i < x.length; i++) {

steps += Math.abs(prevX - x[i])

+ Math.abs(prevY - y[i]);

prevX = x[i];

prevY = y[i];

}

System.out.println(steps);

}

Time Complexity: O(N²)
Auxiliary Space: O(N)