Print the matrix in a spiral format

Printing the matrix in spiral format is a common array question that is asked in the onsite interviews. It is a square matrix that one traverses in following directions: 

1. Left to right
2. Top to bottom
3. Bottom to Top
4. Right to Left

If a specific element is outputted then it won't be outputted. Here is a sample:

Input:    1  2  3  4  5  6  7  8  9  10  11  12  13  14  15 16

Output: 1  2 3  4 8 12  16 15 14  13 9 5 6 7  11 10

Here is the algorithm along with a dry run: 

Algorithm :

Step 1: Declare and initialize a 4x4 matrix(2D array) “a” with the given values 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16.  

Matrix a,

1	2	3	4
5	6	7	8
9	10	11	12
13	14	15	16

Step 2: Declare and initialize a variable “n” with the value 4 (length of 2D array(matrix)). n = 4

 Step 3: Declare and initialize required variables to track rows and columns while printing the matrix in spiral form. row = 0 col = 0 row_now = 0 col_now = 0 Step 4: Using while loop to iterate the matrix in spiral form by repeating the next six steps till the condition fails. Step 5: Assign present row and column values to the variables. row = row_now col = col_now Step 6: Moving to the right -> print the first row from the remaining rows. Step 7: Moving down -> print the last column from the remaining columns. Step 8: Moving to the left -> print the last row from the remaining rows. Step 9: Moving up -> print the first column from the remaining columns. Step 10: For the next iteration decrement the length of matrix and increment the present row and column values.

Iteration 1: (step 4)

n = 4

(4-1) != 1

3 != 1  -> condition true

Present row and col : (step 5)

row = 0

col = 0

Right : (step 6)

IF, 0==0 and 0==0   -> condition true

Iteration 1.1 :

0 != 3  -> condition true

Print a[0][0] = 1

1	2	3	4
5	6	7	8
9	10	11	12
13	14	15	16

Output : 1

col=1 (incremented by 1)

Iteration 1.2 :

1 != 3  -> condition true

Print a[0][1] = 2

1	2	3	4
5	6	7	8
9	10	11	12
13	14	15	16

Output : 1 2

col=2 (incremented by 1)

Iteration 1.3 :

2 != 3  -> condition true

Print a[0][2] = 3

1	2	3	4
5	6	7	8
9	10	11	12
13	14	15	16

Output : 1 2 3

col=3 (incremented by 1)

Iteration 1.4 :

3 != 3  -> condition false.

Terminate the inner loop for right.

Down : (step 7)

IF, 3==3 and 0==0   -> condition true

Iteration 1.1 :

0 != 3  -> condition true

Print a[0][3] = 4

1	2	3	4
5	6	7	8
9	10	11	12
13	14	15	16

Output : 1 2 3 4

row=1 (incremented by 1)

Iteration 1.2 :

1 != 3  -> condition true

Print a[1][3] = 8

1	2	3	4
5	6	7	8
9	10	11	12
13	14	15	16

Output : 1 2 3 4 8

row=2 (incremented by 1)

Iteration 1.3 :

2 != 3  -> condition true

Print a[2][3] = 12

1	2	3	4
5	6	7	8
9	10	11	12
13	14	15	16

Output : 1 2 3 4 8 12

row=3 (incremented by 1)

Iteration 1.4 :

3 != 3  -> condition false.

Terminate the inner loop for down.

Left : (step 8)

IF, 3==3 and 3==3   -> condition true

Iteration 1.1 :

3 != 0  -> condition true

Print a[3][3] = 16

1	2	3	4
5	6	7	8
9	10	11	12
13	14	15	16

Output : 1 2 3 4 8 12 16

col=2 (decremented by 1)

Iteration 1.2 :

2 != 0  -> condition true

Print a[3][2] = 15

1	2	3	4
5	6	7	8
9	10	11	12
13	14	15	16

Output : 1 2 3 4 8 12 16 15

col=1 (decremented by 1)

Iteration 1.3 :

1 != 0  -> condition true

Print a[3][1] = 14

1	2	3	4
5	6	7	8
9	10	11	12
13	14	15	16

Output : 1 2 3 4 8 12 16 15 14

col=0 (decremented by 1)

Iteration 1.4 :

