Decode the Slanted Ciphertext solution and explanation
Google
9 more videos on this problem
Decode the Slanted Ciphertext | Detailed Intuition | 2 Approaches | Leetcode 2075 | codestorywithMIKcodestorywithMIK · 24:10 · 6K views
2075. Decode the Slanted Ciphertext (Leetcode Medium)Programming Live with Larry · 11:19 · 696 views
2075. Decode the Slanted Ciphertext | Leetcode Daily - PythonLeetcode Daily · 5:32 · 332 views
2075. Decode the Slanted CiphertextBreakTheCode · 20:42 · 288 views
Decode the Slanted Ciphertext | LeetCode 2075 - Pythonimpoldev · 7:03 · 192 views
Decode the Slanted Ciphertext | LeetCode 2075 | Java Code | Developer CoderDeveloper Coder · 7:06 · 161 views
leetcode 2075 | FAANG interview Prep | Decode the slanted ciphertext | POTD | C++ solution | DSAShubham Bansal · 24:31 · 78 views
Diagonal Traversal Recovers the Message | Decode the Slanted Ciphertext | LeetCode 2075Daily Dose Of LeetCode · 19:55 · 76 views
Leetcode 2075. Decode the Slanted CiphertextExpertFunda · 13:16 · 61 views
LeetCode Daily 2075 | Decode the Slanted Ciphertext | Beginner Friendly | Easy Step-by-Step SolutionThinkBeforeCode · 8:52 · 29 views
The problem
A string originalText is encoded using a slanted transposition cipher to a string encodedText with the help of a matrix having a fixed number of rows rows.
originalText is placed first in a top-left to bottom-right manner.
The blue cells are filled first, followed by the red cells, then the yellow cells, and so on, until we reach the end of originalText. The arrow indicates the order in which the cells are filled. All empty cells are filled with ' '. The number of columns is chosen such that the rightmost column will not be empty after filling in originalText.
encodedText is then formed by appending all characters of the matrix in a row-wise fashion.
The characters in the blue cells are appended first to encodedText, then the red cells, and so on, and finally the yellow cells. The arrow indicates the order in which the cells are accessed.
For example, if originalText = "cipher" and rows = 3, then we encode it in the following manner:
The blue arrows depict how originalText is placed in the matrix, and the red arrows denote the order in which encodedText is formed. In the above example, encodedText = "ch ie pr".
Given the encoded string encodedText and number of rows rows, return the original string originalText.
Note: originalText does not have any trailing spaces ' '. The test cases are generated such that there is only one possible originalText.
Example 1:
Input: encodedText = "ch ie pr", rows = 3 Output: "cipher" Explanation: This is the same example described in the problem description.
Example 2:
Input: encodedText = "iveo eed l te olc", rows = 4 Output: "i love leetcode" Explanation: The figure above denotes the matrix that was used to encode originalText. The blue arrows show how we can find originalText from encodedText.
Example 3:
Input: encodedText = "coding", rows = 1 Output: "coding" Explanation: Since there is only 1 row, both originalText and encodedText are the same.
Constraints:
0 <= encodedText.length <= 106encodedTextconsists of lowercase English letters and' 'only.encodedTextis a valid encoding of someoriginalTextthat does not have trailing spaces.1 <= rows <= 1000- The testcases are generated such that there is only one possible
originalText.
Approach overview
Problem Overview: The encoded string represents a message written into a matrix with a fixed number of rows, then read diagonally from the top-left toward the bottom-right. Given the encoded text and the number of rows, you need to reconstruct the original message and remove trailing spaces.
Approach 1: Using Matrix Reconstruction (O(n) time, O(n) space)
Compute the number of columns using cols = encodedText.length / rows. Rebuild the matrix by simulating the diagonal traversal used during encoding. Start from each column in the first row, move diagonally with (r + 1, c + 1), and place characters from encodedText into the matrix in that order. Once the matrix is reconstructed, iterate row by row to build the original string. Finally, remove trailing spaces because padding was added during encoding.
This approach mirrors the encoding process exactly, which makes the logic easy to reason about during debugging. The algorithm touches each character once, resulting in O(n) time complexity and O(n) auxiliary space for the matrix.
Approach 2: Simplified Character Reorganization (O(n) time, O(1) extra space)
You can skip building the matrix entirely. Since the encoded text corresponds to a matrix filled row-wise, the character at matrix position (r, c) exists at index r * cols + c in the encoded string. Iterate through each starting column in the first row and simulate the diagonal traversal. For every step, compute the index directly using encodedText[r * cols + (startCol + r)]. Append characters while startCol + r < cols.
This method reconstructs the plaintext in the same order as the diagonal read but avoids storing the full matrix. It uses simple index arithmetic and sequential iteration, which keeps the runtime O(n) and reduces extra memory usage to O(1) beyond the output buffer.
The problem is essentially a string traversal with a structured access pattern. Treating the encoded text as a virtual matrix and simulating the traversal is the key insight. The logic is also a classic example of simulation where you reproduce the exact steps used during encoding.
Recommended for interviews: The simplified character reorganization approach is typically preferred. It demonstrates that you understand how to map 2D matrix coordinates to a 1D string index and optimize space usage. Rebuilding the matrix first is still a good starting point because it clarifies the traversal pattern before moving to the constant-space solution.
Approach 1: Using Matrix Reconstruction
This approach involves reconstructing the matrix from the encoded text and reading back to derive the original text. First, calculate the number of columns needed. Then fill in the columns row-wise using the encoded text. Finally, read the matrix diagonally from top-left to bottom-right to get the original text.
def decodeCiphertext(encodedText, rows):
n = len(encodedText)
cols = n // rows
result = []
for i in range(cols):
for j in range(rows):
index = j * cols + i
if index < n:
result.append(encodedText[index])
return ''.join(result).rstrip()
encoded_text = "iveo eed l te olc"
rows = 4
print(decodeCiphertext(encoded_text, rows))public class DecodeSlantedCiphertext {
public String decodeCiphertext(String encodedText, int rows) {
int len = encodedText.length();
int cols = len / rows;
StringBuilder result = new StringBuilder();
for (int i = 0; i < cols; i++) {
for (int j = 0, k = i; j < rows && k < len; j++, k += cols) {
result.append(encodedText.charAt(k));
}
}
while (result.length() > 0 && result.charAt(result.length() - 1) == ' ') {
result.setLength(result.length() - 1);
}
return result.toString();
}
public static void main(String[] args) {
DecodeSlantedCiphertext decoder = new DecodeSlantedCiphertext();
String encodedText = "iveo eed l te olc";
int rows = 4;
System.out.println(decoder.decodeCiphertext(encodedText, rows));
}
}#include <iostream>
#include <string>
std::string decodeCiphertext(const std::string& encodedText, int rows) {
int len = encodedText.length();
int cols = len / rows;
std::string result;
for (int i = 0; i < cols; ++i) {
for (int j = 0, k = i; j < rows && k < len; ++j, k += cols) {
result += encodedText[k];
}
}
int index = result.size() - 1;
while (index >= 0 && result[index] == ' ') {
--index;
}
return result.substr(0, index + 1);
}
int main() {
std::string encodedText = "iveo eed l te olc";
int rows = 4;
std::cout << decodeCiphertext(encodedText, rows) << std::endl;
return 0;
}function decodeCiphertext(encodedText, rows) {
const len = encodedText.length;
const cols = len / rows;
let result = '';
for (let i = 0; i < cols; i++) {
for (let j = 0; j < rows; j++) {
const index = j * cols + i;
if (index < len) {
result += encodedText[index];
}
}
}
return result.trimEnd();
}
const encodedText = "iveo eed l te olc";
const rows = 4;
console.log(decodeCiphertext(encodedText, rows));#include <stdio.h>
#include <string.h>
#include <stdlib.h>
char* decodeCiphertext(char* encodedText, int rows) {
int len = strlen(encodedText);
int cols = len / rows;
char* result = (char*)malloc(len + 1);
int index = 0;
for (int i = 0; i < cols; ++i) {
for (int j = 0, k = i; j < rows && k < len; ++j, k += cols) {
result[index++] = encodedText[k];
}
}
while (index > 0 && result[index - 1] == ' ') {
--index;
}
result[index] = '\0';
return result;
}
int main() {
char encodedText[] = "iveo eed l te olc";
int rows = 4;
char* originalText = decodeCiphertext(encodedText, rows);
printf("%s\n", originalText);
free(originalText);
return 0;
}using System;
using System.Text;
class DecodeSlantedCiphertext {
public static string DecodeCiphertext(string encodedText, int rows) {
int len = encodedText.Length;
int cols = len / rows;
StringBuilder result = new StringBuilder();
for (int i = 0; i < cols; i++) {
for (int j = 0, k = i; j < rows && k < len; j++, k += cols) {
result.Append(encodedText[k]);
}
}
return result.ToString().TrimEnd();
}
static void Main() {
string encodedText = "iveo eed l te olc";
int rows = 4;
Console.WriteLine(DecodeCiphertext(encodedText, rows));
}
}This Python solution calculates columns, extracts characters diagonally, and joins them into a final string, removing any trailing spaces.
Time Complexity: O(n). Space Complexity: O(n).
Approach 2: Simplified Character Reorganization
This approach focuses on reducing unnecessary overhead by reorganizing characters directly from the encoded text. It navigates through the expected row and column positions, iterating and appending directly into a resultant string.
def decodeCiphertext(encodedText, rows):
n = len(encodedText)
cols = n // rows
result = []
for r in range(rows):
for c in range(r, n, cols + 1):
result.append(encodedText[c])
return ''.join(result).rstrip()
encoded_text = "iveo eed l te olc"
rows = 4
print(decodeCiphertext(encoded_text, rows))public class DecodeSlantedCiphertext {
public String decodeCiphertext(String encodedText, int rows) {
int len = encodedText.length();
int cols = len / rows;
StringBuilder result = new StringBuilder();
for (int r = 0; r < rows; ++r) {
for (int c = r; c < len; c += cols + 1) {
result.append(encodedText.charAt(c));
}
}
while (result.length() > 0 && result.charAt(result.length() - 1) == ' ') {
result.setLength(result.length() - 1);
}
return result.toString();
}
public static void main(String[] args) {
DecodeSlantedCiphertext decoder = new DecodeSlantedCiphertext();
String encodedText = "iveo eed l te olc";
int rows = 4;
System.out.println(decoder.decodeCiphertext(encodedText, rows));
}
}#include <iostream>
#include <string>
std::string decodeCiphertext(const std::string& encodedText, int rows) {
int len = encodedText.length();
int cols = len / rows;
std::string result;
for (int r = 0; r < rows; ++r) {
for (int c = r; c < len; c += cols + 1) {
result += encodedText[c];
}
}
int index = result.size() - 1;
while (index >= 0 && result[index] == ' ') {
--index;
}
return result.substr(0, index + 1);
}
int main() {
std::string encodedText = "iveo eed l te olc";
int rows = 4;
std::cout << decodeCiphertext(encodedText, rows) << std::endl;
return 0;
}function decodeCiphertext(encodedText, rows) {
const len = encodedText.length;
const cols = len / rows;
let result = '';
for (let r = 0; r < rows; r++) {
for (let c = r; c < len; c += cols + 1) {
result += encodedText[c];
}
}
return result.trimEnd();
}
const encodedText = "iveo eed l te olc";
const rows = 4;
console.log(decodeCiphertext(encodedText, rows));#include <stdio.h>
#include <string.h>
#include <stdlib.h>
char* decodeCiphertext(char* encodedText, int rows) {
int len = strlen(encodedText);
int cols = len / rows;
char* result = (char*)malloc(len + 1);
int index = 0;
for (int r = 0; r < rows; ++r) {
for (int c = r; c < len; c += cols + 1) {
result[index++] = encodedText[c];
}
}
while (index > 0 && result[index - 1] == ' ') {
--index;
}
result[index] = '\0';
return result;
}
int main() {
char encodedText[] = "iveo eed l te olc";
int rows = 4;
char* originalText = decodeCiphertext(encodedText, rows);
printf("%s\n", originalText);
free(originalText);
return 0;
}using System;
using System.Text;
class DecodeSlantedCiphertext {
public static string DecodeCiphertext(string encodedText, int rows) {
int len = encodedText.Length;
int cols = len / rows;
StringBuilder result = new StringBuilder();
for (int r = 0; r < rows; r++) {
for (int c = r; c < len; c += cols + 1) {
result.Append(encodedText[c]);
}
}
return result.ToString().TrimEnd();
}
static void Main() {
string encodedText = "iveo eed l te olc";
int rows = 4;
Console.WriteLine(DecodeCiphertext(encodedText, rows));
}
}Python's approach straightforwardly iterates over valid indices from each start point to directly form the resultant list.
Time Complexity: O(n). Space Complexity: O(n).
Approach 3: Simulation
First, we calculate the number of columns in the matrix cols = len(encodedText) / rows. Then, following the rules described in the problem, we start traversing the matrix from the top left corner, adding characters to the answer.
Finally, we return the answer, making sure to remove any trailing spaces.
The time complexity is O(n), and the space complexity is O(n), where n is the length of the string encodedText.
function decodeCiphertext(encodedText: string, rows: number): string {
const cols = Math.ceil(encodedText.length / rows);
const ans: string[] = [];
for (let k = 0; k <= cols; k++) {
for (let i = 0, j = k; i < rows && j < cols; i++, j++) {
ans.push(encodedText[i * cols + j]);
}
}
return ans.join('').trimEnd();
}func decodeCiphertext(encodedText string, rows int) string {
ans := []byte{}
cols := len(encodedText) / rows
for j := 0; j < cols; j++ {
for x, y := 0, j; x < rows && y < cols; x, y = x+1, y+1 {
ans = append(ans, encodedText[x*cols+y])
}
}
for len(ans) > 0 && ans[len(ans)-1] == ' ' {
ans = ans[:len(ans)-1]
}
return string(ans)
}Complexity comparison
| Approach | Complexity |
|---|---|
| Using Matrix Reconstruction | Time Complexity: O(n). Space Complexity: O(n). |
| Simplified Character Reorganization | Time Complexity: O(n). Space Complexity: O(n). |
| Simulation | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Matrix Reconstruction | O(n) | O(n) | When clarity matters or when visualizing the matrix traversal during debugging |
| Simplified Character Reorganization | O(n) | O(1) | Preferred for interviews and optimized implementations with minimal memory |
Frequently asked questions
Is Decode the Slanted Ciphertext easy or hard?
Decode the Slanted Ciphertext is considered a Medium-level problem on LeetCode. The main challenge is recognizing the diagonal traversal pattern and converting between 2D matrix coordinates and the 1D string index.
Decode the Slanted Ciphertext Python/Java solution
In Python or Java, compute cols = encodedText.length() / rows and simulate diagonal traversal from each column. Access characters using index mapping r * cols + (startCol + r) and append them to a result builder. After traversal, trim trailing spaces before returning the decoded message.
How to solve Decode the Slanted Ciphertext in O(n)?
First compute the number of columns as cols = encodedText.length / rows. Iterate over each starting column in the first row and simulate the diagonal movement (r + 1, c + 1). Use index mapping r * cols + (startCol + r) to fetch characters directly from the encoded string and append them to the result, then trim trailing spaces.
What is the best approach for Decode the Slanted Ciphertext?
The best approach uses direct index computation without explicitly building the matrix. Treat the encoded string as a virtual rows × cols grid and simulate the diagonal traversal using index math like r * cols + (startCol + r). This runs in O(n) time and O(1) extra space while keeping the implementation simple.
Is Decode the Slanted Ciphertext asked at Google/Amazon/Meta?
Problems involving matrix traversal, diagonal simulation, and string reconstruction appear frequently in interviews at companies like Amazon, Google, and Meta. While this exact problem may vary, the underlying skills—matrix indexing and simulation—are commonly tested.
What data structure is used in Decode the Slanted Ciphertext?
The problem primarily uses string manipulation and a conceptual 2D matrix. Some solutions explicitly construct a matrix, while optimized solutions treat the string as a virtual matrix using index arithmetic. No complex data structures are required beyond arrays or strings.
What is the time complexity of Decode the Slanted Ciphertext?
The optimal solution runs in O(n) time where n is the length of encodedText. Each character is processed at most once during the diagonal traversal. Space complexity can be O(n) if a matrix is built, or O(1) extra space if you compute indices directly.