Problem Description#

Given an m × n integer matrix mat, sort the elements on each diagonal in ascending order and return the sorted matrix.

The diagonal here refers to the line going from top-left to bottom-right, i.e., all cells whose coordinates satisfy i - j being the same constant.

Example:

1
Input: mat = [[3,3,1,1],
2
             [2,2,1,2],
3
             [1,1,1,2]]
4
Output:     [[1,1,1,1],
5
             [1,2,2,2],
6
             [1,2,3,3]]
7

8
Input: mat = [[1,1,1,1],
9
             [1,1,1,1],
10
             [1,1,1,1],
11
             [1,1,1,1]]
12
Output:     [[1,1,1,1],
13
             [1,1,1,1],
14
             [1,1,1,1],
15
             [1,1,1,1]]

Constraints: m == mat.length, n == mat[i].length, 1 <= m, n <= 100, 1 <= mat[i][j] <= 100.

Approach: First Find the “Starting Point” of Each Diagonal#

The key observation is just one sentence:

On the same top-left → bottom-right diagonal, all cells have equal i - j; conversely, equal i - j means they are on the same diagonal.

For an 3 × 4 matrix, the distribution of i - j looks like this:

1
        j=0  j=1  j=2  j=3
2
i=0      0   -1   -2   -3
3
i=1      1    0   -1   -2
4
i=2      2    1    0   -1

To traverse each diagonal exactly once, there is no need to enumerate every value of i - j; it suffices to enumerate the starting point of each diagonal:

• Every cell in the first column (i, 0) (i = 0..m-1) is the starting point of a diagonal;
• Every cell in the first row except (0, 0), i.e., (0, j) (j = 1..n-1), is also the starting point of a diagonal.

There are m + n - 1 diagonals in total. Starting from the starting point and moving (i, j) → (i+1, j+1) each time until going out of bounds, you will traverse exactly that line.

So the algorithm is very straightforward: read out all the numbers on this diagonal → sort → write them back in their original order.

Process Illustration#

Taking Example 1 as an example, label the i - j of each cell:

1
mat = [[3, 3, 1, 1],        i-j = [[ 0, -1, -2, -3],
2
       [2, 2, 1, 2],                [ 1,  0, -1, -2],
3
       [1, 1, 1, 2]]                [ 2,  1,  0, -1]]
4

5
Group by i-j:
6
  0: (0,0)=3, (1,1)=2, (2,2)=1   → sort [1,2,3]
7
 -1: (0,1)=3, (1,2)=1, (2,3)=2   → sort [1,2,3]
8
 -2: (0,2)=1, (1,3)=2            → sort [1,2]
9
 -3: (0,3)=1                     → sort [1]
10
  1: (1,0)=2, (2,1)=1            → sort [1,2]
11
  2: (2,0)=1                     → sort [1]
12

13
After writing back:
14
[[1, 1, 1, 1],
15
 [1, 2, 2, 2],
16
 [1, 2, 3, 3]]  ✔

Code Implementation#

1
#include <stdlib.h>
2

3
static int cmpInt(const void *a, const void *b) {
4
    int x = *(const int *)a;
5
    int y = *(const int *)b;
6
    return (x > y) - (x < y);          /* Subtraction may overflow, so this is safer */
7
}
8

9
/* Sort the diagonal starting at (r, c) and extending down-right */
10
static void sortDiagonal(int **mat, int m, int n, int r, int c) {
11
    int len = 0;
12
    while (r + len < m && c + len < n) len++;      /* Length of this diagonal */
13

14
    int *buf = (int *)malloc(sizeof(int) * len);
15
    for (int k = 0; k < len; k++) buf[k] = mat[r + k][c + k];
16

17
    qsort(buf, len, sizeof(int), cmpInt);
18

19
    for (int k = 0; k < len; k++) mat[r + k][c + k] = buf[k];
20

21
    free(buf);
22
}
23

24
void diagonalSort(int **mat, int m, int n) {
25
    for (int i = 0; i < m; i++) sortDiagonal(mat, m, n, i, 0);  /* Starting from the first column */
26
    for (int j = 1; j < n; j++) sortDiagonal(mat, m, n, 0, j);  /* Starting from the first row */
27
}

1
#include <algorithm>
2
#include <vector>
3
using namespace std;
4