0 != 0  -> condition false.

Terminate the inner loop for left.

Up : (step 9)

IF, 0==0 and 3==3   -> condition true

Iteration 1.1 :

3 != 0  -> condition true

Print a[3][0] = 13

1	2	3	4
5	6	7	8
9	10	11	12
13	14	15	16

Output : 1 2 3 4 8 12 16 15 14 13 

row=2 (decremented by 1)

Iteration 1.2 :

2 != 0  -> condition true

Print a[2][0] = 9

1	2	3	4
5	6	7	8
9	10	11	12
13	14	15	16

Output : 1 2 3 4 8 12 16 15 14 13 9 

row=1 (decremented by 1)

Iteration 1.3 :

1 != 0  -> condition true

Print a[1][0] = 5

1	2	3	4
5	6	7	8
9	10	11	12
13	14	15	16

Output : 1 2 3 4 8 12 16 15 14 13 9 5 

row=0 (decremented by 1)

Iteration 1.4 :

0 != 0  -> condition false.

Terminate the inner loop for up.

n = 3 (decremented by 1) (step 10)

row_now = 1 (incremented by 1)

col_now = 1 (incremented by 1)

Iteration 2 :

n = 3

(3-1) != 1

2 != 1  -> condition true

Present row and col :

row = 1

col = 1

Right  :

IF, 1==1 and 1==1   -> condition true

Iteration 2.1 :

1 != 2  -> condition true

Print a[1][1] = 6

1	2	3	4
5	6	7	8
9	10	11	12
13	14	15	16

Output : 1 2 3 4 8 12 16 15 14 13 9 5 6

col=2 (incremented by 1)

Iteration 2.2 :

2 != 2  -> condition false.

Terminate the inner loop for right.

Down :

IF, 1==1 and 1==1   -> condition true

Iteration 2.1 :

1 != 2  -> condition true

Print a[1][2] = 7

1	2	3	4
5	6	7	8
9	10	11	12
13	14	15	16

Output : 1 2 3 4 8 12 16 15 14 13 9 5 6 7

row=2 (incremented by 1)

Iteration 2.2 :

2 != 2  -> condition false.

Terminate the inner loop for down.

Left  :

IF, 2==2 and 2==2   -> condition true

Iteration 2.1 :

2 != 0  -> condition true

Print a[2][2] = 11

1	2	3	4
5	6	7	8
9	10	11	12
13	14	15	16

Output : 1 2 3 4 8 12 16 1 5 14 13 9 5 6 7 11

col=1 (decremented by 1)

Iteration 2.2 :

1 != 0  -> condition true.

Print a[2][1] = 10

1	2	3	4
5	6	7	8
9	10	11	12
13	14	15	16

Output : 1 2 3 4 8 12 16 1 5 14 13 9 5 6 7 11 10

col=0 (decremented by 1)

Iteration 2.3 :

0 != 0  -> condition false.

Terminate the inner loop for left.

Up :

IF, 0==1 and 2==2   -> condition false.

Terminate the inner loop for up.

n=2 (decremented by 1)

row_now = 2

col_now = 2

Iteration 3: 

(n-1) != 1

(2-1) != 1

    1 != 1   -> Condition false

Terminate the outer loop.

Implementation: 

#include <iostream>

#include <conio.h>

#include <stdio.h>

using namespace std;

int main()

{

int a[4][4] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16};

int n = 4;

//Initializations

int row_now = 0,row = 0;

int col_now = 0,col = 0;

while(n-1 != 1)

{

row = row_now;

col = col_now;

//Moving to the right

if(row == row_now && col == col_now)

while(col!=n-1)

cout<<a[row][col++]<<" ";

//Moving down

if(col==n-1 && row == row_now)

while(row!=n-1)

cout<<a[row++][col]<<" ";

//Moving left

if(col == n-1 && row == n-1)

while(col!=0)

cout<<a[row][col--]<<" ";

//Moving up

if(col == col_now && row == n-1)

while(row!=0)

cout<<a[row--][col]<<" ";

//Getting ready for the next iteration

n--;

row_now++;

col_now++;

}

getch();

return 0;

}

Output :

1  2 3  4 8 12  16 15 14  13 9 5 6 7  11 10

