Monotonic Stack + DP

currentSteps = 0
while stack not empty AND nums[i] >= nums[stack.top()]:
    currentSteps = max(currentSteps, dp[stack.pop()])

if stack not empty:          // a larger element still blocks nums[i]
    dp[i] = currentSteps + 1
else:                        // nums[i] is a new global maximum — never removed
    dp[i] = 0

answer = max(dp[i]) for all i

for i from n-1 down to 0:
    maxSteps = 0
    while stack not empty AND nums[i] > nums[stack.top()]:
        maxSteps = max(maxSteps + 1, dp[stack.pop()])
    dp[i] = maxSteps
    res = max(res, dp[i])
    stack.push(i)

// java
// LC 2289 - Steps to Make Array Non-decreasing
// IDEA: forward scan; a popped chain hands its max survival time to the element that ate it
// time = O(n), space = O(n)
public int totalSteps(int[] nums) {
    int n = nums.length, maxSteps = 0;
    int[] dp = new int[n];
    Stack<Integer> stack = new Stack<>();   // monotonic decreasing (by value)

    for (int i = 0; i < n; i++) {
        int currentSteps = 0;

        // Pop elements that nums[i] will outlive (nums[i] >= them)
        while (!stack.isEmpty() && nums[i] >= nums[stack.peek()]) {
            currentSteps = Math.max(currentSteps, dp[stack.pop()]);
        }

        if (!stack.isEmpty()) {
            // A larger element still exists to the left → nums[i] will be removed
            dp[i] = currentSteps + 1;
            maxSteps = Math.max(maxSteps, dp[i]);
        }
        // else dp[i] = 0 (never removed)

        stack.push(i);
    }
    return maxSteps;
}

// java
// LC 2289 - Steps to Make Array Non-decreasing
// IDEA: same recurrence scanned right-to-left; dp[i] = rounds before nums[i] disappears
// time = O(n), space = O(n)
public int totalSteps(int[] nums) {
    int n = nums.length, res = 0;
    int[] dp = new int[n];
    Stack<Integer> stack = new Stack<>();

    for (int i = n - 1; i >= 0; i--) {
        int maxSteps = 0;
        while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
            maxSteps = Math.max(maxSteps + 1, dp[stack.pop()]);
        }
        dp[i] = maxSteps;
        res = Math.max(res, dp[i]);
        stack.push(i);
    }
    return res;
}

Matrix:       dp values:     Contribution:
0 1 1 1       0 1 1 1        0+1+1+1 = 3   (row 0)
1 1 1 1  →    1 1 2 2   →   1+1+2+2 = 6   (row 1)
0 1 1 1       0 1 2 3        0+1+2+3 = 6   (row 2)
                                  Total = 15 ✓

// java
// IDEA: the square recurrence, isolated
// LC 1277: Count Square Submatrices with All Ones
public int countSquares(int[][] matrix) {
    int rows = matrix.length, cols = matrix[0].length;
    int[][] dp = new int[rows][cols];
    int result = 0;

    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (matrix[i][j] == 1) {
                if (i == 0 || j == 0) {
                    dp[i][j] = 1;  // first row/col: only 1×1 possible
                } else {
                    dp[i][j] = Math.min(
                        Math.min(dp[i-1][j], dp[i][j-1]),
                        dp[i-1][j-1]
                    ) + 1;
                }
                result += dp[i][j];  // dp[i][j] = count of squares ending here
            }
        }
    }
    return result;
}

// java
// LC 1277 - Count Square Submatrices with All Ones
// IDEA: dp[i][j] = side of the largest all-1 square ending at (i,j); summing dp counts them all
// time = O(m * n), space = O(m * n)
public int countSquares(int[][] matrix) {
    int row = matrix.length, col = matrix[0].length;
    int[][] dp = new int[row + 1][col + 1];  // +1 removes boundary check
    int ans = 0;
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            if (matrix[i][j] == 1) {
                dp[i+1][j+1] = Math.min(
                    Math.min(dp[i][j+1], dp[i+1][j]),
                    dp[i][j]
                ) + 1;
                ans += dp[i+1][j+1];
            }
        }
    }
    return ans;
}

// java
// LC 1277 - Count Square Submatrices with All Ones
// IDEA: same recurrence rolled onto one row; keep the old up-left value in a temp
// time = O(m * n), space = O(n)
public int countSquares(int[][] matrix) {
    int row = matrix.length, col = matrix[0].length, result = 0, prev = 0;
    int[] dp = new int[col + 1];

    for (int i = 1; i <= row; i++) {
        for (int j = 1; j <= col; j++) {
            int temp = dp[j];
            if (matrix[i-1][j-1] == 1) {
                dp[j] = 1 + Math.min(prev, Math.min(dp[j-1], dp[j]));
                result += dp[j];
            } else {
                dp[j] = 0;
            }
            prev = temp;
        }
    }
    return result;
}

Consider:    dp[i-1][j] = 3   →  top supports 3×3
             dp[i][j-1] = 1   →  left supports 1×1 only
             dp[i-1][j-1] = 2  →  diagonal supports 2×2

Even though top supports 3×3, the LEFT neighbor only supports 1×1.
If you tried to make a 2×2 square ending at (i,j), the cell one
column left would need to support a 2×2 — but it only supports 1×1.
So the bottleneck is min(3, 1, 2) = 1 → dp[i][j] = 2.

// java
// LC 926 - Flip String to Monotone Increasing
// IDEA: one pass — either flip this 1 to 0, or flip every 1 seen so far
// time = O(n), space = O(1)
// LC 926 — O(n) time, O(1) space
public int minFlipsMonoIncr(String s) {
    int flips = 0;   // min flips to make prefix monotone
    int ones = 0;    // count of '1's seen so far

    for (char c : s.toCharArray()) {
        if (c == '1') {
            ones++;              // potential future cost if we later want all-0 prefix
        } else {                 // c == '0' — conflict with prior '1's
            // choice 1: flip this '0' → '1'  : cost = flips + 1
            // choice 2: flip all prior '1'→'0': cost = ones
            flips = Math.min(flips + 1, ones);
        }
    }

    return flips;
}

// java
// LC 926 - Flip String to Monotone Increasing
// IDEA: prefix-sum variant — try every split point between the 0-block and the 1-block
// time = O(n), space = O(1)
// Count total zeroes first, then scan for the best "split point"
public int minFlipsMonoIncr(String s) {
    int zeroes = 0, ones = 0;
    for (char c : s.toCharArray()) if (c == '0') zeroes++;

    int output = zeroes;  // worst case: flip all '0' → '1'
    for (char c : s.toCharArray()) {
        if (c == '0') zeroes--;      // this '0' is now on the right → must flip
        else          ones++;        // this '1' is on the left → must flip
        output = Math.min(output, zeroes + ones);
    }
    return output;
}