955.js

/** ------------------------------------------------------------------------------
 * 
 * 955. Delete Columns to Make Sorted II
 * Topics: Array, Greedy
 * https://leetcode.com/problems/delete-columns-to-make-sorted-ii/description/?envType=daily-question&envId=2025-12-21
 * 
 ------------------------------------------------------------------------------ */
/**
 * @param {string[]} strs
 * @return {number}
 */
var minDeletionSize = function (strs) {
  if (!strs || strs.length <= 1) return 0
  const n = strs.length
  const m = strs[0].length
  let deletions = 0

  // sortedPairs[i] === true means strs[i] < strs[i+1] already determined
  const sortedPairs = new Array(n - 1).fill(false)
  let remaining = n - 1 // number of pairs still not strictly ordered

  for (let col = 0; col < m; col++) {
    // Check if keeping this column would cause any violation
    let mustDelete = false
    for (let i = 0; i < n - 1; i++) {
      if (sortedPairs[i]) continue
      if (strs[i].charAt(col) > strs[i + 1].charAt(col)) {
        mustDelete = true
        break
      }
    }

    if (mustDelete) {
      deletions++
      continue // skip applying this column
    }

    // Apply this column: mark any pairs that become strictly ordered
    for (let i = 0; i < n - 1; i++) {
      if (sortedPairs[i]) continue
      if (strs[i].charAt(col) < strs[i + 1].charAt(col)) {
        sortedPairs[i] = true
        remaining--
      }
    }

    // If all adjacent pairs are confirmed in order, no more deletions needed
    if (remaining === 0) return deletions
  }

  return deletions
}

console.log()