Good evening! Here's our prompt for today.

Understanding the Matrix Shift Problem

Suppose you have a matrix where each row and column is sorted in ascending order. Your task is to apply two specific types of shifts, described below, and locate a given element x in the transformed matrix.

Shift Types

Left Circular Shift (l):

• Definition: Moves the first column to the last position, shifting all other columns one step left.

• Example:

  Before:

  PYTHON

  1[
  2   [1, 2, 3],
  3   [4, 5, 6],
  4   [7, 8, 9]
  5]

  After:

  PYTHON

  1[
  2   [2, 3, 1],
  3   [5, 6, 4],
  4   [8, 9, 7]
  5]

• Visual Explanation: Imagine the columns on a circular conveyor belt. The first column wraps to the end, while others shift left.

Top Circular Shift (u):

• Definition: Moves the first row to the last position, shifting all other rows one step up.

• Example:

  Before:

  PYTHON

  1[
  2   [1, 2, 3],
  3   [4, 5, 6],
  4   [7, 8, 9]
  5]

  After:

  PYTHON

  1[
  2   [4, 5, 6],
  3   [7, 8, 9],
  4   [1, 2, 3]
  5]

• Visual Explanation: Picture the rows on a circular escalator. The first row descends to the bottom, while others shift up.

Applying the Shifts to a Specific Example

Let's consider a sequence of shifts like [l,u,l,u,u] and apply them to the given matrix:

1matrix = [
2    [ 1, 2, 3, 4, 5],
3    [ 6, 7, 8, 9,10],
4    [11,12,13,14,15],
5    [16,17,18,19,20]
6]

After applying these rotations, the matrix transforms to:

1matrix = [
2    [9 ,10, 6, 7, 8],
3    [14,15,11,12,13],
4    [19,20,16,17,18],
5    [ 4, 5, 1, 2, 3]
6]

Here's an illustration to help visualize the problem:

Your Task

Given this final matrix and a specific value x, how can you efficiently find the location of this element in the array and return it?

Constraints

1. Matrix Size: Up to 10^5 x 10^5
2. Time Complexity: O(nlogn)
3. Memory Complexity: O(1)
4. Element Existence: The value x is in the matrix.
5. Minimum Elements: At least 1 element in the matrix.
6. Sorting Order: Always sorted in all rows and columns.
7. Uniqueness: Contains unique elements.

Considering these constraints and the above example, can you develop a method to locate the specified element in the transformed matrix?

Try to solve this here or in Interactive Mode.

How do I practice this challenge?

xxxxxxxxxx

var assert = require('assert');

​

function findElementInMatrix(matrix, x) {

  // Your Code Here

}

​

try {

  let matrix = [

    [9, 10, 6, 7, 8],

    [14, 15, 11, 12, 13],

    [19, 20, 16, 17, 18],

    [4, 5, 1, 2, 3],

  ];

  let result = findElementInMatrix(matrix, 17);

  assert(result.length === 2, 'Return type must be of length 2');

  assert(result[0] === 2, 'Wrong Answer');

  assert(result[1] === 3, 'Wrong Answer');

​

  console.log(

    'PASSED: The below matrix should result in `(2,3)`.

​

We'll now take you through what you need to know.

How do I use this guide?