ZigZag Conversion — Day 71(Python)

Photo by Raphaël Biscaldi on Unsplash

Today’s question is based on Strings. This question is commonly asked among Paypal’s interviewers. This question is a medium tagged question Leetcode.

6. ZigZag Conversion

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P   A   H   N

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string s, int numRows);

Example 1:

Input: s = "PAYPALISHIRING", numRows = 3

Example 2:

Input: s = "PAYPALISHIRING", numRows = 4

Example 3:

Input: s = "A", numRows = 1
Output: "A"


  • 1 <= s.length <= 1000
  • s consists of English letters (lower-case and upper-case), ',' and '.'.
  • 1 <= numRows <= 1000

One way to solve this problem is to create a list of the required sizes and then fill each cell with the letters from the input string.

What would the dimensions of this list be? If we look at the example, we realize, the length of the list is already is given to us.

Let us take an example and solve,


We create a list of size 3

Next, we will place each letter in the string into this list until we reach the end of the list.

Once we reach the end of the list, we need to change the direction in which we append the characters in the list. Earlier, we were moving from Up to Down, now, we will reverse the direction from Down to Up.

We will again reverse the direction once we reach the 0th index in the list.

Continue until we have hit all the characters in the string.

In the end, we join all the elements in the list and return it.

To keep track of directions, we can have a flag that will tell us, when we should be moving from Up to Down or when to use a reverse direction.

Let us look into the code snippet.

class Solution:
def convert(self, s: str, numRows: int) -> str:
if(numRows < 2):
return s
arr = ['' for i in range(numRows)]
direction = 'down'
row = 0
for i in s:
arr[row] += i
if row == numRows-1:
direction = 'up'
elif row == 0:
direction = 'down'
if(direction == 'down'):
row += 1
row -= 1

One of the edge cases to remember is when the number of input rows is less than 2. In such cases, we return the string as it is.

Complexity analysis.

Time Complexity

We are visiting each character in the string. Hence the time complexity is O(N), where N is the number of characters.

Space Complexity.

We create a list of size the number of rows. Hence the space complexity is O(r), where r is the number of rows.




Software Engineer. Find me @ www.linkedin.com/in/annamariya-jt

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Practical Inversion of Control in TypeScript with a Functional Twist

November 2018 Po.et Engineering Progress Report

How to Connect an Android Phone to a Docker Container ?

Doing the rounds- A quick guide to creating a modular waypoint system in unity

Getting to Know Pytest: A Simple and Effective Testing Tool

CS373 Spring 2022: Nathan Whyte

Spectrum Management in Autonomous Wireless Networks

Use Flask and SQLalchemy, not Flask-SQLAlchemy!

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Annamariya Tharayil

Annamariya Tharayil

Software Engineer. Find me @ www.linkedin.com/in/annamariya-jt

More from Medium

How to Print Alphabet P in Python?

Coding improves problem solving

Number of Good Pairs — Day 101(Python)

Python’s .sort() vs sorted()