Count unsorted columns

Easy

0/40

Average time to solve is 10m

25 upvotes

Asked in company

Problem statement

You are given an array ‘STRINGS’ having ‘N’ number of strings. The strings are assumed to be arranged such that there is one string in one line.

You need to return the number of columns that are not sorted lexicographically.

Note:

The length of all the strings in the array is the same.

For Example:

If the given array is [ “bde”, “dcf”, “gat” ], then it can be assumed to arranged as
bde
dcf 
gat 

Now the ‘0-th’ column (‘b’, ‘d’, ‘e’) and ‘2-th’ column ( ‘e’, ‘f’, ‘t’ ) are lexicographically sorted but the ‘1-st’ column ( ‘d’, ‘c’, ‘a’ ) is not sorted lexicographically. So you need to return 1.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains a single integer ‘T’, denoting the number of test cases.

Each test case’s first line contains ‘N’, denoting the number of strings in the array.

The next ‘N’ lines contain strings of the same length that make up ‘Strings’.

Output Format:

For each test case, print a single line containing a single integer denoting the number of columns that are not sorted lexicographically.

The output of each test case will be printed in a separated line.

Note:

You don’t need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 50
1 <= N <= 100
1 <= L <= 10 ^ 3

Where ‘T’ is the number of test cases, ‘n’ is the number of strings, and ‘L’  is each string’s length.

Time limit: 1 sec.

Sample Input 1:

2
3
bccde
dehrt
gabzy
2
wr
yz

Sample Output 1:

2
0

Explanation of Sample Input 1:

Test Case 1: In the given strings -
Column 0 - b, d, g is sorted
Column 1 - c, e, a is not sorted
Column 2 - c, h, b is not sorted
Column 3 - d, r, z is sorted
Column 4 - e, t, y is sorted.

Column 1, column 2 is not sorted, so the required answer is ‘2’.

Test Case 2: Both the columns (‘w’, ‘y’) and (‘r’, ‘z’ ) are sorted. So the answer is ‘0’.

Sample Input 2:

2
4
u
e 
y 
b
2
cterub
aybsgn

Sample Output 2:

1
3

Hint 1

Think of traversing the strings column-wise.

Approaches (1)

Approach 1

Column-Wise String Traversal

The simple idea is to traverse through every column of strings. For each column, check if it is lexicographically sorted or not. If not, increment the count by one.

Algorithm

Initialize a variable ‘count’ to store the result.
Run a loop col : 0 to (length of string - 1). to traverse all the columns.
- Run a loop row: 0 to N - 2 to iterate through all characters of a column.
- If char at string[ row ][ col ] > string[ row + 1 ][ col ]
  - Increment ‘count’ by ‘1’.
Return ‘count’.

Time Complexity

O(N * L), where ‘N’ is the number of strings, and ‘L’ is each string’s length.

We are iterating and visiting all the characters in the given strings once, and the total characters in ‘N’ strings of ‘L’ length is ‘N * L’. Therefore time complexity is O(N * L ).

Space Complexity

O(1).

We have not used any extra space. So the space complexity is O(1).

(100% EXP penalty)

Count unsorted columns

Console