How should I practice Sorted Extended Matrix Diagonals?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Capital One online assessment problems in FastPrep.

Is Sorted Extended Matrix Diagonals associated with Capital One?

FastPrep tags this as a Capital One online assessment coding practice problem when the problem catalog has that company and stage context.

Problem · Matrix

Sorted Extended Matrix Diagonals

Learn this problem

● Medium

Capital OneFULLTIMEOA

Problem statement

Given a square matrix of characters matrix with a size of n x n, your task is to create a sorted list of matrix's extended diagonals, where each diagonal has a length of n.

A matrix of size n x n has 2n - 1 diagonals parallel to the main diagonal, with each diagonal starting at its upper point and ending at its lower point. Since these diagonals have different lengths, traverse each one cyclically (go back to the starting point after reaching the end point) until it consists of n characters.

Sort the resulting strings of n characters in alphabetical order, and return an array of 2n - 1 integers, representing the diagonals' 1-based indices in their sorted order. In the case of alphabetically equal strings, their indices should be kept in the original order.

Below you can find an example of diagonals' numbering for a 5 x 5 matrix, where the number in the matrix corresponds to the diagonal index:

Note: You are not expected to provide the most optimal solution, but a solution with time complexity not worse than O(n^4) will fit within the execution time limit.

Function

solution(matrix: String[][]) → int[]

Examples

Example 1

matrix = [["b","b"],["c","a"]]return = [2,3,1]

For

matrix = [["b", "b"],
          ["c", "a"]]

the output should be solution(matrix) = [2, 3, 1].

The diagonal with index 1 is ["c"] and its corresponding cyclic string is "cc".
The diagonal with index 2 is ["b", "a"] and its corresponding cyclic string is "ba".
The diagonal with index 3 is ["b"] and its corresponding cyclic string is "bb".

The alphabetical ordering of the matrix diagonals looks like ["ba", "bb", "cc"], so the answer is [2, 3, 1].

Example 2

matrix = [["a","c","a","b","b"],["c","b","a","c","b"],["a","a","e","c","b"],["b","b","d","a","g"],["a","b","e","b","a"]]return = [1,5,3,7,2,8,9,6,4]

For

matrix = [["a", "c", "a", "b", "b"],
          ["c", "b", "a", "c", "b"],
          ["a", "a", "e", "c", "b"],
          ["b", "b", "d", "a", "g"],
          ["a", "b", "e", "b", "a"]]

the output should be solution(matrix) = [1, 5, 3, 7, 2, 8, 9, 6, 4].

The explanation for this example is not visible in the source image.

Constraints

FastPrep execution-adapter constraints (not shown in the source image):
n = matrix.length and n >= 1.
Every row of matrix has exactly n entries.
Every entry of matrix is a one-character string.