Largest Zigzag Sequence

Time: O(n^2)

Space: O(n^2)

Problem Overview

In an n x n matrix, pick exactly one cell per row from top to bottom so consecutive picks never share a column, and maximize the sum.

Intuition

In an n x n matrix, pick exactly one cell per row from top to bottom so consecutive picks never share a column, and maximize the sum. Ending a row in column j costs mat[i][j] plus the best previous-row total among all columns except j. Tracking the top two previous-row totals (and which column holds the best) turns each row into an O(n) update.

Algorithm

1dp[0][j] = mat[0][j] for every column j.
2For each row i = 1..n-1: scan dp[i-1] to find max1, max2, and col1 (column of max1).
3For each j: dp[i][j] = mat[i][j] + (j != col1 ? max1 : max2).
4Answer is the maximum value in dp[n-1].

Example Walkthrough

Input: mat = [[4, 2, 1], [3, 9, 6], [1, 0, 5]]

1. Row 0 seeds: 4, 2, 1.
2. Row 1: best prior is 4 at col 0, second is 2 - so col 0 gets 3+2=5, col 1 gets 9+4=13, col 2 gets 6+4=10.
3. Row 2: max prior 13 at col 1 - best path ends at 5 + 13 = 18 (columns 0 -> 1 -> 2: 4+9+5).

Output: 18

Common Pitfalls

• Adjacent rows cannot reuse the same column - that is the zigzag constraint.
• When the best previous column equals j, fall back to the second-best previous total.
• Naive per-cell scan of the previous row is O(n^3); top-two tracking keeps it O(n^2).
• Initialize max1/max2 carefully when all values could be zero or negative if constraints allow.

Largest Zigzag Sequence.java

Java

// Approach: Pick one cell per row top to bottom; consecutive picks must use
// different columns. dp[i][j] = mat[i][j] + max(dp[i-1][k] for k != j). Maintain
// the top two values of the previous row (and the column of the largest) so each
 // row fills in O(n) instead of O(n^2) per cell.
// Time: O(n^2) Space: O(n^2)
class Solution {

    public int zigzagSequence(int[][] mat) {
        int n = mat.length;
        int[][] dp = new int[n][n];

        for (int j = 0; j < n; j++) {
            dp[0][j] = mat[0][j];
        }

        for (int i = 1; i < n; i++) {
            int max1 = -1, max2 = -1, col1 = -1;
            for (int k = 0; k < n; k++) {
                if (dp[i - 1][k] > max1) {
                    max2 = max1;
                    max1 = dp[i - 1][k];
                    col1 = k;
                } else if (dp[i - 1][k] > max2) {
                    max2 = dp[i - 1][k];
                }
            }

            for (int j = 0; j < n; j++) {
                dp[i][j] = mat[i][j] + (j != col1 ? max1 : max2);
            }
        }

        int maxSum = Integer.MIN_VALUE;
        for (int j = 0; j < n; j++) {
            maxSum = Math.max(maxSum, dp[n - 1][j]);
        }
        return maxSum;
    }
}

Was this solution helpful?