5
class Solution {
6
public:
7
    vector<vector<int>> diagonalSort(vector<vector<int>>& mat) {
8
        int m = (int)mat.size();
9
        int n = (int)mat[0].size();
10

11
        for (int i = 0; i < m; ++i) sortDiagonal(mat, i, 0);  // Starting from the first column
12
        for (int j = 1; j < n; ++j) sortDiagonal(mat, 0, j);  // Starting from the first row (skip (0,0))
13

14
        return mat;
15
    }
16

17
private:
18
    // Read out the diagonal at (r, c) -> sort -> write back
19
    void sortDiagonal(vector<vector<int>>& mat, int r, int c) {
20
        int m = (int)mat.size();
21
        int n = (int)mat[0].size();
22

23
        vector<int> diag;
24
        for (int i = r, j = c; i < m && j < n; ++i, ++j) diag.push_back(mat[i][j]);
25
        sort(diag.begin(), diag.end());
26

27
        int k = 0;
28
        for (int i = r, j = c; i < m && j < n; ++i, ++j) mat[i][j] = diag[k++];
29
    }
30
};

1
function diagonalSort(mat) {
2
  const m = mat.length;
3
  const n = mat[0].length;
4

5
  // Read out the diagonal at (r, c) -> sort -> write back
6
  const sortDiagonal = (r, c) => {
7
    const diag = [];
8
    for (let i = r, j = c; i < m && j < n; i++, j++) diag.push(mat[i][j]);
9
    diag.sort((a, b) => a - b);
10
    let k = 0;
11
    for (let i = r, j = c; i < m && j < n; i++, j++) mat[i][j] = diag[k++];
12
  };
13

14
  for (let i = 0; i < m; i++) sortDiagonal(i, 0);   // Starting from the first column
15
  for (let j = 1; j < n; j++) sortDiagonal(0, j);   // Starting from the first row (skip (0,0))
16

17
  return mat;
18
}

Complexity#

Let L = min(m, n):

Common Pitfalls#

1. Selection of starting points. The first column must include (0, 0), and the first row must not include (0, 0); otherwise the main diagonal will be sorted twice (although sorting twice does not change the result, it is a wasted pass).
2. Direction of (i, j) advancement. The diagonals in this problem go from top-left to bottom-right, so it is i++, j++; if written as i++, j--, it becomes an anti-diagonal.
3. Diagonal lengths are inconsistent for non-square matrices. When m ≠ n, lengths range from 1 to min(m, n), so the buffer must be allocated according to the actual length and cannot be fixed at m or n.
4. Don’t forget that i - j can be negative. If you switch to the approach of “grouping by i - j”, in C you cannot directly use a negative index as an array subscript.

Extension: In-Place Approach Without Extra Buffer#

A diagonal itself is stored contiguously in the matrix (just diagonally), so you can directly perform insertion sort on the diagonal, reducing the buffer to O(1):

1
// Insertion sort along the diagonal: insert each element forward into the sorted prefix of that diagonal
2
void sortDiagonalInPlace(vector<vector<int>>& mat, int r, int c) {
3
    int m = (int)mat.size(), n = (int)mat[0].size();
4

5
    for (int i = r + 1, j = c + 1; i < m && j < n; ++i, ++j) {
6
        int x = mat[i][j];
7
        int p = i - 1, q = j - 1;
8
        while (p >= r && q >= c && mat[p][q] > x) {   // Shift everything greater than x back by one
9
            mat[p + 1][q + 1] = mat[p][q];
10
            --p;
11
            --q;
12
        }
13
        mat[p + 1][q + 1] = x;
14
    }
15
}

The worst-case time complexity (when the whole matrix has a very long diagonal in reverse order) is O(m·n·min(m, n)), but the extra space is O(1), and it is very fast on nearly sorted input.

Problem Description#

You are given a 2D grid grid with m rows and n columns, and an integer k. You need to migrate grid k times. Each “migration” operation:

• The element at grid[i][j] will move to grid[i][j + 1];
• The element at grid[i][n - 1] will move to grid[i + 1][0];
• The element at grid[m - 1][n - 1] will move to grid[0][0].

Return the final 2D grid obtained after k migration operations.

Example:

1
Input: grid = [[1,2,3],
2
              [4,5,6],
3
              [7,8,9]], k = 1
4
Output:     [[9,1,2],
5
              [3,4,5],
6
              [6,7,8]]
7

8
Input: grid = [[3,8,1,9],
9
              [19,7,2,5],
10
              [4,6,11,10],
11
              [12,0,21,13]], k = 4
12
Output:     [[12,0,21,13],
13
              [3,8,1,9],
14
              [19,7,2,5],
15
              [4,6,11,10]]
