Print string in the zigzag form in `k` rows

Given a string and a positive integer k, print the string in k rows in the zigzag form.

For example,

Zig Zag – 3 rows

Zig Zag – 4 rows

Practice this problem

The idea is to identify a pattern in the problem. If we consider a character’s index in the output, we have observed some patterns:

The first key of each row, i, is present at index i in the string.
For the first and the last row, the distance between each key is (k-1)×2. For example, for k = 4, the difference is 6. So, the first element of the first row is located at index 0; the second element is located at index 6; the third element at 12, and so on… Similarly, the first element of the last row is located at index 3; the second element is located at index 9, the third element at 15, and so on…
For all middle rows, depending upon whether we are going up or going down, the index differs, as evident from the following code:

Zig Zag – 4 rows

The algorithm can be implemented as follows in C++, Java, and Python:

C++

#include <iostream>

#include <string>

using namespace std;

// Function to print given string in the zigzag form in `k` rows

void printZigZag(string str, int k)

{

// base case

if (k == 0) {

return;

}

// base case

if (k == 1)

{

cout << str;

return;

}

// print first row

for (int i = 0; i < str.length(); i += (k-1)*2) {

cout << str[i];

}

// print middle rows

for (int j = 1; j < k - 1; j++)

{

bool down = true;

for (int i = j; i < str.length();)

{

cout << str[i];

if (down) { // going down

i += (k-j-1)*2;

}

else { // going up

i += (k-1)*2 - (k-j-1)*2;

}

down = !down; // switch direction

}

// print last row

for (int i = k - 1; i < str.length(); i += (k-1)*2) {

cout << str[i];

}

int main()

{

string str = "THISPROBLEMISAWESOME";

int k = 4;

printZigZag(str, k);

return 0;

}

Download Run Code

Output:

TOSMHRBIAOEIPLMWSSEE

Java

class Main

{

// Function to print given string in the zigzag form in `k` rows

public static void printZigZag(String str, int k)

{

// base case

if (str == null || k == 0) {

return;

}

// base case

if (k == 1)

{

System.out.print(str);

return;

}

// print first row

for (int i = 0; i < str.length(); i += (k-1)*2) {

System.out.print(str.charAt(i));

}

// print middle rows

for (int j = 1; j < k - 1; j++)

{

boolean down = true;

for (int i = j; i < str.length();)

{

System.out.print(str.charAt(i));

if (down) { // going down

i += (k - j - 1) * 2;

}

else { // going up

i += (k - 1) * 2 - (k - j - 1) * 2;

}

down = !down; // switch direction

}

// print last row

for (int i = k - 1; i < str.length(); i += (k - 1) * 2) {

System.out.print(str.charAt(i));

}

public static void main(String[] args)

{

String str = "THISPROBLEMISAWESOME";

int k = 4;

printZigZag(str, k);

}

Download Run Code

Output:

TOSMHRBIAOEIPLMWSSEE

Python

# Function to print given string in the zigzag form in `k` rows

def printZigZag(s, k):

# base case

if k == 0:

return

# base case

if k == 1:

print(s, end='')

return

# print first row

for i in range(0, len(s), (k - 1) * 2):

print(s[i], end='')

# print middle rows

for j in range(1, k - 1):

down = True

i = j

while i < len(s):

print(s[i], end='')

if down: # going down

i += (k - j - 1) * 2

else: # going up

i += (k - 1) * 2 - (k - j - 1) * 2

down = not down # switch direction

# print last row

for i in range(k - 1, len(s), (k - 1) * 2):

print(s[i], end='')

if __name__ == '__main__':

s = 'THISPROBLEMISAWESOME'

k = 4

printZigZag(s, k)

Download Run Code

Output:

TOSMHRBIAOEIPLMWSSEE

The time complexity of the above solution is O(n), where n is the length of the input string and doesn’t require any extra space.

Print string in the zigzag form in `k` rows

C++

Java

Python

Share this: