Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

The encoded string is the row-major representation of a rectangular grid, but the original text was placed along downward-right diagonals starting in the top row. Following those diagonals reconstructs the writing order without allocating the grid.

Approach

Compute columns = encodedLength / rows. For every starting column in the top row, traverse positions (i, start + i) while they remain in bounds, reading each character directly at index i * columns + start + i. Append these characters in diagonal order. Finally remove trailing padding spaces, preserving spaces inside the message and at its beginning. Return the decoded text. The reference code builds it through repeated string concatenation.

class Solution:
    def decodeCiphertext(self, encodedText: str, rows: int) -> str:
        n = len(encodedText)
        cols = n // rows
        res = ''

        for j in range(cols):
            for i in range(rows):
                if i + j >= cols: break
                res += encodedText[i * cols + (j + i)] # grid[i][i + j]
        
        return res.rstrip()

Complexity analysis

Let N = encodedText.length. Traversal and final trimming take O(N) work. Repeated string concatenation has a conservative O(N^2) time bound when growing prefixes are copied; Python and JavaScript runtimes may optimize these appends, so quadratic behavior is not an unconditional runtime claim. Peak storage is O(N), including the decoded result and temporary strings or concatenation nodes; indexing state alone is O(1).