16
         (Each element moves exactly one full row, equivalent to shifting the whole thing down by one row)
17

18
Input: grid = [[1,2,3],[4,5,6],[7,8,9]], k = 9
19
Output: [[1,2,3],[4,5,6],[7,8,9]]   (9 times wraps exactly back to the original)

Constraints: 1 <= m, n <= 50, -1000 <= grid[i][j] <= 1000, 0 <= k <= 100.

Approach 1: Flatten Then Cyclically Shift as a Whole#

The “snake-like wrap-around” rule of the matrix sounds convoluted, but once you flatten the 2D grid into a 1D array using row-major order by index p = i * n + j, everything becomes simple:

1
grid = [[1,2,3],        flatten →  [1,2,3,4,5,6,7,8,9]
2
        [4,5,6],
3
        [7,8,9]]

The three movement rules, from the 1D perspective, are actually the same thing: each element moves one position forward, and the last one wraps back to the beginning. So migrating k times = cyclically shifting the flattened array right by k positions as a whole. Thus, the element originally at position p will have its new position at:

1
q = (p + k) mod (m * n)

Then convert back to row and column indices using q / n and q % n and write them back.

Note that k can first be taken modulo m * n: after m * n migrations, all elements return to their original positions.

Process Illustration#

1
grid = [[1,2,3],[4,5,6],[7,8,9]]   k = 1
2

3
Flatten: index  0  1  2  3  4  5  6  7  8
4
       value    1  2  3  4  5  6  7  8  9
5

6
Each element q = (p + 1) % 9:
7
  1(0) → 1    2(1) → 2    3(2) → 3
8
  4(3) → 4    5(4) → 5    6(5) → 6
9
  7(6) → 7    8(7) → 8    9(8) → 0   ← 9 wraps back to the beginning
10

11
The new 1D array: 9  1  2  3  4  5  6  7  8
12
Split into groups of 3 per row:
13
[[9,1,2],
14
 [3,4,5],
15
 [6,7,8]]  ✔

Approach 2: Triple Reversal (In-Place, O(1) Extra Space)#

“Cyclically shifting right by k positions” has a classic two-pointer solution: triple reversal. Let the array length be total:

1. Reverse the entire array [0, total-1];
2. Reverse the first k elements [0, k-1];
3. Reverse the remaining [k, total-1].

Each reversal uses left and right pointers converging toward the middle and swapping. Verify with [1..9]、k = 3:

1
Original     1 2 3 4 5 6 7 8 9
2
Reverse all 9 8 7 6 5 4 3 2 1
3
Reverse first 3  7 8 9 6 5 4 3 2 1
4
Reverse the rest 7 8 9 1 2 3 4 5 6   ✔ exactly a right rotation by 3

As long as you’re willing to treat the 2D matrix as a 1D array at the index level (p ↔ (p / n, p % n)), this algorithm can be applied in-place, reducing extra space to O(1).

Code Implementation#

1
#include <stdlib.h>
2

3
int **shiftGrid(int **grid, int m, int n, int k) {
4
    int total = m * n;
5
    k %= total;                                    /* Shifting total times is a no-op */
6

7
    int **res = (int **)malloc(sizeof(int *) * m);
8
    for (int i = 0; i < m; i++) res[i] = (int *)malloc(sizeof(int) * n);
9

10
    for (int i = 0; i < m; i++) {
11
        for (int j = 0; j < n; j++) {
12
            int p = i * n + j;                     /* Flattened index */
13
            int q = (p + k) % total;               /* Index after k shifts */
14
            res[q / n][q % n] = grid[i][j];
15
        }
16
    }
17
    return res;
18
}

1
#include <vector>
2
using namespace std;
3

4
class Solution {
5
public:
6
    vector<vector<int>> shiftGrid(vector<vector<int>>& grid, int k) {
7
        int m = (int)grid.size();
8
        int n = (int)grid[0].size();
9
        int total = m * n;
10
        k %= total;                                // Shifting total times is a no-op
11

12
        vector<vector<int>> res(m, vector<int>(n));
13
        for (int i = 0; i < m; ++i) {
14
            for (int j = 0; j < n; ++j) {
15
                int q = (i * n + j + k) % total;   // Shift forward k positions after flattening
16
                res[q / n][q % n] = grid[i][j];
17
            }
18
        }
19
        return res;
20
    }
21

22
    // Approach 2: three reversals, done in place
23
    vector<vector<int>> shiftGridReverse(vector<vector<int>> grid, int k) {
24
        int m = (int)grid.size(), n = (int)grid[0].size(), total = m * n;
25
        k %= total;
26

27
        // Treat the 2D matrix as a row-major 1D array, reverse [lo, hi]
28
        auto rev = [&](int lo, int hi) {
29
            while (lo < hi) {
30
                swap(grid[lo / n][lo % n], grid[hi / n][hi % n]);
31
                ++lo;
32
                --hi;
33
            }
34
        };
35

36
        rev(0, total - 1);
37
        rev(0, k - 1);
38
        rev(k, total - 1);
39
        return grid;
40
    }
41
};