Algorithm complexity :

O(m*n) m = row and n = column

Find a character in the string

Background:

Background: Finding a character in the string is a very simple algorithm that could be asked in a phone interview or during initial coding rounds. Its a O(n) algo that will look for a character in the string and output it as soon as it finds it. For ex:

1. In string ‘Programming’, if we search for character r then it should return 1.
2. Similarly if we search for character ‘z’ in string ‘Programming’ then it should return null.

This algorithm will find out a character in the string. If string is ‘Programming’, and if you want to find the character r. Then this algorithm will if the character r exists in the string. If you want to find out character ‘z’ then it will return ‘String not found’ since it is not present in the inputted string.

Algorithm:

1. Find the length of the string and store it in len variable.
2. Create a count variable, and initialize to 0.
3. Compare character at each location start from count=0.
4. Increment the count till len and keep comparing its character to inputted character.
5. If character matches then break the loop.

So let's look at the steps now: 

Algorithm :

Step 1: Declare a character array ‘s’ and initialize it with the given string value “Programming”. char s[ ] = “programming”; 

  0     1 2     3 4 5       6 7 8 9     10

‘p’

‘r’

‘o’

‘g’

‘r’

‘a’

‘m’

‘m’

‘i’

‘n’

‘g’

Step 2 : Declare a character variable ‘c’ and initialize it with the individual character to be searched for. char c = ‘g’

Step 3: Declare and initialize a count variable with the value 0(zero). int count = 0 Step 4: Find the length of the given string using strlen() method and assign the length value to the ‘len’ integer variable. strlen(s) = 11 int len = 11; Step 5: Using while loop, iterate through the character array to find whether the given individual character is present or not. If the character is matched, then print the count value otherwise increment the count value. Iteration 1: count = 0, len = 11 0 != 11 -> Condition true

  0     1 2      3 4 5      6 7 8 9      10

‘p’

‘r’

‘o’

‘g’

‘r’

‘a’

‘m’

‘m’

‘i’

‘n’

‘g’

IF : c = ‘g’, s[0] = ‘p’

‘g’ == ‘p’   -> Condition false

ELSE : 

count = 1 (incremented by one)

Iteration 2:

count = 1, len = 11

1 != 11   -> Condition true

  0     1 2      3 4 5      6 7 8 9      10

‘p’

‘r’

‘o’

‘g’

‘r’

‘a’

‘m’

‘m’

‘i’

‘n’

‘g’

IF : c = ‘g’, s[1] = ‘r’

‘g’ == ‘r’   -> Condition false

ELSE : 

count = 2 (incremented by one)

Iteration 3:

count = 2, len = 11

2 != 11   -> Condition true

  0     1 2      3 4 5      6 7 8 9      10

‘p’

‘r’

‘o’

‘g’

‘r’

‘a’

‘m’

‘m’

‘i’

‘n’

‘g’

IF : c = ‘g’, s[2] = ‘o’

‘g’ == ‘o’   -> Condition false

ELSE : 

count = 3 (incremented by one)

Iteration 4:

count = 3, len = 11

3 != 11   -> Condition true

  0     1 2      3 4 5      6 7 8 9      10

‘p’

‘r’

‘o’

‘g’

‘r’

‘a’

‘m’

‘m’

‘i’

‘n’

‘g’

IF : c = ‘g’, s[3] = ‘g’

‘g’ == ‘g’   -> Condition true

Then,

Print the count value to console 3.

Enters the break statement, So terminate the loop.

Step 6: If the count reaches the end of string then print “Character not found” otherwise print “Character found”. Count = 3, len = 11 IF: 3 == 11 -> Condition false ELSE: Print “Character found” to the console.

Implementation:

#include <iostream>

#include <cstring>

using namespace std;

int main()

{

char s[] = "Programming";

char c;

c = 'g';

int count = 0;

int len = strlen(s);

while(count!=len)

{

if(c == s[count])

{

std::cout<<count<<std::endl;

break;

}

else

count++;

}

if(count==len){

std::cout<<"Character not found"<<std::endl;

}

else {

std::cout<<"Character found"<<std::endl;

}

return 0;

}

Output :

Character found at Location: 3

Algorithm Complexity :

O(n)