Leetcode 365 (2023)

Day 3: 944. Delete Columns to Make Sorted

Hi there, Day 3 is here, unfortunately, had to publish this late due to some personal issues.

So onto our daily leetcode DSA questions with concise solutions, Now to the Question.

You are given an array of n strings strs, all of the same length.

The strings can be arranged such that there is one on each line, making a grid. For example, strs = ["abc", "bce", "cae"] can be arranged as:

abc
bce
cae

You want to delete the columns that are not sorted lexicographically. In the above example (0-indexed), columns 0 ('a', 'b', 'c') and 2 ('c', 'e', 'e') are sorted while column 1 ('b', 'c', 'a') is not, so you would delete column 1.

Return the number of columns that you will delete.

Input: strs = ["cba","daf","ghi"]
Output: 1
Explanation: The grid looks as follows:
  cba
  daf
  ghi
Columns 0 and 2 are sorted, but column 1 is not, so you only need to delete 1 column.

Input: strs = ["a","b"]
Output: 0
Explanation: The grid looks as follows:
  a
  b
Column 0 is the only column and is sorted, so you will not delete any columns.

Input: strs = ["zyx","wvu","tsr"]
Output: 3
Explanation: The grid looks as follows:
  zyx
  wvu
  tsr
All 3 columns are not sorted, so you will delete all 3.

with constraints given as follows

Constraints:

• n == strs.length

• 1 <= n <= 100

• 1 <= strs[i].length <= 1000

• strs[i] consists of lowercase English letters.

Approach:

Given an array of alphabets that should be arranged column-wise to give us an idea of which column is not sorted lexicographically.A lexicographical order simply means an ordered set. Also, take note that the solution is to get the column that is not sorted to be deleted.

Typically since the array has to be represented in column format, the first column is initialized to zero to keep track of the number of deletions that need to be made and we are going to iterate through individual columns to get one that is not sorted.

/**
 * @param {string[]} strs
 * @return {number}
 */
var minDeletionSize = function(strs) {
// initialize the count to be 0
  let count = 0;
  for (let i = 0; i < strs[0].length; i++) {
    let m = 0;
    for (let j = 0; j < strs.length-1; j++) {
// the charCodeAt method In JavaScript returns an integer btwn 0 and 65535
      if (strs[j].charCodeAt(i) > strs[j+1].charCodeAt(i))
        m++;
    }
    if(m !== 0)
      count++;
  }
  return count;
};

from the code above, It shows that you can actually delete the columns that are not sorted lexicographically, in which the function gives you a number as an output

So that's all for Day 3, Your comments and optimized solutions to questions are well appreciated. Thank you for reading..