1
function shiftGrid(grid, k) {
2
  const m = grid.length;
3
  const n = grid[0].length;
4
  const total = m * n;
5
  k %= total;                                  // Shifting total times is a no-op
6

7
  const res = Array.from({ length: m }, () => new Array(n));
8

9
  for (let i = 0; i < m; i++) {
10
    for (let j = 0; j < n; j++) {
11
      const q = (i * n + j + k) % total;       // Shift forward k positions after flattening
12
      res[Math.floor(q / n)][q % n] = grid[i][j];
13
    }
14
  }
15
  return res;
16
}

Complexity#

Common Pitfalls#

1. Take modulo before computing. k may be much larger than m * n (in this problem k <= 100 is small, but a general solution needs k %= total). Conversely, forgetting the case of k = 0 is also a common oversight—in that case, empty intervals like rev(0, -1) must be safely skipped (while (lo < hi) naturally satisfies this).
2. Don’t get the migration direction wrong. The problem states each element moves right/forward ((p + k) % total); if you write (p - k + total) % total, it becomes a leftward migration.
3. Row-major flattening. Use p = i * n + j (traverse a full row horizontally first); if you use column-major flattening, the wrap-around order won’t match the problem description.
4. Think clearly about the relationship between k and total before starting. Examples 3’s k = 9 and total = 9 are reminders about taking modulo.

Problem Description#

Given a 2D integer array matrix, return the transpose of matrix.

The transpose of a matrix is obtained by flipping the matrix over its main diagonal, swapping the row index and column index of the matrix.

Example:

1
Input: matrix = [[1,2,3],
2
                [4,5,6],
3
                [7,8,9]]
4
Output:        [[1,4,7],
5
                [2,5,8],
6
                [3,6,9]]
7

8
Input: matrix = [[1,2,3],
9
                [4,5,6]]
10
Output:        [[1,4],
11
                [2,5],
12
                [3,6]]

Constraints: m == matrix.length, n == matrix[i].length, 1 <= m, n <= 1000, 1 <= m * n <= 10^5, -10^9 <= matrix[i][j] <= 10^9.

Approach: Swap Coordinates Once#

The definition of transpose is exactly “swap the row index and column index,” so just map directly:

1
res[j][i] = matrix[i][j]

The original matrix is m × n, and after transposing it becomes n × m: the original i-th row becomes the i-th column.

In-place transposition is possible if and only if the matrix is square—because in that case the input and output shapes are the same. The key to the in-place approach is to cut the traversal range in half: only process the upper triangle i < j, swapping mat[i][j] with mat[j][i]; the diagonal elements i == j don’t need to move.

Why must we cut it in half? The table below illustrates the problem: if both i and j run over the entire matrix, each symmetric pair gets swapped twice, which amounts to no swap at all.

1
Only traverse the upper triangle (i < j)             i and j both run through the full range
2
  (0,1) (0,2)                    each (i,j) is visited once
3
  (1,2)                          (0,1) swapped once → (1,0) swapped again → restored
4

5
Number of visits:   3 pairs                 Number of visits: 9 cells, actually 4 pairs swapped (duplicates)

Process Walkthrough#

Non-square 2 × 3 → 3 × 2:

1
matrix          res[j][i] = matrix[i][j]
2
[1, 2, 3]       res[0][0]=1  res[1][0]=2  res[2][0]=3
3
[4, 5, 6]       res[0][1]=4  res[1][1]=5  res[2][1]=6
4

5
res = [[1, 4],
6
       [2, 5],
7
       [3, 6]]  ✔

In-place transpose of a square matrix:

1
[1, 2, 3]                [1, 4, 7]
2
[4, 5, 6]   ──upper triangle swap──► [2, 5, 8]
3
[7, 8, 9]                [3, 6, 9]
4

5
3 pairs swapped: (0,1)↔(1,0), (0,2)↔(2,0), (1,2)↔(2,1)
6
Diagonal (0,0), (1,1), (2,2) stay unchanged ✔

Code Implementation#

1
#include <stdlib.h>
2

3
/* Non-square: the result is a new n×m matrix */
4
int **transpose(int **mat, int m, int n) {
5
    int **res = (int **)malloc(sizeof(int *) * n);
6
    for (int j = 0; j < n; j++) res[j] = (int *)malloc(sizeof(int) * m);
7

8
    for (int i = 0; i < m; i++)
9
        for (int j = 0; j < n; j++)
10
            res[j][i] = mat[i][j];
11

12
    return res;
13
}
14

15
/* A square matrix can be transposed in place: only process the upper triangle (i < j), the diagonal stays put */
16
void transposeInPlace(int **mat, int m) {
17
    for (int i = 0; i < m; i++)
18
        for (int j = i + 1; j < m; j++) {
19
            int t = mat[i][j];
20
            mat[i][j] = mat[j][i];
21
            mat[j][i] = t;
22
        }
23
}

1
#include <vector>
2
using namespace std;
3

4
class Solution {
5
public:
6
    vector<vector<int>> transpose(vector<vector<int>>& matrix) {
7
        int m = (int)matrix.size();
8
        int n = (int)matrix[0].size();
9
        vector<vector<int>> res(n, vector<int>(m));
10

11
        for (int i = 0; i < m; ++i)
12
            for (int j = 0; j < n; ++j)
13
                res[j][i] = matrix[i][j];
14

15
        return res;
16
    }
17

18
    // A square matrix can be transposed in place: only process the upper triangle
19
    void transposeInPlace(vector<vector<int>>& matrix) {
20
        int m = (int)matrix.size();
21
        for (int i = 0; i < m; ++i)
22
            for (int j = i + 1; j < m; ++j)
23
                swap(matrix[i][j], matrix[j][i]);
24
    }
25
};

1
function transpose(matrix) {
2
  const m = matrix.length;
3
  const n = matrix[0].length;
4
  const res = Array.from({ length: n }, () => new Array(m));
5

6
  for (let i = 0; i < m; i++)
7
    for (let j = 0; j < n; j++) res[j][i] = matrix[i][j];
8

9
  return res;
10
}
11

12
// A square matrix can be transposed in place: only process the upper triangle
13
function transposeInPlace(matrix) {
14
  const m = matrix.length;
15
  for (let i = 0; i < m; i++)
16
    for (let j = i + 1; j < m; j++) {
17
      [matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]];
18
    }
19
}

Complexity#

Common Pitfalls#

1. A non-square matrix cannot be transposed in place. 2 × 3 becomes 3 × 2, the shape changes, so a new array must be allocated. Only a square matrix can be “in-place.”
2. For in-place transposition, j must start from i + 1. Starting from 0 causes each element to be swapped twice, and the final result ends up identical to the original matrix—this is a classic bug that “looks correct but silently fails at runtime.”
3. Don’t swap the two indices. The result matrix is n × m (the number of rows is the original number of columns), so allocate the correct shape first before filling it in.

Problem Description#

Write a function to find the longest common prefix among an array of strings. If there is no common prefix, return the empty string "".

Example:

1
Input: strs = ["flower","flow","flight"]
2
Output: "fl"
3

4
Input: strs = ["dog","racecar","car"]
5
Output: ""
6
Explanation: There is no common prefix in the input.
7

8
Input: strs = ["a"]
9
Output: "a"

Constraints: 1 <= strs.length <= 200, 0 <= strs[i].length <= 200, strs[i] consist only of lowercase English letters.

Approach: Vertical Scanning, Two “Pointers”#

The pointers in previous sections were all numeric indices, but the pointers in this problem are one column and one row:

• Column pointer j: advances along the reference string strs[0] from character 0 to the right;
• Row pointer i: for each j, scans horizontally across strs[1], strs[2], … comparing the j-th character one by one.

The rules are:

1. The common prefix cannot be longer than strs[0], so j only advances within the range of strs[0];
2. For the current j, if the j-th character of some string differs from strs[0][j], or that string has already ended (length less than j + 1), then the common prefix ends here—the answer is the first j characters of strs[0];
3. If all strings successfully make it through strs[0], then strs[0] itself is the common prefix.

Why can “different” and “ended” be checked together? Because in C, accessing the len-th position of a string yields exactly the terminator '\0', and strs[i][j] == '\0' is obviously not equal to strs[0][j]. C++ / JavaScript, however, require an explicit length comparison.

Process Illustration#

1
strs = ["flower", "flow", "flight"]
2
                  ↑ baseline string
3

4
j=0: strs[1][0]='f'='f'  strs[2][0]='f'='f'  → all pass
5
j=1: strs[1][1]='l'='l'  strs[2][1]='l'='l'  → all pass
6
j=2: strs[1][2]='o'='o'  strs[2][2]='i'!='o' → conflict!
7

8
return the first 2 characters of strs[0] = "fl" ✔

Counter-example ["dog","racecar","car"]: when j=0, 'a' != 'd', immediately return "" ✔

Code Implementation#

1
#include <stdlib.h>
2
#include <string.h>
3

4
char *longestCommonPrefix(char **strs, int strsSize) {
5
    int len = (int)strlen(strs[0]);        /* The common prefix cannot be longer than the base string */
6

7
    for (int j = 0; j < len; j++) {        /* j: column pointer advancing along the base string */
8
        char c = strs[0][j];
9
        for (int i = 1; i < strsSize; i++) {   /* i: comparing the remaining strings horizontally */
10
            /* This string has already ended here (read '\0'), or the characters are not equal */
11
            if (strs[i][j] == '\0' || strs[i][j] != c) {
12
                char *cut = (char *)malloc(j + 1);
13
                memcpy(cut, strs[0], j);
14
                cut[j] = '\0';
15
                return cut;
16
            }
17
        }
18
    }
19

20
    char *whole = (char *)malloc(len + 1);
21
    memcpy(whole, strs[0], len + 1);
22
    return whole;
23
}

1
#include <string>
2
#include <vector>
3
using namespace std;
4

5
class Solution {
6
public:
7
    string longestCommonPrefix(vector<string>& strs) {
8
        const string& base = strs[0];                   // Base string
9

10
        for (int j = 0; j < (int)base.size(); ++j) {     // j: column pointer
11
            char c = base[j];
12
            for (int i = 1; i < (int)strs.size(); ++i) { // i: row pointer
13
                // This string has already ended, or the j-th character is not equal
14
                if (j >= (int)strs[i].size() || strs[i][j] != c) {
15
                    return base.substr(0, j);
16
                }
17
            }
18
        }
19
        return base;
20
    }
21
};

1
function longestCommonPrefix(strs) {
2
  const base = strs[0];                    // Base string
3

4
  for (let j = 0; j < base.length; j++) {         // j: column pointer
5
    const c = base[j];
6
    for (let i = 1; i < strs.length; i++) {       // i: row pointer
7
      // This string has already ended, or the j-th character is not equal
8
      if (j >= strs[i].length || strs[i][j] !== c) {
9
        return base.slice(0, j);
10
      }
11
    }
12
  }
13
  return base;
14
}

Complexity#

Let S be the total number of characters across all strings, and L be the length of the shortest string:

Common Pitfalls#

1. Choose the right reference string. Choosing strs[0] is most convenient, because the answer must be a prefix of it. If you arbitrarily pick a string as the reference, the length upper bound becomes hard to control.
2. Handling empty strings. If there is any "" in strs, the answer is immediately ""—in the code above, it will be caught by strs[i][j] == '\0' or the length check during the j = 0 round.
3. Out-of-bounds access no longer occurs in C because of the comparison order. When comparing incrementally with j increasing one by one, the “shorter string” will always be stopped at its own terminator first, so it will not skip past the terminator and read beyond the buffer. This is the implicit precondition that allows this kind of vertical scanning to be safely implemented in C.
4. strs[i] all empty, or strs having only one element are both valid inputs; the former returns "", the latter returns strs[0] itself.

Other Solutions#

Divide and conquer: Split the string array in two, find the common prefix of the left and right halves respectively, then find the common prefix of these two prefixes. Time O(S), space O(m·L) for the recursion stack. Good for demonstrating the divide-and-conquer template, but offers no performance advantage for this problem.

Sort then compare only first and last: Sort strs; the common prefix must equal the common prefix of the “lexicographically smallest string” and the “lexicographically largest string.” Sorting is O(n log n · L), but the pairwise comparison implementation is especially short:

1
string longestCommonPrefixSorted(vector<string>& strs) {
2
    sort(strs.begin(), strs.end());
3
    const string& first = strs.front();
4
    const string& last = strs.back();
5
    int i = 0;
6
    while (i < (int)first.size() && i < (int)last.size() && first[i] == last[i]) ++i;
7
    return first.substr(0, i);
8
}

Although this approach is not two pointers, the idea of “comparing only the first and last” is well worth remembering.